codeforces1027D Number Of Permutations（容斥）_综合

D. Number Of Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence of nn pairs of integers: (a1,b1),(a2,b2),…,(an,bn)(a1,b1),(a2,b2),…,(an,bn). 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)]s=[(1,2),(3,2),(3,1)] is bad because the sequence of first elements is sorted: [1,3,3][1,3,3];
s=[(1,2),(3,2),(1,2)]s=[(1,2),(3,2),(1,2)] is bad because the sequence of second elements is sorted: [2,2,2][2,2,2];
s=[(1,1),(2,2),(3,3)]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)]s=[(1,3),(3,3),(2,2)] is good because neither the sequence of first elements ([1,3,2])([1,3,2]) nor the sequence of second elements ([3,3,2])([3,3,2]) is sorted.

Calculate the number of permutations of size nn such that after applying this permutation to the sequence ss it turns into a good sequence.

A permutation pp of size nn is a sequence p1,p2,…,pnp1,p2,…,pn consisting of nn distinct integers from 11 to nn (1≤pi≤n1≤pi≤n). If you apply permutation p1,p2,…,pnp1,p2,…,pn to the sequence s1,s2,…,sns1,s2,…,sn you get the sequence sp1,sp2,…,spnsp1,sp2,…,spn. For example, if s=[(1,2),(1,3),(2,3)]s=[(1,2),(1,3),(2,3)] and p=[2,3,1]p=[2,3,1] then ss turns into [(1,3),(2,3),(1,2)][(1,3),(2,3),(1,2)].

Input

The first line contains one integer nn (1≤n≤3?1051≤n≤3?105).

The next nn lines contains description of sequence ss. The ii-th line contains two integers aiai and bibi (1≤ai,bi≤n1≤ai,bi≤n) — the first and second elements of ii-th pair in the sequence.

The sequence ss may contain equal elements.

Output

Print the number of permutations of size nn such that after applying this permutation to the sequence ss it turns into a good sequence. Print the answer modulo 998244353998244353 (a prime number).

Examples

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

output

Copy

Note

In first test case there are six permutations of size 33:

if p=[1,2,3]p=[1,2,3], then s=[(1,1),(2,2),(3,1)]s=[(1,1),(2,2),(3,1)] — bad sequence (sorted by first elements);
if p=[1,3,2]p=[1,3,2], then s=[(1,1),(3,1),(2,2)]s=[(1,1),(3,1),(2,2)] — bad sequence (sorted by second elements);
if p=[2,1,3]p=[2,1,3], then s=[(2,2),(1,1),(3,1)]s=[(2,2),(1,1),(3,1)] — good sequence;
if p=[2,3,1]p=[2,3,1], then s=[(2,2),(3,1),(1,1)]s=[(2,2),(3,1),(1,1)] — good sequence;
if p=[3,1,2]p=[3,1,2], then s=[(3,1),(1,1),(2,2)]s=[(3,1),(1,1),(2,2)] — bad sequence (sorted by second elements);
if p=[3,2,1]p=[3,2,1], then s=[(3,1),(2,2),(1,1)]s=[(3,1),(2,2),(1,1)] — good sequence.

题意：

n个二维数对(ai,bi)，求将n个数对排列之后，按ai和bi排序都不是递增的。这样的排列有多少个。
分析：

ans=n！-cnt1-cnt2+cnt12

cnt1：表示以ai升序的排列

cnt2：表示以bi升序的排列

cnt12：表示ai和bi都升序的排列

cnt1求法：cnt1=c1！*c2！*c3！.......，c1表示a数组元素个数。

cnt2求法同理

cnt12求法：

不存在：按第一个关键字和第二个关键字排序，如果第二个关键字不满足递增则是0。

存在：跟cnt1求法类似，求两个关键字看出一个元素即可

#include <bits/stdc++.h>using namespace std;
typedef long long LL;const int N = 3e5 + 100;
const int MOD = 998244353;int n;
pair<int, int> a[N];
LL f[N];int main()
{f[0]=1;for(int i=1;i<N;i++){f[i]=(i*f[i-1])%MOD;}scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d%d", &a[i].first, &a[i].second);LL ans=f[n];for(int t=1;t<=2;t++){sort(a+1,a+n+1);LL res=1;int i=1;while(i<=n){int j=i+1;while(j<=n&&a[i].first==a[j].first){j++;}res=((res%MOD)*(f[j-i]%MOD))%MOD;i=j;}ans=(ans-res+MOD)%MOD;while(ans<0)ans+=MOD;for(int i=1;i<=n;i++){swap(a[i].first,a[i].second);}}sort(a+1,a+n+1);LL res=1;int l=1;while(l<=n){int r=l+1;while(r<=n&&a[l]==a[r])r++;res=((res%MOD)*(f[r-l]%MOD))%MOD;l=r;}for(int i = 2; i <= n; ++i)if(a[i - 1].second > a[i].second)res = 0;ans=(ans+res)%MOD;printf("%lld\n", ans);return 0;
}