Торообразні квитки

На планеті Айсем планується виготовлення пасажирських квитків для нового виду транспорту у формі тора.

Кожен тор створюється з чорного прямокутного гумового листа розміром N \times M клітинок. Деякі з цих клітинок позначені білим кольором, що вказує на пункти відправлення та призначення.

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

Квиток слід склеїти наступним чином. Спочатку потрібно з'єднати дві довгі сторони, утворюючи циліндр. Основи циліндра - це кола, довжина яких дорівнює довжині коротшої сторони початкового шматка гуми. Потім основи циліндра з'єднуються і склеюються так, щоб склеєні клітинки належали одному й тому ж рядку. Внутрішня та зовнішня сторони шматка відрізняються.

Отриманий тор є дійсним квитком.

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

Матеріал квитка та властивості клею настільки якісні, що шов неможливо виявити, що створює певні проблеми. Один і той же тор можна виготовити з різних початкових шматків. Також з одного шматка можна створити тори, які виглядають трохи по-різному.

Завдання транспортних компаній на Айсемі полягає в підрахунку кількості різних маршрутів, які вони можуть організувати за таких умов:

• квитки на різні маршрути повинні бути представлені різними торами;

• якщо певний шматок гуми вже був використаний для позначення якогось маршруту, його не можна використовувати як квиток для іншого маршруту.

Допоможіть обчислити кількість маршрутів, які можуть організувати транспортні компанії.