Let \(f(A)\) be the number of sequences obtained by arranging a set \(A\) of points. Here, the \(X\)- or \(Y\)-coordinates of the points may not be a permutation of the smallest positive integers. In the actual computation of \(f\), however, we compress the values and make it a permutation of those numbers.

Basically, we try all possibilities for the position and direction of the division of \(A\) to recursively call \(f\). However, this can count the same sequence multiple times.

This is because there is a degree of freedom in dividing \(A\) even after fixing the sequence to get. To handle it, let us adopt the following rule so that there is a unique way to divide \(A\).

• Let \(X_x\) denote the division according to whether the \(X\)-coordinate is less than \(x\) or not. Similarly, let \(Y_y\) denote the division according to whether the \(Y\)-coordinate is less than \(y\) or not.
• Among the divisions leading to the desired sequence, we use the leftmost one in \(X_2,Y_2,X_3,Y_3,\cdots,X_K,Y_K\).

For each division in the order of preference, let us count the number of desired sequences that cause the division to be chosen.

Assume that we are considering \(X_x\). Note that whether \(X_x\) is chosen in the above procedure depends on the first \(x-1\) elements in the desired sequence. Thus, we will count the number of such ways to arrange the first \(x-1\) elements. Let us first count the number of sequences obtained by arranging the points whose \(X\)-coordinates are less than \(x\). From this, let us subtract the number of sequences that cause us to choose \(X_2\), \(Y_2\), \(X_3\), \(Y_3\), \(\cdots\), \(X_{x-1}\), or \(Y_{x-1}\) in the above procedure. For instance, the number of sequences that causes us to choose \(X_z\) \((z < x)\) looks as follows: \((\)the first \(z-1\) elements that cause \(X_z\) to be chosen in the procedure\()+(\)the sequence obtained by arranging the set of points whose \(X\)-coordinates are between \(z\) and \(x-1)\). We can count such sequences because we should have already counted the number of ways to arrange \((\)the first \(z-1\) elements that cause \(X_z\) to be chosen in the procedure\()\). Divisions in the \(Y\)-direction can be handled similarly.

Let us estimate the complexity. The set of points passed as an argument to \(f\) can only result from extracting a rectangular region from the set of \(N\) points given in input. Therefore, there are only \(O(N^4)\) states after memoization. We need \(O(N^2)\) time for each state, for a total complexity of \(O(N^6)\).

Long sample submission with a small constant factor (c++)

Short sample submission with a large constant factor (c++)