Pasavci

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Janez Brank
  • UPM 2017

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Nori znanstveniki poskušajo vzrediti novo vrsto čim bolj popadljivega mutantskega pasavca. Genetski zapis posameznega pasavca predstavijo z nizom znakov (v njem so lahko poljubne velike črke angleške abecede, ne nujno samo G, C, A in T). Začeli so z dvema pasavcema (recimo jima 1 in 2), katerih genetski zapis opišemo z nizoma s_1 in s_2. Nato so pasavce parili med seboj in sicer takole: za vsak k od 1 do m so vzeli pasavca št. a_k in b_k ter iz njiju vzredili novega, pasavca št. k + 2, čigar genetski zapis je definiran kot stik genetskih zapisov pasavcev a_k in b_k. To lahko zapišemo s formulo: s_{k+2} = s_{a_k} \cdot s_{b_k}, pri čemer znak \cdot pomeni stikanje nizov.

Uspeli so tudi izolirati gen za popadljivost. Tudi to je nek niz velikih črk angleške abecede, recimo mu p, in pasavec je tem bolj popadljiv, čim večkrat se p pojavi kot podniz v njegovem genetskem zapisu.

Naloga

Napišite program, ki prebere podatke o pasavcih in ugotovi, kako popadljiv je zadnji pasavec v programu vzreje, torej kolikokrat se pojavi p kot podniz v nizu s_{m+2}. Pri tem štejejo tudi take pojavitve, ki se druga z drugo prekrivajo; mora pa biti vsaka pojavitev sama zase strnjena.

Vhodni podatki

V prvi vrstici je niz p, v drugi vrstici je niz s_1, v tretji vrstici je niz s_2, v četrti vrstici pa je celo število m. Sledi še m vrstic, k-ta od njih vsebuje celi števili a_k in b_k, ločeni s presledkom.

Omejitve vhodnih podatkov

  • 1 \leq m \leq 1000
  • Nizi p, s_1 in s_2 so dolgi vsaj 1 in kvečjemu 1000 znakov; vsi znaki so velike črke angleške abecede.
  • Za vsak k od 1 do m velja 1 \le a_k, b_k \le k + 1.

Izhodni podatki

Izpišite eno samo celo število – ostanek po deljenju x z 10^9 + 7, pri čemer je x število pojavitev niza p kot podniza v nizu s_{m+2}.

Primer

Vhod

UVU
U
V
4
1 2
2 1
3 1
5 4

Izhod

2

Komentar

Pri gornjem primeru začnemo z s_1 = {\tt U} in s_2 = {\tt V}, nato pa imamo s_3 = {\tt UV}, s_4 = {\tt VU}, s_5 = {\tt UVU} in s_6 = {\tt UVUVU}. V zadnjem od teh nizov se {\tt UVU} kot podniz pojavlja dvakrat, zato je pravilni odgovor 2.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task