Zadanie

Jasný intervaláč

Počet bodov: 70, časový limit: 500ms

Úloha

Máte pole čísel dĺžky \(n\), ktorého pozície číslujeme od \(1\), v ktorom sú na začiatku samé nuly. Postupne vám príde \(q\) dotazov, ktoré sú dvoch typov:

• Zmeň hodnotu na pozíciách od \(l\) po \(r\), vrátane, o \(+x\).
• Zisti súčet čísel na pozíciách od \(l\) po \(r\), vrátane. Pretože tento súčet môže byť veľký, vypíšte jeho zvyšok po delení \(10^9 + 7\).

Na dotazy je nutné odpovedať on-line. To znamená, že kým nezodpoviete aktuálny dotaz (druhého typu), nedostanete na vstupe ďalší dotaz.

Vstup a výstup

Na prvom riadku vstupu sú dve medzerou oddelené čísla: \(n\) a \(q\). Platí \(1 \leq n \leq 10^{18}\) a \(0 \leq q \leq 20\,000\).

Následne vám príde postupne \(q\) dotazov. Dotazy prvého typu majú tvar zmena <l> <r> <x>, dotazy druhého typu majú tvar sucet <l> <r>, kde \(l, r, x\) majú vyššie uvedený význam. Platí \(1 \leq l \leq r \leq n\) a \(0 \leq x < 10^9 + 7\).

Je päť testovacích sád. Platia v nich nasledovné obmedzenia:
- V sadách \(1\) a \(2\) je \(n \leq 10^5\).
- V sade \(3\) je \(n \leq 10^9\).
- Vo zvyšných sadách je \(n \leq 10^{18}\).

Príklad

Input:

100000 5
zmena 1 90000 1
zmena 4001 94000 1
sucet 4000 90001
zmena 1 100000 10
sucet 30000 95000

Output:

172002
774012