Задачі
Числа Белла
Числа Белла
Число Белла \textbf{B_n} дорівнює кількості розбиттів множини з \textbf{n} елементів на довільну кількість не порожніх підмножин, що не перетинаються. Наприклад, \textbf{B_3} = 5, оскільки існує 5 можливих розбиттів множини \{\textbf{a}, \textbf{b}, \textbf{c}\}: \{\{\textbf{a}\}, \{\textbf{b}\}, \{\textbf{c}\}\}, \{\{\textbf{a}, \textbf{b}\}, \{\textbf{c}\}\}, \{\{\textbf{a}, \textbf{c}\}, \{\textbf{b}\}\}, \{\{\textbf{a}\}, \{\textbf{b}, \textbf{c}\}\}, \{\{\textbf{a}, \textbf{b}, \textbf{c}\}\}. Додатково вважаємо, що \textbf{B_0} = 1.
Розглянемо визначник \textbf{D_n}, вказаний на малюнку.
\includegraphics{https://static.e-olymp.com/content/f0/f065d04a230f47e10a5d516ae0ba21134eea9b81.gif}
Для заданого простого числа \textbf{p} знайти найбільше ціле \textbf{k}, для якого \textbf{D_n} ділиться на \textbf{p^k}
.
\InputFile
Кожен рядок вводу містить два цілих числа \textbf{n} та \textbf{p} (\textbf{0} ≤ \textbf{n}, \textbf{p} ≤ \textbf{10000}). Відомо, що \textbf{p} -- просте.
\OutputFile
Для кожної пари вхідних значень \textbf{n} та \textbf{p} у окремому рядку вивести найбільше ціле \textbf{k}, для якого \textbf{D_n} ділиться на \textbf{p^k}
.
Вхідні дані #1
1 5 3 2 4 2 4 3 10000 3
Вихідні дані #1
0 2 5 2 24962375