A4741 | 巨大的表格

给定一个 $N$ 行 $M$ 列的表格 $A$。

其 $0$ 行上的元素 $A_{0, 0}, A_{0, 1}, \cdots, A_{0, M-1}$ 的值分别为 $0, 1, \cdots, M - 1$；

更正式地 $A_{0, i} = i\ (0 \le i \lt M)$。

现给出 $0$ 列中除 $A_{0, 0}$ 外的 $N - 1$ 个元素 $A_{1, 0}, A_{2, 0}, \cdots, A_{N - 1, 0}$ 的值。

我们可以通过以下方式计算出表格中 $i$ 行 $j$ 列上的元素 $A_{i, j}$ 的值：

$$ A_{i, j} = A_{i - 1, j} \times S + A_{i, j - 1} \times T $$

其中 $1 \le i \lt N, 1 \le j \lt M$。

你需要回答 $Q$ 个查询，每个查询给出两个整数 $R_i$ 和 $C_i$，你需要输出 $A_{R_i, C_i}$ 的值。

由于这个值可能会很大，请你输出其对 $998244353$ 取模后的值。

$\large{数据范围}$

- $2 \le N \le 30$
- $2 \le M \le 10^9$
- $1\le S, T \le 10^9$
- $1 \le A_{i, 0} \le 10^9$
- $1 \le Q \le 100$
- $1 \le R_i \lt N$
- $1 \le C_i \lt M$

对于每个测试文件，格式如下：

$\tt{N\ M\ S\ T}$

$\tt{A_{1, 0}\ A_{2, 0}\ \cdots A_{n - 1, 0}}$

$\tt{Q}$

$\tt{R_1\ C_1}$

$\tt{R_2\ C_2}$

$\tt{\vdots}$

$\tt{R_Q\ C_Q}$

对于每个查询 $(R_i, C_i)$ 在单独的一行中输出 $A_{R_i, C_i}$ 的值。