東京大学プログラミングコンテスト2012

G - k番目の文字列


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

アリスはn (\leq 26)枚のカードを持っていて,それらには,それぞれ a から,アルファベットのn番目の小文字が書かれている. 例えば,n=3 ならば,アリスは a, b, c と書かれた3枚のカードを持っている. アリスは,これらのカードを並べ替えて文字列を作った. さらに,その空でないすべての部分文字列を考え,それらを辞書順にソートした. このとき,k番目の文字列がsであったという. このようなことが起こる並べ替え方は何通りあるだろか.

例えば,n=3 のとき,カードを cab と並べ替えたとすると,その部分文字列を辞書順にソートすると,a,ab,b,c,ca,cab となり,例えば3番目の文字列はb である. 3番めの文字列が b となる並べ替え方の数は,これと,bac の2通り存在する.

すべての部分文字列を辞書順にソートした時に,k番目の文字列が,sとなるような並べ替え方の数を,mod 1000000007 で求めよ. ただし,アリスは夢を見ていて,このような並べ方は本当は存在しないかもしれない. その場合には,0を答えよ.


入力

n k
s

1 行目にカードの数 nk が空白区切りで与えられる. 次の行に文字列 s が与えられる. (長さはnとは限らない)

出力

答えの数字を1行に出力せよ.

制約

部分点

この問題の判定には,50 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす.


入力例 1

2 2
b

入力例 1 に対する出力例

1

入力例 2

3 3
b

入力例 2 に対する出力例

2

入力例 3

3 4
ba

入力例 3 に対する出力例

1

入力例 4

26 300
utpc

入力例 4 に対する出力例

831387601

Submit提出する