Cho dãy số xác định bởi công thức truy hồi tuyến tính:

• F(0) = f₀
• F(1) = f₁
• F(n) = a × F(n-1) + b × F(n-2) với n ≥ 2

Cho n, a, b, f₀, f₁ và M. Hãy tính F(n) mod M.

Với n lên đến 10^18, dùng luỹ thừa ma trận:

[F(n)  ]   =   [a  b] ^ (n-1)   × [F(1)]
[F(n-1)]       [1  0]             [F(0)]

Đầu vào

Một dòng duy nhất gồm các số nguyên n, a, b, f₀, f₁, M (0 ≤ n ≤ 10^18, 0 ≤ a, b, f₀, f₁ < M, 1 ≤ M ≤ 10^9+7).

Đầu ra

Một số nguyên duy nhất là F(n) mod M.

Ví dụ

Input:
10 1 1 0 1 1000000007

Output:
55

Giải thích

Với a=1, b=1, f₀=0, f₁=1, ta có dãy Fibonacci. F(10) = 55.