题目描述

给出一个$\red{k}$阶齐次递推数列$\red{\{f_i\}}$的通项公式$\red{f_i=a_1f_{i-1}+a_2f_{i-2}+...+a_kf_{i-k}(i≥k),}$以及初始值$\red{f_0,f_1,...f_{k-1}}$求$\red{f_n}$。

输入格式

第$\red{1}$行$\red{2}$个整数:$\red{n(0≤}$$\red{n≤}$$\red{1 000 000)}$和$\red{k(1≤}$$\red{k≤}$$\red{100)}$。 第$\red{2}$行$\red{k}$个整数:$\red{a_1 ,a_2,...,a_k(0≤}$$\red{a_i≤}$$\red{10000,1≤}$$\red{i≤}$$\red{k)}$。 第$\red{3}$行$\red{k}$个整数:$\red{f_0,f_1,...,f_{k-1}(0≤}$$\red{f_i}$$\red{<10000,0≤}$$\red{i<k)}$。

输出格式

一行一个整数$\red{p,}$是$\red{f_n}$除以$\red{10000}$的余数。

样例

输入样例

10 2
1 1
1 1

输出样例

89