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

Автор:Г. Гренкин, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
2
4
6
3
5
20

0.040s 0.007s 17