Shaka, regele zuluşilor, a dat ordin să se realizeze un sistem de comunicaţii bazat pe tobe (tam-tam) care să acopere întreaga ţară. Pentru aceasta el a dispus cheltuirea unor mari sume de bani pentru instruirea celor ce vor urma să transmită mesajele. Instructorii i-au transmis că vor avea nevoie de câteva luni bune pentru a face cursanţii să facă distincţie între sunete şi să poată reda succesiunea de sunete pe hârtie. S-a făcut următoarea convenţie de notare: un sunet lung va fi reprezentat prin +, unul scurt prin -, iar unul nedecis (receptorul nu e sigur de lungimea sunetului) prin *.
Spre finalul stagiului Shaka a mers să verifice nivelul de pregătire al cursanţilor. Pentru aceasta el a adunat n cursanţi pe care i-a pus să recepţioneze şi să noteze un mesaj format din m sunete. După transmiterea mesajului s-a constatat că mulţi dintre cursanţi au scris şiruri foarte diferite, ceea ce ducea la o alterare semnificativă a mesajului original, chiar dacă nici cel mai rău cursant nu a fost indecis la mai mult de jumătate din sunete. Supărat Shaka l-a chemat pe instructorul şef şi, ca să-l pedepsească, i-a cerut ca să determine câte mesaje distincte se pot forma din şirurile scrise de cursanţi.
Cerinţă
Scrieţi un program care determină numărul de mesaje distincte rezultate.
Date de intrare
Fişierul de intrare aritma.in conţine pe prima sa linie numerele n şi m separate printr-un spaţiu, iar pe următoarele n linii şiruri de caractere de lungime m formate numai din simbolurile +, - sau *.
Date de ieşire
Pe prima linie a fişierului de ieşire aritma.out se va scrie numărul de mesaje distincte.
Restricţii
1<n<25
1<m<19
Exemple
aritma.in
aritma.out
Explicaţii
3 3
+-*
+*+
-*+
5
Mesajele rezultate sunt: +--, +-+, +++, +-+, --+, -++. Primele două mesaje sunt rezultate din prima identificare, următoarele două sunt din a doua identificare şi ultimele două din ultimul şir ; numai cinci sunt distincte.