---

Problem 797

---

Cyclogenic Polynomials

A monic polynomial is a single-variable polynomial in which the coefficient of highest degree is equal to $1$.

Define $\mathcal{F}$ to be the set of all monic polynomials with integer coefficients (including the constant polynomial $p(x)=1$). A polynomial $p(x)\in\mathcal{F}$ is cyclogenic if there exists $q(x)\in\mathcal{F}$ and a positive integer $n$ such that $p(x)q(x)=x^n-1$. If $n$ is the smallest such positive integer then $p(x)$ is $n$-cyclogenic.

Define $P_n(x)$ to be the sum of all $n$-cyclogenic polynomials. For example, there exist ten $6$-cyclogenic polynomials (which divide $x^6-1$ and no smaller $x^k-1$):
$$\begin{aligned}
& x^6-1 & & x^4+x^3-x-1 & & x^3+2x^2+2x+1 & & x^2-x+1\\
& x^5+x^4+x^3+x^2+x+1 & & x^4-x^3+x-1 & & x^3-2x^2+2x-1 & & \\
& x^5-x^4+x^3-x^2+x-1 & & x^4+x^2+1 & & x^3+1 & & 、、
\end{aligned}$$
giving
$$P_6(x)=x^6+2x^5+3x^4+5x^3+2x^2+5x$$
Also define
$$Q_N(x)=\sum_{n=1}^N P_n(x)$$
It’s given that $Q_{10}(x)=x^{10}+3x^9+3x^8+7x^7+8x^6+14x^5+11x^4+18x^3+12x^2+23x$ and $Q_{10}(2) = 5598$.

Find $Q_{10^7}(2)$. Give your answer modulo $1\ 000\ 000\ 007$.

---

成圆多项式

首一多项式是指最高次项系数为$1$的单变量多项式。

定义$\mathcal{F}$为所有整系数首一多项式（包括常数多项式$p(x)=1$）构成的集合。对于多项式$p(x)\in\mathcal{F}$，若存在$q(x)\in\mathcal{F}$和正整数$n$使得$p(x)q(x)=x^n-1$，则称$p(x)$为成圆多项式。若$n$是满足上述条件的最小正整数，则称$p(x)$是$n$-成圆多项式。

定义$P_n(x)$为所有$n$-成圆多项式的和。例如，总共有十个$6$-成圆多项式（整除$x^6-1$但不整除任意更小的$x^k-1$）：
$$\begin{aligned}
& x^6-1 & & x^4+x^3-x-1 & & x^3+2x^2+2x+1 & & x^2-x+1\\
& x^5+x^4+x^3+x^2+x+1 & & x^4-x^3+x-1 & & x^3-2x^2+2x-1 & & \\
& x^5-x^4+x^3-x^2+x-1 & & x^4+x^2+1 & & x^3+1 & &
\end{aligned}$$
因此
$$P_6(x)=x^6+2x^5+3x^4+5x^3+2x^2+5x$$
再定义
$$Q_N(x)=\sum_{n=1}^N P_n(x)$$
已知$Q_{10}(x)=x^{10}+3x^9+3x^8+7x^7+8x^6+14x^5+11x^4+18x^3+12x^2+23x$和$Q_{10}(2) = 5598$。

求$Q_{10^7}(2)$，并将你的答案对$1\ 000\ 000\ 007$取余。

---