Compute the n-th Term of a k-Order Homogeneous Linear Recurrence

Given a (k)-order homogeneous linear recurrence sequence ({a_i}) defined by the recurrence

[ a_n = \sum_{i=1}^{k} f_i \times a_{n-i} ]

for (n \ge k) with the initial terms (a_0, a_1, \dots, a_{k-1}) provided, your task is to compute the (n)-th term (a_n).

inputFormat

The input consists of three parts:

• The first line contains two integers \(k\) and \(n\), where \(k\) is the order of the recurrence, and \(n\) is the index of the term to compute.
• The second line contains \(k\) integers \(f_1, f_2, \dots, f_k\) which are the coefficients of the recurrence.
• The third line contains \(k\) integers \(a_0, a_1, \dots, a_{k-1}\) which are the initial terms of the sequence.

If \(n < k\), simply output the \(n\)-th initial value.

outputFormat

Output a single integer which is the value of \(a_n\) computed using the recurrence relation.

sample

2 5
1 1
0 1

5