Problem Description
GS is suffering from tons of boring math assignment. He find it make him tired and impatient so he asks you to finish his assignment in hope that he could hang out in many places of interest and enjoy his life.
In this assignment, you’re asked to solve the following problem:
Given a recurrent function
and boundary values
You should solve for f[n].
What a easy problems! Wait for a moment, you see a few lines in the last paragraph. It reads as follows: To make the problem a little hard, you are now informed that, at some special values of n (there are q such values, namely n1, n2, . . . , nq), the recurrent formula changes into something else, which means for the kth such value nk, the recurrent formula changes into
Still an easy problem, isn’t it?
Since f[n] may be quite large, you just need to output f[n] module 109 + 7.
Input
There are several test cases.
For each test case, the first line contains three integers n (m < n ≤ 109), m (1 ≤ m ≤ 100), q (0 ≤ q ≤ 100). The second line contains m integers, namely f[1], f[2], . . . , f[m].
The following line contains several integers, first comes t (t ≤ 100), then t integers namely c[1], c[2], . . . , c[t].
The following q lines describe q special cases of the recurrent formula, each containing several integers, namely nk, tk (tk ≤ 100, tk < nk), ck[1], ck[2], . . . , ck[tk], as mentioned earlier. It is satisfied that ni != nj if i != j.
All integers are non-negative. Unless specified, all integers are not greater than 109.
Input is terminated by EOF.
You might assume that all given data is correct.
Output
For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is the desired answer.
Sample Input
7 5 0
1 1 2 3 5
2 1 1
10 5 1
1 1 2 3 5
2 1 1
10 2 1 2
Sample Output
Case 1: 13
Case 2: 76
用矩阵乘法没错，优化只在于矩阵乘法的顺序。先用长度为100的单位向量乘以100*100的矩阵，计算量就降下来了。从10^8*log(n)降到了10^6*log(n)。
设递推的单位矩阵为M，缓存M^2,M^4,M^8......，设各个阶段的单位向量为V[i]，从V[0]递推到V[1]一般的计算方法是这样：
V[0] * M^k，k为递推的项数，将k做2进制分解。
V[1] = V[0] * (M * M^2 *M^4....)
改变一下矩阵连乘的顺序，复杂度由100^3 * log(k)变为了100^2 * log(k)，这样推100次，总的计算量大概100^3*log(k)。
初始化计算M^2,M^4...计算量也是100^3*log(k)，但这部分可以缓存起来，因此总的计算量从10^8*log(n)降为了10^6*log(n)。