2633: 例6.1-1 普通递推数列

给出一个k阶齐次递推数列{fi}的通项公式f_i=a₁f_i-1+a₂f_i-2+…+a_kf_i-k(i≥k)，以及初始值f₀,f₁,…,f_k-1，求f_n。

第1行2个整数：n(0≤n≤1000000)和k(1≤k≤100)。

第2行k个整数：a₁,a₂,…,a_k(0≤a_i≤10000,1≤i≤k)。

第3行k个整数：f₀,f₁,…,f_k-1(0≤f_i＜10000,0≤i＜k)。

一行一个整数p，是f_n除以10000的余数。

10 2
1 1
1 1

89