You are given a sequence of n pairs of integers: (a_1, b_1), (a_2, b_2), ... , (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, ... , p_n consisting of n distinct integers from 1 to n (1 ≤ p_i ≤ n). If you apply permutation p_1, p_2, ... , p_n to the sequence s_1, s_2, ... , s_n you get the sequence s_{p_1}, s_{p_2}, ... , 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)].

Input

The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5).

The next n lines contains description of sequence s. The i-th line contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n) — the first and second elements of i-th pair in the sequence.

The sequence s may contain equal elements.

Output

Print the number of permutations of size n such that after applying this permutation to the sequence s it turns into a good sequence. Print the answer modulo 998244353 (a prime number).

Examples

Input


3
1 1
2 2
3 1


Output


3


Input


4
2 3
2 2
2 1
2 4


Output


0


Input


3
1 1
1 1
2 3


Output


4

Note

In first test case there are six permutations of size 3: 

  1. if p = [1, 2, 3], then s = [(1, 1), (2, 2), (3, 1)] — bad sequence (sorted by first elements); 
  2. if p = [1, 3, 2], then s = [(1, 1), (3, 1), (2, 2)] — bad sequence (sorted by second elements); 
  3. if p = [2, 1, 3], then s = [(2, 2), (1, 1), (3, 1)] — good sequence; 
  4. if p = [2, 3, 1], then s = [(2, 2), (3, 1), (1, 1)] — good sequence; 
  5. if p = [3, 1, 2], then s = [(3, 1), (1, 1), (2, 2)] — bad sequence (sorted by second elements); 
  6. if p = [3, 2, 1], then s = [(3, 1), (2, 2), (1, 1)] — good sequence. 
import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations


def li ():
	return list (map (int, sys.stdin.readline ().split ()))


def num ():
	return map (int, sys.stdin.readline ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def lcm ( x, y ):
	gg = find_gcd (x, y)
	return (x * y // gg)


mm = 998244353
yp = 0

def solve ():
	t = 1
	for tt in range (t):
		n=nu()
		a=[]
		p=[]
		q=[]
		fact=[0]*(n+1)
		fact[0]=1
		for i in range(1,n+1):
			fact[i]=(fact[i-1]*i)%mm
		for i in range(n):
			x,y=num()
			p.append(x)
			q.append(y)
			a.append((x,y))
		a.sort()
		p.sort()
		q.sort()
		cc=1
		last=p[0]
		ans1=1
		for i in range(1,n):
			if(last==p[i]):
				cc+=1
			else:
				ans1=(ans1*fact[cc])%mm
				cc=1
				last=p[i]
		ans1 = (ans1 * fact [ cc ]) % mm
		cc=1
		last=q[0]
		ans2=1
		for i in range(1,n):
			if(last==q[i]):
				cc+=1
			else:
				ans2=(ans2*fact[cc])%mm
				cc=1
				last=q[i]
		ans2 = (ans2 * fact [ cc ]) % mm
		ans3=1
		cc=1
		last=a[0]
		for i in range(1,n):
			if(last==a[i]):
				cc+=1
			elif(last[0]>a[i][0] or last[1]>a[i][1]):
				ans3=0
			else:
				ans3=(ans3*fact[cc])%mm
				cc=1
				last=a[i]
		ans3 = (ans3 * fact [ cc ]) % mm
		print((fact[n]-ans1-ans2+ans3+mm)%mm)

if __name__ == "__main__":
	solve ()