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 spacemiles long and consists of one planet every spacemile, named . Fax initially only has units of fuel on his Kyuwing, so he may need to stop at some planets to refuel. There are planets where Fax can refuel, and they have a limited supply of fuel. For each of the planets, the planet is numbered and contains 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 , Fax must determine , the number of distinct routes (modulo ), given the fuel supplies of the planets. If , Fax needs to determine the fuel supplies of the planets so that there are (modulo ) distinct routes. Two routes are distinct if there is at least one planet that is in one route but not the other.
None of the planets will share the same .
For test cases with , .
The first line contains .
If , the second line contains three integers , , and .
On the next lines, the line will contain two integers, and .
If , the second line contains , the number of routes (modulo ).
If , print , the number of routes Fax can take to reach his destination, modulo .
If , on the first line, print three integers , , and .
On the next lines, the line should contain two integers, and .
Your output must satisfy the given constraints. The number of routes (modulo ) should be equal to .
Sample Input 1
1 10 5 5 1 5 4 2 5 3 6 2 8 2
Sample Output 1
Explanation for Sample Output 1
The routes are as follows:
Sample Input 2
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
Sample Output 3
2 1 1 1 1