Nonsense

$n$, $x$, $y$가 주어졌을 때, $f_{n,x,y}(a,b)$를 다음 식의 값으로 정의한다. $\sum_{i=a}^{n-b} \binom{i}{a} x^{i-a} \binom{n-i}{b} y^{n-i-b}.$ 여기서 $\binom{n}{k} = \frac{n!}{(n-k)!\,k!}$이다.

보보에게는 $q$개의 쌍 $(a_1, b_1), \dots, (a_q, b_q)$도 있다. $f_{n,x,y}(a_1, b_1), \dots, f_{n,x,y}(a_q, b_q)$의 값을 $998244353$으로 나눈 나머지를 구하시오.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스의 첫 줄에는 정수 $n$, $x$, $y$, $q$가 주어진다. 이어지는 $q$개의 줄에는 각각 정수 $a_i$와 $b_i$가 주어진다.

각 쌍에 대해 $f_{n,x,y}(a_i, b_i)$의 값을 $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$이며, 각 $1 \leq i \leq q$에 대해 $a_i + b_i \leq n$이다. 각 입력에서 $\max(a_1, b_1, \dots, a_q, b_q)$의 합은 $5000$을 넘지 않고, $q$의 합은 $2 \times 10^5$을 넘지 않는다.