ThingExplainer is a well-known koala in the koala world for his excellent explanations. You tune into a recording of his most recent explanation about a game called Koala Ball.
In the game, there are types of balls, indexed from to , and distinct baskets in a line, similarly indexed. The koalas are given balls of type . The koalas are then given five minutes to huddle up and determine how many ways there are to split all the balls into the baskets. However, the game isn't as simple as that! They are also given rules, where any valid arrangement must satisfy all of them. The rules are given in the form , , , and . For each rule, the koalas are not allowed to have more than balls of type combined among all the baskets from to inclusive. Koalas are simple-minded creatures, so there is at most one rule applied to any basket. Note that baskets may be left empty in a valid arrangement.
Wanting to show ThingExplainer his skills, Daniel the Koala asks you to help him find the number of ways to split all the balls among the baskets. The answer may be very large, and as Koalas are not very proficient mathematicians, he asks you to give him the answer modulo .
Note: Two arrangements are considered different if any basket contains a different amount of a certain type of ball.
This problem was originally part of the An Animal Contest 2 problemset.
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
The first line of input contains space-separated integers , , and .
The next line contains integers , with the integer representing the number of balls of type .
Each of the next lines contain , , , and , representing a rule.
Output a single integer, the number of ways, modulo .
Sample Input 1
2 3 1 1 1 1 1 1 0
Sample Output 1
Sample Input 2
2 4 3 2 2 3 4 2 1 1 1 2 1 2 2 1 1
Sample Output 2