لدى 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