题目描述
广义的斐波那契数列是指形如 $a_n=pa_{n-1}+qa_{n-2}$ 的数列。今给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和 $a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n$ 除以 $m$ 的余数。
输入
输入包含一行6个整数。依次是 $p,q,a_1,a_2,n,m$，其中在 $p,q,a_1,a_2$ 整数范围内，$n$ 和 $m$ 在长整数范围内。
输出
输出包含一行一个整数，即 $a_n$ 除以 $m$ 的余数。
样例输入输出
提示
对于 $100\%$ 的数据，$1\leq n\leq 10000000000$。