| Codeforces Round 1135 (Div. 2) |
|---|
| Finished |
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:
...
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.
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$$$.
For each query, output a single integer — the number of special partitions of $$$a$$$ for the query, modulo $$$10^9 + 7$$$.
25 2 31 2 3 2 13 02 15 -18 3 63 1 4 5 1 7 2 31 04 28 -22 15 -17 3
420310611
In the first test case there are $$$3$$$ queries:
| Name |
|---|


