G - Access Counter Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

高橋君は自身が運営しているWebサイトにアクセスカウンターを設置することにしました。
彼のWebサイトに対して発生するアクセスの様子は以下のように記述されます。

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

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

高橋君がアクセスカウンターを設置したのがある日の 0 時直前の時、設置してから N 回目のアクセスが青木君によるものになる確率を \mod 998244353 で求めてください。

注記

求める確率は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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

高橋君がアクセスカウンターを設置してから 1 回目のアクセスが青木君によるものになる確率は \frac{2}{3} です。

入力例 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}

Output

Print the answer.

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