当前没有测试数据。

1.数列求解

题目描述

广义的斐波那契数列是指形如$a_{n} = p a_{n-1} + q a_{n-2}$的数列。今给定数列的两系数$p$和$q$，以及数列的最前两项$a_{1}$和$a_{2}$，另给出两个整数$n$和$m$，试求数列的第$n$项$a_{n}$除以$m$的余数。

输入格式

输入包含一行，共六个整数，依次是$p$，$q$，$a_{1}$，$a_{2}$，$n$，$m$。其中$p$，$q$，$a_{1}$，$a_{2}$在整数范围内，$n$，$m$在长整数范围内。

输出格式

输出包含一行一个整数，即$a_{n}$除以$m$的余数。

数据范围与提示

对于$100\%$的数据，$1 < n < 1000000000$。

样例

1 1 1 1 10 7

6