==Include(page="template/taskheader" task_id="iv")==
 
Nu se stie de ce Igor si Vitalie s-au apucat de matematica. Cert e ca s-au lovit de o problema pentru care creionul si hartia nu sunt suficiente. Avand la dispozitie doua siruri de caractere, ei incearca sa le interclaseze astfel incat sa obtina un palindrom. Desi obtinerea unui singur palindrom este o treaba usoara, ei ar dori sa calculeze cate moduri diferite de a interclasa cele doua siruri exista astfel incat rezultatul sa fie palindrom.
 
h2. Cerinta
 
Ajutati-i pe Igor si Vitalie sa rezolve aceasta problema ce le framanta spiritul..
 
h2. Date de intrare
 
Fisierul $iv.in$ contine doua linii, cate una pentru fiecare sir de caractere, fiecare format din cel mult $500$ de litere mici ale alfabetului englez.
 
h2. Date de iesire
 
Fisierul $iv.out$ va contine pe prima linie un singur numar, reprezentand numarul calculat de posibilitati modulo $3210121$.
 
h2. Restrictii si observatii
 
* Lungimea fiecarui sir de caractere este cuprinsa intre $1$ si $500$
* Pentru $20%$ din teste lungimea fiecaruia din cele doua siruri este cuprinsa intre $1$ si $10$
* Pentru $60%$ din teste lungimea fiecaruia din cele doua siruri este cuprinsa intre $1$ si $200$
 
h2. Exemplu
 
table(example). |_. iv.in |_. iv.out |
| ab
ba
| 4 |
 
h3. Explicatii
 
Exista $4$ posibilitati de a interclasa cele doua siruri astfel incat sa se obtina un palindrom. Caracterele primului sir sunt marcate cu rosu, cele din al doilea sir sunt marcate cu albastru:
{%{color:red}ab%}{%{color:blue}ba%}
{%{color:red}a%}{%{color:blue}b%}{%{color:red}b%}{%{color:blue}a%}
{%{color:blue}b%}{%{color:red}a%}{%{color:blue}a%}{%{color:red}b%}
{%{color:blue}ba%}{%{color:red}ab%}
 
==Include(page="template/taskfooter" task_id="iv")==

==Include(page="template/taskheader" task_id="iv")==
 
==Include(page="template/raw")==
 
iv
 
 
 
Nu se stie de ce Igor si Vitalie s-au apucat de matematica. Cert e ca s-au lovit de o problema pentru care creionul si hartia nu sunt suficiente. Avand la dispozitie doua siruri de caractere, ei incearca sa le interclaseze astfel incat sa obtina un palindrom. Desi obtinerea unui singur palindrom este o treaba usoara, ei ar dori sa calculeze cate moduri diferite de a interclasa cele doua siruri exista astfel incat rezultatul sa fie palindrom.
 
h2. Cerinta
 
Ajutati-i pe Igor si Vitalie sa rezolve aceasta problema ce le framanta spiritul..
 
h2. Date de Intrare
 
Fisierul iv.in contine doua linii, cate una pentru fiecare sir de caractere, fiecare format din cel mult 500 de litere mici ale alfabetului englez.
 
h2. Date de Iesire
 
Fisierul iv.out va contine pe prima linie un singur numar, reprezentand numarul calculat de posibilitati modulo 3210121.
 
h2. Restrictii si observatii
S Lungimea fiecarui sir de caractere este cuprinsa intre 1 si 500
S Pentru 20% din teste lungimea fiecaruia din cele doua siruri este cuprinsa intre 1 si 10
S Pentru 60% din teste lungimea fiecaruia din cele doua siruri este cuprinsa intre 1 si 200
 
h2. Exemplu
 
iv.in iv.out Explicatie
ab 4 Exista 4 posibilitati de a interclasa cele doua siruri astfel incat sa se obtina un palindrom. Caracterele primului sir sunt marcate cu rosu, cele din al doilea sir sunt marcate cu albastru:
 
ba
 
abba
 
abba
 
baab
 
baab
 
 
 
 
==Include(page="template/taskfooter" task_id="iv")==

929