题目609：Π序列

永恒的蓝色梦想

π sequences

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

We say that a sequence of integers u = (u₀, ..., u_m) is a Π sequence if

• u_n≥1 for every _n
• u_n+1 = Π(u_n)
• u has two or more elements
  

For u₀ = 10 there are three distinct Π 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 Π sequences u for which u₀≤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⁸). Give your answer modulo 1000000007.

weiter

机翻：
π序列

为每一个n≥1素数计数函数Π(n)等于素数不超过n.
例如，Π(6)=3，Π(100)=25。

我们说一个整数序列u=(U)0.，你m)是一个Π序列，如果
un≥1n
un+1=Π(un)
u有两个或多个元素
为你0=10有三个不同的Π序列：(10，4)，(10，4，2)和(10，4，2，1)。

让c(u)的元素数。u那不是质数。
让p(n,k)是Π序列的数目u对此你0≤n和c(u) = k.
设P(N)是所有p(N)的乘积n,k)大于0的。
给出：P(10)=3×8×9×3=648，P(100)=31038676032。

寻找P(10)8)。给出你的回答模块1000000007。