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 itertools


def Runs(a, key=lambda k: k):
    i = 0
    while i < len(a):
        j = i
        while j < len(a) and key(a[i]) == key(a[j]):
            j += 1
        if i != j - 1:
            yield i, j - 1
        i = j

def Intersection(x, y):
    # print()
    # print(x)
    # print(y)
    # print()
    result = []
    ai = 0
    bi = 0
    while ai < len(x) and bi < len(y):
        a = x[ai]
        b = y[bi]
        if a[1] < b[0]:
            ai += 1
        elif b[1] < a[0]:
            bi += 1
        elif a[0] <= b[0]:
            if a[1] <= b[1]:
                result.append((b[0], a[1]))
                ai += 1
            else:
                result.append((b[0], b[1]))
                bi += 1
        else:
            if b[1] <= a[1]:
                result.append((a[0], b[1]))
                bi += 1
            else:
                result.append((a[0], a[1]))
                ai += 1
    return result

# import unittest

# class Tester(unittest.TestCase):
#     def test1(self):
#         x = [(1, 2), (3, 4)]
#         y = [(2, 3)]
#         self.assertEqual(Intersection(x, y), [(2, 2), (3, 3)])

#     def test2(self):
#         x = [(1, 2), (3, 4)]
#         y = [(2, 5)]
#         self.assertEqual(Intersection(x, y), [(2, 2), (3, 4)])

#     def test3(self):
#         x = [(1, 2), (3, 4)]
#         y = [(5, 5)]
#         self.assertEqual(Intersection(x, y), [])

#     def test4(self):
#         x = [(1, 3)]
#         y = [(0, 1), (2, 3)]
#         self.assertEqual(Intersection(x, y), [(1, 1), (2, 3)])


# unittest.main()
m1 = 998244353

def IsNonDecreasing(a):
    a = list(a)
    for i in range(len(a)-1):
        if a[i] > a[i+1]:
            return False
    return True

def Factorial(n):
    result = 1
    for i in range(n):
        result *= (i+1)
        result = result % m1
    return result

def Solve(a):
    n = len(a)
    a = list(sorted(a))
    # print('here1')
    do = IsNonDecreasing(x[1] for x in a)
    # print('here2')
    r1 = 1
    x = list(Runs(a, lambda x: x[0]))
    for i, j in x:
        f = Factorial(j - i + 1)
        r1 *= f
        r1 = r1 % m1
    # print('here3')

    r2 = 1
    if not do:
        a = sorted(a, key=lambda x: x[1])
    # print('here4')
    y = list(Runs(a, lambda x: x[1]))
    # print('here5')
    # print(y)
    for i, j in y:
        f = Factorial(j - i + 1)
        r2 *= f
        r2 = r2 % m1
    # print('here6')

    d1 = 0
    if do:
        d1 = 1
        z = Intersection(x, y)
        # print(z)
        for i, j in z:
            f = Factorial(j - i + 1)
            d1 *= f
            d1 = d1 % m1
    # print('here7')
    # print("r1:%s r2:%s d1:%s" % (r1, r2, d1))
    # if d1 == 1:
        # d1 = 0
    return (Factorial(n) - r1 - r2 + d1) % m1

# def Solve1(a):
#     n = len(a)
#     a = list(sorted(a))
#     r1 = 1
#     d1 = 0
#     do = IsNonDecreasing(x[1] for x in a)
#     # print(do)
#     for ai, aj in Runs(a, lambda x: x[0]):
#         k = aj - ai + 1
#         f = Factorial(k)
#         # if f > 1:
#             # print('r1', ai, aj, "%s! = %s" % (k, f))
#         if do:
#             for bi, bj in Runs(a[ai:aj+1], lambda x: x[1]):
#                 f2 = Factorial(bj - bi + 1)
#                 # if f2 > 1:
#                     # print('d1', bi, bj, f2)
#                 f = f // f2
#         r1 *= f

#     r2 = 1
#     if not do:
#         a = sorted(a, key=lambda x: x[1])
#     for bi, bj in Runs(a, lambda x: x[1]):
#         k = bj - bi + 1
#         f = Factorial(k)
#         # if f > 1:
#             # print('r2', bi, bj, "%s! = %s" % (k, f))
#         if do:
#             for ai, aj in Runs(a[bi:bj+1], lambda x: x[1]):
#                 f2 = Factorial(aj - ai + 1)
#                 # if f2 > 1:
#                     # print('d1', ai, aj, f2)
#                 f = f // f2
#         # r2 *= f
#     print(r1, r2, d1)
#     return Factorial(n) - r1 - r2 + (d1)

def Classify(a):
    bad1 = True
    bad2 = True
    for i in range(len(a) - 1):
        if a[i][0] > a[i+1][0]:
                bad1 = False
        if a[i][1] > a[i+1][1]:
                bad2 = False
    if bad1 or bad2:
        return "BAD", bad1, bad2
    else:
        return "GOOD",

import collections
def SolveBrute(a):
    count = collections.Counter()
    for x in itertools.permutations(a):
        c = Classify(x)
        count[c[0]] += 1
        if c[0] == 'BAD':
            # print(x, c)
            if c[1]:
                count['b1'] += 1
            if c[2]:
                count['b2'] += 1
            if c[1] and c[2]:
                count['b12'] += 1
    # print(count)
    return count["GOOD"]


import random
def Generate(n):
    # k = 4
    k = 25000
    return [(random.randint(1, k), random.randint(1, k)) for _ in range(n)]

import sys
def Run():
    f = sys.stdin
    t, = next(f).split()
    t = int(t)
    r = []
    for _ in range(t):
        i, j = next(f).split()
        r.append((int(i), int(j)))
    # for line in :
        # n = line.split()
    print(Solve(r))

Run()
# a = Generate(300000)
# print(Solve(a))

# for _ in range(10000):
#     a = Generate(5)
#     if SolveBrute(a) != Solve(a):
#         print(a)
# a = Generate(6)
# a = ((1, 0), (1, 1), (1, 2), (1, 2), (2, 2), (3, 2))
# # a = ((1, 0), (1, 1), (1, 2), (2, 2), (3, 2))
# # a = ((1, 3), (1, 2), (2, 2))
# a = ((1, 1), (1, 1), (2, 3))
# a = [(3, 3), (3, 3), (3, 2), (2, 2)]
# a = [(1, 1), (4, 4), (3, 3), (1, 3)]
# print(SolveBrute(a))
# print(Solve(a))