Consideram permutare $BR$: bit reverse.
Un sir de lungime $2^k$ este $BR-permutare$ daca si numai daca este egal cu el insusi dupa ce se aplica $BR$.

Se da un sir de caractere de lungime $N$, indexat de la 0. Sirul de caractere $S(i, j)$ este sirul de caractere de lungime $2^j$ ce se termina pe pozitia $i$, daca el exista. Functia $brperm(i, j)$ este $1$ daca $S(i, j)$ exista si este $BR-permutare$, iar 0 altfel. In aceasta problema se cere sa calculati eficient functia $brperm$.

Se da un arbore cu $N$ noduri, indexate de la 0, cu caractere pe muchii. Sirul de caractere $S(i, j)$ este sirul de caractere de lungime $2^j$ format prin concatenarea caracterelor de pe lantul de acea lungime de la $i$ inspre radacina. Functia $brperm(i, j)$ este $1$ daca $S(i, j)$ este $BR-permutare$, iar 0 altfel. In aceasta problema se cere sa calculati eficient functia $brperm$.

h2. Date de intrare

Fişierul de intrare $brperm.in$ contine pe primul rand numarul $N$, iar pe al doilea rand sirul de caractere dat.

Fişierul de intrare $brperm.in$ contine pe primul rand numarul $N$ de noduri.
Al doilea rand contine cate $N - 1$ numere, iar al $i$-lea este tatal nodului $i$ in arbore (retineti ca nodul $0$ este radacina). Se garanteaza ca tatal unui nod are indicele mai mic ca el.
Al treilea rand contine un sir de $N - 1$ caractere, din care al $i$-lea caracter este caracterul pe muchia dintre $i$ si tatal sau.
Al patrulea rand contine valorile $Q X{~1~} Y{~1~} a b c d$.

h2. Date de ieşire

În fişierul de ieşire $brperm.out$ se afiseaza suma din $brperm(i, j) * 2^20i + j^$ pentru $i$ de la $0$ la $N - 1$ si $j$ de la $0$ la $19$.

În fişierul de ieşire $brperm.out$ se afiseaza numerele $X{~Q+1~} Y{~Q+1~}$. Acestea se definesc dupa recurentele urmatoare:
 
$A{~i~} = X{~i~} mod N$
$B{~i~} = Y{~i~} mod log{~2~}(lungimea lantului de la A{~i~} la radacina)$
$R{~i~} = brperm(A{~i~}, B{~i~})$
$X{~i+1~} = (i + X{~i~} + R{~i~}) * a + b mod 1.000.000.007$
$Y{~i+1~} = (i + Y{~i~} + R{~i~}) * c + d mod 1.000.000.007$

h2. Restricţii