Dãy Fibonacci: ~F[i] = 1 \cdot F[i - 1] + 1 \cdot F[i - 2]~ là một dãy truy hồi tuyến tính (linear recurrence). Xét một công thức tổng quát hơn và cũng khó hơn: Chúng ta sẽ cho thêm biến ~i~ vào.

Cụ thể hơn, xét một dãy vô hạn đuợc định nghĩa bởi ~n~ phần tử đầu tiên: ~a_{0}, a_{1}, ..., a_{n - 1}~ và các hệ số ~c_{1}, c_{2}, ..., c_{n}, p, q, r~. Với mọi ~i \geq n~:

~a_{i} = (c_{1} \cdot a_{i - 1} + c_{2} \cdot a_{i - 2} + ... + c_{n} \cdot a_{i - n}) + p + i \cdot q + i^2 \cdot r~

Hãy tính ~a_{k} ~ ~mod~ ~10^9 + 7~ ~(1000000007)~.

Input

Dòng đầu chứa hai số nguyên duơng ~n~ ~(1 \leq n \leq 10)~ và ~k~ ~(1 \leq k \leq 10^{18})~.

Dòng thứ hai chứa ~n~ số nguyên ~a_{0}, a_{1}, ..., a_{n - 1}~ ~(0 \leq a_{i} < 10^9 + 7)~.

Dòng thứ ba chứa ~n~ số nguyên ~c_{1}, c_{2}, ..., c_{n}~ ~(0 \leq c_{i} < 10^9 + 7)~.

Dòng thứ tư chứa ~3~ số nguyên ~p, q, r~ ~(0 \leq p, q, r < 10^9 + 7)~.

Output

In ra một dòng chứa ~a_{k}~ ~mod~ ~10^9 + 7~.

Sample Input 1

2 2
0 30
2 1
2 1 1

Sample Output 1

68

Sample Input 2

1 3
5
1
2 3 4

Sample Output 2

85

Giải thích các test đề

Ở ví dụ thứ nhất, ta có ~a_{0} = 0, a_{1} = 30, a_{i} = (a_{i - 1} \cdot 2 + a_{i - 2}) + 2 + i + i^2~

Do đó ~a_{2} = 2 \cdot a_{1} + a_{0} + 2 + 2 + 2^2 = 2 \cdot 30 + 0 + 2 + 2 + 4 = 68~.

Ở ví dụ thứ hai, năm số đầu tiên của dãy là ~(5, 14, 38, 85, 163)~. Vì ~k = 3~, chúng ta in ra ~a_{3} = 85~.