Pool - MarisaOJ: Marisa Online Judge

Pool

Time limit: 2000 ms
Memory limit: 512 MB
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$