C. Primes and Multiplication

Let's introduce some definitions that will be needed later.

Let prime(x)prime(x) be the set of prime divisors of xx. For example, prime(140)={2,5,7}prime(140)={2,5,7}, prime(169)={13}prime(169)={13}.

Let g(x,p)g(x,p) be the maximum possible integer pkpk where kk is an integer such that xx is divisible by pkpk. For example:

g(45,3)=9g(45,3)=9 (4545 is divisible by 32=932=9 but not divisible by 33=2733=27),
g(63,7)=7g(63,7)=7 (6363 is divisible by 71=771=7 but not divisible by 72=4972=49).

Let f(x,y)f(x,y) be the product of g(y,p)g(y,p) for all pp in prime(x)prime(x). For example:

f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10,
f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63.

You have integers xx and nn. Calculate f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7)f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7).

Input

The only line contains integers xx and nn (2≤x≤1092≤x≤109, 1≤n≤10181≤n≤1018) — the numbers used in formula.

Output

Print the answer.

Examples

input

Copy

10 2

output

Copy

input

Copy

20190929 1605

output

Copy

363165664

input

Copy

947 987654321987654321

output

Copy

593574252

Note

In the first example, f(10,1)=g(1,2)⋅g(1,5)=1f(10,1)=g(1,2)⋅g(1,5)=1, f(10,2)=g(2,2)⋅g(2,5)=2f(10,2)=g(2,2)⋅g(2,5)=2.

In the second example, actual value of formula is approximately 1.597⋅101711.597⋅10171. Make sure you print the answer modulo (109+7)(109+7).

In the third example, be careful about overflow issue.

题解：这是到算贡献的题，不难发现，有一种暴力解法就是对于n遍历求出贡献，但显然对于1e18的数据，会tle，因此我们可以换一种思路，对于素因子来说，他的贡献显然是指他的倍数

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MOD = 1000000007;
int x;
long long n;
int p[100], pn = 0;
long long quickmul(int a, int b)
{
	long long ret = 1;
	for(; b; b >>= 1, a = (long long)a * a % MOD)
		if(b & 1)
			ret = ret * a % MOD;
	return ret;
}
int main()
{
	cin >> x >> n;
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0)
		{
			p[++pn] = i;
			while(x % i == 0)
				x /= i;
		}
	if(x > 1)
		p[++pn] = x;
	int ans = 1;
	for(int i = 1; i <= pn; i++)
	{
		long long now = n;
		long long cnt = 0;
		while(now > 0)
		{
			now /= p[i];
			cnt += now;
		}
		cnt %= MOD - 1;
		ans = ans * quickmul(p[i], cnt) % MOD;
	}
	cout << ans << endl;
	return 0;
}