Шоколадні плитки

Мабуть, всім відомо, що шоколад корисний для людського мозку. Тому учасники національної олімпіади принесли на змагання багато шоколадок, щоб швидше приходили гарні ідеї. Однак шоколаду принесли надто багато, і після змагання в офісі залишилося (N) прямокутних плиток шоколаду, кожна з яких складається з шматків розміром (1 1). Двоє учасників вирішили з'їсти частину залишеного шоколаду, але, оскільки вони вже досить наїлися шоколаду під час змагання, вирішили зробити це у досить незвичній грі за такими правилами.

Гравці роблять ходи по черзі: спочатку перший учасник, потім другий, потім знову перший і так далі. Під час свого ходу учасник обирає одну з плиток шоколаду та виконує одну з наступних операцій:

1. Розламати плитку на дві частини; лінія розлому повинна бути паралельною до сторін плитки і проходити між шматками.

2. Відламати й з’їсти будь-який «рядок» чи «стовпець» плитки, який не є крайовим.

3. Відламати й з’їсти всі шматки плитки, які знаходяться на краю, але після цього має залишитися хоча б один шматок (мінімальний розмір плитки для цієї операції — (3 3)).

Жодну з цих операцій не можна виконати на плитці розміром (1 1), тож усі такі плитки залишаються до кінця гри. Учасник, який не може зробити жодної операції під час свого ходу, програє.

Напишіть програму, яка за даною інформацією про плитки шоколаду, що залишилися після змагання, визначає кількість варіантів першого ходу першого учасника, які гарантують йому перемогу за умови подальшої оптимальної стратегії.