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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/*
*
* hadiLotfy
* 14_09_2019
*
* */
public class D_2 {
    private static class Pair<A>{
        private A first ;
        private A second ;

        Pair(A first, A second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair<?> pair = (Pair<?>) o;

            if (!first.equals(pair.first)) return false;
            return second.equals(pair.second);
        }

        @Override
        public int hashCode() {
            int result = first.hashCode();
            result = 31 * result + second.hashCode();
            return result;
        }

    }
    private static final int N = (int)(3e5+100) ;
    private static final int mod = 998244353 ;
    private static final int[] fact = new int[N+1];

    static {
        fact[0] =1 ;
        for (int i = 1 ; i<N+1 ; i++){
            fact[i] = (int)((fact[i-1]*1L*i)%mod);
        }
    }

    public static void main(String[] args) throws IOException{
//        long l = (mod *1L* N);
//        System.out.println(l);
//        System.out.println(fact[N]);

//        Integer l ;
//        if ((l=null)==null){
//            System.out.println("nuulll");
//        } else {
//            System.out.println("dlkjdlkjdlkjd");
//        }

        solution();

    }


    private static void solution()throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Pair<Integer> [] pairs = new Pair[n];
        Map<Integer,Integer> map1 = new HashMap<>(),map2 = new HashMap<>();
        Map<Pair<Integer>,Integer> map = new HashMap<>();
        for (int i = 0 ; i< n ;i++){
            String [] strs= br.readLine().split(" ");
            int first =Integer.valueOf(strs[0]) ;
            int second =Integer.valueOf(strs[1]) ;
            Pair<Integer> pair =  new Pair<>(first,second);
            //array
            pairs[i] =pair;
            //fS map
            Integer l = map.get(pair);
            if (l==null){
                l=0;
            }
            map.put(pair,++l);
            //F map
            l = map1.get(pair.first);
            if (l==null){
                l=0;
            }
            map1.put(pair.first,++l);
            //S map
            l = map2.get(pair.second);
            if (l==null){
                l=0;
            }
            map2.put(pair.second,++l);
        }

        int tmp = 1, res = fact[n];
        for (Integer i : map1.values()){
            tmp =(int)((tmp*1L*fact[i])%mod);
        }
        res = (res+mod-tmp)%mod ;

        tmp = 1 ;
        for (Integer i : map2.values()){
            tmp =(int)((tmp*1L*fact[i])%mod);
        }
        res = (res+mod-tmp)%mod ;

        tmp = 1 ;
        Arrays.sort(pairs,(a,b)->{
            if (a.first.equals(b.first)){
                if(a.second==b.second){
                    return 0;
                }
                return a.second > b.second? 1 : -1 ;
            }
            return a.first > b.first ? 1: -1 ;
        });
        for (int i =1 ; i<n ;i ++){
            if (pairs[i-1].second>pairs[i].second){
                tmp = 0 ;
                break;
            }
        }
        if (tmp!=0){
            for (Integer i : map.values()){
                tmp =(int)((tmp*1L*fact[i])%mod);
            }
        }
        res = (res+tmp)%mod ;
        System.out.println(res);

    }
}
