408408: GYM103115 B cocktail with hearthstone

Mr. Cocktail like a game named Hearthstone. In this game, there is a game mode "Arena" with the four rules as follows.

1.The record of each player is described as $$$(a,b)$$$, where $$$a$$$ means number of wins, and $$$b$$$ means number of losses. At the beginning of the game, the record is (0,0), that is, 0 wins and 0 losses.

2.For each round, the number of wins in winner's record will be added one point. And the defeated one will be added one point in the number of losses in his record. There is no tie in this game.

3.Each round will be start between two persons with same record. That is, when your record is (a, b), your opponent's record is also (a, b). Obviously, a player with a record of (a+1, b) will be produced after each round, and a record of (a, b+1) players.

4.When someone win N times or lost M times , he will automatically exit and end his game.

In order for everyone to have an opponent before the end of the game, $$$2^{n+m}$$$ players were assigned to participate by Mr. Cocktail.

He will ask q times, and each time he give $$$a, b$$$ and want to know how many people were automatically out of the game with a record of $$$(a,b)$$$. (Guaranteed that $$$(a,b)$$$ meets the exit conditions).

Since the answer may be very large, you only need to output the result after the answer is modulo $$$10^9+7$$$.

In the first line input three integer $$$n,m,q(1 \leq m < n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)$$$ as described in statement.

Then it will input $$$q$$$ lines data. every line will only contain two integer $$$a, b$$$($$$0 \leq a \leq n, 0 \leq b \leq m $$$, ensure that b == m or a == n ).

For each query, output an integer on a line to indicate the answer.

2 1 1
0 1

4

A total of $$$2^{2+1}=8$$$ people with record $$$(0,0)$$$ participating in this game. After the first round, 4 $$$(1,0)$$$ and 4 $$$(0,1)$$$ are generated. Among them, $$$(0,1)$$$ is eliminated directly, and there will be no players with $$$(0,1)$$$ records in subsequent matches, so the answer is 4.