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.util.stream.IntStream;

public class Laba {
    FScanner fs;
    PrintWriter pw;
    int n;
    boolean[] used;
    int[][] g;
    int[][] dst;

    public static void main(String[] args) throws IOException {
        new Laba().start();
    }

    public void start() throws IOException {
        fs = new FScanner(new InputStreamReader(System.in));
        // reader = new FScanner(new FileReader("input"));
        //pw = new PrintWriter("input.txt");
        pw = new PrintWriter(System.out);
        n = fs.nextInt();
        long modulo = 998244353;
        Pair[] f1 = new Pair[n];
        Pair[] f2 = new Pair[n];
        for (int i = 0; i < n; i++) {
            f1[i] = new Pair(fs.nextInt(), fs.nextInt(), i);
            f2[i] = new Pair(f1[i].x, f1[i].y, i);
        }
        long fac[] = new long[n + 1];
        fac[0] = fac[1] = 1;
        for (long i = 2; i <= n; i++) {
            fac[(int) i] = (fac[(int) (i - 1)] * i) % modulo;
        }
        Arrays.sort(f1, new Comparator<Pair>() {
            @Override
            public int compare(Pair pair, Pair t1) {
                return Integer.compare(pair.x, t1.x);
            }
        });
        Arrays.sort(f2, new Comparator<Pair>() {
            @Override
            public int compare(Pair pair, Pair t1) {
                return Integer.compare(pair.y, t1.y);
            }
        });
        int st = 0;
        int end = 0;
        long total = fac[n];
        long ttotal = 1;
        while (st < f1.length) {
            while (end < f1.length && f1[st].x == f1[end].x)
                end++;
            int num = end - st;
            ttotal = (ttotal * fac[num]) % modulo;
            st = end;
        }
        boolean check = true;
        int max = 0;
        st = 0;
        end = 0;
    dayn:    while (st < f1.length) {
            if (max > f1[st].y) {
                check = false;
                break;
            }
            int pmax = max;
            max = f1[st].y;
            while (end < f1.length && f1[st].x == f1[end].x) {
                max = Math.max(max, f1[end].y);
                if (pmax > f1[end].y) {
                    check = false;
                    break dayn;
                }
                end++;
            }
            st = end;
        }
        if (total < ttotal)
            total = total - ttotal + modulo;
        else total -= ttotal;
        ttotal = 1;
        if (check) {
            Arrays.sort(f1, new Comparator<Pair>() {
                @Override
                public int compare(Pair pair, Pair t1) {
                    if (pair.x == t1.x)
                        return Integer.compare(pair.y, t1.y);
                    return Integer.compare(pair.x, t1.x);
                }
            });
            st = 0;
            end = 0;
            while (st < f1.length) {
                while (end < f1.length && f1[end].x == f1[st].x)
                    end++;
                int qr1 = st, wr1 = st;
                while (qr1 < end) {
                    while (wr1 < end && f1[qr1].y == f1[wr1].y)
                        wr1++;
                    int num = wr1 - qr1;
                    ttotal = (ttotal * fac[num]) % modulo;
                    qr1 = wr1;
                }
                st = end;
            }
            total = (total + ttotal) % modulo;
        }
        st = 0;
        end = 0;
        ttotal = 1;
        while (st < f2.length) {
            while (end < f2.length && f2[st].y == f2[end].y)
                end++;
            int num = end - st;
            ttotal = (ttotal * fac[num]) % modulo;
            st = end;
        }
        if (total < ttotal)
            total = total - ttotal + modulo;
        else total -= ttotal;
        pw.println(total);
        pw.close();
    }
}

class Pair {
    int x, y, c;

    Pair(int x1, int y1, int c1) {
        x = x1;
        y = y1;
        c = c1;
    }
}

class FScanner {
    StringTokenizer st;
    BufferedReader reader;

    FScanner(InputStreamReader isr) throws IOException {
        reader = new BufferedReader(isr);
    }

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

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

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

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

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

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

    int[] iarr(int n) throws IOException {
        int[] mas = new int[n];
        for (int i = 0; i < n; i++)
            mas[i] = nextInt();
        return mas;
    }

    double[] darr(int n) throws IOException {
        double[] mas = new double[n];
        for (int i = 0; i < n; i++)
            mas[i] = nextDouble();
        return mas;
    }

    char[][] cmas2(int n, int m) throws IOException {
        char[][] mas = new char[n][m];
        for (int i = 0; i < n; i++)
            mas[i] = nextLine().toCharArray();
        return mas;
    }

    long[] larr(int n) throws IOException {
        long[] mas = new long[n];
        for (int i = 0; i < n; i++)
            mas[i] = nextLong();
        return mas;
    }
}