Luego de una larga espera por el nacional, Luis se encontraba aburrido de tanto estudiar, por lo que decidió jugar su juego favorito Runtime Bandicoot. El juego consiste en una serie de niveles donde el nivel ~i~ tiene como puntuación ~P(i)~. Los primeros ~x~ niveles son el tutorial y tienen una puntuación fija. Hace no mucho, Runtime Bandicoot actualizó su sistema de puntuación por uno llamado "Puntuación por Memoria", donde la puntuación se calcula a partir de la suma de las puntuaciones de los x niveles anteriores, cada una multiplicada por un parámetro a_i o formalmente:

$$\displaystyle P(k)=\sum _{i=1}^x a_i\cdot P(k-i)$$

Luis, ante el nuevo cambio, investigó esa curiosa forma de calcular el puntaje, llegando al punto donde descubrió el valor de los parámetros. Como es un fanático del juego, quiere saber cuál va a ser la puntuación en un determinado nivel.

Tu tarea consiste en ayudar a Luis con su cálculo, dados los parámetros que este conoce y la puntuación de los x niveles iniciales. Debido a que a Luis no le gustan los números muy grandes, imprime el resultado módulo ~10^9+7~.

Entrada

• La primera línea contiene dos enteros ~x~ ~(2 \leq x \leq 100)~ y ~K~ ~(x < K \leq 10^{18})~, la cantidad de niveles de tutorial y el nivel del que se quiere conocer la puntuación.
• La segunda línea contiene ~x~ enteros ~a_1, a_2,..., a_x~: los parámetros.
• La tercera línea contiene ~x~ enteros ~P(1), P(2),..., P(x)~: la puntuación de los primeros ~x~ niveles.

Salida

Un único entero que representa ~P(K)~ módulo ~10^9+7~.

Ejemplo #1 de Entrada

3 4
9 0 5
79 100 64

Ejemplo #1 de Salida

971

Ejemplo #2 de Entrada

2 4
1 9
83 12

Ejemplo #2 de Salida

867