3-й этап Республиканской олимпиады по информатике 2022-2023, 1й тур

Есеп C. Жалпы аудан

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Альтаирге жиі қызықты сыйлықтар беріледі. Бұл жолы Ариф оған ұшақта әртүрлі нүктелер жиынын берді, әрине ол Арифке алғыс айтты. Бірақ ол бұл нүктелермен не істеу керектігін мүлде білмейді, сондықтан ол есеп ойлап тапты. Альтаир $S$ жиынындағы барлық нүктелерді қамтитын, жақтары координат осьтеріне параллель, ең кішкентай тіктөртбұрыштың ауданын есептейтін $f(S)$ функциясын анықтады (егер нүкте тіктөртбұрыштың ішінде немесе шекарасында болса, тіктөртбұрыш оны қамтитын болып саналады). Бірақ мұндай функцияны есептеу оған тым қарапайым және қызықсыз болып көрінеді, сондықтан ол берілген нүктелердің барлық мүмкін бос емес ішкі жиындарыны бойынша $f$ функцияларының қосындысын тапқысы келеді. Альтаир үлкен сандарды қалай пайдалану керектігін білмейтіндіктен және жауап тым үлкен болатындықтан, оның $10^9 + 7$-ға бөлген кездегі қалдығын есептеу керек.

Формат входного файла

Бірінші жолда бір натуралды сан $n$ ($1 <= n <= 10^5$) беріледі — сыйлықтағы нүктелер саны. Сосын $n$ жол беріледі, $i$-ші жолда екі бүтін сан $x_i$, $y_i$ ($1 <= x_i, y_i <= 10^9$) жазылған — $i$-ші нүктенің координаттары.

Формат выходного файла

Бір сан шығарыңыз - $10^9 + 7$ модулі бойынша есептің жауабы.

Пример:

Вход

3
4 10
5 7
7 9

Ответ

19

Замечание

Мысалды қарастырайық. Бұл мысалды 7 бос емес ішкі жиын бар. Бірінші және екінші нүктелерден тұратын ішкі жиынның тіктөртбұрышының ауданы: $f(\{1, 2\}) = 3$. $f(\{1\}) = f(\{2\}) = f(\{3\}) = 0$ $f(\{1, 2\}) = 3$ $f(\{1, 3\}) = 3$ $f(\{2, 3\}) = 4$ $f(\{1, 2, 3\}) = 9$ Барлығының қосындысы $f(S)$ -- $19$. ( Altair Ashurov )

Комментарий/решение