In an alternate universe, the game of Chess is played on an ~N~ by ~M~ board (with cell ~(1, 1)~ being on the bottom left and cell ~(N, M)~ on the top right). Pawns in this game can only move forward diagonally. That is, a pawn at cell ~(x, y)~ may only move to cells ~(x \pm 1, y + 1)~ so long as the cell is inside the board.

There is a pawn at cell ~(i, j)~. For ~Q~ different cells ~(u_q, v_q)~ determine the number of ways the pawn can reach that cell with a non-negative number of legal moves. Because this number may be large, output the answer modulo ~10^9+7~.

Constraints

~1 \le N, M \le 2 \times 10^3~

~1 \le i, u_q \le N~

~1 \le j, v_q \le M~

~1 \le Q \le 2 \times 10^5~

Input Specification

The first line of input will contain ~5~ integers ~N~, ~M~, ~i~, ~j~, and ~Q~.

The next ~Q~ lines will contain ~2~ space-separated integers ~(u_q, v_q)~ for that query.

Output Specification

For each of the ~Q~ queries output the number of ways the pawn can reach the cell with a non-negative number of legal moves modulo ~10^9+7~, on a new line.

Sample Input

3 4 2 2 3
2 4
2 3
1 1

Sample Output

2
0
0

Explanation

.1.
.2.
.P.
3..

The pawn is at P in the diagram above. The first query is at cell ~(2, 4)~, 1 in the diagram. There are two possible ways to get there. The first is going to cell ~(1, 3)~ then to ~(2, 4)~. The second is going to cell ~(3, 3)~ then to ~(2, 4)~.

For the second query, there are no ways to reach the cell. This is also the case for the third query as a pawn may not move backwards.