선형 점화수열의 항

각 질의에서 음이 아닌 정수 $N$과 항의 번호가 $0$부터 시작하는 수열 $f_0, f_1, \cdots$가 주어진다. 수열은 질의의 종류를 나타내는 정수 $P$에 따라 다음과 같이 주어진다.

• $P=1$: 점화식의 차수 $K$, 계수 $c_0, c_1, \cdots, c_{K-1}$과 초기항 $f_0, f_1, \cdots, f_{K-1}$이 주어진다. $K>0$이면 이후의 항은 다음 점화식을 따른다.
  \[ f_i=\sum_{j=1}^{K}c_{j-1}f_{i-j}\qquad(i\ge K). \]
  $K=0$이면 모든 항은 $0$이다.
• $P=2$: 주어지는 항의 개수 $L$과 처음 $L$개 항 $f_0, f_1, \cdots, f_{L-1}$이 주어진다. 수열은 차수가 $\lfloor L/2\rfloor$ 이하인 선형 점화식을 따른다.

각 질의의 $f_N$을 구해 보자. 모든 계산은 소수 $10^9+7$로 나눈 나머지로 한다.

첫 번째 줄에 질의의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le50)$

각 질의는 종류에 따라 다음과 같이 주어진다.

• $P=1$: 첫 번째 줄에 정수 $1$, $K$, $N$이 공백으로 구분되어 주어진다. $(0\le K\le120; 0\le N\le2^{63}-1)$
  
  두 번째 줄에 정수 $c_0, c_1, \cdots, c_{K-1}$이 공백으로 구분되어 주어진다. $(0\le c_i<10^9+7)$
  
  세 번째 줄에 정수 $f_0, f_1, \cdots, f_{K-1}$이 공백으로 구분되어 주어진다. $(0\le f_i<10^9+7)$
• $P=2$: 첫 번째 줄에 정수 $2$, $L$, $N$이 공백으로 구분되어 주어진다. $(0\le L\le250; 0\le N\le2^{63}-1)$
  
  두 번째 줄에 정수 $f_0, f_1, \cdots, f_{L-1}$이 공백으로 구분되어 주어진다. $(0\le f_i<10^9+7)$

길이가 $0$인 배열도 빈 줄을 차지한다. 입력 마지막에 연속한 빈 줄은 생략해도 된다.

모든 질의에서 주어지는 $K$와 $L$의 합은 $500$ 이하이다.

각 질의에 대해 $f_N$을 $10^9+7$로 나눈 나머지를 입력 순서대로 한 줄에 하나씩 출력한다.