네모난 순열 찾기 2

$N^2$개의 수가 $N$행 $N$열의 표 $A$에 채워져 있다. 표의 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열에 위치한 칸에는 정수 $A\_{r,c}$가 적혀 있으며, $r$행 $c$열을 편의상 $(r,c)$로 표현한다. 이때, 표 $A$에 채워진 값은 모두 다르다.

표 $A$에서 직사각형 맨 왼쪽 위 칸이 $(r\_1,c\_1)$이고, 맨 오른쪽 아래 칸이 $(r\_2,c\_2)$가 되게 직사각형을 선택할 때, $1\leq r\_1\leq r\leq r\_2\leq N,1\leq c\_1\leq c\leq c\_2\leq N$ 을 만족하는 $A\_{r,c}$는 직사각형 안에 있는 수이다.

수 $x$개로 이루어진 배열이 $1$부터 $x$까지의 서로 다른 정수 $x$개로 이루어져 있다면, 순열이다. 예를 들어 $\[2,3,1,5,4]$는 순열이지만, $\[1,2,2]$와 $\[1,3,4]$는 순열이 아니다.

직사각형의 네 변이 표의 경계선과 겹치도록 직사각형을 선택할 때, 직사각형 안에 있는 수를 나열한 것이 순열이 되는 경우의 수는 얼마일까?

첫째 줄에 표 $A$의 행과 열의 개수 $N$이 주어진다. ($1\leq N\leq 1\\, 000$)

이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $A\_{i,1},A\_{i,2},\ldots ,A\_{i,N}$이 공백으로 구분되어 주어진다. ($1\leq A\_{i,j}\leq N^2$)

표 $A$에 채워진 값은 서로 다르다.

첫째 줄에 경우의 수를 출력한다.