---

Problem 632

---

Square prime factors

For an integer $n$, we define the square prime factors of $n$ to be the primes whose square divides $n$. For example, the square prime factors of $1500=2^2\times 3\times 5^3$ are $2$ and $5$.

Let $C_k(N)$ be the number of integers between $1$ and $N$ inclusive with exactly $k$ square prime factors. You are given some values of $C_k(N)$ in the table below.

	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$
$N=10$	$7$	$3$	$0$	$0$	$0$	$0$
$N={10}^2$	$61$	$36$	$3$	$0$	$0$	$0$
$N={10}^3$	$608$	$343$	$48$	$1$	$0$	$0$
$N={10}^4$	$6083$	$3363$	$533$	$21$	$0$	$0$
$N={10}^5$	$60794$	$33562$	$5345$	$297$	$2$	$0$
$N={10}^6$	$607926$	$335438$	$53358$	$3218$	$60$	$0$
$N={10}^7$	$6079291$	$3353956$	$533140$	$32777$	$834$	$2$
$N={10}^8$	$60792694$	$33539196$	$5329747$	$329028$	$9257$	$78$

Find the product of all non-zero $C_k({10}^{16})$. Give the result reduced modulo $1000000007$.

---

平方质因数

对于整数$n$，称平方后能整除$n$的质数为$n$的平方质因数。例如，$1500=2^2\times 3\times 5^3$的平方质因数包括$2$和$5$。

记$C_k(N)$为$1$与$N$之间（含$1$和$N$）恰好有$k$个平方质因数的整数之和。下表给出了部分$C_k(N)$的取值：

	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$
$N=10$	$7$	$3$	$0$	$0$	$0$	$0$
$N={10}^2$	$61$	$36$	$3$	$0$	$0$	$0$
$N={10}^3$	$608$	$343$	$48$	$1$	$0$	$0$
$N={10}^4$	$6083$	$3363$	$533$	$21$	$0$	$0$
$N={10}^5$	$60794$	$33562$	$5345$	$297$	$2$	$0$
$N={10}^6$	$607926$	$335438$	$53358$	$3218$	$60$	$0$
$N={10}^7$	$6079291$	$3353956$	$533140$	$32777$	$834$	$2$
$N={10}^8$	$60792694$	$33539196$	$5329747$	$329028$	$9257$	$78$

求出所有非零的$C_k({10}^{16})$的乘积，并将结果对$1000000007$取余。

---