Зрошувачі
У фермера Джона є велике поле, і він планує засіяти частину його солодкою кукурудзою. Після огляду поля, Джон виявив, що воно має форму квадрата розміром (n − 1) * (n − 1). Південно-західний кут поля знаходиться в координаті (0, 0), а північно-східний — в координаті (n - 1, n - 1).
На деяких цілочисельних координатах встановлені двоголові зрошувачі, які розбризкують воду та добрива. Зрошувач, розташований у координаті (i, j), поливає ділянки поля на північ і схід від себе, а удобрює ділянки на південь і захід. Формально, він поливає всі координати (x, y), для яких n ≥ x ≥ i і n ≥ y ≥ j, і удобрює всі координати (x, y), для яких 0 ≤ x ≤ i і 0 ≤ y ≤ j.
Фермер Джон хоче посадити солодку кукурудзу в прямокутнику, вирівняному по осях, з цілочисельними кутовими координатами. Щоб цукрова кукурудза росла, всі точки в прямокутнику повинні бути поливані та удобрені зрошувачами. Прямокутник також повинен мати позитивну площу, інакше фермер Джон не зможе вирощувати в ньому кукурудзу.
Допоможіть фермеру Джону визначити кількість прямокутників з позитивною площею, на яких він міг би вирощувати солодку кукурудзу. Оскільки це число може бути великим, виведіть залишок від цього числа за модулем 10^9 + 7.
Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 10^5) — розмір поля. Кожен з наступних n рядків містить два цілі числа. Якщо ці числа i і j, де 0 ≤ i, j ≤ n − 1, то вони позначають зрошувач, розташований в координаті (i, j).
Гарантується, що в кожному стовпці є рівно один зрошувач і в кожному рядку є рівно один зрошувач. Тобто немає двох зрошувачів з однаковою координатою x, і немає двох зрошувачів з однаковою координатою y.
Вихідні дані
Виведіть єдине ціле число: кількість прямокутників з позитивною площею, які повністю зрошені і повністю удобрені, за модулем 10^9 + 7.