Nonsense

Given $n$, $x$ and $y$, let $f\_{n, x, y}(a, b)$ denote the value of $\sum\_{i = a}^{n - b} \binom{i}{a} x^{i - a} \binom{n - i}{b} y^{n - i - b}\text{.}$

Bobo also has $q$ pairs $(a\_1, b\_1), \dots, (a\_q, b\_q)$. Find the value of $f\_{n, x, y}(a\_1, b\_1), \dots, f\_{n, x, y}(a\_q, b\_q)$ modulo $998244353$.

Note: $\binom{n}{k} = \frac{n!}{(n - k)! k!}\text{.}$

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains four integers $n$, $x$, $y$ and $q$.

In the following $q$ lines, the $i$-th line contains two integers $a\_i$ and $b\_i$.

For each pair, output an integer which denotes the value modulo $998244353$.

• $2 \leq n \leq 10^9$
• $0 \leq x, y < 998244353$
• $1 \leq q \leq 2 \times 10^5$
• $1 \leq a\_i, b\_i \leq 5000$ for each $1 \leq i \leq q$
• $a\_i + b\_i \leq n$ for each $1 \leq i \leq q$
• In each input, the sum of $\max(a\_1, b\_1, \dots, a\_q, b\_q)$ does not exceed $5000$. The sum of $q$ does not exceed $2 \times 10^5$.