You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

Format

Input

输入包含一行六个整数，$p,q,a_1,a_2,n,m$

Output

输出包含一行一个整数表示答案。

Samples

1 1 1 1 10 7

6

Limitation

对于 $100\%$ 的数据，$p,q,a_1,a_2 \in [0,2^{31}-1]$，$1\le n,m \le 2^{31}-1$。