Access Counter

题目描述

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

对于 $i=0,1,2,\ldots,23$，每天在 $i$ 点钟都有可能发生一次访问： 如果 $c_i=$$T$，Takahashi 以 $X$ 百分比的概率访问该网页。 如果 $c_i=$$A$，Aoki 以 $Y$ 百分比的概率访问该网页。 Takahashi 或 Aoki 是否访问该网页在每次都独立决定。

没有其他访问。

另外，Takahashi 希望从放置计数器起第 $N$ 次访问不是由他自己完成。
如果 Takahashi 在某一天的 0 点之前 放置计数器，求第 $N$ 次访问由 Aoki 完成的概率，模 $998244353$。

输入格式

输入从标准输入按如下格式给出： $N$ $X$ $Y$ $c_0 c_1 \ldots c_{23}$

输出格式

输出答案。

1 50 50
ATATATATATATATATATATATAT

665496236

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT

0

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT

744124544

提示

$1 \leq N \leq 10^{18}$ $1 \leq X,Y \leq 99$ $c_i$ 是 $T$ 或 $A$。 $N$, $X$, 和 $Y$ 是整数。我们可以证明所求的概率总是一个有限的有理数。此外，在本题的约束下，当该值表示为互质整数 $P$ 和 $Q$ 的 $\frac{P}{Q}$ 时，我们可以证明存在唯一的整数 $R$ 使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求这个 $R$。将计数器放置后第 $1$ 次访问由 Aoki 完成的概率是 $\frac{2}{3}$。
Aoki 没有访问。

标签: AtCoder|abc271G

来源

AtCoder|abc271G