Weather Forecast Prediction

A company’s weather forecasting system encodes the weather of a day as an integer between 0 and 4146 (inclusive). The forecast for a future day is computed using the weather observations from the previous n days. Specifically, if w_i denotes the weather condition on day i (with i > n), then the following recurrence is used:

\(w_i = (a_1 \times w_{i-1} + a_2 \times w_{i-2} + \cdots + a_n \times w_{i-n}) \mod 4147\)

Here, a₁, a₂, \dots, a_n are known constant coefficients. Given the weather conditions for the first n days, your task is to predict the weather condition on the m^th day.

inputFormat

The input consists of three lines:

• The first line contains two integers n and m (1 ≤ n ≤ m). Here, n is the number of initially given days and m is the day for which the weather prediction is required.
• The second line contains n integers: w₁, w₂, ..., w_n, each representing the weather condition of that day (0 ≤ w_i ≤ 4146).
• The third line contains n integers: a₁, a₂, ..., a_n, representing the coefficients used in the recurrence.

Note: For m ≤ n, simply output the m^th weather condition.

The recurrence is defined as follows for i > n:

\(w_i = (a_1 \times w_{i-1} + a_2 \times w_{i-2} + \cdots + a_n \times w_{i-n}) \mod 4147\)

outputFormat

Output a single integer, which is the predicted weather condition on the m^th day.

sample

3 5
1 2 3
1 1 1

11