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.
Constraints
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
Input Specification
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 Specification
Output a single integer, the number of ways, modulo .
Sample Input 1
2 3 1
1 1
1 1 1 0
Sample Output 1
6
Sample Input 2
2 4 3
2 2
3 4 2 1
1 1 2 1
2 2 1 1
Sample Output 2
54
Comments