Counting Painting Purchase Schemes

You are a master of counting. One day, your friend Luka, a talented painter, challenges you with the following problem.

Luka has an infinite supply of paintings in two types: colored paintings and black-and-white paintings. He dislikes selling black-and-white paintings and therefore requires that at least c customers purchase a colored painting.

There are n customers (numbered from 1 to n). The i^th customer will buy at most a_i colored paintings and at most b_i black-and-white paintings, but they must purchase at least one painting in total. However, each customer can only choose one type of painting—they either buy only colored paintings or only black-and-white paintings.

Originally, each customer has parameters a_i and b_i. Over q operations, the parameters for a specific customer are updated. After each update, your task is to determine how many purchasing schemes satisfy the following conditions:

• Each customer makes a purchase (choosing one type).
• If the customer buys colored paintings, they can buy between 1 and a_i paintings.
• If the customer buys black-and-white paintings, they can buy between 1 and b_i paintings.
• At least c customers buy colored paintings.

For each scheme, if customer i chooses colored paintings, there are a_i possibilities, and if they choose black-and-white paintings, there are b_i possibilities. Hence, a scheme for a given subset S of customers who choose colored paintings has a total of

$$\prod_{i\in S}a_i\ \cdot\ \prod_{j\notin S}b_j.$$

Your answer for each query should be the total number of valid schemes modulo $10^4+7$ (i.e. modulo 10007).

Hint: One way to think of the problem is to construct the generating function

$$P(x)=\prod_{i=1}^{n}(b_i+a_i x),$$

and then summing the coefficients of $x^k$ for all $k\ge c$.

inputFormat

The input begins with three integers n, c, and q: the number of customers, the minimum required number of customers buying colored paintings, and the number of updates.

This is followed by n lines, each containing two integers a_i and b_i, representing the initial values for customer i.

Then, q lines follow. Each line contains three integers: i, new_a, and new_b, meaning that customer i's parameters are updated to a_i = new_a and b_i = new_b.

outputFormat

For each update, print a single integer on a new line: the number of valid schemes modulo $10007$.

sample

3 2 3
1 2
3 4
5 6
1 2 3
3 6 7
2 1 1

151
180
56

</p>