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 , where means number of wins, and means number of losses. At the beginning of the game, the record is , that is, wins and 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 , your opponent's record is also . Obviously, a player with a record of will be produced after each round, and a record of players.

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

In order for everyone to have an opponent before the end of the game, players were assigned to participate by Mr. Cocktail.

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

Since the answer may be very large, you only need to output the result after the answer is modulo .

In the first line input three integer  as described in statement. 

Then it will input  lines data. every line will only contain two integer , ensure that  or  ).

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

2 1 1
0 1

4

A total of  people with record  participating in this game. After the first round,   and   are generated. Among them,  is eliminated directly, and there will be no players with  records in subsequent matches, so the answer is .