Problem Description

Author: eedwang

我總是想讓我跟 百鬼あやめ 的互動充滿樂趣和驚喜。 為了博得大小姐的歡心，我準備了一個小謎題。

某天放學後，我和大小姐在走廊上閒晃。大小姐忽然說她想玩一個「連鎖加總」的遊戲，規則聽起來很簡單，但她提醒我一句話：

「如果你算錯了，就等著被我吐槽到抬不起頭來。」

遊戲一開始，大小姐先丟給我三個整數 n、m、k。 接著她又拿出一張紙條，上面寫了 n 個整數，依序代表數列 a 的前 n 項 a[1], a[2], … , a[n]。

然後大小姐再給我 m 個整數 p1, p2, … , pm（保證每個 pi 都在 1 到 n 之間）。 她說這些數字代表她「想加哪些位置」，而且她的規則很任性：索引可以重複，重複就代表那一項要被加好幾次。

大小姐定下的連鎖規則如下：

• 第 n+1 項 a[n+1] 由前 n 項中的指定位置相加而成 a[n+1] = a[p1] + a[p2] + … + a[pm]

• 從那之後，大小姐每走一步就把「窗口」往後平移一格，依然只加同樣的位置 對所有 t > n a[t] = a[t-n-1+p1] + a[t-n-1+p2] + … + a[t-n-1+pm]

大小姐最後瞇著眼問我：

「那你告訴我，第 k 項 a[k] 是多少？」

請你輸出 a[k] 的值，讓我能漂亮地回答大小姐，不要當場出糗。

Input Format

第一行輸入一個整數 T，代表測資筆數

接下來有 T 組測資，每組格式如下

1. 一行 n m k
2. 一行 n 個整數，表示 a[1] … a[n]
3. 一行 m 個整數，表示 p1 … pm

Output Format

對每組測資輸出一行，表示該組的 a[k] mod 1e9+7。

2
3 2 7
1 2 3
1 3
4 3 10
2 1 3 4
1 2 4

13
76

Hint

1 <= T <= 20

1 <= n <= 30

1 <= m <= 30

1 <= k <= 40

1 <= pi <= n，且 pi 可重複

0 <= a[i] <= 10^9

對於第二筆範例測資:</code>

• a5 = a1 + a2 + a4 = 2 + 1 + 4 = 7

• a6 = a2 + a3 + a5 = 1 + 3 + 7 = 11

• a7 = a3 + a4 + a6 = 3 + 4 + 11 = 18

• a8 = a4 + a5 + a7 = 4 + 7 + 18 = 29

• a9 = a5 + a6 + a8 = 7 + 11 + 29 = 47

• a10 = a6 + a7 + a9 = 11 + 18 + 47 = 76