Перекидання карточок

Limits: 2 sec., 256 MiB

Марічка дуже любить різноманітні карти та картки. Починаючи від карти Нової Зеландії до карток з гри «Намчкін». Сьогодні Зеник подарував їй нову колоду карт.

Колода складається з \(n\) карток, на двох сторонах яких написано по числу. Нові блискучі картки їй так сподобалися, що вона вирішила скласти з них зростаючу послідовність.

Для цієї послідовності Марічка розставить усі картки в деякому порядку і для кожної з них вибере, якою стороною догори вона буде лежати. Отримана послідовність чисел на картках обов’язково повинна бути строго зростаючою. Їй так сподобався цей процес з блискучими реквізитами, що вона вирішила скласти не одну, не дві, а всі можливі зростаючі послідовності. Послідовності вважаються різними, якщо існує позиція в якій числа відрізняються

Марічка дуже швидко розкладає картки — по одному набору за секунду.

Завдання для вас: знайдіть, скільки часу Марічка розкладатиме карти і виведіть остачу від ділення цього числа на просте число \(10^9 + 7\).

Input

У першому рядку задано одне ціле число \(n\) — кількість карток.

У кожному з наступних \(n\) рядків задано по два цілих числа \(a_i\) і \(b_i\) — числа записані на двох сторонах \(i\)-ї картки.

Output

У єдиному рядку виведіть одне ціле число — час який Марічка розкладатиме карти по модулю \(10^9 + 7\).

Constraints

\(1 \leq n \leq 10^5\),

\(1 \leq a_i, b_i \leq 10^6\),

у 5 тестах усі \(a_i\) і \(b_i\) різні.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 6 6 1 2 4 5 2 3	6

Input (stdin) сopy	Output (stdout) сopy
3 2 3 2 2 3 2	0

Notes

У першому тесті є такі варіанти послідовності:

• (2, 3, 4, 6);

• (2, 3, 5, 6);

• (1, 2, 4, 6);

• (1, 2, 5, 6);

• (1, 3, 4, 6);

• (1, 3, 5, 6).