402347: GYM100735 B Retrospective Sequence

Retrospective sequence is a recursive sequence that is defined through itself. For example Fibonacci specifies the rate at which a population of rabbits reproduces and it can be generalized to a retrospective sequence. In this problem you will have to find the n-th Retrospective Sequence modulo MOD = 1000000009. The first (1 ≤ N ≤ 20) elements of the sequence are specified. The remaining elements of the sequence depend on some of the previous N elements. Formally, the sequence can be written as F_m = F_m - k1 + F_m - k2 + ... + F_m - ki + ... + F_{m - kC - 1} + F_m - kC. Here, C is the number of previous elements the m-th element depends on, 1 ≤ k_i ≤ N.

The first line of each test case contains 3 numbers, the number (1 ≤ N ≤ 20) of elements of the retrospective sequence that are specified, the index (1 ≤ M ≤ 10¹⁸) of the sequence element that has to be found modulo MOD, the number (1 ≤ C ≤ N) of previous elements the i-th element of the sequence depends on.

The second line of each test case contains N integers specifying 0 ≤ F_i ≤ 10, (1 ≤ i ≤ N).

The third line of each test case contains C ≥ 1 integers specifying k₁, k₂, ..., k_C - 1, k_C (1 ≤ k_i ≤ N).

Output single integer R, where R is F_M modulo MOD.

2 2 2
1 1
1 2

1

2 7 2
1 1
1 2

13

3 100000000000 3
0 1 2
1 2 3

48407255