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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.math.*;
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
 
 
 
public class Main {
	static class Node {
		  public long first;
		  public  long second;


		  Node(long a,long b) {
		    first = a;
		    second = b;
		    
		  }
		}

	
	static int k;
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
 
    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
        	int n=in.nextInt();
        	Node[] arr=new Node[n];
        	long mod=998244353;
        	for(int i=0;i<n;i++) {
        		arr[i]=new Node(in.nextLong(),in.nextLong());     		
        	}
        	asort(arr,0,n);

        	long[] pre=new long[n+1];
        	pre[0]=1;
        	for(int i=1;i<=n;i++) {
        		pre[i]=(pre[i-1]*i)%mod;
        		pre[i]%=mod;
        	}
        
        	long c1=1;
        	long c2=1;
        	long x=1;
        	int j=0;
        	int k=1;
        	for(int i=0;i<n;i++) {
        		j=i+1;
        		if(j<n && arr[i].first==arr[j].first ) {
        			k++;
        		}
        		else {
        			c1=c1*pre[k]%mod;
        			k=1;
        		}
        	//	System.out.println(k+" k");
        		
        	}
        	bsort(arr,0,n);
        	k=1;
        	for(int i=0;i<n;i++) {
        		j=i+1;
        		if(j<n && arr[i].second==arr[j].second ) {
        			k++;
        			
        		}
        		else {
        			c2=c2*pre[k]%mod;
        			k=1;
        		}
        		
        	}
      //  	System.out.println(c1+" "+c2);
        	asort(arr,0,n);
        	int check=0;
        	for(int i=0;i<n-1;i++) {       		
        		if(arr[i].second>arr[i+1].second) {
        			check=1;
        			break;
        		}
        	}
        	
        	if(check==1) {
        		System.out.println(((pre[n]-c1-c2)%mod+mod)%mod);
        	}
        	else {
        		int c=1;
        		for(int i=0;i<n;i++) {
        			j=i+1;
        			if(j<n && arr[i].first==arr[j].first && arr[i].second==arr[j].second) {
        				c++;
        				
        			}
        			else {
        				x=(x%mod)*pre[c]%mod;
        				c=1;
        			}
        		//	System.out.println(x);
        		}
				
        	//	System.out.println(x+" x");
       // 		System.out.println(pre[n]);
      		System.out.println(((pre[n]-c1-c2+x)%mod+mod)%mod);
        	}
        
        
        }
    }
   
    	
    static long moduloMultiplication(long a, long b, long mod) {
    	long res = 0;   
    	a %= mod; 

    	while (b > 0) {
		if ((b & 1) > 0) { 
    			res = (res + a) % mod; 
    		} 
    		a = (2 * a) % mod; 
    		b >>= 1;
    	} 
    	return res; 
    } 
    static class InputReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
   
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    
    }
    public static void asort(Node[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        // recursively sort 
        asort(a, low, mid); 
        asort(a, mid, high); 
        // merge two sorted subarrays
        Node[] temp = new Node[N];
        int i = low, j = mid;
       
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j].first<a[i].first) 
                temp[k] = a[j++];
            else if(a[j].first==a[i].first) {
            	if(a[i].second>a[j].second)
                    temp[k] = a[j++];
            	else
                    temp[k] = a[i++];

            }
            else 
                temp[k] = a[i++];
        }   
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    public static void bsort(Node[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        // recursively sort 
        bsort(a, low, mid); 
        bsort(a, mid, high); 
        // merge two sorted subarrays
        Node[] temp = new Node[N];
        int i = low, j = mid;
       
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j].second<a[i].second) 
                temp[k] = a[j++];
       
            else 
                temp[k] = a[i++];
        }   
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    
    

   
    
}