有 $n$ 个存储单元，每个单元可以存储一个整数，这些单元的编号为 $1$ 到 $n$ 。一开始，每个单元的数字都是 $0$，接下来依次有 $m$ 条指令：

• 第一种指令以 + 开头，后接两个整数 $l$ 与 $r$，含义是将编号 $l$ 到编号 $r$ 单元的数字分别加一。

• 第二种指令以 * 开头，后接两个整数 $l$ 与 $r$，含义是重复执行第 $l$ 条指令到第 $r$ 条指令。保证这些指令的序号都在当前指令之前。

请输出每个单元格最后的数字，由于可能很大，输出它们模10^9+7的余数。

第一行：两个整数 n 与 m

第二行到第 m+1 行：在第 i+1 行，先有一个字符 + 或 *，后接两个整数 l 与 r

若是 +，则保证 1\leq l\leq r\leq n

若是 *，则保证 1\leq l \leq r \leq i

共 n 行，第i 行只有一个数表示第 i 个单元内存储的整数模 1,000,000,007的余数

对于 30\%的数据，1\leq n,m\leq 20

对于 60\%的数据，1\leq n,m\leq 1000

对于 100\% 的数据，1\leq n,m\leq 200,000