Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1.

Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.

Cerința

Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: S[i], S[i+1], … , S[j], cu i<=j, pentru care lmax[S[i]]+lmax[S[i+1]]+... +lmax[S[j]]=L.

Date de intrare

Fișierul de intrare secvpal1.in conține pe prima linie două numere naturale N, L cu semnificaţia din enunţ, iar pe fiecare dintre următoarele N linii, câte un şir de caractere.

Date de ieșire

Fișierul de ieșire secvpal1.out va conține pe prima linie un număr natural nr ce reprezintă numărul de secvenţe de şiruri de caractere ce îndeplinesc condiţia cerută.

Restricții și precizări

• 2 ≤ N ≤ 50 000;
• 0 ≤ nr ≤ 10 000;
• 1 ≤ lungimea maximă a oricărui şir S[i] ≤ 10 000, 1≤i≤N;
• 1 ≤ lungimea maximă a unei secvenţe palindromice lmax[S[i]] ≤ 1 000;
• 1 ≤ (lungimea maximă şir S[i]) × N ≤ 1 000 000;
• Cele N şiruri de caractere conţin doar caracterele ‘A’..’Z’, ’a’..’z’;
• Un palindrom este un şir de caractere care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi.

Exemplu:

secvpal1.in

5 11
aCCACCACaBa
AAPAPAACCAA
acaacc
capac
CACAACAACACCAACP

secvpal1.out

2

Explicație

1. lmax(”aCCACCACaBa”)=6
2. lmax(”AAPAPAACCAA”)=7
3. lmax(”acaacc”)=4
4. lmax(”capac”)=5
5. lmax(”CACAACAACACCAACP”)=11

Cele două secvenţe de lungime 11 sunt: (2,3) şi (5)