Description

定义$f_i=A \times f_{i-1}+B \times f_{i-2} + C \times i^2 + D \times i + E$，给出$f_0,\ f_1,\ A,\ B,\ C,\ D,\ E,\ n,\ p$ 求$f_n \bmod p$。

Input Format

对于每个测试用例，一行九个正整数，分别代表$f_0,\ f_1,\ A,\ B,\ C,\ D,\ E,\ n,\ p$。

题目的数据范围：$1 \le f_0,\ f_1,\ A,\ B,\ C,\ D,\ E,\ p\le 10^6,\ 1 \le n \le 10^{12}$。

Output Format

对于每个测试用例，输出一个整数表示结果。

0 1 1 1 1 1 1 3 998244353

22

Source

Online Judge http://127.0.0.1