Fişierul intrare/ieşire:deceeu.in, deceeu.outSursăACM ICPC Faza Nationala 2015
AutorDin FolclorAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test1.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

De ce eu?

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!

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.

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.

Restricţii

  • 1 ≤ N ≤ 200
  • 1 ≤ T ≤ 20

Exemplu

deceeu.indeceeu.out
5
abc
abca
effeef
bbbb
aabbbaaabababbabbaab
0
1
10
7
25545

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}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?