Problem 4250: gpt

Într-un laborator secret, cercetătorii au construit o versiune experimentală a unui model GPT. Modelul este organizat sub forma unui arbore de module neuronale, fiecare nod al arborelui reprezentând un modul. Considerăm modulul neuronal $1$ ca fiind rădăcina arborelui.

Fiecărui modul $i$ îi este asociat un token, adică o literă mică $c_i$ din alfabetul englez.

Când un mesaj este transmis între două module $u$ și $v$ , acesta urmează unicul drum simplu dintre nodurile respective. Pe parcurs, fiecare modul adaugă propriul token la fluxul de date.

Pentru două noduri $u$ și $v$ , notăm cu $T(u,v)$ șirul obținut prin concatenarea token-urilor modulelor întâlnite pe drum, în ordinea parcurgerii.

Se dau $Q$ query-uri independente. Fiecare query este de forma $u \ v$ .

Se consideră un șir fix $P$ , comun tuturor query-urilor, reprezentând „semnătura GPT perfectă”. Notăm cu $L$ lungimea șirului $P$ .

Cerință

Pentru fiecare query, determinați de câte ori apare șirul $P$ ca subșir în șirul $T(u,v)$ .

Un subșir al unui șir se obține prin eliminarea a zero sau mai multe caractere, păstrând ordinea relativă a caracterelor rămase.

Rezultatul fiecărui query se va afișa modulo $10^9 + 7$ .

Date de intrare

Fișierul de intrare gpt.in conține:

Pe prima linie, un număr întreg $N$ .
Pe următoarele $N-1$ linii, câte două numere întregi $u$ și $v$ , indicând existența unei muchii între nodurile $u$ și $v$ .
Pe următoarea linie, $N$ caractere separate prin câte un spațiu: $c_1, c_2, \dots, c_N$ , reprezentând token-urile asociate fiecărui modul.
Pe următoarea linie, șirul $P$ .
Pe următoarea linie, un număr întreg $Q$ — numărul total de query-uri.
Pe următoarea linie, două valori întregi $a$ și $b$ (folosite pentru generarea query-urilor).
Pe ultima linie, două numere întregi $u_0$ și $v_0$ , reprezentând primul query.

Query-urile rămase se generează automat folosind formula:

u_i = ((u_{i-1} \cdot a + b) \text{ xor } i) \bmod N + 1

v_i = ((u_i \cdot a + b) \text{ xor } i) \bmod N + 1

unde $\text{xor}$ este operatorul ^ din C++ și $i=1$ pentru primul query generat, $i=2$ pentru al doilea etc. Se recomandă folosirea unui tip de date de 64 de biți pentru aceste calcule.

Date de ieșire

Fișierul de ieșire gpt.out va conține $Q$ linii. Pe linia $i$ se va afișa răspunsul corespunzător celui de-al $i$ -lea query, modulo $10^9 + 7$ .

Restricții și precizări

$1 \leq N \leq 50 \ 000$
$1 \leq Q \leq 2 \ 000 \ 000$
$1 \leq u, v \leq N$
$1 \leq L \leq 7$
$1 \leq a, b \leq 1 \ 000 \ 000$

#	Puncte	Restricții
1	2	$N, Q \leq 1\ 000$ și $L = 1$
2	8	$N, Q \leq 1\ 000$ și $L \leq 3$
3	5	$N, Q \leq 1\ 000$
4	5	$L = 1$ , $N \leq 20\ 000$ , $Q \leq 100\ 000$
5	30	$L \leq 3$ , $N \leq 20\ 000$ , $Q \leq 100\ 000$
6	40	$N \leq 20\ 000$ și $Q \leq 100\ 000$
7	10	Fără restricții suplimentare

Exemplu

gpt.in

7
1 2
1 3
2 4
2 5
3 6
3 7
a b a a b a b
ab
2
3 12
4 7

gpt.out

4
0

Explicație

Primul query se citește direct: $u_0 = 4$ , $v_0 = 7$ .
Valorile pentru generarea query-urilor sunt $a = 3$ , $b = 12$ .
Al doilea query se generează astfel:

u_1 = ((4 \cdot 3 + 12) \text{ xor } 1) \bmod 7 + 1 = (24 \text{ xor } 1) \bmod 7 + 1 = 25 \bmod 7 + 1 = 4 + 1 = 5

v_1 = ((5 \cdot 3 + 12) \text{ xor } 1) \bmod 7 + 1 = (27 \text{ xor } 1) \bmod 7 + 1 = 26 \bmod 7 + 1 = 5 + 1 = 6

Astfel, al doilea query devine $u = 5$ , $v = 6$ .

Structura arborelui este:
Muchii: $(1,2)$ , $(1,3)$ , $(2,4)$ , $(2,5)$ , $(3,6)$ , $(3,7)$

Token-urile nodurilor:

1 \to a,\; 2 \to b,\; 3 \to a,\; 4 \to a,\; 5 \to b,\; 6 \to a,\; 7 \to b

Șirul fix este $\text{ab}$ .

Pentru query-ul $4 \ 7$ . Drumul este $4 \to 2 \to 1 \to 3 \to 7$ , iar șirul obținut este $\text{abaab}$ . Numărul de apariții ale subșirului $\text{ab}$ este $4$ .
Pentru query-ul $5 \ 6$ : Drumul este $5 \to 2 \to 1 \to 3 \to 6$ , iar șirul obținut este $\text{bbaaa}$ . Subșirul $\text{ab}$ nu apare în șirul obținut.

gpt