問題文

九頭龍さんは、ある女の子から英小文字のみからなる長さ 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 は英小文字のみからなる

入力例 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