Rezolvare PBinfo #4044

Cerința

Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

Date de intrare

Prima linie din input conține numerele N și M. Pe următoarele N linii se vor găsi câte M caractere din mulțime {'A', 'N', 'C'}, reprezentând elementele matricii.

Date de ieșire

Se va afișa un singur număr, reprezentând valoarea cerută.

Restricții și precizări

• 1 ≤ N, M ≤ 300

Exemplu:

Intrare

3 4
ACNN
NCCA
AACN

Ieșire

18

Explicație

Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.