配点 : 100 点
問題文
长度 N 字符串 给出了 S 。S 中的每个字符是 \mathtt{A},\mathtt{B},\mathtt{C} 。
从现在开始 对 S 执行以下操作 执行 K 次。决赛 S 可能的字符串数量为 选择 998244353 求余数。 在
- 1\leq i\leq |S|-1 的整数只有 i 。S 的 i 信和 i+1 如果字符相等,S 的 i 紧接在第一个字符之后 S 的 i 插入与该字符相同的字符。如果没有,S 的 i 紧接在第一个字符之后 \mathtt{A},\mathtt{B},\mathtt{C} 出 S 的 i 信和 i+1 插入一个不等于任一字符的字符。 仅由
制約
- 2\leq N\leq 2\times 10^5
- 1\leq K\leq 2\times 10^5
- S 表示 \mathtt{A},\mathtt{B},\mathtt{C} 组成的长度 N 字符串 给出了
入力
输入是按以下格式从标准输入给出的。 请输出
N K S
出力
决赛 S 可能的字符串数量为 选择 998244353 的余数。
入力例 1
4 2 AABB
出力例 1
7
例如,使用以下步骤 您可以创建 \mathtt{AABCBB} 。
- i=2 。 插入S 的 2 紧接在第一个字符之后 \mathtt{C} 。
- i=2 。 插入S 的 2 紧接在第一个字符之后 \mathtt{B} 。
入力例 2
2 10 CC
出力例 2
1
入力例 3
19 21 AABCBAACCCACACCCBAB
出力例 3
957795267