Задача E. Y-хромосома ≡

Условие

Не только земляне наблюдают за Марсом и находят там воду, но и марсиане активно наблюдают за землянами в недавно построенный телескоп. Марсиане удивились: среди людей почти поровну мужчин и женщин, в то время как мужчин-марсиан совсем мало. Поэтому жители красной планеты решили подать сигнал другим планетам о том, что им не хватает Y-хромосомы.

На Марсе есть квадратное световое табло, разделённое на N × N квадратиков. Каждый квадратик может либо светиться, либо не светиться. Требуется, чтобы на табло появилась буква Y в виде русской буквы У.

Буква должна состоять из двух диагональных линий. Первая линия должна идти слева направо и снизу вверх под углом 45°, начинаться она может с любого места. Вторая линия должна начинаться с любого не крайнего квадратика первой линии и идти влево и вверх (также под углом 45°) до тех пор, пока не достигнет самой левой горизонтали или самой верхней вертикали первой линии. В первой (большой) диагонали должно быть не менее 3-х клеток. Примеры таких букв показаны на рисунке.

Сколько существует способов изобразить букву Y на табло N × N? Буквы, отличающиеся размерами и/или местом, либо положением второй (маленькой) диагонали, считаются различными.

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

Входной файл содержит единственное целое число N.

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

Выходной файл должен содержать целое число — количество способов.

Ограничения

3 ≤ N ≤ 100

Примеры тестов

3

1

4

6

5

20

Разбор

Сначала выберем объемлющий квадрат для буквы размером k × k квадратиков, 3 ≤ k ≤ N. Это можно сделать (N − k + 1)² способами.

Для каждого такого квадрата выбрать маленькую диагональ можно (k − 2) способами. Таким образом, ответ равен ∑Nk = 3(k − 2)(N − k + 1)².

Ответ можно привести к другому виду: 112(N − 2)(N − 1)² N.