U201721 小 C 的质数

小 C 是一位卷王。他经常会做一些奇奇怪怪的题。

小 C 最近在做和质数有关的题。今天他遇到了这样一个问题： 定义函数 $P(n)=\begin{cases}1\;( n\text{ 是质数})\\0\;(n\text{ 不是质数})\end{cases},f(i,k)=k^iP(i)$。给定正整数 $n,k$，你需要求出 $\left(\sum\limits_{i=2}^{n}f(i,k)\right)\bmod\left(10^9+7\right)$ 的值。 然而小 C 并不能解决这个问题，所以他想让精通 OI 的你帮帮他。 **请注意题目不寻常的时空限制和各子任务之间不同的数据规模。**

两个正整数 $n$ 和 $k$。

共一个数，表示答案。

**【样例1解释】** 小于等于 $11$ 的数中，$2,3,5,7,11$ 满足 $P(i)=1$，因此答案即为 $2^2+2^3+2^5+2^7+2^{11}=2220$。 **【样例3提示】** 模 $10^9+7$ 之前的答案是 $34631818207$，但是要注意取模的问题。 **【数据规模与约定】** **本题采用捆绑测试。** |子任务编号|$n$|$k$|时间限制|空间限制|分值| | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | |$\text{Subtask 1}$|$5\leqslant n\leqslant 10^8$|$1\leqslant k\leqslant 10^8$|$\text{2s}$|$\text{256M}$|$10$| |$\text{Subtask 2}$|$5\leqslant n\leqslant 10^{13}$|$k=1$|$\text{5s}$|$\text{512M}$|$25$| |$\text{Subtask 3}$|$5\leqslant n\leqslant 10^9$|$1\leqslant k\leqslant 10^8$|$\text{2s}$|$\text{256M}$|$25$| |$\text{Subtask 4}$|$5\leqslant n\leqslant 10^9$|$1\leqslant k\leqslant 10^8$|$\text{2s}$|$\text{4M}$|$40$| 对于 $100\%$ 的数据，满足 $5\leqslant n\leqslant 10^{13},1\leqslant k\leqslant 10^8$。