G. Новый год и торт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы уже поняли, Лимак — полярный медвежонок. Следуя древней традиции, его медвежья семья приготовила новогодний торт. А Лимак очень любит тортики.

Новогодний торт имеет форму строго выпуклого многоугольника из n вершин.

Родители не разрешают Лимаку есть больше половины торта, потому что иначе у него начнётся аллергия. Немного подумав, они решили выбрать ровно одну из n·(n - 3) / 2 диагоналей и разрезать торт вдоль неё. После этого Лимаку достанется меньшая по площади часть (любая, если они равны).

Лимак понимает правила, но всё равно будет очень несчастен, если не доставшаяся ему часть будет сильно больше. Его неудовольствие будет равно разнице между площадью большей и меньшей частей, умноженной на 2. Несложно заметить, что в данной задаче неудовольствие Лимака всегда выражается целым числом.

Существует n·(n - 3) / 2 возможных сценариев разрезания торта на две части. Вычислите суммарное неудовольствие Лимака по всем сценариям по модулю 109 + 7.

Входные данные

В первой строке записано единственное целое число n (4 ≤ n ≤ 500 000) — количество вершин в строго выпуклом многоугольнике, описывающем торт.

В каждой из следующих n строк записано два целых числа xi и yi (|xi|, |yi| ≤ 109) — координаты i-й точки.

Гарантируется, что все точки различны, многоугольник является строго выпуклым и точки даны в порядке обхода по часовой стрелке.

Выходные данные

Выведите сумму неудовольствия Лимака по всем возможным вариантам разрезания торта на две части по модулю 109 + 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.