Problems
Bell numbers
Bell numbers
A Bell number \textbf{B_n} is equal to the quantity of ways, in which a set of \textbf{n} elements can be partitioned into disjoint non-empty subsets. For example, \textbf{B_3} = 5, because we have 5 possible partitions of the set \{\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}\}\}.
Additionally consider, that \textbf{B_0} = 1.
Regard a determinant \textbf{D_n}, given on the figure.
\includegraphics{https://static.e-olymp.com/content/f0/f065d04a230f47e10a5d516ae0ba21134eea9b81.gif}
For a given prime number \textbf{p} find the greatest integer \textbf{k}, for which \textbf{D_n} is divisible by \textbf{p^k}
.
\InputFile
Each line of input contains two integers \textbf{n} and \textbf{p} (\textbf{0} ≤ \textbf{n}, \textbf{p} ≤ \textbf{10000}). It is known, that \textbf{p} is prime.
\OutputFile
For each pair of input values \textbf{n} and \textbf{p} on a separate line output the greatest integer \textbf{k}, for which \textbf{D_n} is divisible by \textbf{p^k}
Input example #1
1 5 3 2 4 2 4 3 10000 3
Output example #1
0 2 5 2 24962375