Как вы уже поняли, Лимак — полярный медвежонок. Следуя древней традиции, его медвежья семья приготовила новогодний торт. А Лимак очень любит тортики.
Новогодний торт имеет форму строго выпуклого многоугольника из n вершин.
Родители не разрешают Лимаку есть больше половины торта, потому что иначе у него начнётся аллергия. Немного подумав, они решили выбрать ровно одну из n·(n - 3) / 2 диагоналей и разрезать торт вдоль неё. После этого Лимаку достанется меньшая по площади часть (любая, если они равны).
Лимак понимает правила, но всё равно будет очень несчастен, если не доставшаяся ему часть будет сильно больше. Его неудовольствие будет равно разнице между площадью большей и меньшей частей, умноженной на 2. Несложно заметить, что в данной задаче неудовольствие Лимака всегда выражается целым числом.
Существует n·(n - 3) / 2 возможных сценариев разрезания торта на две части. Вычислите суммарное неудовольствие Лимака по всем сценариям по модулю 109 + 7.
Примечание
В первом примере возможные значения неудовольствия Лимака равны 0, 18, 18, 24, 30.