피보나치 기계

피보나치 수는 다음과 같이 정의된다.

• $F(0) = 0$
• $F(1) = 1$
• $m \ge 2$ 일 때 $F(m) = F(m-1) + F(m-2)$

피보나치 기계는 정수 레지스터 $n$개로 이루어진 수열 $\langle i_1, i_2, \dots, i_n \rangle$ 을 관리하며, 처음에는 모든 레지스터가 $0$이다. 이 기계는 두 가지 연산을 제공한다.

• 더하기: 구간 $[a, b]$ 에 속한 모든 레지스터에 $1$을 더한다. 즉 $i_a, i_{a+1}, \dots, i_b$ 를 각각 $1$씩 증가시킨다.
• 합: 구간 $[a, b]$ 에 속한 레지스터 값을 색인으로 하는 피보나치 수들의 합, 즉 $F(i_a) + F(i_{a+1}) + \dots + F(i_b)$ 를 구한다.

피보나치 기계를 시뮬레이션하는 프로그램을 작성하라.

첫 번째 줄에 레지스터의 개수 $n$과 연산의 개수 $k$가 공백으로 구분되어 주어진다 ($1 \le n, k \le 100000$). 이어지는 $k$개의 줄에는 각각 하나의 연산이 주어지며, 문자 하나와 두 정수 $a$, $b$ ($1 \le a \le b \le n$)로 구성된다.

• D a b 는 구간 $[a, b]$ 에 더하기 연산을 수행한다.
• S a b 는 구간 $[a, b]$ 에 합 연산을 수행한다.

합 연산 S 는 적어도 한 번 이상 주어진다.

각 S 연산마다 구한 피보나치 수들의 합을 $10^9 + 7$ 로 나눈 나머지를 한 줄에 하나씩 출력한다.

예시에서 마지막 질의를 수행하는 시점의 레지스터는 $\langle 1, 3, 4, 3, 2 \rangle$ 이므로, S 2 3 의 결과는 $F(3) + F(4) = 2 + 3 = 5$ 이다.