Koala Ball

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

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.


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


Sample Input 2

2 4 3
2 2
3 4 2 1
1 1 2 1
2 2 1 1

Sample Output 2



There are no comments at the moment.