Ключове розуміння
Аліса та Боб люблять обмінюватися повідомленнями, але їм не до вподоби, коли їхні повідомлення читають інші. Ваш друг Чарльз дуже цікавиться тим, що Аліса та Боб надсилають один одному, проте, оскільки вони шифрують свої повідомлення, він не може їх прочитати, навіть якщо йому вдається перехопити зашифровані повідомлення (які називаються "шифротекст").
Рисунок 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' (число нуль).