← 返回题目列表

AtCoder · pakencamp_2023_day3_a

A. 字母ABC

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

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

  1. i=2 。 插入S 的 2 紧接在第一个字符之后 \mathtt{C} 。
  2. i=2 。 插入S 的 2 紧接在第一个字符之后 \mathtt{B} 。

入力例 2

2 10
CC

出力例 2

1

入力例 3

19 21
AABCBAACCCACACCCBAB

出力例 3

957795267