eolymp
Задачи

Числа Белла

Числа Белла

Число Белла Bn равно количеству разбиений множества из n элементов на произвольное количество непересекающихся непустых подмножеств. Например, B3 = 5, так как существует 5 возможных разбиений множества:

{a, b, c}: {{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}}, {{a, b, c}}

Дополнительно считаем, что B0 = 1.

Рассмотрим определитель Dn, указанный на рисунке.

prb97

Для заданного простого числа p найти наибольшее целое k, для которого Dn делится на pk.

Входные данные

Каждая строка ввода содержит два целых числа n и p (0 ≤ n, p ≤ 10000). Известно, что p – простое.

Выходные данные

Для каждой пары входных значений n и p в отдельной строке виведите наибольшее целое k, для которого Dn делится на pk.

Лимит времени 0.5 секунд
Лимит использования памяти 64 MiB
Входные данные #1
1 5
3 2
4 2
4 3
10000 3
Выходные данные #1
0
2
5
2
24962375