Tính số Fibonacci nhưng với truy hồi mở rộng: \(F(n) = x \times F(n-1) + y \times F(n-2) + z\) với \(z\) là hằng số. \(F(0)=0, F(1)=1\).

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

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

Định dạng đầu ra

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

Ví dụ

Input:

5 1 1 0

Output:

5

Ràng buộc

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