Masala C

Xotira 512 MB Vaqt 1000 ms

Harfli ketma-ketlik #1

Ismoil yo'ldan qog'oz topib oldi. Qog'ozda katta K ta ingliz harflardan tashkil topgan M uzunlikdan iborat ketma-ketlik bor ekan. U quydagicha:
$1. AAAAA...A$

$2. AAAAA...B$

$3. AAAAA...C$

$.......................$

Ismoil qiziqib qoldi. Agar shunday tartib bilan ketgan bo'lsa S kod berilsa, shu kod nechanchi qatorda joylashgan ekanligiga va buni topishga qiynaldi. Siz unga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda K va M natural son kiritiladi. $(1≤K≤26)$ , $(1≤M<10^8)$

Ikkinchi qatorda S kod beriladi. $len(S)==M$

Chiquvchi ma'lumotlar:

Masala javobini $10^9+7$ ga bo'lgandagi qoldiqqa mos natijani chop eting.

Misollar

#	input.txt	output.txt
1	4 3 ABC	7
2	5 5 DAAAA	1876
3	4 5 CAABD	520

Izoh:

1-testda
1. AAA
2. AAB
3. AAC
4. AAD
5. ABA
6. ABB
7. ABC
8. ABD
9. ACA
…… kabi bo'lganda 7 qatorda ABC satr joylashgan.