斐波那契数列定义如下：

$$F(0) = 0, \;\;\; F(1) = 1, \;\;\; F(m) = F(m-1) + F(m-2)\; \text{ for } m \geq 2$$

斐波那契机器对一个包含 $n$ 个整数的寄存器序列 $< i_{1}, i_{2}, ..., i_{n} >$ 进行操作，该序列初始时全为零。机器提供两种操作：

• 将区间 $[a, b]$ 内的每个寄存器值加 1，即对 $i_{a}, i_{a+1}, \ldots, i_{b}$ 每个数加 $1$。
• 计算区间 $[a, b]$ 内寄存器所存储的斐波那契数之和，即计算 $F(i_{a}) + F(i_{a+1}) + \ldots + F(i_{b})$。

你的任务是编写一个斐波那契机器的模拟器。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $k$ ($1 \leq n, k \leq 100\,000$)，由单个空格分隔，分别表示序列的长度和操作次数。接下来的 $k$ 行，每行包含一个操作的描述。描述由一个字符 D 或 S 以及两个整数 $a$ 和 $b$ ($1 \leq a \leq b \leq n$) 组成，由单个空格分隔。字符 D 表示将区间 $[a, b]$ 加 1，字符 S 表示计算区间 $[a, b]$ 内寄存器对应斐波那契数的和。你可以假设操作序列中至少包含一个 S 操作。

输出格式

对于每个 S 操作，向标准输出打印一行结果。每个结果应模 $10^{9} + 7$ 输出。

样例

输入 1

5 7
D 1 4
S 1 5
D 3 5
D 2 3
S 1 5
D 2 5
S 2 3

输出 1

4
6
5

说明

经过七次操作后，寄存器序列变为 $< 1, 3, 4, 3, 2>$。最后一次查询的结果等于 $F(3) + F(4) = 5$。