G - Palindromic Love Letter
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
九頭龍さんは、ある女の子から英小文字のみからなる長さ N の回文 S をもらいました。
しかし、九頭龍さんの弟子のあいちゃんが、この回文に以下のようないたずらをしてしまいました。
- S の i \ (1 \leq i \leq N) 番目の文字を異なる英小文字に変更する、という操作を ちょうど K 回行う
(ただし、同じ位置の文字を複数回選ぶこともあるものとします)
いたずらをされた後の文字列 T と整数 K が与えられるので、元の回文としてありうるものが何通りあるかを 10^9 + 7 で割ったあまりを求めてください。
制約
- N は 1 \leq N \leq 2 \times 10^{5} を満たす整数
- K は 0 \leq K \leq 10^{9} を満たす整数
- |T| = N
- T は英小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
N K T
出力
元の回文としてありうるものの通り数を 10^9 + 7 で割ったあまりを出力せよ。
入力例 1
5 1 abbaa
出力例 1
2
aabaa
,abbba
が条件を満たします。
入力例 2
4 1 aaaa
出力例 2
0
- 操作をちょうど K 回行うことに注意してください。
入力例 3
1 100 a
出力例 3
26
入力例 4
11 7 abracadabra
出力例 4
1019576