18281번 - Fantastični Fožgaj 다국어

Fožgaj se želi sprijateljiti s Dodom i u tu svrhu je odlučio sastaviti govor o prijateljstvu.

Fožgajev govor je riječ koja se sastoji od m malih slova engleske abecede. Domagoj (koji je već od Fožgaja čuo jedan govor o prijateljstvu) zna da postoji popis od n riječi koje bi mogle preplašiti malog Dodu.

Gospodin Malnar je uspio Fožgaju nabaviti taj popis, a sada Fožgaja zanima koliko postoji različitih riječi duljine m u kojima se ne pojavljuje nijedna riječ s popisa. Za riječ s popisa kažemo da se pojavljuje u Fožgajevom govoru ako je u njemu prisutna kao niz uzastopnih znakova.

Pomozite Fožgaju i ispišite koliko postoji različitih riječi duljine m u kojoj se ne pojavljuje nijedna riječ s popisa, modulo 10⁹ + 7.

U prvom se retku nalaze prirodni brojevi n (1 ≤ n ≤ 100) i m (1 ≤ m ≤ 10⁹) iz teksta zadatka.

U svakom od sljedećih n redaka nalazi se jedna riječ s Domagojevog popisa. Riječi s popisa sastoje se od malih slova engleske abecede i neće se ponavljati. Također, suma duljina svih riječi će biti najviše 100.

U jedini redak ispišite traženi broj iz teksta zadatka.