给定 $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}$$

Bobo 还有 $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$ 取模的结果。

注： $$\binom{n}{k} = \frac{n!}{(n-k)!k!}$$

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据： 第一行包含四个整数 $n, x, y$ 和 $q$。 接下来的 $q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$。

数据范围

• $2 \le n \le 10^9$
• $0 \le x, y < 998244353$
• $1 \le q \le 2 \times 10^5$
• 对于每个 $1 \le i \le q$，有 $1 \le a_i, b_i \le 5000$
• 对于每个 $1 \le i \le q$，有 $a_i + b_i \le n$
• 在每组输入中，$\max(a_1, b_1, \dots, a_q, b_q)$ 的总和不超过 $5000$。$q$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每一对 $(a_i, b_i)$，输出一个整数，表示该值对 $998244353$ 取模的结果。

样例

样例输入 1

3 1 2 2
1 1
1 2
100 2 3 1
1 1

样例输出 1

6
1
866021789