e-olymp
Задачи

Числа Белла

Числа Белла

Число Белла 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 (0n, p10000). Известно, что p – простое.

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

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

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