Nhân ma trận nhị phân tính số Fibonacci thứ N lớn

Mục tiêu kiến thức

• Biểu diễn hệ thức truy hồi tuyến tính dưới dạng nhân ma trận: F_n+1
  F_n = 1 & 1
  1 & 0 F_n
  F_n-1 .
• Cài đặt phép nhân ma trận 2 × 2 và lũy thừa ma trận nhị phân trong thời gian O(K³ log N).
• Xử lý giá trị N cực lớn lên tới 10¹⁸ theo modulo 10⁹+7.

Mô tả bài toán

Dãy số Fibonacci được định nghĩa:

• F₀ = 0
• F₁ = 1
• F_n = F_n-1 + F_n-2 với mọi n ≥ 2.

Cho số nguyên N (0 ≤ N ≤ 10¹⁸). Hãy tìm giá trị F_N mod 10⁹+7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ T ≤ 10⁴.
• 0 ≤ N ≤ 10¹⁸.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.