puterea-p

Pentru orice șir de numere, definim noțiunile de putere a unei valori și de putere totală.

Fie $a = (a_1, a_2, \dots, a_L)$ un șir de $L$ numere și fie $P$ o valoare care apare în acest șir. Notăm cu $freq_P$ numărul de poziții $i$ (cu $1 \le i \le L$) pentru care $a_i = P$. Puterea valorii $P$ în șirul $a$ este definită ca

Puterea totală a șirului $a$ este suma puterilor tuturor valorilor distincte care apar în $a$ (fiecare valoare distinctă fiind luată în calcul o singură dată):

Cerință

Se citește o valoare $C \in \{1, 2\}$, care precizează tipul cerinței.

Cerința 1 ($C = 1$). Se dă un șir $s = (s_1, s_2, \dots, s_N)$ și $Q$ operații. O operație este descrisă printr-o pereche $(pos, val)$ și constă în atribuirea $s_{pos} \leftarrow val$. Operațiile se aplică în ordinea în care sunt date, iar efectele lor sunt persistente (fiecare operație modifică șirul curent).

Înainte de aplicarea oricărei operații, precum și după fiecare operație, trebuie să calculați suma puterilor totale ale tuturor subsecvențelor șirului $s$, fiecare subsecvență fiind considerată separat. O subsecvență este formată din elementele aflate pe poziții consecutive, adică $(s_l, s_{l+1}, \dots, s_r)$ pentru $1 \le l \le r \le N$.

Cerința 2 ($C = 2$). Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$. Fiecare nod $i$ conține valoarea $s_i$. Se dau, de asemenea, $Q$ operații de forma $(pos, val)$, cu același efect ca mai sus: valoarea nodului $pos$ devine $val$, modificările fiind persistente.

Înainte de aplicarea oricărei operații, precum și după fiecare operație, trebuie să calculați suma puterilor totale ale tuturor lanțurilor din arbore, fiecare lanț fiind considerat separat o singură dată. Un lanț este determinat de o pereche de noduri $(u, v)$, cu $1 \le u \le v \le N$, și este format din șirul valorilor nodurilor aflate pe drumul simplu (unic în arbore) dintre $u$ și $v$.

În ambele cerințe, deoarece rezultatele pot fi foarte mari, fiecare valoare cerută se va afișa modulo $10^9 + 7$.

Date de intrare

Prima linie conține un întreg $C$, egal cu $1$ sau cu $2$, reprezentând tipul cerinței.

A doua linie conține întregul $N$, numărul de elemente ale șirului (respectiv numărul de noduri ale arborelui dacă $C = 2$).

A treia linie conține cele $N$ valori $s_1, s_2, \dots, s_N$, separate prin spații.

Dacă $C = 1$:

• linia următoare conține întregul $Q$, numărul de operații;
• fiecare dintre următoarele $Q$ linii conține doi întregi $pos$ și $val$, descriind o operație.

Dacă $C = 2$:

• următoarele $N - 1$ linii descriu muchiile arborelui; fiecare conține doi întregi $u$ și $v$, ceea ce înseamnă că există o muchie între nodurile $u$ și $v$;
• linia următoare conține întregul $Q$, numărul de operații;
• fiecare dintre următoarele $Q$ linii conține doi întregi $pos$ și $val$, descriind o operație.

Date de ieșire

Se vor afișa $Q + 1$ linii. Prima linie conține rezultatul calculat pentru configurația inițială, înainte de aplicarea oricărei operații. Pentru fiecare $k$ cu $1 \le k \le Q$, linia $k + 1$ conține rezultatul calculat după aplicarea primelor $k$ operații. Fiecare rezultat se afișează modulo $10^9 + 7$.

Restricții și precizări

• $C \in \{1, 2\}$
• $1 \le N \le 200 \ 000$
• $0 \le Q \le 200 \ 000$
• $1 \le s_i \le 10^9$, pentru orice $1 \le i \le N$
• $1 \le pos \le N$, pentru fiecare operație
• $1 \le val \le 10^9$, pentru fiecare operație
• Pentru $C = 2$, cele $N - 1$ muchii formează un arbore (graf conex și fără cicluri)
• Toate rezultatele se afișează modulo $10^9 + 7$.

Exemplul 1

puterea-p.in

1
4
1 2 1 3
1
3 2

puterea-p.out

26
22

Explicație

Acest exemplu corespunde cerinței $1$, cu $N = 4$ și șirul inițial $s = (1, 2, 1, 3)$.

Subsecvențele de lungime $1$ au puterea totală $0$ (o singură valoare apare o dată, deci $freq \cdot (1 - freq) = 1 \cdot 0 = 0$).

Pentru celelalte subsecvențe:

• $(s_1, s_2) = (1, 2)$, $(s_2, s_3) = (2, 1)$ și $(s_3, s_4) = (1, 3)$ au fiecare două valori distincte, deci putere totală $1 \cdot 1 + 1 \cdot 1 = 2$.
• $(s_1, s_2, s_3) = (1, 2, 1)$: $freq_1 = 2$, $freq_2 = 1$, $L = 3$, putere $2 \cdot 1 + 1 \cdot 2 = 4$.
• $(s_2, s_3, s_4) = (2, 1, 3)$: toate distincte, $L = 3$, putere $3 \cdot (1 \cdot 2) = 6$.
• $(s_1, s_2, s_3, s_4) = (1, 2, 1, 3)$: $freq_1 = 2$, $freq_2 = 1$, $freq_3 = 1$, $L = 4$, putere $2 \cdot 2 + 1 \cdot 3 + 1 \cdot 3 = 10$.

Suma este $2 + 2 + 2 + 4 + 6 + 10 = 26$, valoarea afișată pe prima linie.

După operația $(pos, val) = (3, 2)$, șirul devine $s = (1, 2, 2, 3)$. Recalculând (de exemplu, subsecvența $(2, 2)$ are acum puterea $0$), suma puterilor totale devine $22$.

Exemplul 2

puterea-p.in

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

puterea-p.out

22
10

Explicație

Acest exemplu corespunde cerinței $2$, cu $N = 4$. Nodul $1$ este conectat cu nodurile $2$, $3$ și $4$ (asemenea figurii de mai jos), iar valorile inițiale sunt $s_1 = 1$, $s_2 = 2$, $s_3 = 2$, $s_4 = 3$.

Lanțurile formate dintr-un singur nod au puterea totală $0$. Pentru perechile de noduri distincte:

• $\{1, 2\}$: valorile $(1, 2)$, putere $2$.
• $\{1, 3\}$: valorile $(1, 2)$, putere $2$.
• $\{1, 4\}$: valorile $(1, 3)$, putere $2$.
• $\{2, 3\}$: drumul $2$–$1$–$3$, valorile $(2, 1, 2)$, deci $freq_2 = 2$, $freq_1 = 1$, $L = 3$, putere $2 \cdot 1 + 1 \cdot 2 = 4$.
• $\{2, 4\}$: drumul $2$–$1$–$4$, valorile $(2, 1, 3)$, putere $6$.
• $\{3, 4\}$: drumul $3$–$1$–$4$, valorile $(2, 1, 3)$, putere $6$.

Suma este $2 + 2 + 2 + 4 + 6 + 6 = 22$, valoarea afișată pe prima linie.

După operația $(pos, val) = (1, 2)$, valorile devin $s = (2, 2, 2, 3)$. Acum lanțurile $\{1, 2\}$, $\{1, 3\}$ și $\{2, 3\}$ au puterea $0$, lanțul $\{1, 4\}$ are puterea $2$, iar lanțurile $\{2, 4\}$ și $\{3, 4\}$ au fiecare puterea $4$. Suma devine $0 + 0 + 2 + 0 + 4 + 4 = 10$.