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. 
//package train1;


import java.io.*;
import java.util.*;
import java.util.Arrays;
import java.lang.reflect.Array;

public class main1207D {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter = new FastScanner(System.in);
    public static long[] fact = new long[3 * (int) 1e5 + 1];
    public static long mod = 998244353;
    public static int[] was = new int[3 * (int) 1e5 + 1];

    public static void main(String[] args) throws IOException {
        fact[0] = 1;
        for (int i = 1; i < fact.length; i++) {
            fact[i] = fact[i - 1]*i;
            fact[i] %= mod;
        }
        int n = enter.nextInt();
        long[] up = new long[n];
        long[] down = new long[n];
        pair[] mass=new pair[n];
        for (int i = 0; i < n; i++) {
            up[i] = enter.nextLong();
            down[i] = enter.nextLong();
            mass[i]=new pair(up[i], down[i]);
        }
        sortMergeNoRecursive(mass, 0 ,n, pair.class, pair::compareTo);

        for (int i = 0; i <n ; i++) {
            up[i]=mass[i].x;
            down[i]=mass[i].y;
        }

        long ansOnlyUp=1;
        long ansOnlyDown=1;
        HashMap<Long, Long> map=new HashMap<>();
        for (int i = 0; i <up.length; i++) {
            if(map.get(up[i])==null) map.put(up[i],1L);
            else map.put(up[i], map.get(up[i])+1);
        }
        for (long a:map.values()) {
            ansOnlyUp*=fact[(int)a];
            ansOnlyUp%=mod;
        }
        map.clear();
        for (int i = 0; i <down.length; i++) {
            if(map.get(down[i])==null) map.put(down[i],1L);
            else map.put(down[i], map.get(down[i])+1);
        }
        for (long a:map.values()) {
            ansOnlyDown*=fact[(int)a];
            ansOnlyDown%=mod;
        }
        long ansBoth;
        if(!check(down)){
            ansBoth=0;
        }
        else {
            ansBoth=1;
            TreeSet<Integer> tree=new TreeSet<>();
            long last1=-1;
            long last2=-1;
            for (int i = 0; i <up.length; i++) {
                if(up[i]!=last1) tree.add(i);
                last1=up[i];
                if(down[i]!=last2) tree.add(i);
                last2=down[i];
            }
            tree.add(up.length);
            ArrayList<Integer> arr=new ArrayList<>();
            int N=tree.size();
            for (int i = 0; i <N ; i++) {
                arr.add(tree.pollFirst());
            }
            for (int i = 1; i <arr.size() ; i++) {
                ansBoth*=fact[arr.get(i)-arr.get(i-1)];
                ansBoth%=mod;
            }
        }


        ansBoth=(ansOnlyDown+ansOnlyUp)%mod-ansBoth;
        ansBoth%=mod;
        ansBoth=fact[n]-ansBoth;
        ansBoth=(ansBoth%mod+mod)%mod;
        System.out.println(ansBoth);
    }


    public static boolean check(long[] mass){
        long first=-1;
        for (int i = 0; i <mass.length ; i++) {
            if(mass[i]<first) return false;
            first=mass[i];
        }
        return true;
    }

    static class pair implements Comparable<pair>{
        long x;
        long y;

        public pair(long x, long y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(pair o) {
            if(o.x==x) return Long.compare(y, o.y);
            else return Long.compare(x,o.x);
        }
    }


    public static <T> void sortMergeNoRecursive(T[] arr, int first, int last, Class<T> c, Comparator<T> comparator) {
        int len = last;
        int n = 1;
        int shift;
        int two_size;
        T[] arr2;
        while (n < len) {
            shift = first;
            while (shift < len) {
                if (shift + n >= len) break;
                two_size = (shift + n * 2 > len) ? (len - (shift + n)) : n;
                arr2 = merge(Arrays.copyOfRange(arr, shift, shift + n),
                        Arrays.copyOfRange(arr, shift + n, shift + n + two_size), c, comparator);
                for (int i = 0; i < n + two_size; ++i)
                    arr[shift + i] = arr2[i];
                shift += n * 2;
            }
            n *= 2;
        }
    }

    public static <T> T[] merge(T[] arr_1, T[] arr_2, Class<T> c, Comparator<T> comparator) {
        int len_1 = arr_1.length, len_2 = arr_2.length;
        int a = 0, b = 0, len = len_1 + len_2;
        //T[] result = new <>[len];
        T[] result = (T[]) Array.newInstance(c, len);


        for (int i = 0; i < len; i++) {
            if (b < len_2 && a < len_1) {
                if (comparator.compare(arr_1[a], arr_2[b]) > 0) result[i] = arr_2[b++];
                else result[i] = arr_1[a++];
            } else if (b < len_2) {
                result[i] = arr_2[b++];
            } else {
                result[i] = arr_1[a++];
            }
        }
        return result;
    }



    private static long cnk(int k, int n) {
        long ans = fact[n];
        long down_1 = fact[n - k];
        long down_2 = fact[k];
        down_1 *= down_2;
        down_1 %= mod;
        down_1 = bin_pow(down_1, mod - 2, mod);
        ans *= down_1;
        ans %= mod;
        return ans;

    }

    public static long bin_pow(long a, long b, long mod) {//a^b %mod
        long ans = 1;
        while (b != 0) {
            if ((b & 1) == 1) ans *= a;
            a *= a;
            ans %= mod;
            a %= mod;
            b >>= 1;
        }
        return ans;
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() throws IOException {
            while (stok == null || !stok.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return null;
                }
                stok = new StringTokenizer(s);
            }
            return stok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        char nextChar() throws IOException {
            return (char) (br.read());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }
    }
}
