Problem I: Coin and Die
Problem
表と裏のあるコインと $1$ から $N$ までの目があるサイコロがある。Gachoくんはこれらを用いて以下のゲームをして遊ぶことにした。
ゲームは最初に得点が $0$ の状態から始まり、以下の手順で進められる。
- サイコロを $1$ 回振り、そのとき出た目の数を得点に加算する
- 現在の得点が $K$ 以上ならゲームクリアとなりゲームを終了する
- 現在の得点が $K$ 未満ならコインを投げ表が出れば1.に戻り、裏が出ればゲームオーバーとなりゲームを終了する
コインは投げると $P\%$の確率で表になり、 $(100-P)\%$の確率で裏になる。また、サイコロは振ると、それぞれの目が等確率で出現する。
このとき、一度のゲームでGachoくんがゲームクリアすることができる確率を求めよ。
求める確率を互いに素な整数 $P, Q$ を用いて $\frac{P}{Q}$ と表したとき、 $R \times Q \equiv P\bmod 998244353$ となる $0$ 以上 $998244352$ 以下の整数 $R$ を出力せよ。この問題の制約下で、このような $R$ は必ず一意に存在する。
Input
入力は以下の形式で与えられる。
$N$ $K$ $P$
$N, K, P$ が空白区切りで一行に与えられる。
Constraints
入力は以下の条件を満たす。
- $1 \leq N \leq 10^5 $
- $1 \leq K \leq 10^5 $
- $1 \leq P \leq 99 $
- 入力はすべて整数
Output
ゲームをクリアすることができる確率を互いに素な整数 $P, Q$を用いて $\frac{P}{Q}$ と表したとき、$R \times Q\equiv P\bmod 998244353$ となる $0$ 以上 $998244352$ 以下の整数 $R$ を出力せよ。
Sample Input 1
1 1 50
Sample Output 1
1
Sample Input 2
2 2 10
Sample Output 2
648858830
Sample Input 3
6 10 99
Sample Output 3
650893870