Županijsko natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) - 3. zadatak

Davne 2003. godine, u prvom hrvatskom pjevačkom talent-showu sudjelovali su Saša, Tin i Kedžo koji su nakon showa osnovali boy-bend koji se zvao – pogodite kako?

Zvao se Saša, Tin i Kedžo. Njihov jedini hit bila je pjesma 365.

("Tri, šest, pet jeee prošlo dana, bez tebe bolje saaam, uzalud me zoveeeš, ja te dobro znaaam..." iz e-mola.)

Zaluđene tinejdžerke vrištale su za Sašom, Tinom i Kedžom te su na zidu jedne zgrade napisale grafit sa slovima iz njihovih imena.

Riječ je o tablici od R redaka i S stupaca u čijem svakom polju piše neko malo slovo engleske abecede.

Saša, Tin i Kedžo našli su se pred tim grafitom i u tablici slova počeli tražiti svoja imena.

Preciznije:

Saša je pronašao pravokutnik unutar tablice (podtablicu) koji sadrži samo slova iz njegovog imena (s ili a), Tin je pronašao drugi pravokutnik koji sadrži samo slova njegovog imena (t, i ili n), a Kedžo treći pravokutnik koji sadrži samo slova njegovog imena (k, e, d, z ili o). Odabrana tri pravokutnika bili su disjunktni, tj. nisu imali zajedničkih polja.

Napišite program koji, dok svira pjesma 365, za dani grafit odgovara na sljedeće pitanje:

na koliko su načina Saša, Tin i Kedžo mogli izabrati opisane pravokutnike? (Pogledajte donje primjere za bolje razumijevanje zadatka.)

Ulazni podaci

U prvom su retku brojevi R i S (1 ≤ R, S ≤ 2000), dimenzije tablice slova.

Idućih R redaka sadrži po S malih slova engleske abecede koji čine opisanu tablicu.

Izlazni podaci

U jedini redak ispišite traženi broj načina, točnije njegov ostatak pri dijenjenju s 1 000 000 007.

Primjer zadatka

Ulaz

1 5
ssstk

Izlaz

6

Objašnjenje

Pojašnjenje prvog probnog primjera: Tin je mogao izabrati samo treće (t), a Kedžo četvrto slovo (k) u jedinom retku tablice.

Saša je od prva tri slova s mogao izabrati prvo, drugo, treće, prva dva, druga dva ili sva tri, što je ukupno šest mogućnosti.

Ulaz

3 5
sasax
tinyw
kedzo

Izlaz

900

Ulaz

3 6
sadsam
sasvim
sretna

Izlaz

190