You have a recursive formula such as

It is easy to calculate if n is smaller than 1000. But when n comes to 10⁹, it may be hard to calculate the answer unless you can really computing!

I think you have this ability, so just do it!

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