Pool - MarisaOJ: Marisa Online Judge
Given a rectangle consisting of $1001$ rows and $N$ columns. Each cell in the table can be either safe or unsafe. You need to select a subrectangle such that:
- All cells of the subrectangle are safe.
- It has a bottom side adjacent to the bottom side of the large rectangle.
You only know that for each cell of the rectangle, the probability of it being safe is $q$, and the probability of it being unsafe is $1-q$. Find the probability for the largest possible subrectangle with the exact area $K$.
### Input
- A line containing four positive integers $N, K, x, y$, with $1 \le x < y \le 998244353$. The value of $q$ is $\frac{x}{y}$.
### Output
- Output an integer as the answer to the problem modulo $998244353$.
- In other words, if the answer is in the form $\frac{a}{b}$ after simplification, where $a$ and $b$ are coprime integers, output an integer $x$ such that $bx \equiv a \mod 998244353$ and $0 \leq x < 998244353$.
### Example
Input:
```
10 5 1 2
```
Output:
```
342025319
```
### Constraints
Test |
N |
K |
1,2 |
=1 |
$\leq 1000$ |
3 |
$\leq 10$ |
$\leq 8$ |
4 |
$\leq 9$ |
5 |
$\leq 10$ |
6 |
$\leq 1000$ |
$\leq 7$ |
7 |
$\leq 8$ |
8 |
$\leq 9$ |
9,10,11 |
$\leq 100$ |
12,13,14 |
$\leq 1000$ |
15,16 |
$\leq 10^9$ |
$\leq 10$ |
17,18 |
$\leq 100$ |
19,20 |
$\leq 1000$ |
Topic
Math
Dynamic Programming
Rating
2700
Solution (0)
Solution