广义的斐波那契数列是指形如 $a_n=p{a}_{n-1}+q{a}_{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$ 在长整数范围内。

对于 $100$ 的数据，$1\le n\le 10000000000$。