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

Cerința

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...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 1.000.000.007
• Prin subșir T de lungime p al lui A se înțelege un șir [A[t1], A[t2], A[t3], ..., A[tp]] determinat de pozițiile [1 ≤ t1 < t2 < t3 < ... < tp ≤ n]
• Orice subsecvență a lui B este determinată de două poziții [1 ≤ p ≤ q ≤ m] și este egală cu șirul [B[p], B[p+1], ..., B[q]] Lungimea secvenței este egală cu q - p + 1.
• Două subsecvențe din B, determinate respectiv de perechile de poziții p1, q1 și p2, q2 sunt distincte dacă au lungimi diferite sau dacă au lungimi egale și există k astfel încât p1 ≤ p1 + k * q1 și p2 ≤ p2 + k ≤ q2 și B[p1 + k] ≠ B[p2 + k].
• 1 ≤ m ≤ n
• Pentru 7 puncte, C=1 și n ≤ 20
• Pentru 9 puncte, C=1 și 21 ≤ n ≤ 500
• Pentru 19 puncte, C=1 și 501 ≤ n ≤ 5000
• Pentru 3 puncte, C=2 și n ≤ 20
• Pentru 9 puncte, C=2 și 21 ≤ n ≤ 100
• Pentru 15 puncte, C=2 și 101 ≤ n ≤ 5000
• Pentru 9 puncte, C=3 și n ≤ 20
• Pentru 9 puncte, C=3 și 21 ≤ n ≤ 100
• Pentru 20 de puncte, C=3 și 101 ≤ n ≤ 500

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.