class="markdown_views prism-atom-one-light"> Description 给出一个长度为$k$的序列$A_1,...,A_k$，定义$f(m)$为满足以下条件的$C$序列的数量： 1.若$A_i=-1$则$C_i$可以取$[0,m)$中任意整数，否则$C_i=A_i\%m$ 2.同余方程$sumlimits_{i=1}^kC_ix_iequiv 1(mod m)$有解 给出一整数$n$，求$sumlimits_{m=1}^nf(m)$ Input 第一行一整数$T​$表示用例组数，每组用例首先输入两个整数$k,n​$，之后输入一长度为$k​$的序列$A_i​$ $(1le Tle 250,1le kle 50,1le nle 10^9,-1le A_ile 10^9)$ Output 输出答案，结果模$10^9+7$ Sample Input 2
5 10
-1 -1 8 -1 -1
3 20
-1 6 18 Sample Output Case #1: 24354
Case #2: 140 Solution 方程有解当且仅当$gcd(C,m)=1$，假设$A$序列中已经确定值的$gcd$为$g$，尚未确定的数字有$x$个 1.若$g eq 0$，记$f(d)$为使得$gcd(C,m)=d$的序列$C$的个数，$F(d)$为使得$d|gcd(C,m)$的序列$C$的个数，则显然有
$F(d)=(frac{m}{d})^x$
且由$F(d)=sumlimits_{d|i}f(i)$，莫比乌斯反演有
$f(1)=sumlimits_{d|gcd(g,m)}mu(d)F(d)=sumlimits_{d|gcd(g,m)}mu(d)(frac{m}{d})^x$
进而有
$ans=sumlimits_{m=1}^nsumlimits_{d|gcd(g,m)}mu(d)(frac{m}{d})^x=sumlimits_{d|g}mu(d)sumlimits_{i=1}^{lfloorfrac{n}{d} floor}i^x=sumlimits_{d|g}mu(d)S(lfloorfrac{n}{d} floor,x)$
其中$S(n,k)=sumlimits_{i=1} i^k$，通过伯努利序列即可$O(k^2)$预处理$O(k)$得到$S(n,k)$，那么该种情况即可$O(xsqrt{g})$解决 2.若$g=0$，将之前的式子稍作修改有
$ans=sumlimits_{m=1}^nsumlimits_{d|m}mu(d)(frac{m}{d})^x=sumlimits_{d=1}^nmu(d)S(lfloorfrac{n}{d} floor,x)$