ל־Farmer John יש $N$ פרות בחווה שלו ($2 \leq N \leq 2\cdot 10^5$), הממוספרות לנוחותנו $1 \dots N$. פרה $i$ נמצאת בקואורדינטות השלמות $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John רוצה לבחור שתי קבוצות למשחק mooball!

אחת הקבוצות תהיה הקבוצה ה״אדומה״, והאחרת תהיה הקבוצה ה״כחולה״. יש רק כמה דרישות מהקבוצות. אף קבוצה אינה יכולה להיות ריקה, וכל אחת מ־$N$ הפרות יכולה להשתייך לכל היותר לקבוצה אחת (ייתכן שלא תשתייך לאף אחת). הדרישה הנוספת היחידה נובעת מתכונה ייחודית של mooball: רשת באורך אינסופי, שיש להציב כקו אופקי או אנכי במישור בקואורדינטה שאינה שלמה, כגון $x = 0.5$. FJ חייב לבחור קבוצות כך שיהיה אפשר להפריד ביניהן באמצעות רשת. הפרות אינן מוכנות לזוז כדי לאפשר זאת.

עזרו לחקלאי! חשבו עבור Farmer John את מספר הדרכים לבחור קבוצה אדומה וקבוצה כחולה המקיימות את הדרישות לעיל, מודולו $10^9+7$.

קלט

השורה הראשונה של הקלט מכילה מספר שלם יחיד $N.$

כל אחת מ־$N$ שורות הקלט הבאות מכילה שני מספרים שלמים $x_i$ ו־$y_i$ המופרדים ברווח. מובטח שה־$x_i$ מהווים תמורה של $1\dots N$, וכך גם ה־$y_i$.

פלט

מספר שלם יחיד המציין את מספר הדרכים לבחור קבוצה אדומה וקבוצה כחולה המקיימות את הדרישות לעיל, מודולו $10^9+7$.

דוגמאות

קלט 1

2
1 2
2 1

פלט 1

2

הערה

אפשר לבחור את פרה 1 לקבוצה האדומה ואת פרה 2 לקבוצה הכחולה, או להפך. בשני המקרים אפשר להפריד בין הקבוצות באמצעות רשת (למשל, $x=1.5$).

קלט 2

3
1 1
2 2
3 3

פלט 2

10

הערה

להלן כל עשר הדרכים האפשריות לשייך את הפרות לקבוצות; התו ה־$i$ מציין את הקבוצה של הפרה ה־$i$, או . אם הפרה ה־$i$ אינה משתייכת לקבוצה.

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

קלט 3

3
1 1
2 3
3 2

פלט 3

12

הערה

להלן כל שתים עשרה הדרכים האפשריות לשייך את הפרות לקבוצות:

RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR

קלט 4

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

פלט 4

441563023

הערה

הקפידו להדפיס את התשובה מודולו $10^9+7$.

תת־משימות

• קלט 5: $N\le 10$
• קלטים 6-9: $N\le 200$
• קלטים 10-13: $N\le 3000$
• קלטים 14-24: אין מגבלות נוספות.

מחבר הבעיה: Dhruv Rohatgi