Ключевое понимание
Алиса и Боб любят обмениваться сообщениями, но им не нравится, когда кто-то другой читает их переписку. Ваш друг Чарльз очень хочет узнать, что именно они отправляют друг другу, но поскольку Алиса и Боб шифруют свои сообщения, он не может их прочитать, даже если ему удается перехватить зашифрованные сообщения (называемые "шифротекстом").
Рисунок 1: Пример перестановки.
Недавно Чарльз не только перехватил зашифрованное сообщение, но и узнал его исходное содержание (называемое "открытым текстом"). Чтобы помочь ему расшифровать будущие сообщения между Алисой и Бобом, вас просят написать программу, которая поможет ему найти ключ шифрования.
Чарльз сообщил, что знает, что Алиса и Боб используют блочный шифр перестановки. Это означает, что для каждого блока из k символов в сообщении символы внутри блока переупорядочиваются в одну из k! возможных перестановок во время шифрования. Каждая перестановка определяется своим уникальным ключом шифрования. Ключ, соответствующий перестановке, показанной на Рисунке 1, будет каким-то представлением (123456) → (514362). Поскольку ваша задача заключается только в подсчете (возможных) ключей, фактическое представление не имеет значения.
К счастью, Чарльз знает размер блока k, и он уверен, что открытый текст и шифротекст, которые он перехватил, состоят из одного или нескольких полных блоков длиной k (т.е. нет неполных блоков), каждый из которых был зашифрован с использованием одного и того же ключа.
Имея открытый текст M и шифротекст C, которые перехватил Чарльз, ваша программа должна вычислить количество возможных ключей шифрования.
Входные данные
Для каждого теста входные данные содержат три строки:
Одна строка, содержащая положительное целое число k, размер блока (k ≥ 1).
Одна строка, содержащая M, открытый текст (1 ≤ |M| ≤ 100, |M| кратно k).
Одна строка, содержащая C, шифротекст (|C| = |M|).
Открытый текст и шифротекст состоят только из строчных букв.
Выходные данные
Для каждого теста выведите одну строку, содержащую количество возможных ключей шифрования размера k. Это число не превысит 2^63-1. Если невозможно получить M из C с помощью шифра перестановки размера блока k, выведите '0' (число ноль).