Kevin的满分秘籍

题号：NC261528
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\sf I\ feel\ something\ so\ right$

$\sf Doing\ the\ wrong\ thing$

—— $Counting\ Stars,\ \text{OneRepublic}$

氧气少年拿到了一张包含 $n$ （ $n$ 为偶数）道选择题的试卷，选择题的特点如下：

每道题只有两个选项，用 $\tt A$ 和 $\tt B$ 表示；
每道题只有一个正确答案；
每道题答对得 $1$ 分，答错得 $0$ 分；
整张试卷的满分为 $n$ ；
标准答案中正确答案为 $\tt A$ 的题目和正确答案为 $\tt B$ 的题目均恰好有 $\frac{n}{2}$ 个。

氧气少年必须做完整张试卷上的所有题目，不能空题。

由于试卷太难，氧气少年一道题也不会做，因此他只能猜答案。氧气少年猜的答案将会以一个长度为 $n$ 的只包含 $\tt A$ 和（或） $\tt B$ 的字符串的形式给出。

氧气少年猜完答案后，他将试卷交给了月色哥哥，月色哥哥检查完成后，告诉氧气少年他得了 $k$ 分。

氧气少年的目标是得到满分，因此如果他得到的不是满分（即 $k<n$ ），那么他接下来采取下面的步骤：

修改自己试卷上的不超过 $1$ 道题的答案。
将试卷交给月色哥哥，得到新的分数，然后进行下面的判断：

如果得分是满分，则停止；
否则，回到步骤 $1$ 。

氧气少年需要采取最优策略，来最小化步骤 $1$ 的执行次数。

请求出步骤 $1$ 执行次数的期望。请注意步骤 $1$ 可能执行零次。

可以证明，答案可以表示成 $\frac{p}{q}$ 的形式。其中， $p\geq 0,q\geq 1,\gcd(p,q)=1,q\mod 998244353\neq 0$ 。因此你只需输出 $p\cdot q^{998244351}\mod 998244353$ 即可。

输入描述:

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

第一行包含两个整数 。保证  是偶数。
第二行包含一个长度为  的字符串 ，表示所猜的答案。保证  只包含  和（或），保证所猜的答案符合题目的约束。

输出描述:

对于每组测试用例：
仅输出一行，包含一个整数，表示答案。

示例1

输入

复制

4
2 1
AA
6 5
ABBBAB
6 6
ABAABB
12 8
BAAABABBBABA

输出

复制