== include(page="template/taskheader" task_id="deceeu") ==
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!
Poveste şi cerinţă...
h2. Date de intrare
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$.
Fişierul de intrare $deceeu.in$ ...
h2. Date de ieşire
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$.
În fişierul de ieşire $deceeu.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 200$
* $1 ≤ T ≤ 20$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. deceeu.in |_. deceeu.out |
| 5
abc
abca
effeef
bbbb
aabbbaaabababbabbaab
| 0
1
10
7
25545
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
