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.*;
import java.util.*;
import java.math.*;
import java.lang.*;
import static java.lang.Math.*;
 
public class fast implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        
        public int read() {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
            
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
            
            return res * sgn;
        }
        
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
        
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    
    public class pair<U extends Comparable<U>,V extends Comparable<V>> implements Comparable<pair<U,V>>{
        U x;
        V y;
        pair(U x, V y){
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(pair<U,V> other){
            if(this.x.compareTo(other.x)!=0) return this.x.compareTo(other.x);
            return this.y.compareTo(other.y);
        }
        @Override   
        public String toString(){
            return x.toString()+","+y.toString();
        }
        @Override
        public boolean equals(Object obj){
            pair<U,V> other=(pair<U,V>) obj;
            return this.x.equals(other.x) && this.y.equals(other.y);
        }
        @Override
        public int hashCode(){
            return toString().hashCode();
        }
    }
 
    class dist implements Comparable<dist>{
        int x,y,z;
        dist(int xi, int yi, int zi){
            x=xi;
            y=yi;
            z=zi;
        }
        @Override
        public int compareTo(dist other){
            if(this.z>other.z){return 1;}
            if(this.z<other.z){return -1;}
            return 0;
        } 
    } 
    
    public static void main(String args[]) throws Exception {
        new Thread(null, new fast(),"fast",1<<26).start();
    }
    
    public void sortbyColumn(int arr[][], final int col){ 
        // Using built-in sort function Arrays.sort 
        Arrays.sort(arr, new Comparator<int[]>() { 
            
          @Override              
          // Compare values according to columns 
          public int compare(final int[] entry1, final int[] entry2) { 
  
            // To sort in descending order revert  
            // the '>' Operator 
            if (entry1[col] > entry2[col]) 
                return 1; 
            if(entry1[col] < entry2[col])
                return -1;
            return 0;
          } 
        });  // End of function call sort(). 
    }
    
    public void sortbyColumn(long arr[][], final int col){ 
        // Using built-in sort function Arrays.sort 
        Arrays.sort(arr, new Comparator<long[]>() { 
            
          @Override              
          // Compare values according to columns 
          public int compare(final long[] entry1, final long[] entry2) { 
  
            // To sort in descending order revert  
            // the '>' Operator 
            if (entry1[col] > entry2[col]) 
                return 1; 
            if(entry1[col] < entry2[col])
                return -1;
            return 0;
          } 
        });  // End of function call sort(). 
    }
    
    public void sort(int ar[]){
        int n=ar.length;
        Integer arr[]=new Integer[n];
        for(int i=0;i<n;i++){
            arr[i]=ar[i];
        }
        Arrays.sort(arr); 
        for(int i=0;i<n;i++){
            ar[i]=arr[i].intValue();
        }
    }
    
    public void sort(long ar[]){
        int n=ar.length;
        Long arr[]=new Long[n];
        for(int i=0;i<n;i++){
            arr[i]=ar[i];
        }
        Arrays.sort(arr); 
        for(int i=0;i<n;i++){
            ar[i]=arr[i].longValue();
        }
    }
    
    long power(long x, long y, long p){  
        long res = 1;      
        x = x % p;  
        while (y > 0) 
        { 
            if((y & 1)==1) 
                res = (res * x) % p; 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    }
    
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}

    long combi(int n, int m, long mod, long[] fac){
        long ans=fac[n];
        ans*=power(fac[m],mod-2,mod);
        ans%=mod;
        return (ans*power(fac[n-m],mod-2,mod))%mod;
    }

    public void run(){
        InputReader s = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        
        int n=s.nextInt();
        dist[] d=new dist[n];
        for(int i=0;i<n;i++){
            d[i]=new dist(i,s.nextInt(), s.nextInt());
        }
        Arrays.sort(d, new Comparator<dist>(){
            public int compare(dist o1, dist o2){
                if(o1.y!=o2.y) return o1.y-o2.y;
                return 0;
            }
        });
        long[] fac=new long[300001];
        fac[0]=1;
        long mod=998244353,ans;
        for(int i=1;i<300001;i++){
            fac[i]=fac[i-1]*i;
            fac[i]%=mod;
        }
        int sz=1;
        ans=fac[n];
        long t1=1, t2=1, t3=1;
        for(int i=1;i<n;i++){
            if(d[i].y!=d[i-1].y){
                t1*=fac[sz];
                t1%=mod;
                sz=1;
            } else sz++;
        }
        t1*=fac[sz];
        t1%=mod;
        Arrays.sort(d, new Comparator<dist>(){
            public int compare(dist o1, dist o2){
                if(o1.z!=o2.z) return o1.z-o2.z;
                return 0;
            }
        });
        sz=1;
        for(int i=1;i<n;i++){
            if(d[i].z!=d[i-1].z){
                t2*=fac[sz];
                t2%=mod;
                sz=1;
            } else sz++;
        }
        t2*=fac[sz];
        t2%=mod;
        Arrays.sort(d, new Comparator<dist>(){
            public int compare(dist o1, dist o2){
                if(o1.y!=o2.y) return o1.y-o2.y;
                if(o1.z!=o2.z) return o1.z-o2.z;
                return 0;
            }
        });
        sz=1;
        for(int i=1;i<n;i++){
            if(d[i].y!=d[i-1].y || d[i].z!=d[i-1].z){
                if(d[i].z<d[i-1].z) t3=0;
                t3*=fac[sz];
                t3%=mod;
                sz=1;
            } else sz++;
        }
        t3*=fac[sz];
        t3%=mod;
        ans+=t3-t2-t1+mod+mod;
        ans%=mod;
        w.println(ans);

        w.close();
    }
}