== include(page="template/taskheader" task_id="deceeu") ==
Poveste şi cerinţă...
PCP tocmai a primit, de la serviciile secrete, un şir de $N$ caractere mici ale alfabetului englez. Acesta trebuie să afle câte subşiruri ale şirului dat sunt perfecte.
Un şir de caractere se numeste perfect dacă poate fi format concatenând două copii ale aceluiaşi şir. Spre exemplu, ”mama” (”ma” + ”ma”) sau ”abcabc” (”abc” + ”abc”) sunt şiruri perfecte, pe când ”pap” sau ”abcd” nu sunt. Un şir $X$ este considerat subşir al şirului $Y$ dacă $X$ poate fi format prin ştergerea a zero sau mai mai multe caractere din $Y$.
Când a citit problema, PCP a fost foarte descurajat, întrebându-se ”De ce am primit eu cerinţa aceasta?”. Voi trebuie să-i arataţi că încă există speranţă şi să-l ajutaţi cu rezolvarea!
h2. Date de intrare
Fişierul de intrare $deceeu.in$ ...
Fişierul de intrare $deceeu.in$ conţine pe prima linie $T$, numărul de teste. Urmează $T$ linii, fiecare linie descriind un test şi fiind formată dintr-un şir de caractere de dimensiune $N$.
h2. Date de ieşire
În fişierul de ieşire $deceeu.out$ ...
Fişierul de ieşire $deceeu.out$ trebuie să conţină $T$ linii. Cea de-a $i$-a linie reprezintă răspunsul pentru testul $i$ din fişiserul de intrare. Deoarece răspunsul poate fi foarte mare, afisaţi-l modulo $1.000.000.007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 200$
* $1 ≤ T ≤ 20$
h2. Exemplu
table(example). |_. deceeu.in |_. deceeu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
abc
abca
effeef
bbbb
aabbbaaabababbabbaab
| 0
1
10
7
25545
|
h3. Explicaţie
...
Subşirurile sunt descrise prin poziţiile din şirul iniţial care le formează.
Pentru testul 3, cele 10 subşiruri sunt: {1, 4}, {1, 5}, {4, 5}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 3, 5, 6}, {2, 3}, {2, 6}, {3, 6}.
Pentru testul 4, cele 7 subşiruri sunt: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3, 4}.
== include(page="template/taskfooter" task_id="deceeu") ==
