Description

XMU的神经病XXX由于美赛成绩不理想，最近在研究建模题，今天他看到了这样一道建模题。题目如下：

现在已经知道最近3个月的服务器访问量（以月为单位），请你预测接下来若干月份的服务器访问量。

很多人见到这个第一眼就想用灰度预测、回归预测或者是时间序列分析预测，比较牛逼的用ARIMA模型。

而XXX太菜了，这些都不会，于是他想到一个最简单的方法，FF(n)=A*F(n-1)+B*F(n-2)+C*F(n-3)，但是这个方法太暴力了不可取，于是他又想到，未来人们使用网络肯定越来越频繁，所以可以加上时间影响因素，而他打算采用最简单的二次函数来模拟时间影响因素T(n)=D*n^2+E*n+F，对于第n个月的访问量，F(n)=FF(n)+T(n)，这样就是最终预测值。

模型建完了，接下来就只要调参就可以了（雾），但是他比较懒，只愿意瞎编系数，所以请你帮忙他计算，当这些系数给定的时候，第n个月的服务器访问量是多少。

Format

Input

多组测试数据
每组测试数据第一行为一个整数N(1<=N<=10^18),表示需要你计算的第N个月的服务器访问量，第二行六个整数，分别为A、B、C、D、E、F，如题所述(0<=A,B,C,D,E,F<=10^9)，第三行为三个整数F1、F2、F3，分别为第1、2、3个月的服务器访问量。(0<=F1,F2,F3<=10^18)

Output

对于每组测试数据输出一行，为第N个月的预测的访问量，答案对1000000007取模。

Sample 1

Input

4
1 2 3 4 5 6
7 8 9

Output

136

Limitation

1s, 128MB for each test case.

Hint

F(4)=3*F(1) + 2*F(2) + 1*F(3) + 4*4^2 + 5*4 + 6 = 136
F(5)=3*F(2) + 2*F(3) + 1*F(4) + 4*5^2 + 5*5 + 6

Source

Coolxxx