图片说明

牛客多校的账号是组里一同学单独买的，看他在群里说别***当天就只看了看题。这道题一开始没把式子看懂，后来自己举了几个例子发现其实就是最多有几个c相乘输出其值。以样例来说 f(10)=5 * f(gcd(5,10))=5 * f(5)=5* 5* f(1)=25.也就是说，这个函数退出的条件就是f(gcd(i,x))=1,也就是说跟gcd有关，就不难想到只要分解x的质因数数量并且把每一个都用上就可以得到最多个c相乘，即递归次数最多。
再举个例子：8用质因数相乘表示即为->8=2* 2* 2 所以f(8)=
c* f(gcd(2,8))=c* f(4)=c* c* f(gcd(2* 2))=c* c* f(2)=c* c* c* f(gcd(1,2))=c* c* c* f(1)=c^3.

补充几个知识点：
质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）
质因数（或质因子）在数论里是指能整除给定正整数的质数。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。

正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以指数表示。 

#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n, c, cnt;
ll ksm(ll a, ll b, ll MOD)
{
	ll res=1,base = a;
	while(b)
	{
		if(b%2)
		{
			res=res*a%MOD;
		}
		a=a*a%MOD;
		b/=2;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int t; cin >> t;
	while(t--)
	{
		cin >> n >> c;
		cnt=0;
		for(int i=2;i*i<=n;i++)
        {
            while (n%i==0)
            {
                cnt++;
                n/=i;
            } 
        }
        if(n>1) cnt++;
		ll ans;ans=ksm(c,cnt,MOD);
		cout << ans << endl;
	 } 
	
	return 0;
}