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.*;
import java.math.*;

public class Es4
{
    static IO io = new IO();
    public static void main(String[] args)
    {
		int n = io.getInt();
		long[] fact = new long[n+1];
		fact[0] = 1;
		for(int i=1; i<=n; i++)
			fact[i] = modMul(fact[i-1],i,998244353);
		IntegerPair[] arr1 = new IntegerPair[n];
		IntegerPair[] arr2 = new IntegerPair[n];
		for(int i=0; i<n; i++){
			int tmp1 = io.getInt();
			int tmp2 = io.getInt();
			arr1[i] = new IntegerPair(tmp1 , tmp2);
			arr2[i] = new IntegerPair(tmp2 , tmp1);
		}
		
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		int count = 1;
		long ans1 = 1;
		for(int i=1; i<n; i++){
			if(arr1[i].a == arr1[i-1].a)
				count++;
			else
			{
				ans1 = modMul(ans1 , fact[count],998244353);
				count = 1;
			}
		}
		ans1 = modMul(ans1 , fact[count],998244353);
		long ans2 = 1;
		count = 1;
		for(int i=1; i<n; i++){
			if(arr2[i].a == arr2[i-1].a)
				count++;
			else
			{
				ans2 = modMul(ans2 , fact[count],998244353);
				count = 1;
			}
		}
		ans2 = modMul(ans2 , fact[count],998244353);
		count = 1;
		long ans3 = 1;
		for(int i=1; i<n; i++){
			if(arr1[i].b < arr1[i-1].b)
				ans3 = 0;
		}
		for(int i=1; i<n; i++){
			if(arr1[i].a == arr1[i-1].a && arr1[i].b == arr1[i-1].b)
				count++;
			else
			{
				ans3 = modMul(ans3 , fact[count],998244353);
				count = 1;
			}
		}
		ans3 = modMul(ans3 , fact[count],998244353);
		io.println(((fact[n]-(ans1+ans2-ans3))+998244353*2)%998244353);
		
        io.close();
    }
	
	
	static long modMul(long a, long b, long mod) 
    { 
        long res = 0;   
  
        // Update a if it is more than  
        // or equal to mod  
        a %= mod; 
  
        while (b > 0)  
        { 
              
            // If b is odd, add a with result  
            if ((b & 1) > 0)  
            { 
                res = (res + a) % mod; 
            } 
  
            // Here we assume that doing 2*a  
            // doesn't cause overflow  
            a = (2 * a) % mod; 
  
            b >>= 1; // b = b / 2  
        } 
        return res; 
    } 
}

class IntegerPair implements Comparable<IntegerPair>
{
	public IntegerPair(int _a, int _b){a = _a; b=_b;}
	
	public int compareTo(IntegerPair p)
	{
		if(this.a != p.a)
			return this.a - p.a;
		return this.b - p.b;
	}
	
	int a, b;
}

class IO extends PrintWriter {
	public IO() {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(System.in));
    }

    public IO(String fileName) {
        super(new BufferedOutputStream(System.out));
        try{
            r = new BufferedReader(new FileReader(fileName));
        } catch (FileNotFoundException e) {
            this.println("File Not Found");
        }
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

	public String getLine(){
        try{
            st = null;
            return r.readLine();
        }
        catch(IOException ex){}
        return null;
    }
	

    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}
