Educational Codeforces Round 33 E. Counting Arrays

You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:

There are y elements in F, and all of them are integer numbers;
.

You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that Ai ≠ Bi. Since the answer can be very large, print it modulo 109 + 7.

Input

The first line contains one integer q (1 ≤ q ≤ 105) — the number of testcases to solve.

Then q lines follow, each containing two integers xi and yi (1 ≤ xi, yi ≤ 106). Each of these lines represents a testcase.

Output

Print q integers. i-th integer has to be equal to the number of yi-factorizations of xi modulo 109 + 7.

         Example       
           input                       Copy          
2
6 3
4 2
           output         
36
6

Note

In the second testcase of the example there are six y-factorizations:

{ - 4, - 1};
{ - 2, - 2};
{ - 1, - 4};
{1, 4};
{2, 2};
{4, 1}.

思路:很明显,先求出所有都是正数的方案数ans,考虑负号 ans=ans+ans* sigma c(y,2)*c(y,4)`````` == ans*2^(y-1) 为什么是 2^(y-1) 看看二项展开定理就好了

#include<bits/stdc++.h>
#define PI acos(-1.0)
using namespace std;
typedef long long ll;

const int MAX_N=1e6+50;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int F[MAX_N],Finv[MAX_N],inv[MAX_N];

void init(){
    inv[1]=1;
    for(int i=2;i<MAX_N;i++)
        inv[i]=(MOD-MOD/i)*1ll*inv[MOD%i]%MOD;
    F[0]=Finv[0]=1;
    for(int i=1;i<MAX_N;i++){
        F[i]=F[i-1]*1ll*i%MOD;
        Finv[i]=Finv[i-1]*1ll*inv[i]%MOD;
    }
}

int c(int n,int m){
    if(m<0 || m>n)  return 0;
    return F[n]*1ll*Finv[n-m]%MOD*Finv[m]%MOD;
}

ll mypow(int a,int b){
    ll ans=1;
    while(b){
        if(b&1) ans*=a,ans%=MOD;
        a=(1ll*a*a)%MOD;
        b/=2;
    }
    return ans;
}

int main(void){
    init();
    int t;
//    cout << c(2,1);
    cin >>t;
    ll sum=0;
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);
        ll ans=1;
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                int cnt=0;
                while(x%i==0){
                    x/=i;
                    cnt++;
                }
//                cout <<"cnt="<<cnt<<endl;
                ans*=c(y+cnt-1,y-1)%MOD;
                ans%=MOD;
            }
        }
        if(x>1)   ans=1ll*ans*y%MOD,ans%=MOD;
        ans=1ll*ans*(mypow(2,y-1))%MOD;
        cout << ans << endl;
    }
    return 0;
}