Contest Duration: - (local time) (100 minutes) Back to Home
G - Access Counter /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

• i=0,1,2,\ldots,23 に対し、毎日 i 時ちょうどにアクセスが発生する可能性がある。
• c_i=T の場合、高橋君が X パーセントの確率でアクセスする。
• c_i=A の場合、青木君が Y パーセントの確率でアクセスする。
• 高橋君や青木君がアクセスするかどうかは毎回独立に決まる。
• これ以外のアクセスは発生しない。

また、高橋君はアクセスカウンターを設置してから N 回目のアクセスが自身によるものではない方が好ましいと考えています。

制約

• 1 \leq N \leq 10^{18}
• 1 \leq X,Y \leq 99
• c_iT または A
• N,X,Y は整数

入力

N X Y
c_0 c_1 \ldots c_{23}


入力例 1

1 50 50
ATATATATATATATATATATATAT


出力例 1

665496236


入力例 2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT


出力例 2

0


入力例 3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT


出力例 3

744124544


Score : 600 points

Problem Statement

Takahashi has decided to put a web counter on his webpage.
The accesses to his webpage are described as follows:

• For i=0,1,2,\ldots,23, there is a possible access at i o'clock every day:
• If c_i=T, Takahashi accesses the webpage with a probability of X percent.
• If c_i=A, Aoki accesses the webpage with a probability of Y percent.
• Whether or not Takahashi or Aoki accesses the webpage is determined independently every time.
• There is no other access.

Also, Takahashi believes it is preferable that the N-th access since the counter is put is not made by Takahashi himself.

If Takahashi puts the counter right before 0 o'clock of one day, find the probability, modulo 998244353, that the N-th access is made by Aoki.

Notes

We can prove that the sought probability is always a finite rational number. Moreover, under the constraints of this problem, when the value is represented as \frac{P}{Q} with two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq X,Y \leq 99
• c_i is T or A.
• N, X, and Y are integers.

Input

The input is given from Standard Input in the following format:

N X Y
c_0 c_1 \ldots c_{23}


Sample Input 1

1 50 50
ATATATATATATATATATATATAT


Sample Output 1

665496236


The 1-st access since Takahashi puts the web counter is made by Aoki with a probability of \frac{2}{3}.

Sample Input 2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT


Sample Output 2

0


There is no access by Aoki.

Sample Input 3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT


Sample Output 3

744124544