---

Problem 609

---

$\pi$ sequences

For every $n\ge 1$ the prime-counting function $\pi (n)$ is equal to the number of primes not exceeding $n$.
E.g. $\pi (6)=3$ and $\pi (100)=25$.

We say that a sequence of integers $u=(u_0,\cdots ,u_m)$ is a $\pi$ sequence if

• $u_n\ge 1$ for every $n$
• $u_{n+1}=\pi (u_n)$
• $u$ has two or more elements

For $u_0=10$ there are three distinct $\pi$ sequences: (10,4), (10,4,2) and (10,4,2,1).

Let $c(u)$ be the number of elements of $u$ that are not prime.
Let $p(n,k)$ be the number of $\pi$ sequences $u$ for which $u_0\le n$ and $c(u)=k$.
Let $P(n)$ be the product of all $p(n,k)$ that are larger than 0.
You are given: P(10)=3×8×9×3=648 and P(100)=31038676032.

Find $P({10}^8)$. Give your answer modulo 1000000007.

---

$\pi$序列

对于任意$n\ge 1$，素数计数函数$\pi (n)$表示不超过$n$的素数数目。
例如，$\pi (6)=3$以及$\pi (100)=25$。

我们称序列$u=(u_0,\cdots ,u_m)$为$\pi$序列，如果

• 对于任意$n$，$u_n\ge 1$
• $u_{n+1}=\pi (u_n)$
• $u$中包含至少两个元素

对于$u_0=10$，有三个不同的$\pi$序列：(10,4)，(10,4,2)和(10,4,2,1)。

记$c(u)$为序列$u$中非素数元素的数目。
记$p(n,k)$为满足$u_0\le n$和$c(u)=k$的$\pi$序列$u$的数目。
记$P(n)$为所有大于0的$p(n,k)$的乘积。
已知：P(10)=3×8×9×3=648以及P(100)=31038676032。

求$P({10}^8)$，并将答案对1000000007取模。

---