← 返回题目列表

AtCoder · ttpc2019_g

G. 回文情书

中文机器翻译题面 查看原题

配点 : 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