题目描述

时间限制：1s

内存限制：512MB

小 P 和小 Q 正在进行一场特殊的乒乓球比赛，规则如下：

1. 开始时，小 P 和小 Q 的得分均为 $0$；
2. 有一个开始时就确定的长度为 $m$ 的字符串 $S$（只有 P 和 Q 两种字符，分别对应两位选手），最开始的时候为 $S_1$ 选手发球，第 $2$ 回合为 $S_2$ 选手发球……第 $m$ 回合为 $S_m$ 选手发球，第 $m+1$ 回合为 $S_1$ 选手发球……发球顺序不断循环这个字符串；
3. 在一个回合中获胜的选手得分加一；
4. 当其中一位选手的得分大于等于另一位选手的得分加 $n$ 时比赛结束，得分较高者获胜。

小 P 和小 Q 的发挥非常稳定，在一个回合中，当小 P 发球时，小 P 有 $p=\frac{p_a}{p_b}$ 的概率获胜；当小 $Q$ 发球时，小 P 有 $q=\frac{q_a}{q_b}$ 的概率获胜。

现在需要你求出小 P 获胜的概率为多少，可以证明最后的答案可以表示为一个分数 $\frac{a}{b}$，你只需要输出满足 $cb\equiv a\bmod 998244353$ 且同时满足 $c\in[0,998244353)$ 的 $c$，可以证明这样的 $c$ 是唯一的。

输入格式

从文件 pingpong.in 中读入数据。

第一行一个整数 $t$，表示测试数据的组数。

接下来每一组测试数据，第一行两个整数 $m,n$，分别表示字符串 $S$ 的长度以及最后需要达到的分差。

接下来一行为一个长度为 $m$ 的字符串 $S$，且只由 P 和 Q 构成。

接下来一行包含四个整数 $p_a,p_b,q_a,q_b$，由题意得到不同选手发球时小 P 获胜的概率。

输出格式

输出到 pingpong.out 中。

对于每一组输出输出一个整数，表示结果在 $\bmod\, 998244353$ 下的结果。

输入输出样例

输入

3
1 2
P
2 3
1 3
2 2
PQ
2 3
1 3
1 1
P
2 3
1 3

输出

399297742
499122177
665496236

样例解释

• 第一组数据：$S=\text{`P`}$，发球人永远是小 P。小 P 每回合得分概率为 $p = 2/3$，小 Q 得分概率为 $1/3$。分差达到 $2$ 获胜。理论计算小 P 获胜的概率为 $4/5 \equiv 399297742 \pmod{998244353}$。
• 第二组数据：$S=\text{`PQ`}$。小 P 在自己发球时有 $2/3$ 的概率得分，小 Q 在自己发球时有 $2/3$ 的概率得分。计算可得双方获胜概率均为 $1/2 \equiv 499122177 \pmod{998244353}$。
• 第三组数据：$n=1$。只需一回合即可决出胜负。第一局由小 P 发球，小 P 得分（即获胜）的概率直接是 $p = 2/3 \equiv 665496236 \pmod{998244353}$。

测试数据范围

共 $20$ 个测试点，测试点分配如下：

对于 $100\%$ 的数据：$1 \le t \le 10$，$1 \le n \le 10^{18}$，$1 \le m \le 100$，$1 \le p_a < p_b < 998244353$，$1 \le q_a < q_b < 998244353$。

数据保证在特殊性质要求下按一定方式随机生成