Subtask 1 ~(n \le 4)~:

• Vì kích cỡ ma trận bị giới hạn bởi ~4~ nên số ô tối đa của ma trận ~A~ là ~16~ ô.

• Nhận xét : Cho ~B~ và ~B'~ là ~2~ ma trận vuông có kích thước ~n \times n~ với mỗi ô trên ma trận ~B~ có giá trị là ~1~ số nguyên không âm và ~B'~ là ma trận thu được sau khi thay toàn bộ các số nguyên dương trên ma trận ~B~ bằng số ~1~. Với số nguyên dương ~k~ bất kỳ, dễ thấy nếu ~B^k~ là ma trận toàn ~0~ thì ~B'^k~ cũng là ma trận toàn ~0~.

• Vậy nếu đặt ~B = A~ thì ~B'~ chỉ có tối đa ~2^{16}~ trạng thái do mỗi ô phải có giá trị ~0~ hoặc ~1~, ta coi mỗi trạng thái của ma trận ~B'~ là ~1~ đỉnh trên đồ thị và dựng cạnh có hướng giữa các cặp đỉnh ~B'~ và ~(B' \times A)'~, vậy ta cần tìm đường đi ngắn nhất giữa đỉnh gốc và đỉnh ma trận ~B'~ toàn ~0~ trên đồ thị (hoặc in ra ~-1~ nếu giữa ~2~ đỉnh không tồn tại đường đi), bài có thể giải bằng thuật toán BFS với độ phức tạp ~O(2^{n^2} * n^3)~ với ~n^3~ là độ phức tạp của một phép nhân ma trận.

Subtask 2 ~(n \le 60)~:

Cách 1 (dựa vào phán đoán):

• Vì tác giả không bắt in ra kết quả mod ~10^9+7~ (hoặc giảm tải output theo cách khác) nên rất có thể kết quả của bài phải nằm trong giới hạn của biến long long.

• Đặt ~X~ là ~1~ số nguyên vừa đủ to để ~2^X~ vượt quá giới hạn của biến long long, chẳng hạn như ~X = 70~.

• Ta tính trước tất cả các ma trận ~A~ có dạng ~A^{2^x}~ với ~x~ là số nguyên trong khoảng ~[0, X]~, rồi dùng kỹ thuật binary lifting để tìm ra số ~k-1~ (là lũy thừa lớn nhất sao cho ma trận ~A~ còn lại ít nhất ~1~ số nguyên dương), nếu kết quả ~k~ tìm được vô tình vượt quá giới hạn của long long thì ta in ra ~-1~. Độ phức tạp của cách làm này là ~O(n^3 \times X)~.

Cách 2 (dựa vào nhận xét):

• Nhận xét : Trên thực tế có thể chứng minh được rằng nếu ~k~ tồn tại thì phải thỏa mãn ~k \le n~, tuy nhiên phần chứng minh sẽ được để lại cho thí sinh tự suy nghĩ. Từ nhận xét này, dễ thấy ta chỉ cần tính hết ~n~ lũy thừa đầu tiên của ma trận ~A~ là đủ biết kết quả, độ phức tạp của cách làm này là ~O(n^4)~.

Subtask 3:

• Để hoàn thành subtask này, chúng ta cần thay đổi góc nhìn về bài toán. Ta coi ~A~ như là ~1~ adjencent matrix của đồ thị tương ứng gọi là ~G~ (vì ~A~ chỉ gồm ~0~ hoặc ~1~). Lúc này, ô ~(i, j)~ trong ma trận ~A^k~ sẽ cho biết số đường đi độ dài ~k~ giữa ~2~ đỉnh ~i, j~ trên đồ thị ~G~.

• Nếu đồ thị ~G~ mà có chu trình (tính cả self-loop và chu trình có độ dài ~2~) thì kết quả sẽ là ~-1~, vì luôn tồn tại ít nhất ~1~ đường đi có độ dài ~k~ giữa ~2~ đỉnh nào đó cùng nằm trên chu trình này. Vì vậy nếu ~k~ tồn tại thì ~G~ phải là ~1~ đồ thị ~DAG~ và đường đi dài nhất trên đồ thị ~G~ có độ dài chính bằng ~k-1~. Tìm đường đi dài nhất trên đồ thị ~DAG~ là ~1~ bài tập kinh điển từng xuất hiện trong series atcoder dp và được giải bằng ~DFS~ với độ phức tạp ~O(n+m)~.