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