G. Шинэ жил ба бялуу

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лимак бол бяцхан туйлын баавгай юм.Нэгэн хуучин уламжлалын дагуу,түүний баавгайн гэр бүл шинэ жилийн бялуу хийхээр бэлджээ.Мөн Лимак бялуунд дуртай ажээ.

Таны мэдэж байгаачлан, шинэ жилийн бялуу нь заавал $n$ ширхэг орой бүхий гүдгэр олон өнцөгт байх юм.

Эцэг эх нь Лимак-ыг өвдөж болох учраас бялууны талаас илүүг идэхийг зөвшөөрөхгүй.Хэсэг бодсоны дараа тэд бялууг $n*(n - 3) / 2$ диагоналиудын нэгийнх нь дагуу хуваахаар шийджээ.Дараа нь Лимак их биш зүсмийг авах юм.

Лимак дүрмийг ойлгож байгаа боловч хэрэв 2-дахь зүсэм нь илүү том байвал тэрээр баяртай байхгүй ажээ.Лимак-ын урам хугаралт нь 2 зүсмийн талбайн зөрүүг 2-оор үржүүлсэнтэй тэнцүү байх юм.Өгөгдсөн шаардлагуудын хувьд уг утга нь бүхэл тоо байх нь баттай юм.

Нийт $n*(n - 3) / 2$ ширхэг боломжит хуваалт байна.Тэдгээрийг бүгдийн бодолцон Лимак-ын урам хугаралтын утгуудын нийлбэрийг $10^{9} + 7$ модулаар бодож олно уу.

Оролт

Эхний мөрөнд бялууг тэмдэглэх олон өнцөгтийн оройн тоог илэрхийлэх ганц бүхэл тоо $n$ ($4 ≤ n ≤ 500 000$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд $i$-дахь цэгийн координатууд болох 2 бүхэл тоо $x_{i}$ болон $y_{i}$ ($|x_{i}|, |y_{i}| ≤ 10^{9}$) өгөгдөнө.

Бүх цэгүүд ялгаатай байх ба олон өнцөгт нь заавал гүдгэр бөгөөд цэгүүд нь цагийн зүүний дагуу дарааллаар өгөгдөнө.

Гаралт

Бүх боломжит хуваалтуудын Лимак-ын урам хугаралтын утгуудын нийлбэрийг $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5
2 4
2 7
5 7
5 4
3 -2
Гаралт
90
Оролт
4
-1000000000 -5000000
0 1234567
1 1
-5 -100000000
Гаралт
525185196
Оролт
8
-10 0
-6 6
0 10
6 6
10 0
6 -6
0 -10
-6 -6
Гаралт
5216

Тэмдэглэл

Эхний жишээнд Лимак-ын урам хугаралтын боломжит утгууд нь $0, 18, 18, 24, 30$ байх юм.

Сэтгэгдлүүдийг ачааллаж байна...