|
Шифр «Решетка»
(Время: 1 сек. Память: 16 Мб Сложность: 54%)
Рассмотрим перестановочный шифр, называемый «Решетка» («перестановочный» означает, что символы, составляющие послание, не изменяются, но меняются местами). Суть его заключается в следующем. Выбирается четное число n, затем в квадрате n×n вырезается n2/4 клеток. При этом клетки выбираются так, что если наложить решетку на квадрат n х n, и затем последовательно развернуть ее на 90, 180 и 270 градусов, то каждый раз квадратики, совмещенные с вырезанными клетками, будут различны.
Такой квадрат n×n называется «правильным ключом». Ваша задача посчитать количество «правильных ключей». Так как это число может быть очень большим, мы предлагаем Вам найти его значение по модулю m. Ключи, получаемые поворотом на 90, 180 и 270 градусов считаются различными.
Входные данные
Входной файл INPUT.TXT содержит целые числа n и m (2 ≤ n, m ≤ 106), n - четно.
Выходные данные
В выходной файл OUTPUT.TXT выведите количество «правильных ключей» размером n×n по модулю m.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 100 | 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
