Степені перестановок#1140
Нехай — натуральне число, і S = \{ 1, 2, 3, \ldots, N \}. Функція f : S \to S називається красивою, якщо існує бієктивна функція g : S \to S така, що для кожного із виконується рівність g(g(g(\ldots g(x) \ldots ))) = f(x), де застосовується рівно разів.
Потрібно знайти кількість красивих функцій. Оскільки відповідь може бути дуже великою, виведіть результат по модулю .
Вхідний файл складається з одного рядка, що містить натуральні числа і (N \leq 2000, d \leq 10^{18}).
Виведіть кількість красивих функцій для заданих і по модулю .
Приклад 1