Nosaukums
Puķu dobes (dobes)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
31%

Definīcija

Gudrinieku ciemā tuvojas ikgadējā puķu dobju izstāde. Vecmāmiņa Rasulīte nosprauda sev mērķi šogad iegūt pirmo vietu, lai parādītu, kas ciemā ir OG! (Outstanding Granny.)

Rasulīte jau ir sagatavojusi savu puķu dobi un vēlas noskaidrot, cik tā ir skaista. Viņas puķu dobe ir × M rūtiņu laukums, katrā rūtiņā atrodas tieši viens zieds. Katram no ziediem ir sava krāsa, ko apzīmē ar mazajiem latīņu alfabēta burtiem (no a līdz z).

Izstādes žūrija noteica, ka puķu dobe ir skaista, ja to var sadalīt taisnstūros ar vienādu augstumu un platumu (visiem taisnstūriem jābūt vienādi pagrieztiem) tā, ka dobes daļa visos taisnstūros izskatās identiski. Zīmējumā parādīts viens skaists puķu dobes sadalījums.

Žūrija novērtē puķu dobi ar kopēju veidu skaitu, kā dobi var skaisti sadalīt. Palīdziet vecmāmiņai Rasulītei noskaidrot šo skaitu!


Ievaddatu raksturojums

Pirmā rinda satur divus veselus skaitļus N un M, dobes izmērus (1 ≤ N, M ≤ 5000). Nākamās N rindas katra satur M simbolu virkni, dobes aprakstu. Visi simboli ir mazi latīnu alfabēta burti.


Izvaddatu raksturojums

Izvadiet vienu veselu skaitli, kopējo skaistu puķu dobes sadalījumu skaitu.


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
N, M ≤ 100 10
NM ≤ 500 20
NM ≤ 1500 30
Bez papildus ierobežojumiem 40
Kopā:    100

 


Paraugdati

Stdin
4 6
rbyrby
yvbyvb
rbyrby
yvbyvb
Stdout
4

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.