generator 1

题号：NC51469
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given four positive integers $x_0, x_1, a, b$ . And you know $x_i = a \cdot x_{i-1} + b \cdot x_{i-2}$ for all $i \ge 2$ .

Given two positive integers n, and MOD, please calculate $x_n$ modulo MOD.

Does the problem look simple? Surprise! The value of n may have many many digits!

输入描述:

The input contains two lines.
The first line contains four integers  ().
The second line contains two integers n, MOD (, n has no leading zero).

输出描述:

Print one integer representing the answer.

示例1

输入

复制

1 1 1 1
10 1000000001

输出

复制

说明

The resulting sequence x is Fibonacci sequence. The 11-th item is 89.

示例2

输入

复制

1315 521 20185 5452831
9999999999999999999999999999999999999 1000000007

输出

复制

914730061