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.util.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;
import static java.lang.Math.*;

public class Main implements Runnable
{
    boolean multiiple = false;
    int p = 998244353;

    class Pair implements Comparable<Pair>
    {
        @Override
        public int compareTo(Pair o)
        {
            if (a == o.a)
                return b - o.b;
            return a - o.a;
        }

        int a, b;

        Pair(int x, int y)
        {
            a = x;
            b = y;
        }
    }

    void solve() throws Exception
    {
        int n = sc.nextInt();

        for (int i = 0; i < dp.length; i++)
            dp[i] = -1;

        ArrayList<Pair> list = new ArrayList<>();

        for (int i = 0; i < n; i++)
            list.add(new Pair(sc.nextInt(), sc.nextInt()));

        long sort1 = 1;

        HashMap<Integer, Integer> count1 = new HashMap<>();

        for (Pair pair : list)
            if (count1.containsKey(pair.a))
                count1.put(pair.a, count1.get(pair.a) + 1);
            else
                count1.put(pair.a, 1);

        for (Integer key : count1.keySet())
            sort1 = (factorial(count1.get(key)) * sort1) % p;

        long sort2 = 1;

        HashMap<Integer, Integer> count2 = new HashMap<>();

        for (Pair pair : list)
            if (count2.containsKey(pair.b))
                count2.put(pair.b, count2.get(pair.b) + 1);
            else
                count2.put(pair.b, 1);

        for (Integer key : count2.keySet())
            sort2 = (factorial(count2.get(key)) * sort2) % p;

        HashMap<Integer, ArrayList<Pair>> map = new HashMap<>();

        for (Pair pair : list)
        {
            if (map.containsKey(pair.a))
                map.get(pair.a).add(pair);
            else
            {
                map.put(pair.a, new ArrayList<>());
                map.get(pair.a).add(pair);
            }
        }

        long sortBoth = 1;

        for (Integer chunk : map.keySet())
        {
            long sortChunk = 1;

            HashMap<Integer, Integer> count = new HashMap<>();

            for (Pair pair : map.get(chunk))
                if (count.containsKey(pair.b))
                    count.put(pair.b, count.get(pair.b) + 1);
                else
                    count.put(pair.b, 1);

            for (Integer key : count.keySet())
                sortChunk = (factorial(count.get(key)) * sortChunk) % p;

            sortBoth = (sortChunk * sortBoth) % p;
        }

        Collections.sort(list);

        boolean gay = true;
        for (int i = 0; i < list.size() - 1; i++)
            if (!(list.get(i + 1).a >= list.get(i).a && list.get(i + 1).b >= list.get(i).b))
                gay = false;

        if (!gay)//!!
            sortBoth = 0;

        sort1 = (sort1 + sort2) % p;
        sort1 = (sort1 - sortBoth) % p;
        
        long ans = (factorial(n) - sort1) % p;
        
        while (ans < 0)
            ans += p;
        
        System.out.println(ans);
    }

    long factorial(int in)
    {
        if (dp[in] != -1)
            return dp[in];
        if (in <= 1)
            return 1;
        return dp[in] = ((in * factorial(in - 1)) % p);
    }

    long[] dp = new long[1000000];

    @Override
    public void run()
    {
        try
        {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            sc = new FastScanner(in);
            if (multiiple)
            {
                int q = sc.nextInt();
                for (int i = 0; i < q; i++)
                    solve();
            }
            else
                solve();
        }
        catch (Throwable uncaught)
        {
            Main.uncaught = uncaught;
        }
        finally
        {
            out.close();
        }
    }

    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Main(), "", (1 << 26));
        thread.start();
        thread.join();
        if (Main.uncaught != null) {
            throw Main.uncaught;
        }
    }

    static Throwable uncaught;
    BufferedReader in;
    FastScanner sc;
    PrintWriter out;
}

class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in)
    {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

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

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

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

}