Задачі
Числа Белла
Числа Белла
Число Белла B_n дорівнює кількості розбиттів множини з n елементів на довільну кількість не порожніх підмножин, що не перетинаються. Наприклад, B_3 = 5, оскільки існує 5 можливих розбиттів множини {a, b, c}: {{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}}, {{a, b, c}}. Додатково вважаємо, що B_0 = 1.
Розглянемо визначник D_n, вказаний на малюнку.
Для заданого простого числа p знайти найбільше ціле k, для якого D_n ділиться на p^k
.
Вхідні дані
Кожен рядок вводу містить два цілих числа n та p (0 ≤ n, p ≤ 10000). Відомо, що p – просте.
Вихідні дані
Для кожної пари вхідних значень n та p у окремому рядку вивести найбільше ціле k, для якого D_n ділиться на p^k
.
Приклад
Вхідні дані #1
1 5 3 2 4 2 4 3 10000 3
Вихідні дані #1
0 2 5 2 24962375