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. 
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1207D
   {
      static long MOD = 998244353L;
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         Pair[] arr = new Pair[N];
         for(int i=0; i < N; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[i] = new Pair(a,b);
         }
         Arrays.sort(arr); //sort by 1st element
         long[] fac = new long[N+1];
         fac[0] = 1L;
         for(int i=1; i <= N; i++)
            fac[i] = (fac[i-1]*i)%MOD;
         int curr = arr[0].a;
         ArrayList<Integer> ls = new ArrayList<Integer>();
         ls.add(arr[0].b);
         long both = 1L;
         for(int i=1; i < N; i++)
         {
            if(curr == arr[i].a)
               ls.add(arr[i].b);
            else
            {
               long temp = 1L;
               int cnt = 1;
               int num = ls.get(0);
               for(int a=1; a < ls.size(); a++)
               {
                  if(ls.get(a) == num)
                     cnt++;
                  else
                  {
                     temp = (temp*fac[cnt])%MOD;
                     num = ls.get(a);
                     cnt = 1;
                  }
               }
               temp = (temp*fac[cnt])%MOD;
               both = (both*temp)%MOD;
               ls.clear();
               ls.add(arr[i].b);
               curr = arr[i].a;
            }
         }
         //do last
         long temp = 1L;
         int cnt = 1;
         int num = ls.get(0);
         for(int a=1; a < ls.size(); a++)
         {
            if(ls.get(a) == num)
               cnt++;
            else
            {
               temp = (temp*fac[cnt])%MOD;
               num = ls.get(a);
               cnt = 1;
            }
         }
         temp = (temp*fac[cnt])%MOD;
         both = (both*temp)%MOD;
         int[] a = new int[N];
         for(int i=0; i < N; i++)
            a[i] = arr[i].a;
         long res = find(a, fac);
         int[] b = new int[N];
         for(int i=0; i < N; i++)
            b[i] = arr[i].b;
         res = (res+find(b, fac))%MOD;
         if(fake(arr))
            both = 0;
         res -= both;
         res += MOD;
         res %= MOD;
         res = fac[N]-res+MOD;
         res %= MOD;
         System.out.println(res);
      }
      public static boolean fake(Pair[] arr)
      {
         int N = arr.length;
         for(int i=1; i < N; i++)
            if(arr[i].b < arr[i-1].b || arr[i].a < arr[i-1].a)
               return true;
         return false;  
      }
      public static long find(int[] arr, long[] fac)
      {
         sort(arr);
         long res = 1L;
         int cnt = 1;
         int val = arr[0];
         for(int i=1; i < arr.length; i++)
         {
            if(val == arr[i])
               cnt++;
            else
            {
               val = arr[i];
               res = (res*fac[cnt])%MOD;
               cnt = 1;
            }
         }
         res = (res*fac[cnt])%MOD;
         return res;
      }
      public static void sort(int[] arr)
      {
         //stable heap sort
         PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
         for(int a: arr)
            pq.add(a);
         for(int i=0; i < arr.length; i++)
            arr[i] = pq.poll();
      }
   }
   class Pair implements Comparable<Pair>
   {
      public int a;
      public int b;
      
      public Pair(int c, int d)
      {
         a = c;
         b = d;
      }
      public int compareTo(Pair oth)
      {
         if(a == oth.a)
            return b-oth.b;
         return a-oth.a;
      }
   }