The Fibonacci numbers are defined as follows:

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

The Fibonacci machine operates on an $n$-element integer register sequence $< i_{1}, i_{2}, ..., i_{n} >$ which initially contains zeroes only. The machine provides two operations:

• adding one to each register in interval $[a, b]$, i.e. adding $1$ to the numbers $i_{a}, i_{a+1}, \ldots, i_{b}$.;
• calculating the sum of those Fibonacci numbers, the sequence numbers of which are stored in registers from the interval $[a, b]$, i.e. calculating $F(i_{a}) + F(i_{a+1}) + \ldots + F(i_{b})$.

Your task is to write a simulator of the Fibonacci machine.

Input Format

The first line of the standard input contains two integers $n$ and $k$ ($1 ≤ n, k ≤ 100\,000$), separated by a single space and representing the length of the sequence and the number of operations. Each of the following $k$ lines contains a description of one operation. Such a description consists of a character D or S and two integers $a$ and $b$ ($1 ≤ a ≤ b ≤ n$), separated by single spaces. The character D stands for adding of 1 to the interval $[a, b]$, and the character S stands for calculating the sum of Fibonacci numbers the sequence numbers of which are from $[a, b]$. You may assume that at least one operation of type Sappears in the sequence of operations.

Output Format

For each operation S write to the standard output exactly one line with the desired Fibonacci sum. Each result should be calculated modulo $10^{9} + 7$.

Example

Input

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

Output

4
6
5

After seven operations the sequence of registers becomes $< 1, 3, 4, 3, 2>$. The result of the last query is equal to $F(3) + F(4) = 5$.