You are given a sequence of $n$ pairs of integers: $(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$. This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:

• $s = [(1, 2), (3, 2), (3, 1)]$ is bad because the sequence of first elements is sorted: $[1, 3, 3]$;
• $s = [(1, 2), (3, 2), (1, 2)]$ is bad because the sequence of second elements is sorted: $[2, 2, 2]$;
• $s = [(1, 1), (2, 2), (3, 3)]$ is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;
• $s = [(1, 3), (3, 3), (2, 2)]$ is good because neither the sequence of first elements $([1, 3, 2])$ nor the sequence of second elements $([3, 3, 2])$ is sorted.

Calculate the number of permutations of size $n$ such that after applying this permutation to the sequence $s$ it turns into a good sequence.

A permutation $p$ of size $n$ is a sequence $p_1, p_2, \dots , p_n$ consisting of $n$ distinct integers from $1$ to $n$ ($1 \le p_i \le n$). If you apply permutation $p_1, p_2, \dots , p_n$ to the sequence $s_1, s_2, \dots , s_n$ you get the sequence $s_{p_1}, s_{p_2}, \dots , s_{p_n}$. For example, if $s = [(1, 2), (1, 3), (2, 3)]$ and $p = [2, 3, 1]$ then $s$ turns into $[(1, 3), (2, 3), (1, 2)]$.