Một bảng trò chơi \(n\times n\) chứa một số nguyên không âm trong mỗi ô. Bạn bắt đầu ở góc trên bên trái và cần đến góc dưới bên phải. Số trong ô hiện tại là độ dài bắt buộc của bước nhảy tiếp theo. Mỗi bước chỉ được đi sang phải hoặc đi xuống và không được ra ngoài bảng. Ô chứa \(0\) là ngõ cụt.

Hãy tính số đường đi hợp lệ từ góc trên bên trái đến góc dưới bên phải.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\). Mỗi dòng trong \(n\) dòng tiếp theo chứa \(n\) số nguyên mô tả bảng.

Dữ liệu ra

In một số nguyên: số đường đi hợp lệ.

Ràng buộc

• \(4\le n\le 100\).
• Mỗi ô chứa một số nguyên từ \(0\) đến \(9\).
• Đáp án có không quá \(100\) chữ số thập phân.

Phân nhóm

• Có thể đạt \(70\%\) số điểm nếu dùng kiểu số nguyên \(64\) bit.
• Để đạt toàn bộ số điểm, cần xử lý số nguyên lớn.

Ví dụ

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

3