Fax McClad delivering Mighty Reactors and green goods. Note the dangerous microwave radiation from the Mighty Reactors.

Fax McClad, Croneria's best bounty hunter, has been hired by a mysterious group called BSE to deliver some goods from the planet Croneria to the planet Phantom-R. On his delivery confirmation list, he notices that the cargo consists of dangerously radioactive Mighty Reactors, and green goods. The hazardous goods don't concern Fax, because money is always more important than safety.

The route from Croneria to Phantom-R is ~D~ spacemiles long and consists of one planet every spacemile, named ~1, \dots, D-1~. Fax initially only has ~N~ units of fuel on his Kyuwing, so he may need to stop at some planets to refuel. There are ~P~ planets where Fax can refuel, and they have a limited supply of fuel. For each of the ~P~ planets, the ~i^\text{th}~ planet is numbered ~Q_i~ and contains ~R_i~ units of fuel. Unfortunately, because of security reasons, Fax must dump all of the fuel he has on his Kyuwing upon entering a planet. It takes one unit of fuel to travel one spacemile.

However, Fax knows that evil organizations such as the Dankey Kang Gang want to steal the precious goods that he is delivering. As such, Fax needs to plan several routes to get to his destination. To speed up his delivery, Fax will not backtrack, nor visit the same planet twice.

In order to prepare for this delivery, Fax needs to simulate different traveling conditions. If ~X = 1~, Fax must determine ~W~, the number of distinct routes (modulo ~10^9+7~), given the fuel supplies of the planets. If ~X = 2~, Fax needs to determine the fuel supplies of the planets so that there are ~W~ (modulo ~10^9+7~) distinct routes. Two routes are distinct if there is at least one planet that is in one route but not the other.

Constraints

~2 \le D \le 100\,000~

~1 \le N \le D~

~1 \le P, Q_i, R_i \le D-1~

None of the ~P~ planets will share the same ~Q_i~.

For test cases with ~X = 2~, ~0 \le W < 10^9+7~.

Subtask	Points	~X~	Additional Constraints
1	20	~X = 1~	~D \le 10~
2	10	~X = 1~	~D \le 1000~
3	20	~X = 1~	None
4	10	~X = 2~	~W \le 100\,000~
5	20	~X = 2~	None
6	20	~X = 2~	~D < 70~

Input Specification

The first line contains ~X~.

If ~X = 1~, the second line contains three integers ~D~, ~N~, and ~P~.
On the next ~P~ lines, the ~i^\text{th}~ line contains two integers, ~Q_i~ and ~R_i~.

If ~X = 2~, the second line contains ~W~, the number of routes (modulo ~10^9+7~).

Output Specification

If ~X = 1~, print ~W~, the number of routes Fax can take to reach his destination, modulo ~10^9+7~.

If ~X = 2~, on the first line, print three integers ~D~, ~N~, and ~P~.
On the next ~P~ lines, the ~i^\text{th}~ line should contain two integers, ~Q_i~ and ~R_i~.
Your output must satisfy the given constraints. The number of routes (modulo ~10^9+7~) should be equal to ~W~.

Sample Input 1

1
10 5 5
1 5
4 2
5 3
6 2
8 2

Sample Output 1

11

Explanation for Sample Output 1

The ~11~ routes are as follows:

• ~0 \to 1 \to 4 \to 5 \to 6 \to 8 \to 10~
• ~0 \to 1 \to 4 \to 5 \to 8 \to 10~
• ~0 \to 1 \to 4 \to 6 \to 8 \to 10~
• ~0 \to 1 \to 5 \to 6 \to 8 \to 10~
• ~0 \to 1 \to 5 \to 8 \to 10~
• ~0 \to 1 \to 6 \to 8 \to 10~
• ~0 \to 4 \to 5 \to 6 \to 8 \to 10~
• ~0 \to 4 \to 5 \to 8 \to 10~
• ~0 \to 4 \to 6 \to 8 \to 10~
• ~0 \to 5 \to 6 \to 8 \to 10~
• ~0 \to 5 \to 8 \to 10~

Sample Input 2

2
420

Sample Output 2

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

Sample Input 3

2
1

Sample Output 3

2 1 1
1 1