祝你一发抽到PUR∠( ᐛ 」∠)＿（图片来自Twitter@bemanistyle）

优酱最近痴迷于KONMAI某街机音(抽)乐(卡)游戏Music Voltex Heavenly Haven，这个游戏除了可以给人带来爽上天的1600%疾走感之外，最为吸引人的就是可以以60块钱5张的价格抽取现场印刷的真实的卡片。虽然优酱的游戏水平非常低，但这并没有影响她抽卡的热情，毕竟一次性往街机里投60个币同时享受别人看智障的眼神，也是非常有爽快感的。

但是单纯的抽卡并不能满足优酱，她决定建立一个递推模型来量化这种爽快感：给出一个整数表示优酱一共会进行道抽卡，给出一个整数表示每一道抽卡的爽快感会与过去道抽卡的爽快感相关，再给出一个长度的整数向量表示过去道抽卡对当前这一道的影响因子。

我们定义表示第轮抽卡的爽快感，则有：

* 当时，
* 当时，

我们的目标是求出最后一道抽卡的爽快感即的值，由于Music Voltex的爽上天特性，这个爽快感数值可能非常巨大，因此请将其对取模后输出。

单文件，多数据，请循环读取到文件末尾。
对于每组数据：
* 第一行为两个整数和，用空格分割，含义和范围范围请参见题目描述。
* 第二行为个整数，用空格分割，表示，含义和范围请参见题目描述。
我们保证数据中没有多余不可见字符。

对于每组数据，请输出一个整数，表示答案，独占一行。

10 3
1 2 3

4083