U494839 矩阵快速幂之死

~~关于SPFA，他死了~~ 关于矩阵快速幂，他死了

有一个数列： $F_1=a$ $F_2=b$ $F_n=c*F_{n-1}+d*F_{n-2}$ 请你求出 $F_n \bmod P$ 的值。 为了防止你是蒙对的，有多组询问。

第一行五个正整数 $a,b,c,d,P$。 第二行一个正整数 $q$ 代表询问次数。 接下来输入 $q$ 行，每行一个正整数 $n$，表示要求的 $F_n \bmod P$ 的值。

输出 $q$ 行，每行一个正整数 $x$，表示 $F_n \bmod P$ 的值

|测试点编号|$q \le$|$n \le$|$P \le$| | :----------: | :----------: | :----------: | :----------: | |$1,2$|$10$|$10^6$|$10007$| |$3,4$|$10^5$|$10^6$|$10007$| |$5,6$|$10^5$|$10^{18}$|$2$| |$7,8$|$10^5$|$10^{18}$|$10007$| |$9,10$|$2 \times 10^6$|$10^{18}$|$10007$| 对于所有测试点，$1 \le q \le 2 \times 10^6$，$1 \le n \le 10^{18}$，$1 \le a,b,c,d \le 10^3$，$2 \le P \le 10007$。 **建议使用较快的读入方式。**