NOI '17 P3 - Pool

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

There is a pool that can be modeled as a rectangular grid with width N meters and height 1001 meters. The bottom edge of the grid corresponds to a beach. Each 1m \times 1m square cell of the grid represents a unit of sea.

A safe area for swimming shall satisfy the following constraints:

  • All cells in the pool are safe.
  • Must be rectangular.
  • Must be adjacent to the bottom edge (i.e. the beach).

Given that each square cell of 1m \times 1m has probability q to be safe (independently), and 1-q probability to be not safe, find the probability such that the largest safe area for swimming is exactly K.

Input Specification

Input a line with four positive integers N,K,x,y where 1 \leq x < y < 998244353. The parameter q is just \frac{x}{y}.

Output Specification

Output a line with an integer denoting the answer modulo 998244353: if the answer is \frac{a}{b} in reduced form (i.e. a and b are coprime), then output x such that bx \equiv a \bmod 998244353 and 0 \leq x < 998244353.

Input

10 5 1 2

Output

342025319

Hint

x^{p-1} \equiv 1 \bmod p where p is prime and x \in [1,p).

Constraints

Test caseNK
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

Comments

There are no comments at the moment.