AT_ttpc2019_g Palindromic Love Letter

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_g 九頭龍さんは、ある女の子から英小文字のみからなる長さ $ N $ の回文 $ S $ をもらいました。 しかし、九頭龍さんの弟子のあいちゃんが、この回文に以下のようないたずらをしてしまいました。 - $ S $ の $ i\ (1\ \leq\ i\ \leq\ N) $ 番目の文字を異なる英小文字に変更する、という操作を **ちょうど** $ K $ 回行う （ただし、同じ位置の文字を複数回選ぶこともあるものとします） いたずらをされた後の文字列 $ T $ と整数 $ K $ が与えられるので、元の回文としてありうるものが何通りあるかを $ 10^9\ +\ 7 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T $

元の回文としてありうるものの通り数を $ 10^9\ +\ 7 $ で割ったあまりを出力せよ。

### 制約 - $ N $ は $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^{5} $ を満たす整数 - $ K $ は $ 0\ \leq\ K\ \leq\ 10^{9} $ を満たす整数 - $ |T|\ =\ N $ - $ T $ は英小文字のみからなる ### Sample Explanation 1 \- `aabaa`, `abbba` が条件を満たします。 ### Sample Explanation 2 \- 操作をちょうど $ K $ 回行うことに注意してください。