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 \times F(n-1) + b \times F(n-2)\) với \(n \ge 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 \le n \le 10^18, 0 \le a, b, f₀, f₁ < M, 1 \le M \le 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.

Ràng buộc & Subtasks