There is a pool that can be modeled as a rectangular grid with width meters and height 1001 meters. The bottom edge of the grid corresponds to a beach. Each 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 has probability to be safe (independently), and probability to be not safe, find the probability such that the largest safe area for swimming is exactly .
Input Specification
Input a line with four positive integers where . The parameter is just .
Output Specification
Output a line with an integer denoting the answer modulo 998244353: if the answer is in reduced form (i.e. and are coprime), then output such that and .
Input
10 5 1 2
Output
342025319
Hint
where is prime and .
Constraints
Test case | ||
---|---|---|
1,2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9,10,11 | ||
12,13,14 | ||
15,16 | ||
17,18 | ||
19,20 |
Comments