Кодові Перестановки
Ви ось-ось закінчите школу матемагії Гогвортс і відчуваєте гордість за свої досягнення; всі ваші зусилля та наполеглива праця нарешті дали плоди. Ви завжди були успішними у своїх починаннях і зазвичай вважалися взірцем здорового глузду та доброї матемагії. Але ви не такі, як усі; ви провели свої юні роки, таємно займаючись комп'ютерами, пишучи код, щоб виконувати ваше рутинне домашнє завдання за вас. Останнім часом ви навіть почали планувати, як вкласти всі свої матемагічні навички в комп'ютер, щоб повністю усунути потребу в матемагіках! Щоб продемонструвати іншим свою велику далекоглядність, ви плануєте зробити свою випускну церемонію незабутньою.
Для цього вам потрібно зламати сейф вашого заклятого ворога, Волохатого Петра. Сейф захищений кодовим механізмом: усі натуральні числа від 1 до N потрібно ввести в правильному порядку, встановленому Волохатим Петром. На щастя, ви знаєте, що Волохатий, будучи добрим матемагіком, має певну слабкість; у нього є нездорова одержимість числом K. (Наприклад, він завжди представляється K разів, коли знайомиться з новими людьми, що робить його досить дратівливим у спілкуванні.) Тому ви впевнені, що його код, розглянутий як перестановка перших N натуральних чисел, має порядок точно K. (Тобто K є найменшим додатним числом, таким що якщо ви K разів заміните x ∈ {1,...,N} на позицію x в коді Волохатого, ви отримаєте x, з якого почали, для всіх x. Наприклад, порядок перестановки, що відповідає коду 2 3 1, дорівнює 3, оскільки 1 → 3 → 2 → 1 і 2 → 1 → 3 → 2 і 3 → 2 → 1 → 3.) Хоча це не допомагає вам безпосередньо, це значно зменшує кількість кодових введень, які вам, можливо, доведеться спробувати, перш ніж ви знайдете правильний. "Скільки?" - це питання, яке ви зараз обмірковуєте. Ви повинні знати точну кількість, інакше ризикуєте підготувати занадто мало часу для зламу сейфа.
У вас також є певна матемагічна слабкість - можливо, навіть гірша, ніж у Волохатого Петра: через ваш темний задум програмувати матемагічні комп'ютери, ви наполягаєте, що немає чисел, більших за ті, які можна представити знаковим 32-бітним цілим числом, а саме просте число P = 2^31 - 1. Звісно, не повинно бути нічого, що ваші комп'ютери не можуть порахувати. Насправді ви так ненавидите цю верхню межу P, що вирішили створити нову матемагію, де P дорівнює 0. Ха, ось так! (Ну, ви цілком усвідомлюєте, що ви насправді просто рахуєте за модулем P, але це буде достатньо, поки ви не знайдете кращих способів покарати P.) Насправді це виявляється досить перевагою для вас! Наприклад, якщо кількість кодових перестановок, які вам потрібно перевірити, виявиться 2^31, насправді буде лише одна перестановка, яку вам потрібно перевірити, оскільки 2^31 mod P = 1. (Або принаймні ви так думаєте...) Це просто чудово!
Вхідні дані
Вхід складається з двох цілих чисел N (1 ≤ N ≤ 100) та K (1 ≤ K ≤ 2^31 - 1) відповідно.
Вихідні дані
Виведіть кількість перестановок з N елементів порядку K, за модулем 2^31 - 1.