Cho truy hồi \(f(n) = a \times f(n-1) + b \times f(n-2)\) với \(f(0), f(1)\) cho trước. Tính \(f(n)\).

Định dạng đầu vào

• Một dòng chứa \(n, a, b, f0, f1\) (\(0 \le n \le 10^{18}\), \(1 \le a,b \le 10^9\)).

Định dạng đầu ra

• Một số nguyên modulo \(10^9+7\).

Ví dụ

Input:

5 1 1 0 1

Output:

5

Ràng buộc

• 100% số điểm: \(n \le 10^{18}\).