Kritik Yanlış Okuma#3448

Kritik Yanlış Okuma

1 saniye
128 megabayt

Küçük Latin harflerinden oluşan adet s_1, s_2, \ldots, s_k dizgisi verilmektedir.

Küçük Latin harflerinden oluşan ve s_1, s_2, \ldots, s_k dizgilerinin hiçbirini alt dizgi (ardışık karakterlerden oluşan bir dizi) olarak içermeyen, uzunluğundaki dizgilerin sayısını bulunuz. Bu sayı büyük olabileceğinden, cevabı modülüne göre yazdırınız.

Giriş

İlk satırda, sayılacak dizgilerin uzunluğu olan ve yasaklı dizgi sayısı olan (1 \le n \le 10^9, 1 \le k \le 10) olmak üzere iki tam sayı bulunur.

Sonraki satırın her birinde bir s_i dizgisi bulunur. Her dizgi küçük Latin harflerinden oluşur ve uzunluğu ile arasında (bu değerler dahil) değişir.

Çıktı

s_i dizgilerinin hiçbirini alt dizgi olarak içermeyen, uzunluğundaki dizgilerin sayısını, modülüne göre tek bir tam sayı olarak yazdırınız.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading