Problem8279--ABC280 —— E - Critical Hit

8279: ABC280 —— E - Critical Hit

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 3StatisticsShowOff!

Description

There is a monster with initial stamina $N$.
Takahashi repeatedly attacks the monster while the monster's stamina remains 1 or greater.
An attack by Takahashi reduces the monster's stamina by 2 with probability $\frac{P}{100}$ and by 1 with probability $1−\frac{P}{100}$.
Find the expected value, modulo 998244353 (see Notes), of the number of attacks before the monster's stamina becomes 0 or less.

【Notes】

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

Input

The input is given from Standard Input in the following format:
$N\ P$

Output

Find the expected value, modulo 998244353, of the number of Takahashi's attacks.

Constraints

$1≤N≤2×10^5$
$0≤P≤100$
All values in the input are integers.

Sample 1 Input 

3 10

Sample 1 Output 

229596204


An attack by Takahashi reduces the monster's stamina by 2 with probability $\frac{10}{100}=\frac{1}{10}$ and by 1 with probability $\frac{100−10}{100}=\frac{9}{10}$.

  • The monster's initial stamina is 3.
  • After the first attack, the monster's stamina is 2 with probability $\frac{9}{10}$ and 1 with probability $\frac{1}{10}$.
  • After the second attack, the monster's stamina is 1 with probability $\frac{81}{100}$, 0 with probability $\frac{18}{100}$, and −1 with probability $\frac{1}{100}$. With probability $\frac{18}{100}+\frac{1}{100}=\frac{19}{100}$, the stamina becomes 0 or less, and Takahashi stops attacking after two attacks.
  • If the stamina remains 1 after two attacks, the monster's stamina always becomes 0 or less by the third attack, so he stops attacking after three attacks.

Therefore, the expected value is $2\times \frac{19}{100}+3\times (1−\frac{19}{100})=\frac{281}{100}$. Since $229596204×100≡281(\bmod 998244353)$, print 229596204.


Sample 2 Input 

5 100

Sample 2 Output 

3

Takahashi's attack always reduces the monster's stamina by 2. After the second attack, the stamina remains 5−2×2=1, so the third one is required.

Sample 3 Input 

280 59

Sample 3 Output 

567484387

Source/Category

 
Submit