题目描述
一个由自然数组成的数列按下式定义:
对于 i≤k:ai=bi。
对于 i>k:ai=∑j=1kcj×ai−j。
其中 b1…k 和 c1…k 是给定的自然数。
写一个程序,给定自然数 m≤n,计算 (∑i=mnai)modp。
输入格式
第一行一个自然数 k。
第二行 k 个自然数 b1,b2,…,bk。
第三行 k 个自然数 c1,c2,…,ck。
第四行三个自然数 m,n,p。
输出格式
一行一个正整数,表示 ∑i=mnaimodp 的值。
2
1 1
1 1
2 10 1000003
142
提示
对于 20% 的数据,n≤106。
对于另外 30% 的数据,k=1。
对于 100% 的数据,1≤k≤15,1≤m≤n≤1018,0≤bi,ci≤109,p≤108。