---

Problem 78

---

Coin partitions

Let $p(n)$ represent the number of different ways in which $n$ coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so $p(5)=7$.

$$
\begin{aligned}
&\text{OOOOO}\\
&\text{OOOO O}\\
&\text{OOO OO}\\
&\text{OOO O O}\\
&\text{OO OO O}\\
&\text{OO O O O}\\
&\text{O O O O O}
\end{aligned}
$$

Find the least value of $n$ for which $p(n)$ is divisible by one million.

---

硬币分拆

记$p(n)$是将$n$枚硬币分拆成堆的不同方式数。例如，$5$枚硬币分拆成堆有$7$种的不同方式，因此$p(5)=7$。

$$
\begin{aligned}
&\text{OOOOO}\\
&\text{OOOO O}\\
&\text{OOO OO}\\
&\text{OOO O O}\\
&\text{OO OO O}\\
&\text{OO O O O}\\
&\text{O O O O O}
\end{aligned}
$$

求最小的使$p(n)$能被一百万整除的$n$。

---