Nhân dịp kỷ niệm 75 năm ngày thành lập Đoàn TNCS Hồ Chí Minh, Ban chấp hành Đoàn trường THPT X tổ chức một trò chơi trên lưới ô vuông cho các đội chơi. Lưới ô vuông có kích thước \(n \cdot n\). Các dòng của lưới được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột của lưới được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ô nằm trên giao của dòng \(i\), cột \(j\) được gọi là ô \((i, j)\) của lưới. Trên mỗi ô \((i, j)\) của lưới ghi một số nguyên dương \(a_{ij}\) (\(1 \le i, j \le n\)) chính là giá trị của món quà đặt trên đó.

Nhiệm vụ của người chơi là xuất phát từ ô \((1, 1)\) bên trái của lưới tìm cách di chuyển sang ô bên phải của lưới để lấy được nhiều món quà nhất về cho đội của mình (khi đi qua ô nào thì nhận được quà trên ô đó). Quy tắc di chuyển là từ một ô bất kỳ của lưới được phép di chuyển sang ô bên phải có giá trị không nhỏ hơn giá trị ô đó.

Yêu cầu: Đếm xem có bao nhiêu cách di chuyển theo quy tắc trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa các số nguyên \(a_{i1}, a_{i2}, \dots, a_{in}\) (\(1 \le i \le n\)). Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số duy nhất là số cách di chuyển theo quy tắc trên. Nếu không có cách nào di chuyển thì ghi số \(0\).

Example

3
1 2 3
2 4 1
3 3 2

3

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài có: \(1 \le n \le 10, a_{ij} \le 30\).
• Có \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài có: \(n \le 20, a_{ij} \le 10^3\).