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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;
import java.util.TreeSet;

public class Solution {
    static long fact[];
    public static long count(Pair arr[],long M)
    {
        int c=1;
        long ans=1;
        for(int i=0;i<arr.length-1;i++)
        {
            if(arr[i].val==arr[i+1].val)
            {
                c++;
            }
            else
            {
               ans=(ans*fact[c]) %M;
               c=1;
            }
        }
        ans=(ans*fact[c])%M;
        return ans;
    }
    public static long count1(Pair arr1[],Pair arr2[],long M)
    {
        int c=1,i=0,j=0,n=arr1.length;
        long ans=1;
        TreeSet<Integer> set1=new TreeSet<>();
        TreeSet<Integer> set2=new TreeSet<>();
        /*for(i=0;i<n;i++)
        {
            System.out.println(arr1[i].val+" "+arr1[i].pos);
        }
        for(i=0;i<n;i++)
        {
            System.out.println(arr2[i].val+" "+arr2[i].pos);
        }*/
        i=0;
        while(i<=n-1 || j<=n-1)
        {
            if(set1.size()==0) {
                if(i<n)
                    set1.add(arr1[i].pos);
                while(i<n-1 && arr1[i].val==arr1[i+1].val) {
                    set1.add(arr1[i+1].pos);
                    i++;
                }
                i++;
            }
            if(set2.size()==0) {
                if(j<n)
                    set2.add(arr2[j].pos);
                while(j<n-1 && arr2[j].val==arr2[j+1].val) {
                    set2.add(arr2[j+1].pos);
                    j++;
                }
                j++;
            }
            //System.out.println(set1);
            //System.out.println(set2);

            if(set1.size()==set2.size())
            {
                for(Integer x:set1) {
                    if (!set2.contains(x))
                        return 0;
                }
                set1=new TreeSet<>();
                set2=new TreeSet<>();
            }
            else if(set1.size()>set2.size())
            {
                for(Integer x:set2) {
                    if (!set1.contains(x))
                        return 0;
                    set1.remove(x);
                }
                set2=new TreeSet<>();
            }
            else
            {
                for(Integer x:set1) {
                    if (!set2.contains(x))
                        return 0;
                    set2.remove(x);
                }
                set1=new TreeSet<>();
            }
        }
        //System.out.println(ans);
        for(i=0;i<n-1;i++)
        {
            //System.out.println(c);
            if(arr1[i].val==arr1[i+1].val && arr2[i].val==arr2[i+1].val)
                c++;
            else
            {
                ans=(ans*fact[c]) %M;
                c=1;
            }
        }
        return (ans*fact[c])%M;
    }
    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i,j,k=0,f;
        long M=998244353;
        int n=in.nextInt();
        fact=new long[300001];
        fact[0]=1;
        for(i=1;i<=300000;i++)
            fact[i]=(fact[i-1]*i)%M;
        Pair arr1[]=new Pair[n];
        Pair arr2[]=new Pair[n];
        for(i=0;i<n;i++)
        {
            arr1[i]=new Pair(in.nextInt(),i);
            arr2[i]=new Pair(in.nextInt(),i);

        }
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        /*for(i=0;i<n;i++)
            System.out.println(arr[i].val1+" "+arr[i].val2);*/
        long ans=fact[n],a,b,c;
        a=count(arr1,M);
        b=count(arr2,M);
        c=count1(arr1,arr2,M);
        long x=(a+b-c+M)%M;
        //System.out.println(n+" "+ans+" "+a+" "+b+" "+c);
        ans=(ans-x+M)%M;
        System.out.println(ans);
    }
}
class Pair implements Comparable<Pair>
{
    int val,pos;
    public Pair(int x,int y)
    {
        val=x;
        pos=y;
    }
    public int compareTo(Pair x)
    {
        if(this.val>x.val)
            return 1;
        else if(this.val<x.val)
            return -1;
        else
            return 0;
    }
}
class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}