D. Reverse Partition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given positive integers $$$n$$$ and $$$m$$$.

A partition is an array $$$p$$$ of $$$m$$$ positive integers such that $$$p_1 + p_2 + \ldots + p_m = n.$$$

For any array $$$b$$$ of length $$$n$$$ and a partition $$$p$$$, define $$$f(b, p)$$$ as an array $$$c$$$ of length $$$m$$$ where:

  • $$$c_1$$$ is the sum of the first $$$p_1$$$ elements of $$$b$$$,
  • $$$c_2$$$ is the sum of the next $$$p_2$$$ elements of $$$b$$$,

    ...

  • $$$c_m$$$ is the sum of the last $$$p_m$$$ elements of $$$b$$$.

For an array $$$d$$$ of length $$$n$$$, let $$$e$$$ be the array obtained by reversing $$$d$$$. A partition $$$p$$$ is a special partition of $$$d$$$ if $$$f(d, p) = f(e, p)$$$.

You are given an array $$$a$$$ of length $$$n$$$. You must answer $$$q$$$ independent queries. For each query, you are given two integers $$$i$$$ and $$$v$$$. Set $$$a_i := a_i + v$$$, and then output the number of special partitions of $$$a$$$. Since the answer may be large, output it modulo $$$10^9 + 7$$$.

Note that the queries are independent, meaning that after each query, $$$a$$$ reverts to its original value.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \le m \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$) – the length of $$$a$$$, the length of the partition, and the number of queries respectively.

The second line of each test case contains $$$n$$$ integers – $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \le 10^9$$$).

The next $$$q$$$ lines of each test case contain two integers $$$i$$$ and $$$v$$$ ($$$1 \le i \le n, |v| \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each query, output a single integer — the number of special partitions of $$$a$$$ for the query, modulo $$$10^9 + 7$$$.

Example
Input
2
5 2 3
1 2 3 2 1
3 0
2 1
5 -1
8 3 6
3 1 4 5 1 7 2 3
1 0
4 2
8 -2
2 1
5 -1
7 3
Output
4
2
0
3
1
0
6
1
1
Note

In the first test case there are $$$3$$$ queries:

  • In the first query, the array is $$$a=[1,2,3,2,1]$$$. The special partitions are $$$[1,4],[2,3],[3,2]$$$, and $$$[4,1]$$$.
  • In the second query, the array is $$$a=[1,3,3,2,1]$$$. The special partitions are $$$[1,4]$$$, and $$$[4,1]$$$.
  • In the third query, the array is $$$a=[1,2,3,2,0]$$$. It can be shown that there are no special partitions.