Fişierul intrare/ieşire:	pattern.in, pattern.out	Sursă	Lot Cluj 2009, Baraj 6
Autor	Silviu-Ionut Ganceanu	Adăugată de	Sima Cotizo •sima_cotizo
Timp execuţie pe test	0.45 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pattern

Se dau un text şi o mască formate din litere mici ale alfabetului englez. În plus, în mască pot apărea caracterele speciale ? şi *.

Spunem că masca se potriveşte peste o subsecvenţă S din text dacă şi numai dacă înlocuind fiecare caracter ? cu exact o literă (câte o literă pentru fiecare ? din mască) şi fiecare * cu o secvenţă de litere (eventual vidă; câte una pentru fiecare * din mască) se obţine subsecvenţa S.

Două potriviri peste aceeaşi subsecvenţă S sunt considerate diferite dacă există cel puţin un character special care se înlocuieşte cu un caracter/secvenţă de pe alte poziţii din S în cele două potriviri. De asemenea, două potriviri peste subsecvenţe diferite din text sunt considerate distincte. Două subsecvenţe sunt considerate diferite dacă se găsesc pe poziţii diferite în text, chiar dacă ele sunt egale dacă le comparăm ca string-uri.

Cerinţă

Aflaţi numărul de potriviri distincte ale măştii în text.

Date de intrare

Pe prima linie a fişierului de intrare pattern.in se găseşte un număr T care reprezintă numărul de teste. Urmează câte două linii pentru fiecare test: pe prima linie textul iar pe a doua masca pentru testul respectiv.

Date de ieşire

În fişierul de ieşire pattern.out se vor găsi T linii conţinând câte un singur număr egal cu numărul posibilităţilor de potrivire a măştii în text modulo 1 000 000 007 pentru fiecare test.

Restricţii

• 1 ≤ T ≤ 3
• 1 ≤ lungime(text) ≤ 100 000
• 1 ≤ lungime(mască) ≤ 50 000
• Pentru 40% din teste: lungime(text) ≤ 3 000 şi lungime(mască) ≤ 1 000.
• Numărul caracterelor speciale din mască va fi mai mic decât 101.
• În mască nu vor exista două * alăturate şi există cel puţin o literă.

Exemplu

Explicaţie

În primul test avem următoarele potriviri: aababba, aababba, aababba, aababba, aababba, aababba, aababba.
Pentru al doilea test avem o singură potrivire: abbabbcbaba.
Pentru al treilea test avem potrivirile (caracterele îngroşate sunt potrivite peste *): aaa,aaa, aaa, aaa

Cum se trimit solutii?