HZNUOJ

B_M的忧虑

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:178     AC:43     Score:100.00

Description

        B_M学长喜欢减肥,为此他制定出了一个详细的减肥计划。因为这个计划过于详细,所以他甚至可以推算出在未来的某一天自己的体重。

        体重的计算规律如下:要计算出自己某一天的体重,需要通过在此之前n天的体重来计算

        设$w_x$为第$x$天的体重,那么$w_x=\sum_{i=1}^n (a_i $ $\times$ $w_{x-i})$ , 其中 $a_i$ 是给定的常数

        现在给出B_M前$n$天的体重,询问他第$x$天的体重,题目保证$x > n$

      

Input

输入数据的第一行是两个正整数 $n$ ($1 \le n \le 100$)$x$ ($1 \le x \le 10^{18}$),第二行有 $n$ 个非负整数,分别为 $w_n, w_{n-1}, ... w_2, w_1$。第三行有 $n$ 个非负整数,分别表示 $a_1, a_2, ..., a_{n-1}, a_{n}$($0 \le a_i, w_i \le 193$)

Output

输出一个整数,表示对第 $x$ 天的体重预测结果。结果需要对193取余,至于为什么我也不知道

Samples

input
2 3 5 9 3 3
output
42

Author

WEI, Wei