## Educational Codeforces Round 71 (Rated for Div. 2) D - Number Of Permutations 转

o
osc_ogi0qclx

Educational Codeforces Round 71 (Rated for Div. 2)

D - Number Of Permutations

You are given a sequence of n pairs of integers: (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)] 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 p1,p2,…,pn consisting of n distinct integers from 1 to n (1≤pi≤n). If you apply permutation p1,p2,…,pn to the sequence s1,s2,…,sn you get the sequence sp1,sp2,…,spn. 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⋅105).

The next n lines contains description of sequence s. The i-th line contains two integers ai and bi (1≤ai,bi≤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.

[2,2] [3,1] [1,1]   [3,1] [2,2] [1,1] 符合条件。

`````` 1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 #include<algorithm>
6 #include<map>
7 #include<set>
8 #include<vector>
9 #include<queue>
10 #include<stack>
11 #include<list>
12 //#include<unordered_map>
13 using namespace std;
14 #define ll long long
15 const int inf=1e9+7;
16
17 const int maxn=3e5+10;
18 const int mod=998244353;
19 ll int jiecheng[maxn];//记录阶乘
20
21 pair<int,int> p[maxn];//pair数组
22
23 map<pair<int,int>,int>mp1;//记录重复二元组数
24
25 map<int,int>x;//标记
26 map<int,int>y;
27
28 bool cmp(const pair<int,int> &a,const pair<int,int> &b)
29 {                        //令x递增顺序排
30     if(a.first != b.first)
31         return a.first < b.first;
32     else
33         return a.second < b.second;
34 }
35
36 int main()
37 {
38     ios::sync_with_stdio(false);
39
40     int n;
41     cin>>n;
42
43     x.clear();//初始化
44     y.clear();
45     mp1.clear();
46
47     jiecheng[0]=1;
48     for(int i=1;i<=n;i++)
49     {
50         cin>>p[i].first>>p[i].second;
51         jiecheng[i]=jiecheng[i-1]*i%mod;//算阶乘
52         x[p[i].first]++;//标记
53         y[p[i].second]++;
54         mp1[p[i]]++;//标记二元组
55     }
56
57     sort(p+1,p+n+1,cmp);//排序
58
59     ll int flag=1;
60
61     for(int i=2;i<=n;i++)//看x，y是否同时递增
62     {
63         if(!(p[i-1].first<=p[i].first&&p[i-1].second<=p[i].second))
64         {
65             flag=0;//不符合
66             break;
67         }
68     }
69     ll int ans=0;
70
71     if(flag==1)//x,y同时递增
72     {
73         for(auto it=mp1.begin();it!=mp1.end();it++)
74             flag=flag*jiecheng[it->second]%mod;
75         ans=mod-flag;//减去重复情况
76     }
77
78     ll int res=1;
79
80     for(auto it=x.begin();it!=x.end();it++)//累加x
81         res=res*jiecheng[it->second]%mod;
82     ans=(ans+res)%mod;
83
84     res=1;
85     for(auto it=y.begin();it!=y.end();it++)//累加y
86         res=res*jiecheng[it->second]%mod;
87     ans=(ans+res)%mod;
88
89     ans=(jiecheng[n]-ans+mod)%mod;//全排列减去所有递增为最终答案
90
91     cout<<ans<<endl;
92
93     return 0;
94 }``````

o

### osc_ogi0qclx

CDH5: 使用parcels配置lzo

cloud-coder
2014/07/01
6.8K
1
JavaScript 模板引擎--fragment.js

Fragment.js 允许你加载 html 碎片到任何元素中，只需要使用 data-fragment 属性。 <div data-fragment="fragment.html"></div> 也可通过 JSON 进行加载，如： <div data-fragment-json="fra......

2013/03/24
2.4K
0
CSS 选择器--Q.js

1, 和Sizzle的兼容 Q(expr, context, result, seed) Q.matches 支持Sizzle特别的setFilter伪类如:even,:first,:last,:lt... 支持复杂的:not和:has选择器（和sizzle一样） 2, 结果的正确性 Si...

hackwaly
2012/10/23
4.6K
0
iOS 的 Canvas 和 Audio 实现--Ejecta

Ejecta 是一个快速开源的 JavaScript、Canvas 和 音频实现，适用于 iOS 平台。你可以把它想象成一个只支持显示 Canvas 元素的浏览器，它像一个浏览器却无需浏览器，适用于游戏和动画开发。无...

2012/10/26
4.4K
0
ZimbraBackend

2012/11/04
732
0

SQL 语句大全

GeneralMa

0
0

osc_qv1fwke0
19分钟前
7
0

zhang_rick

0
0

osc_anefoz50
19分钟前
0
0

19分钟前
13
0