题目 2202:
I can do it!(I)
时间限制: 4s
内存限制: 576MB 提交: 30 解决: 1
题目描述
You have a recursive formula such as
It is easy to calculate if n is smaller than 1000. But when n comes to 109, it may be hard to calculate the answer unless you can really computing!
I think you have this ability, so just do it!
But the answer may be to large to calculate, so you can only calculate the answer mod 1e9+7.输入格式
The input consists of many test cases, but no more than 5 cases.
Each case will have three lines.
There are two integers n, k in the first line. k<n≤1010, 1≤k≤100
The second line has k numbers, and the i-th number is ai. |ai|≤109
The third line has k numbers too, and the i-th number is Fi. |Fi|≤109
输出格式
For each test case, you should output a number describe the answer.
样例输入
83167 5 270044411 64763 389502790 165642235 3775223 136407894 699370879 998658047 184722627 -678977043 79679 3 427397619 485492671 476934139 -360282785 178718524 606397373
样例输出
299168603 559548063