Cho dãy (ai) các số tự nhiên được định như sau:

  a_i = b_i (với  i <= k)
  a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k (với  i > k)

với b_i và c_i là các số tự nhiên cho trước (1<=j<=k). Hãy tính a_n modulo 10⁹, với n cho trước.

Dữ liệu

Dòng đầu tiên chứa số c là số lượng test (1<=c<=1000). Mỗi test chứa 4 dòng:

Dòng 1: chứa số k, là số phần tử của dãy c và b (1 <= k <= 10)
Dòng 2: chứa các số b₁,...,b_k  với 0 <= b_j <= 10⁹, mỗi số cách nhau một dấu cách.
Dòng 3:chứa các số c₁,...,c_k  với 0 <= c_j <= 10⁹, mỗi số cách nhau một dấu cách.
Dòng 4: chứa số n (1 <= n <= 10⁹)

Kết quả 

Gồm c dòng, mỗi dòng là kết quả của một test, ghi giá trị: a_n modulo 10⁹