010 - k番目の文字列
時間制限 2 秒 / メモリ制限 256 MB / 得点 16 / x 0 /
問題
アリスはn枚のカードを持っていて,それらには,それぞれ '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 行目にカードの数 n とk が空白区切りで与えられる.
次の行に文字列 s が与えられる. (長さはnとは限らない)
出力
答えの数字を1行に出力せよ.
制約
- 1 ≦ n ≦ 26
- 1 ≦ k ≦ n(n+1)/2
- sのすべての文字は互いに異なる
- sは アルファベットの1~n番目の小文字からなる
入出力例
入力例1
2 2 b
出力例1
1
入力例2
3 3 b
出力例2
2
入力例3
3 4 ba
出力例3
1
入力例4
26 300 utpc
出力例4
831387601