问题描述

Takahashi 决定在他的网页上放置一个网页计数器。
对他的网页的访问描述如下：

• 对于每天的 $i=0,1,2,\ldots,23$ 时刻可能会有一次访问：
  • 如果 $c_i=$T，则 Takahashi 以 $X$ 的概率访问该网页。
  • 如果 $c_i=$A，则 Aoki 以 $Y$ 的概率访问该网页。
  • Takahashi 或 Aoki 是否访问该网页是独立确定的。
• 没有其他访问。

另外，Takahashi 认为，自从计数器被放置后的第 $N$ 次访问最好不是由 Takahashi 自己完成的。

如果 Takahashi 在一天的 0 时刻前 放置计数器，请找出第 $N$ 次访问是由 Aoki 完成的概率，模 $998244353$。

注意

我们可以证明所求的概率始终是一个有限的有理数。此外，在问题的约束条件下，当该值表示为具有两个互质整数 $P$ 和 $Q$ 的 $\\frac{P}{Q}$ 时，我们可以证明存在唯一的整数 $R$，使得 $R \\times Q \\equiv P\\pmod{998244353}$ 且 $0 \\leq R \\lt 998244353$。寻找这个 $R$。

约束条件

• $1 \\leq N \\leq 10^{18}$
• $1 \\leq X,Y \\leq 99$
• $c_i$ 是 T 或 A。
• $N$、$X$ 和 $Y$ 是整数。

输入

输入使用以下格式从标准输入给出：

$N$ $X$ $Y$ $c_0 c_1 \\ldots c_{23}$

输出

输出答案。

示例输入 1

1 50 50
ATATATATATATATATATATATAT

示例输出 1

665496236

自从 Takahashi 放置网页计数器以来的第 1 次访问是由 Aoki 完成的概率为 $\frac{2}{3}$。

示例输入 2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT

示例输出 2

0

没有 Aoki 的访问。

示例输入 3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT

示例输出 3

744124544