Cho hệ truy hồi hai biến: \(f(n) = a \times g(n-1) + b \times f(n-1)\) \(g(n) = c \times f(n-1) + d \times g(n-1)\) với \(f(0), g(0)\) cho trước. Tính \(f(n), g(n)\) modulo \(10^9+7\).

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

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

Định dạng đầu ra

• Hai số nguyên \(f(n)\) và \(g(n)\).

Ví dụ

Input:

5 1 1 1 0 1 0

Output:

8 5

Ràng buộc

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