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取模。