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.*;
     
    public class Main {
        static int t,n,m,k,mod=998244353,maxn=300000;
        static long INF=(long)1e16;
        
        
        void solve(PrintWriter out, Reader in) throws IOException{
            n = in.nextInt();
            
            Integer[] a2 = new Integer[n];
            Integer[] b2 = new Integer[n];
            Node[] pr = new Node[n];
            
            for(int i=0;i<n;i++){
                a2[i] = new Integer(in.nextInt());
                b2[i] = new Integer(in.nextInt());
                pr[i] = new Node((int)a2[i],(int)b2[i]);
            }
            Arrays.sort(a2);
            Arrays.sort(b2);
            Arrays.sort(pr);
            
            int[] a = new int[n];
            int[] b = new int[n];
            for(int i=0;i<n;i++){
                a[i] = (int)a2[i];
                b[i] = (int)b2[i];
            }
            
            long as=-1;
            long bs=-1;
            long ps=-1;
            int cnta=1,cntb=1,cntp=1;
            long[] v = new long[maxn+1];
            v[1]=1;
            for(int i=2;i<=maxn;i++) v[i] = (v[i-1]*(long)i)%mod;
            
            for(int i=1;i<n;i++){
                if(a[i]==a[i-1]){
                    cnta++;
                }else{
                    if(as==-1){
                        as=v[cnta];
                    }else{
                        as = (as*v[cnta])%mod;
                    }
                    cnta=1;
                }
                
                if(b[i]==b[i-1]){
                    cntb++;
                }else{
                    if(bs==-1){
                        bs=v[cntb];
                    }else{
                        bs = (bs*v[cntb])%mod;
                    }
                    cntb=1;
                }
                
                if(pr[i].x<pr[i-1].x || pr[i].y<pr[i-1].y) ps=0;
                if(pr[i].x==pr[i-1].x && pr[i].y==pr[i-1].y){
                    cntp++;
                }else{
                    if(ps==-1){
                        ps=v[cntp];
                    }else{
                        ps = (ps*v[cntp])%mod;
                    }
                    cntp=1;
                }
            }
            
            if(as==-1) as = v[cnta];
            else as = (as*v[cnta])%mod;
            
            if(bs==-1) bs = v[cntb];
            else bs = (bs*v[cntb])%mod;
            
            if(ps==-1) ps = v[cntp];
            else ps = (ps*v[cntp])%mod;
            
            long all=1;
            for(int i=2;i<=n;i++) all = (all*i)%mod;
            
            long resp = (as+bs-ps+mod)%mod;
            out.println((all+mod-resp)%mod);
        }
        
        static class Node implements Comparable<Node>{
            int x,y;
            
            Node(int x,int y){
                this.x = x;
                this.y = y;
            }
            
            public int compareTo(Node o){
                if(this.x!=o.x){
                    return this.x-o.x;
                }
                return this.y-o.y;
            }
        }
        
        static class Reader {
     
        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
     
        public Reader() {
            this(System.in);
        }
     
        public Reader(InputStream is) {
            mIs = is;
        }
     
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
     
        }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
     
        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
     
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
     
        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 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 boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
     
        }
        public static void main(String[] args) throws IOException {
            PrintWriter out = new PrintWriter(System.out);
            Reader in = new Reader();
            Main solver = new Main();
            solver.solve(out, in);
            out.flush();
            out.close();
     
        }
    }