Кодовые Перестановки
Вы скоро заканчиваете школу матемагии Хагвортс и вполне довольны собой; все ваши усилия и тяжелая работа наконец-то окупились. Будучи успешным в большинстве своих начинаний, вы обычно становитесь образцом здравого смысла и хорошей матемагии. Однако вы выделяетесь не только тем, что в юности тайно взламывали компьютеры, создавая код для выполнения рутинных домашних заданий, но и тем, что недавно начали планировать, как загрузить все свои матемагические навыки в компьютер, чтобы полностью устранить необходимость в матемагиках! Чтобы продемонстрировать другим свою дальновидность, вы планируете сделать свою церемонию выпуска незабываемой.
Для этого вам нужно взломать сейф вашего заклятого врага, Хэри Петера. Сейф заперт кодовым механизмом: все натуральные числа от 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.