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

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

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

  * g(45, 3) = 9 (45 is divisible by 3^2=9 but not divisible by 3^3=27), 
  * g(63, 7) = 7 (63 is divisible by 7^1=7 but not divisible by 7^2=49). 



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

  * f(30, 70) = g(70, 2) ⋅ g(70, 3) ⋅ g(70, 5) = 2^1 ⋅ 3^0 ⋅ 5^1 = 10, 
  * f(525, 63) = g(63, 3) ⋅ g(63, 5) ⋅ g(63, 7) = 3^2 ⋅ 5^0 ⋅ 7^1 = 63. 



You have integers x and n. Calculate f(x, 1) ⋅ f(x, 2) ⋅ … ⋅ f(x, n) mod{(10^{9} + 7)}.

Input

The only line contains integers x and n (2 ≤ x ≤ 10^{9}, 1 ≤ n ≤ 10^{18}) — the numbers used in formula.

Output

Print the answer.

Examples

Input


10 2


Output


2


Input


20190929 1605


Output


363165664


Input


947 987654321987654321


Output


593574252

Note

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

In the second example, actual value of formula is approximately 1.597 ⋅ 10^{171}. Make sure you print the answer modulo (10^{9} + 7).

In the third example, be careful about overflow issue.
import java.io.*;
import java.lang.reflect.Array;
import java.math.*;
import java.util.*;
import java.util.Map.Entry;

public class Main {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	static int BIT[];
	public final static int INF = (int) 1E9;
	static ArrayList<Integer> adj[];
	static boolean Visited[];
	static HashSet<Integer> exc;
	static long oddsum[] = new long[1000001];
	static long co = 0, ans = 0;
	static int parent[];
	static int size[], color[], res[], k;
	static ArrayList<Integer> al[];
	static long MOD = (long) 1e9 + 7;
	static int[] levl, dist;
	static int[] eat;
	static int nm = 1000007;
	static boolean divisor[];
	static int[] phi;
	static int mod = (int) 1e9 + 7;
	static HashSet<Integer> div;
	static double maxvector = 1.5 * (1e6);

	public static void solve() {
		
		
		int x = nextInt();
		long n = nextLong();
//		sieve((int)1e5);
		HashSet<Integer> a = get_factors(x);
		
		long all = 1;
		for (int i: a) {
			long total_power = 0;
			long y = n / i;
			total_power += y;
			while(y !=0) {
				total_power += y/i;
				y = y/i;
			}
			long p = pow(i,total_power, mod);
			all = (all * (p%mod) )% mod;
		}
		pw.println(all);
		

	}
	
	public static HashSet<Integer> get_factors(int x) {
		HashSet<Integer> a = new HashSet<>();
		while( x%2== 0) {
			a.add(2);
			x = x/2;
		}
		for(int i=3; i*i<=x;i+=2) {
			while( x % i == 0) {
				x = x / i;
				a.add(i);
			}
		}
		if (x > 2) {
			a.add(x);
		}
		return a;
	}
	
	

	public static void main(String args[]) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		new Thread(null, new Runnable() {
			public void run() {
				try {
					solve();

					pw.close();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	static StringBuilder sb;

	public static void test() {
		sb = new StringBuilder();
		int t = nextInt();
		while (t-- > 0) {

			solve();

		}
		pw.println(sb);
	}

	public static long pow(long n, long p, long mod) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n % mod;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2, mod);
			return (temp * temp) % mod;
		} else {
			long temp = pow(n, p / 2, mod);
			temp = (temp * temp) % mod;
			return (temp * n) % mod;

		}
	}

	public static long pow(long n, long p) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2);
			return (temp * temp);
		} else {
			long temp = pow(n, p / 2);
			temp = (temp * temp);
			return (temp * n);

		}
	}

	public static long gcd(long x, long y) {
		if (x == 0)
			return y;
		else
			return gcd(y % x, x);
	}

	public static boolean isPrime(int n) {
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;

		if (n % 2 == 0 || n % 3 == 0)
			return false;

		for (int i = 5; i * i <= n; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		return true;
	}

	private static void buildgraph(int n) {
		adj = new ArrayList[n + 1];
		Visited = new boolean[n + 1];
		levl = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			adj[i] = new ArrayList<Integer>();

		}

	}

	static void sprime() {
		spf = new int[nm + 1];
		for (int i = 2; i < nm; i++) {
			if (spf[i] != 0)
				continue;
			for (int j = i; j < nm; j += i) {
				spf[j] = i;
			}
		}
	}

	static void toposort(int i) {
		Visited[i] = true;

		for (int j : adj[i]) {
			if (!Visited[j])
				toposort(j);
		}

	}

	static void comp(int n) {
		for (int i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				if (i == n / i)
					div.add(i);
				else {
					div.add(i);
					div.add(n / i);
				}
			}
		}
	}

	static void calculatephi() {
		int end = (int) 1e6 + 5;
		for (int i = 1; i < end; i++)
			phi[i] = i;
		for (int i = 2; i < end; i++) {
			if (phi[i] == i) {
				phi[i] = i - 1;
				for (int j = 2 * i; j < end; j = j + i) {
					phi[j] = (phi[j] / i) * (i - 1);
				}
			}

		}

	}

	static void randomize(long arr[], int n) {
		Random r = new Random();
		for (int i = n - 1; i > 0; i--) {
			int j = r.nextInt(i);
			long temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}

	static class pa implements Comparator<Integer> {

		public int compare(Integer a, Integer b) {
			return b - a;

		}
	}

	static class node implements Comparable<node> {
		long r;
		long i;

		node(long r, long i) {
			this.r = r;
			this.i = i;
		}

		public int compareTo(node other) {
			return Long.compare(this.r, other.r);

		}
	}

	/*
	 * static void BITupdate(int x,int val) { while(x<=n) { BIT[x]+=val; x+= x & -x;
	 * } }
	 */
	/*
	 * static void update(int x,long val) {
	 * 
	 * val=val%MOD; while(x<=n) { // System.out.println(x); BIT[x]=(BIT[x]+val)%MOD;
	 * x+=(x & -x); } // System.out.println("dfd"); }
	 */
	static int BITsum(int x) {
		int sum = 0;
		while (x > 0) {
			sum += BIT[x];
			x -= (x & -x);
		}
		return sum;
	}

	/*
	 * static long sum(int x) { long sum=0; while(x>0) { sum=(sum+BIT[x])%MOD; x-=x
	 * & -x; } return sum; }
	 */
	static boolean union(int x, int y) {
		int xr = find(x);
		int yr = find(y);
		if (xr == yr)
			return false;
		if (size[xr] < size[yr]) {
			size[yr] += size[xr];
			parent[xr] = yr;
		} else {
			size[xr] += size[yr];
			parent[yr] = xr;

		}
		return true;

	}

	static int find(int x) {
		if (parent[x] == x)
			return x;
		else {
			parent[x] = find(parent[x]);
			return parent[x];
		}

	}

	public static class Edge implements Comparable<Edge> {
		long x;
		int i;

		public Edge(long x, int i) {
			this.x = x;
			this.i = i;
			// this.s = s;
		}

		public int hashCode() {
			return Objects.hash();
		}

		public int compareTo(Edge other) {
			return Long.compare(this.x, other.x);

		}

	}

	static int col[];

	static int no_vert = 0;

	public static String reverseString(String s) {
		StringBuilder sb = new StringBuilder(s);
		sb.reverse();
		return (sb.toString());
	}

	static int indeg[];
	/*
	 * private static void kahn(int n){
	 * 
	 * PriorityQueue<Integer> q=new PriorityQueue<Integer>(); for(int i=1;i<=n;i++){
	 * if(indeg[i]==0){ q.add(i); } } while(!q.isEmpty()){ int top=q.poll();
	 * st.push(top); for(Node i:adj[top]){ indeg[i.to]--; if(indeg[i.to]==0){
	 * q.add(i.to); } } } }
	 * 
	 * static int state=1; static long no_exc=0,no_vert=0; static Stack<Integer> st;
	 * static HashSet<Integer> inset; private static void topo(int curr){
	 * 
	 * Visited[curr]=true; inset.add(curr); for(int x:adj[curr]){
	 * if(adj[x].contains(curr) || inset.contains(x)){ state=0; return; }
	 * if(state==0) return;
	 * 
	 * } st.push(curr);
	 * 
	 * inset.remove(curr); }
	 */
	static HashSet<Integer> hs;

	static boolean prime[];
	static int spf[];

	public static void sieve(int n) {
		prime = new boolean[n + 1];
		spf = new int[n + 1];

		Arrays.fill(spf, 1);
		Arrays.fill(prime, true);
		prime[1] = false;
		spf[2] = 2;

		for (int i = 2; i * i <= n; i++) {
			if (prime[i]) {
				spf[i] = i;
				for (int j = 2 * i; j <= n; j += i) {

					prime[j] = false;

				}
			}
		}

	}

	// To Get Input
// Some Buffer Methods

	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static int[] nextIntArray(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[][] next2dArray(int n, int m) {
		long[][] arr = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i][j] = nextLong();
			}
		}
		return arr;
	}

	private static char[][] nextCharArray(int n, int m) {
		char[][] c = new char[n][m];
		for (int i = 0; i < n; i++) {
			String s = nextLine();
			for (int j = 0; j < s.length(); j++) {
				c[i][j] = s.charAt(j);
			}
		}
		return c;
	}

	private static long[] nextLongArray(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			pw.print(arr[i] + " ");
		}
		pw.println();
		return;
	}

	private static void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++) {
			pw.print(arr[i] + " ");
		}
		pw.println();
		return;
	}

	private static void pArray(boolean[] arr) {
		for (int i = 0; i < arr.length; i++) {
			pw.print(arr[i] + " ");
		}
		pw.println();
		return;
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}

}