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 java.util.*;
import java.io.*;
public class EdC {
	static int num = 998244353;
	static long[] fact = new long[300001];

	public static void main(String[] args) throws Exception{
		
		fact[0] = 1;
		long ans1 = 1;
		for(int i = 1;i<=300000;i++){
			ans1= (ans1*i) % num;
			fact[i] = ans1;
		}
		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		int n = Integer.parseInt(bf.readLine());
 		ArrayList<Integer> x = new ArrayList<Integer>();
 		ArrayList<Integer> y = new ArrayList<Integer>();
 		TreeMap<Integer, ArrayList<Integer>> mp = new TreeMap<Integer, ArrayList<Integer>>();
 		for(int j =0 ;j<n;j++){
 			StringTokenizer st = new StringTokenizer(bf.readLine());
 			int a = Integer.parseInt(st.nextToken());
 			int b = Integer.parseInt(st.nextToken());
 			if (!mp.containsKey(a))
 				mp.put(a,  new ArrayList<Integer>());
 			mp.get(a).add(b);
 			x.add(a);
 			y.add(b);
 		}
 		long prod = 1;
 		int currmin = 0;
 		int currmax = 0;
 		for(int j : mp.keySet()){
 			int tempmin = Integer.MAX_VALUE;
 			int tempmax = Integer.MIN_VALUE;
 			for(int k : mp.get(j)){
 				tempmin = Math.min(k,  tempmin);
 				tempmax = Math.max(k,  tempmax);
 			}
 			if (tempmin >= currmax){
 				prod = (prod * numberGood(mp.get(j)))%num;
 				currmin = tempmin;
 				currmax = tempmax;
 			}
 			else{
 				prod = 0;
 				break;
 			}
 		}
 		long ans = numberGood(x) + numberGood(y);
 		ans = (ans%num+num)%num;
 		ans = ans-prod;
 		ans = (ans%num+num)%num;
 		ans = fact[n]-ans;
 		ans = (ans%num+num)%num;
 		
 		out.println(ans);
	 		
 		out.close();
 		
 		
 		
 	}
	public static long numberGood(ArrayList<Integer> array){
		Map<Integer, Integer> freqcount = new HashMap<Integer, Integer>();
		for(int j : array){
			if (!freqcount.containsKey(j))
				freqcount.put(j,  1);
			else
				freqcount.put(j,  freqcount.get(j)+1);
		}
		long ans = 1;
		for(int j : freqcount.keySet()){
			ans = (ans*fact[freqcount.get(j)])%num;
		}
		return ans;
	}
	public static int power(long x, long y, long mod){
		long ans = 1;
		while(y>0){
			if (y%2==1)
				ans = (ans*x)%mod;
			x = (x*x)%mod;
			y/=2;
		}
		return (int)(ans);
	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	


