Supermerge

Supermerge super merge cum ar spune Tanaka, dar nu merge că nu are picioare. Recent, Andrei și Andrei au descoperit $N$ mulțimi $S_1, S_2, \ldots, S_N$, care pot conține doar numere naturale de la $1$ la $VMAX$. Inițial, toate mulțimile sunt vide. Asupra mulțimilor, au observat că se întâmplă următoarele operații:

• flip poz val - dacă elementul $val$ există în șirul $S_{poz}$, atunci, îl scoatem din mulțime. În caz contrar, îl introducem.
• supermerge st1 dr1 st2 dr2 - se aplică:

procedure Supermerge
    for i ← st1 ... dr1 do
        for j ← st2 ... dr2 do
        	S[i], S[j] ← S[i] ∪ S[j]

Cerință

Cum operațiile produc numai haos în capul celor doi Andrei, ei vor să știe câte elemente sunt în fiecare mulțime, după fiecare operație. Pentru a simplifica rezultatul, ei solicită doar calcularea sumei următoare: $(|S_1| + |S_2| \cdot \text{mod} + |S_3| \cdot \text{mod}^2 + \ldots + |S_N| \cdot \text{mod}^{N-1}) \ \% \ 2^{64}$, unde $\text{mod} = 10^9 + 7$.

Detalii de implementare

Va trebui să implementezi mai multe funcții. Prima dintre ele este:

void init(int N, int VMAX)

care primește ca parametri:

• $N$, numărul total de mulțimi
• $VMAX$, valoarea maximă pe care o poate lua elementul unei mulțimi

std::uint64_t flip(int poz, int val)

care:

• primește ca parametri indicele șirului și valoarea
• returnează suma care descrie mulțimile

std::uint64_t supermerge(int st1, int dr1, int st2, int dr2)

care:

• primește ca parametri intervalele între care are loc operația supermerge
• returnează suma care descrie mulțimile

Funcția init va fi apelată o singură data, iar funcțiile flip și supermerge vor fi apelate în total de maxim $Q$ ori.

Restricții și precizări

• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq N \cdot VMAX \leq 1 \ 000 \ 000$
• Pentru orice operație de tip flip, se garantează că $1 \leq poz \leq N$ și $1 \leq val \leq VMAX$
• Pentru orice operație de tip supermerge, se garantează că $1 \leq st1 \leq dr1 \leq N$ și $1 \leq st2 \leq dr2 \leq N$
• Prin S[i], S[j] ← S[i] ∪ S[j] am notat că ambele șiruri primesc rezultatul reuniunii celor două mulțimi simultan.

Exemple

input

5 3 5
0 1 1
1 1 2 2 3
0 3 2
1 1 1 5 5
0 2 2

output

1
1000000015000000057
2000000029000000106
4173964637407773643
4173964638407773650

Explicație

Starea mulțimilor, după fiecare operație, este:

1. $S_1 = \{1\}, \ S_2 = \emptyset, \ S_3 = \emptyset, \ S_4 = \emptyset, \ S_5 = \emptyset$
2. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1\}, \ S_4 = \emptyset, \ S_5 = \emptyset$
3. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \emptyset$
4. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \{1\}$
5. $S_1 = \{1\}, \ S_2 = \{1, 2\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \{1\}$