시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 0 0 0 0.000%

문제

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 109 + 7.

입력

U prvom se retku nalaze prirodni brojevi n (1 ≤ n ≤ 100) i m (1 ≤ m ≤ 109) 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.

예제 입력 1

2 1
a
b

예제 출력 1

24

예제 입력 2

3 2
a
ba
bb

예제 출력 2

624

예제 입력 3

4 10
wa
tle
mle
sigsegv

예제 출력 3

798986899