Fibonaccin lukujono $(F_n)_{n=0}^\infty$ määritellään siten, että $F_0 = 0$, $F_1 = 1$ ja $F_n = F_{n-1} + F_{n-2}$ kaikille $n\geq 2$. Ensimmäiset lukujonon alkiot ovat siis $(0, 1, 1, 2, 3, 5, 8, 13, \ldots)$.

Taulukossa on $n$ epänegatiivista lukua $T[1], T[2], \ldots, T[n]$. Aluksi kaikki luvut ovat $0$. Tehtäväsi on toteuttaa seuraavat operaatiot:

1. kasvata lukuja $T[a], T[a+1], T[a+2], \ldots, T{[}{b}{]}$ arvolla $x$
2. laske summa $F_{T[a]} + F_{T[a+1]} + F_{T[a+2]} + \ldots + F_{T{[}{b}{]}}$ modulo $10^9+7$

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua $n$ ja $q$, taulukon koko ja kyselyjen määrä. Tämän jälkeen syötteessä on $q$ riviä, joista jokainen kuvaa yhden kyselyn.

Jos kysely on tyyppiä 1, rivi on muotoa "1 $a$ $b$ $x$". Tämä tarkoittaa, että välin $[a,b]$ lukuja tulee kasvattaa $x$:llä.

Jos kysely on tyyppiä 2, rivi on muotoa "2 $a$ $b$". Tämä tarkoittaa, että tulee laskea välin $[a,b]$ lukuja vastaavien Fibonaccin lukujen summa modulo $10^9+7$.

Tuloste

Tulosta jokaisesta tyypin 2 kyselystä lukujen summa omalle rivilleen.

Rajat

• $1 \le n \le 3\cdot 10^5$
• $1 \le q \le 3\cdot 10^5$
• $1 \le a \le b \le n$
• $1 \le x \le 10^9$

Esimerkki

Syöte:

5 5
2 2 4
1 3 4 2
2 2 4
1 1 3 3
2 1 5

Tuloste:

0
2
10