题目背景

矩阵快速幂是计算机科学中常见的基础工具。

不过，当矩阵规模非常大时，即使采用快速幂，也无法直接存储和计算整个矩阵。本题给出的矩阵具有特殊的元素结构，并且只要求查询矩阵幂中的少量位置。

请计算这些指定位置上的元素。

题目描述

给定四个整数 $d,q,n,k$。

构造一个 $n\times n$ 的矩阵 $A$。矩阵的行、列下标均从 $0$ 开始，即：

$$0\le i,j<n.$$

矩阵 $A$ 的第 $i$ 行第 $j$ 列元素定义为：

$$a_{i,j}=d\cdot i+q^j.$$

其中，$q^0=1$。

令：

$$B=A^k.$$

这里的矩阵乘法采用通常的定义。对于两个 $n\times n$ 的矩阵 $X,Y$，其乘积 $Z=XY$ 满足：

$$z_{i,j} = \sum_{t=0}^{n-1}x_{i,t}y_{t,j}.$$

现在给定 $T$ 个查询。第 $t$ 个查询给出两个下标 $r_t,c_t$，要求计算：

$$b_{r_t,c_t}\bmod 1\,000\,000\,007.$$

请按照查询顺序输出所有答案。

输入格式

第一行包含四个整数：

$$d,q,n,k.$$

第二行包含一个整数 $T$，表示查询数量。

接下来 $T$ 行，每行包含两个整数 $r_t,c_t$，表示需要查询矩阵 $B$ 的第 $r_t$ 行、第 $c_t$ 列元素。

输出格式

输出一行 $T$ 个整数。

第 $t$ 个整数表示：

$$b_{r_t,c_t}\bmod 1\,000\,000\,007.$$

答案按照查询在输入中出现的顺序输出，相邻整数之间用一个空格分隔。

数据范围

对于所有测试数据：

• $0\le d\le 10^9$；
• $1\le q\le 10^9$；
• $1\le n\le 10000$；
• $1\le k\le 10^9$；
• $1\le T\le 50$；
• $0\le r_t<n$；
• $0\le c_t<n$。

样例 1

输入

1 2 2 2
4
0 0
0 1
1 0
1 1

输出

5 8 8 13

解释

矩阵 $A$ 为：

$$A= \begin{pmatrix} 1&2\\ 2&3 \end{pmatrix}.$$

因此：

$$B=A^2 = \begin{pmatrix} 1\cdot1+2\cdot2& 1\cdot2+2\cdot3\\ 2\cdot1+3\cdot2& 2\cdot2+3\cdot3 \end{pmatrix} = \begin{pmatrix} 5&8\\ 8&13 \end{pmatrix}.$$

四个查询依次要求矩阵 $B$ 的全部四个元素，因此输出：

5 8 8 13

样例 2

输入

0 1 10 3
10
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

输出

100 100 100 100 100 100 100 100 100 100

解释

由于 $d=0$ 且 $q=1$，矩阵 $A$ 中的每个元素都是 $1$。

因此 $A^2$ 中每个元素都是 $10$，$A^3$ 中每个元素都是 $100$。

样例 3

输入

0 1000000000 1 1000000000
3
0 0
0 0
0 0

输出

1 1 1

解释

当 $n=1$ 时，矩阵只有一个元素：

$$a_{0,0}=d\cdot0+q^0=1.$$

因此无论 $k$ 为多少，$A^k$ 的唯一元素始终为 $1$。