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 ~T~ types of balls, indexed from ~1~ to ~T~, and ~B~ distinct baskets in a line, similarly indexed. The koalas are given ~t_i~ balls of type ~i~. 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 ~R~ rules, where any valid arrangement must satisfy all of them. The rules are given in the form ~l_i~, ~r_i~, ~a_i~, and ~b_i~. For each rule, the koalas are not allowed to have more than ~b_i~ balls of type ~a_i~ combined among all the baskets from ~l_i~ to ~r_i~ 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 ~10^9+7~.

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

~1 \le T, B \le 500~

~0 \le t_i \le 500~

~0 \le R \le B~

~1 \le l_i \le r_i \le B~

~1 \le a_i \le T~

~0 \le b_i \le t_{a_i}~

Subtask 1 [10%]

~1 \le T,B \le 5~

~0 \le t_i \le 2~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains ~3~ space-separated integers ~T~, ~B~, and ~R~.

The next line contains ~T~ integers ~t_i~, with the ~i^{th}~ integer representing the number of balls of type ~i~.

Each of the next ~R~ lines contain ~l_i~, ~r_i~, ~a_i~, and ~b_i~, representing a rule.

Output Specification

Output a single integer, the number of ways, modulo ~10^9+7~.

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