对于每组数据，给出x和y，求一个长度为y的序列，其乘积为x，允许有负数，求这种序列的个数，对1e9+7取模

---

首先不考虑正负号，那么我们可以把原题看作把\(x\)的质因子分配到序列的若干个位置中，那么设\(x=\prod_ip_i^{k_i}\)，则对于每个\(p_i\)，都有把\(k_i\)个小球放到\(y\)个有标号盒子中，并且盒子可以为空，相当于有\(k_i+y\)个小球放到\(y\)个有标号盒子中，每个盒子不能为空，于是用插板法解决，方案数为\(\begin{pmatrix}k_i+y-1\\y-1\end{pmatrix}\)。

然后考虑正负号的问题，我们肯定是每次选择序列中偶数个位置，把他们变为负数，所以有如下式子：

\[\sum_{i=0}^{\lfloor\frac{y}{2}\rfloor}\begin{pmatrix}y\\2i\end{pmatrix} \]

考虑化简这个式子，那么先考虑\(y\)是奇数，那么有：

\[\begin{aligned}\sum_{i=0}^{\frac{y-1}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\\ =\sum_{i=0}^\frac{y-1}{2}\begin{pmatrix}y\\i\end{pmatrix}\end{aligned}\]

而我们发现\(2^y=\sum_{i=0}^y\begin{pmatrix}y\\i\end{pmatrix},\begin{pmatrix}y\\i\end{pmatrix}=\begin{pmatrix}y\\y-i\end{pmatrix}\)，那么原式就\(=2^{y-1}\)。

然后考虑\(y\)是偶数，那么有：

\[\sum_{i=0}^{\frac{y}{2}}\begin{pmatrix}y\\2i\end{pmatrix} \]

然后如果\(\frac{y}{2}\)是奇数，那么有：

\[\begin{aligned}2\sum_{i=0}^{\frac{\frac{y}{2}-1}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\\=2\sum_{i=0}^{\frac{y}{2}-1}\begin{pmatrix}y-1\\i\end{pmatrix}\end{aligned}\\=2(2^{y-2})=2^{y-2} \]

而如果\(\frac{y}{2}\)是偶数，那么有：

\[\begin{aligned}2\sum_{i=0}^{\frac{\frac{y}{2}-2}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\end{aligned}+\begin{pmatrix}y\\\frac{y}{2}\end{pmatrix}\\=2\sum_{i=0}^{\frac{y}{2}-2}\begin{pmatrix}y-1\\i\end{pmatrix}+\begin{pmatrix}y\\\frac{y}{2}\end{pmatrix}\\=2(2^{y-2}-\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix})+\begin{pmatrix}y-1\\\frac{y}{2}\end{pmatrix}+\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix}\\=2^{y-1}+\begin{pmatrix}y-1\\\frac{y}{2}\end{pmatrix}-\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix}\\=2^{y-1} \]

综上所述可以得到\(\sum_{i=0}^{\lfloor\frac{y}{2}\rfloor}\begin{pmatrix}y\\2i\end{pmatrix}=2^{y-1}\)。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 2e6;
const int p = 1e9 + 7;
using namespace std;
int T,x,y,fac[N + 5],inv[N + 5],ans;
int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % p : 0,a = 1ll * a * a % p,x >>= 1);return s;}
int C(int n,int m)
{
    return 1ll * fac[n] * inv[n - m] % p * inv[m] % p;
}
int main()
{
    scanf("%d",&T);
    fac[0] = 1;
    for (int i = 1;i <= N;i++)
        fac[i] = 1ll * fac[i - 1] * i % p;
    inv[1] = 1;
    for (int i = 2;i <= N;i++)
        inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
    inv[0] = 1;
    for (int i = 1;i <= N;i++)
        inv[i] = 1ll * inv[i - 1] * inv[i] % p;
    while (T--)
    {
        scanf("%d%d",&x,&y);
        ans = mypow(2,y - 1);
        int xx = x;
        for (int i = 2;i * i <= xx;i++)
            if (xx % i == 0)
            {
                int cnt = 0;
                while (xx % i == 0)
                {
                    xx /= i;
                    cnt++;
                }
                ans = 1ll * ans * C(cnt + y - 1,y - 1) % p;
            }
        if (xx != 1)
            ans = 1ll * ans * y % p;
        printf("%d\n",ans);
    }
    return 0;
}