Problem M
Löggeng endanleg stöðuvél - Talning

Þú færð endanlega löggenga stöðuvél gefna sem samþykkir málið $\mathcal{L}$. Þú færð svo fyrirspurnir sem biðja um fjölda orða af tiltekinni lengd í $\mathcal{L}$, sem þú skalt prenta í sömu röð og fyrirspurnir eru gefnar.

Inntak

Fyrsta lína inntaksins inniheldur fjórar jákvæðar heiltölur $n$, $c$, $s$ og $f$ þar sem $n$ er fjöldi staða, $c$ er stærð stafrófsins, $s$ er upphafsstaðan og $f$ er fjöldi lokastaða. Önnur línan inniheldur streng $\Sigma = \Sigma _1 \Sigma _2 \dots \Sigma _c$ sem samanstendur af $c$ ólíkum táknum sem eru allt ASCII lágstafir. Þriðja línan inniheldur $f$ ólíkar jákvæðar heiltölur, mengi lokastaða stöðuvélarinnar. Næst fylgja $n$ línur, hver með $c$ jákvæðum heiltölum, sem gefa stöðuskiptatöfluna. Sem sagt, $j$-ta talan á $i$-tu línu gefur stöðuna sem stöðuvélin fer í ef hún var í stöðu $i$ og las inn stafinn $\Sigma _j$.

Hver staða er táknuð með heiltölu frá $1$ til $n$. Gefið er að $n \cdot c \leq 2\, 000$, $1 \leq s \leq n$ og $0 \leq f \leq n$.

Að lokum kemur heiltala $m$, þar sem $1 \leq m \leq 10\, 000$ og svo $m$ línur. Lína $i$ inniheldur heiltöluna $\ell _i$, fyrir öll $1 \leq i \leq m$, sem táknar fyrirspurn um fjölda orða af lengd $\ell _i$ í $\mathcal{L}$. Þú mátt gera ráð fyrir að $\ell _i \cdot n \leq 500\, 000$ fyrir sérhvert $i$.

Úttak

Fyrir sérhverja fyrirspurn skaltu prenta fjölda orða með tilteknu lengdina í $\mathcal{L}$. Þar sem þessar tölur geta verið mjög stórar skaltu skrifa þær út mátaðar við $1\, 000\, 000\, 007$.

5 2 1 2
ab
4 5
2 3
3 4
4 5
5 4
4 4
5
0
1
2
3
4

0
0
3
8
16

2 4 1 1
acgt
1
2 2 2 2
2 2 2 2
3
0
1
2

1
0
0