Range Sum 5

Du har en lista med heltalen $A_0, A_1, \cdots , A_{N-1}$. Till en början är $A_i=0$ för alla $i \in [0,N)$. Du ska hantera två sorters frågor:

• Typ 0: givet heltalen $l$ och $r$, skriv ut värdet på $A_l^3 + A_{l+1}^3 + \cdots + A_{r}^3 \ (\mathrm{mod}\ 10^9+7)$

• Typ 1: givet heltalen $l,r,v$, sätt $A_i=A_i+v$ för alla $i \in [l,r]$

Indata

Den första raden innehåller heltalen $N, Q$ ($1 \leq N, Q \leq 2*10^5$).

Därefter följer $Q$ rader som innehåller en fråga vardera. Varje fråga börjar med talet $T$.

Om $T=0$ följer heltalen $l, r$ ($0 \leq l \leq r \leq N - 1$). I detta fall ska du skriva ut summan som beskrivet i frågor av typ 1.

Om $T=1$ följer heltalen $l, r, v$ ($0 \leq l \leq r \leq N - 1$, $1 \leq V \leq 10^9$). I detta fall ska du uppdatera talen som beskrivet i frågor av typ 2.

Utdata

För varje fråga med $T=0$, skriv ut summan i det efterfrågade intervallet.

Poängsättning

Din lösning kommer att testas på flera testfall. För att lösa problemet måste du klara alla testfall.

4 6
0 0 3
1 0 1 10
1 1 2 5
0 0 0
0 1 1
0 2 2

0
1000
3375
125

3 6
1 0 1 12345678
1 1 2 87654321
0 0 0
0 1 1
0 2 2
0 0 2

826976094
558999999
607501738
993477824