DP-TÍNH TOÁN

ĐỀ BÀI: TRUY VẤN DÃY SỐ

Cho dãy số \((x_n, y_n)\) được xác định bởi công thức truy hồi:

• \(x_1 = a, y_1 = b\)
• \(x_{n+1} = c \times x_n + d \times y_n\)
• \(y_{n+1} = e \times x_n + f \times y_n\)

với \(2 \le a, b, c, d, e, f \le 20\).

Yêu cầu: Cho số nguyên dương \(n \le 10^6\) và \(k \in \{0, 1\}\). Hãy tính:

• Nếu \(k = 0\): In ra \(x_n \pmod{10^9 + 7}\).
• Nếu \(k = 1\): In ra \(y_n \pmod{10^9 + 7}\).

Dữ liệu vào:

• Dòng 1: Chứa 6 số nguyên \(a, b, c, d, e, f\).
• Dòng 2: Chứa 2 số nguyên \(n, k\).

Kết quả ra:

• Một số nguyên duy nhất là kết quả bài toán sau khi chia lấy dư cho \((10^9 + 7)\).

Ví dụ:

Input

3 4 2 3 4 5
2 0

Output

18

Giải thích: \(x_1 = 3, y_1 = 4\). Với \(n = 2, k = 0\), ta có: \(x_2 = 2 \times 3 + 3 \times 4 = 18 \pmod{10^9 + 7}\).