Sales Prediction

A department store wants to predict how many units of each item it will sell each month. Keeping a large inventory is costly, and running out of stock is also a problem. As the store's sales consultant, I built a model that predicts the monthly sales S from the sales of the previous R months.

$S(n) = a_1 S(n-1) + a_2 S(n-2) + \cdots + a_R S(n-R)$

Here $S(n)$ is the predicted sales for month n when n > R, and $S(1)$ to $S(R)$ are seed values.

The manager wants a list of every Kth month's sales and the sum of the first N values in that list. For example, he wants the December sales (K=12, with January as month 1) summed over the next 10 years (N=10, K=12), or the end-of-quarter sales (K=3) summed over the next 2 years (N=8, K=3).

Write a program that computes these sums.

The first line contains the number of test cases T. Each test case consists of three lines.

The first line of each test case contains N, R, K.

The second line of each test case contains R integers $S(1), S(2), \ldots, S(R)$.

The third line of each test case contains R integers $a_1, a_2, \ldots, a_R$, the coefficients of the prediction model.

For each test case, output the requested sum modulo 1,000,000,007.

• $1 \le T \le 40$
• $1 \le N \le 10^9$
• $1 \le R \le 8$
• $1 \le K \le 8$
• All other input values are at least 0 and less than 1,000,000,007.

In the first test case, F(1) = 1 and the relation is F(n) = 2F(n-1). Sequence G contains every term of F because K is 1. The answer is therefore the sum of the first 4 terms of F.

In the second test case, sequence F is the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34. Sequence G consists of 2, 8, 34, which sum to 44.