Seqstr

Se dau două șiruri, $A$ și $B$, cu valori din mulțimea $\{0, 1\}$.

Cerință

1. Să se afle numărul de subsecvențe distincte din $B$ care sunt subșiruri în $A$.
2. Să se afle, pentru o subsecvență $B_{p \dots q}$, numărul de subșiruri din $A$ egale cu aceasta.
3. Să se afle numărul de subșiruri din $A$ care sunt subsecvențe în $B$.

Date de intrare

Pe prima linie a fișierului seqstr.in se află $n$ reprezentând lungimea șirului $A$. Pe linia a doua se află cele $n$ elemente ale șirului $A$ separate prin câte un spațiu. Pe linia a treia se află numărul $m$ reprezentând lungimea șirului $B$. Pe linia a patra se află cele $m$ elemente ale șirului $B$ separate prin câte un spațiu. Pe linia a cincea se află numărul $C$ reprezentând cerința $1$, $2$ sau $3$.

Dacă $C$ este $2$ atunci pe linia a șasea se află două numere $p$ și $q$ separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire seqstr.out va conține o singură linie pe care va fi scris numărul cerut, conform cerinței.

Restricții și precizări

• Rezultatele cerute vor fi calculate și afișate modulo $10^9 + 7$.
• Prin subșir $T$ de lungime $p$ al lui $A$ se înțelege un șir $A_{t_1}, A_{t_2}, A_{t_3}, \dots, A_{t_p}$ determinat de pozițiile $1 \leq t_1 < t_2 < t_3 < \dots < t_p \leq n$
• Orice subsecvență a lui $B$ este determinată de două poziții $1 \leq p \leq q \leq m$ și este egală cu șirul $B_p, B_{p+1}, \dots, B_q$. Lungimea secvenței este egală cu $q - p + 1$.
• Două subsecvențe din $B$, determinate respectiv de perechile de poziții $(p_1, q_1)$ și $(p_2, q_2)$ sunt distincte dacă au lungimi diferite sau dacă au lungimi egale și există $k$ astfel încât $p_1 \leq p_1 + k \leq q_1$ și $p_2 \leq p_2 + k \leq q_2$ și $B_{p_1 + k} \neq B_{p_2 + k}$.
• $1 \leq m \leq n$

Exemplul 1

seqstr.in

5
1 1 0 0 1
3
0 1 1
1

seqstr.out

4

Explicație

Avem de rezolvat cerința $1$. Subsecvențele distincte din șirul $B$ pentru care există subșir în $A$ sunt: $(0)$, $(1)$, $(0, 1)$ și $(1, 1)$. Pentru subsecvența $(0, 1, 1)$ din $B$ nu există subșir în $A$.

Exemplul 2

seqstr.in

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

seqstr.out

3

Explicație

Avem cerința $2$. Subșirurile din $A$ egale cu subsecvența $(1, 1)$ din $B$ sunt cele determinate de subșirurile de poziții: $(1, 2)$, $(1, 5)$ și $(2, 5)$.

Exemplul 3

seqstr.in

5
1 1 0 0 1
3
0 1 1
3

seqstr.out

10

Explicație

Avem cerința $3$. Vor fi analizate numai subșirurile de lungime $1$, $2$ sau $3$. Nu avem subșiruri de lungime $3$ în $A$ egale cu subsecvențe din $B$, iar din cele de lungime $1$ sau $2$ sunt numărate cele egale cu $(0)$, $(1)$, $(0, 1)$ și $(1, 1)$.