由于数据规模可能较大，因此采用如下方式生成数据。

每个数据包含六个数：n,Sa,Sb,Sc,Sd,A1,Modn,S_a,S_b,S_c,S_d,A_1,\mathrm{Mod}n,S​a​​,S​b​​,S​c​​,S​d​​,A​1​​,Mod，意为共有 $n$ 个音符，第一个音符为 A1A_1A​1​​。
生成规则如下： 定义生成函数 F(x)=Sax3+Sbx2+Scx+SdF(x) = S_ax^3 + S_bx^2 + S_cx + S_dF(x)=S​a​​x​3​​+S​b​​x​2​​+S​c​​x+S​d​​；
那么给出递推公式 Ai=F(Ai−1)+F(Ai−2)A_i = F(A_{i-1}) + F(A_{i-2})A​i​​=F(A​i−1​​)+F(A​i−2​​)，此处规定 A0=0A_0 = 0A​0​​=0。
由于中间过程的数可能会特别大，所以要求每一步与 $A$ 中的每个数都对一个给定的数 $\mathrm{M}\mathrm{o}\mathrm{d}$ 取模。

输出一行，包含一个正整数 $\mathrm{A}\mathrm{n}\mathrm{s}$。

样例输入

3 815 6901 3839 178 199 10007

样例输出

1334

样例解释

生成的数列为 $19945681901$，此时将 $4568$ 修改为 $3234$，$1901$ 也修改为 $3234$ 即可，代价为 $1334$。

对于 $100\%$ 的数据，n≤5000000, Sa,Sb,Sc,Sd,A1≤10000, Mod≤1000000007n \leq 5000000,\ S_a,S_b,S_c,S_d,A_1 \leq 10000,\ \mathrm{Mod} \leq 1000000007n≤5000000, S​a​​,S​b​​,S​c​​,S​d​​,A​1​​≤10000, Mod≤1000000007。