판매량 예측

한 백화점은 품목별로 매달 몇 개가 팔릴지 예측하려고 합니다. 재고를 많이 쌓아 두면 비용이 들고, 재고가 바닥나는 것도 문제입니다. 저는 이 백화점의 판매 컨설턴트로서, 직전 R개월의 판매량으로 매달의 판매량 S를 예측하는 모델을 만들었습니다.

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

여기서 $S(n)$은 n > R일 때 n번째 달의 예측 판매량이고, $S(1)$부터 $S(R)$까지는 초기값입니다.

관리자는 K개월마다 하나씩 뽑은 판매량 목록을 만들고, 그 목록의 처음 N개 값의 합을 원합니다. 예를 들어 12월 판매량(K=12, 1월을 1번째 달로 셈)을 앞으로 10년 동안 합산하거나(N=10, K=12), 분기 말 달의 판매량(K=3)을 앞으로 2년 동안 합산하는 식입니다(N=8, K=3).

이 합을 계산하는 프로그램을 작성해 주세요.

첫 줄에 테스트 케이스의 수 T가 주어집니다. 각 테스트 케이스는 세 줄로 이루어집니다.

각 테스트 케이스의 첫 줄에는 N, R, K가 주어집니다.

둘째 줄에는 $S(1), S(2), \ldots, S(R)$을 나타내는 정수 R개가 주어집니다.

셋째 줄에는 예측 모델의 계수 $a_1, a_2, \ldots, a_R$을 나타내는 정수 R개가 주어집니다.

각 테스트 케이스마다 요청된 합을 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$
• 그 밖의 입력값은 모두 0 이상 1,000,000,007 미만입니다.

첫 번째 테스트 케이스에서 F(1) = 1이고 관계식은 F(n) = 2F(n-1)입니다. K가 1이므로 수열 G는 F의 모든 항으로 이루어집니다. 따라서 답은 F의 처음 4개 항의 합입니다.

두 번째 테스트 케이스에서 수열 F는 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34입니다. 수열 G는 2, 8, 34로 이루어지며, 그 합은 44입니다.