#411. MATRIXPOW - Lũy thừa ma trận

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho ma trận vuông A cấp m và một số nguyên dương n . Hãy tính B = A^n .

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương m n ;
  • m dòng sau, dòng thứ i chứa m số nguyên a_{i1}, a_{i2}, …, a_{im} . Hai số liên tiếp được ghi cách nhau một dấu cách.

Dữ liệu ra:

  • m dòng của ma trận B = A^n . Các phần tử của ma trận B được chia cho 10^9 + 7 lấy phần dư.

Ví dụ:

Dữ liệu vào:
2 2
1 2
3 4
Dữ liệu ra:
7 10
15 22

Giới hạn:

  • 1 ≤ m ≤ 100; 1 ≤ n ≤ 10^{18}; 0 ≤ a_{ij} ≤ 10^9 .