tester 解です。

形式的冪級数を用いた解法を紹介します。

\(M=1\) なら答えは明らかに \(N\) です。以降は \(M>1\) の場合を考えます。

\(M\) 以下の素数の個数を \(K\) とします。

\(x=(x_1,\ldots,x_K)\) に対し \(\displaystyle f(x)=\sum_{i=1}^M \prod_{k=1}^K x_k^{v_{p_k}(i)}\) とします。ここで、 \(v_{p_k}(i)\) は \(k\) 番目に小さい素数 \(p_k\) が \(i\) を割り切る回数です。

\(f\) をこのように定義すると、長さを \(n\) に固定した場合の答えは \(\displaystyle S_n=\sum_{i_1,\ldots,i_K}\left\{\prod _{k=1}^K (i_k+1) \right\}\left[\prod_{k=1}^K x_k^{i_k} \right] f^n\) となります。

この式を式変形すると、

\[ \begin{aligned} &\phantom{=}S_n\\ &=\sum_{i_1,\ldots,i_K}\left\{\prod _{k=1}^K (i_k+1) \right\}\left[\prod_{k=1}^K x_k^{i_k} \right] f^n\\ &=\sum_{i_1,\ldots,i_K}\left[\prod_k x_k^{i_k} \right] \frac{\partial^K}{\partial x_1 \cdots\partial x_K}\left(f^n\prod_{k} x_k \right) \\ &=\left.\frac{\partial^K}{\partial x_1 \cdots\partial x_K}\left(f^n\prod_{k} x_k \right)\right|_{x_1,\ldots,x_K=1} \end{aligned} \]

ここで、 \(y_k=x_k-1\) として \(\displaystyle f(y)=\sum_{i=1}^M \prod_{k=1}^K (y_k+1)^{v_{p_k}(i)}\) と置き直すと、

\[ \begin{aligned} &\phantom{=}S_n\\ &=\left.\frac{\partial^K}{\partial y_1 \cdots\partial y_K}\left(f^n\prod_{k} (y_k+1) \right)\right|_{y_1,\ldots,y_K=0}\\ &=\left[\prod_k y_k \right]f^n\prod_{k} (y_k+1) \end{aligned} \]

となります。よって、求める答え \(S\) は

\[ \begin{aligned} &\phantom{=}S\\ &=\sum_{n=1}^N S_n\\ &=\left[\prod_k y_k \right]\left\{\prod_{k} (y_k+1) \right\} \sum_{n=1}^N f^n \\ &=\left[\prod_k y_k \right]\left\{\prod_{k} (y_k+1) \right\} \frac{f-f^{N+1}}{1-f} \\ \end{aligned} \]

\(c=1-f\left(\{0\}^K\right)\left(=1-M\right),\ g=f+c-1\) とすると \(g\left(\{0\}^K\right)=0\) を満たすから、

\[ \begin{aligned} &\phantom{=}S\\ &=\left[\prod_k y_k \right]\left\{\prod_{k} (y_k+1) \right\} \frac{f-f^{N+1}}{c-g} \\ &=\frac1c\left[\prod_k y_k \right]\left\{\prod_{k} (y_k+1) \right\} (f-f^{N+1})\sum_{i=0}^\infty\left(\frac gc\right)^i \\ &=\frac1c\left[\prod_k y_k \right]\left\{\prod_{k} (y_k+1) \right\} (f-f^{N+1})\sum_{i=0}^K\left(\frac gc\right)^i \\ \end{aligned} \]

となります。最後の式変形は \(g\left(\{0\}^K\right)=0\) なので \(K+1\) 乗すると鳩の巣原理よりいずれかの変数の指数が \(2\) 以上になってしまうことから \(K+1\) 乗以上を考える必要は無いことを利用しています。この事実から、計算途中の多項式の係数として持つ必要のある箇所は \(2^K\) 個であることも分かります。

必要な情報のみを持った多項式の乗算は Subset Convolution を用いることで \(O(K^22^K)\) で計算できるので、 \(f^{N+1}\) の計算に繰り返し二乗法を用いることでこの係数は \(O(K^22^K\log N)\) で計算できます。 (参考：Subset Convolution (yosupo judge))

以上でこの問題が解けました。計算量は \(O(K^22^K(K+\log N))\) です。

問題の制約下では \(K\) は \(6\) 以下なので、この制約下では高速に解くことができます。

なお、 \(f^{N+1}\) の計算に二項定理を用いることで計算量を \(O(K^32^K+\log N)\) に改善することもできます。