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.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}

    static int groups = 0;
    static int[] fa;
    static int[] sz;

    static void init1(int n) {
        groups = n;
        fa = new int[n];
        for (int i = 1; i < n; ++i) {
            fa[i] = i;
        }
        sz = new int[n];
        Arrays.fill(sz, 1);
    }

    static int root(int p) {
        while (p != fa[p]) {
            fa[p] = fa[fa[p]];
            p = fa[p];
        }
        return p;
    }

    static void combine(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        fa[i] = j;
        if (sz[i] < sz[j]) {
            fa[i] = j;
            sz[j] += sz[i];
        } else {
            fa[j] = i;
            sz[i] += sz[j];
        }
        groups--;
    }


    public static String roundS(double result, int scale){
        String fmt = String.format("%%.%df", scale);
        return String.format(fmt, result);
    }

    int[] unique(int a[]){
        int p = 1;
        for(int i=1;i<a.length;++i){
            if(a[i]!=a[i-1]){
                a[p++] = a[i];
            }
        }
        return Arrays.copyOf(a,p);
    }


    public static int bigger(long[] a, long key) {
        return bigger(a,0,a.length,key);
    }

    public static int bigger(long[] a, int lo, int hi,
                             long key) {
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] > key) {
                hi = mid;
            }else {
                lo = mid+1;
            }
        }
        return lo;
    }


    static int h[];
    static int to[];
    static int ne[];
    static int m = 0;

    public static void addEdge(int u, int v, int w) {
        to[++m] = v; ne[m] = h[u]; h[u] = m;
    }



    int w[];

    int cc = 0;

    void add(int u,int v,int ww) {
        to[++cc] = u;
        w[cc] = ww;
        ne[cc] = h[v];
        h[v] = cc;

        to[++cc] = v;
        w[cc] = ww;
        ne[cc] = h[u];
        h[u] = cc;
    }


//    List<int[]> li = new ArrayList<>();
//
//    void go(int j){
//        d[j] = l[j] = ++N;
//        int cd = 0;
//        for(int i=h[j];i!=0;i= ne[i]){
//            int v= to[i];
//            if(d[v]==0){
//                fa[v] = j;
//                cd++;
//                go(v);
//                l[j] = Math.min(l[j],l[v]);
//                if(d[j]<=l[v]){
//                    cut[j] = true;
//                }
//                if(d[j]<l[v]){
//                    int ma = Math.max(j,v);
//                    int mi = Math.min(j,v);
//                    li.add(new int[]{mi,ma});
//                }
//            }else if(fa[j]!=v){
//                l[j] = Math.min(l[j],d[v]);
//            }
//        }
//        if(fa[j]==-1&&cd==1){
//            cut[j] = false;
//        }
//        if (l[j] == d[j]) {
//            while(p>0){
//                mk[stk[p-1]] = id;
//            }
//            id++;
//        }
//    }
//    int mk[];
//    int id=  0;
//    int l[];
//    boolean cut[];
//    int p = 0;
//    int d[];int N = 0;
//    int stk[];


    static class S{
        int l = 0;
        int r = 0 ;
        int miss = 0;
        int cnt = 0;
        int c = 0;

        public S(int l,int r) {
            this.l = l;
            this.r = r;
        }
    }

    static S a[];
    static int[] o;

    static void init11(int[] f){
        o = f;
        int len = o.length;
        a = new S[len*4];
        build1(1,0,len-1);
    }

    static void build1(int num,int l,int r){
        S cur = new S(l,r);
        if(l==r){
            cur.c = o[l];
            a[num] = cur;
            return;
        }else{
            int m = (l+r)>>1;
            int le = num<<1;
            int ri = le|1;
            build1(le, l,m);
            build1(ri, m+1,r);
            a[num] = cur;
            pushup(num, le, ri);
        }
    }

    static int query1(int num,int l,int r){
        if(a[num].l>=l&&a[num].r<=r){
            return a[num].c;
        }else{
            int m = (a[num].l+a[num].r)>>1;
            int le = num<<1;
            int ri = le|1;

            int mi = -1;

            if(r>m){
                int res = query1(ri, l,r);
                mi = Math.max(mi,res);
            }

            if(l<=m) {
                int res = query1(le, l, r);
                mi = Math.max(mi,res);
            }

            return mi;
        }
    }

    static void pushup(int num,int le,int ri){
        a[num].c = Math.max(a[le].c,a[ri].c);

    }

    int root[] = new int[10000];

    void dfs(int j){

        clr[j] = 1;

        for(int i=h[j];i!=0;i=ne[i]){
            int v = to[i];
            dfs(v);
        }
        for(Object go:qr[j]){
            int g = (int) go;
            int id1 = qs[g][0];
            int id2 = qs[g][1];
            int ck;
            if(id1==j){
                ck = id2;
            }else{
                ck = id1;
            }

            if(clr[ck]==0){
                continue;
            }else if(clr[ck]==1){
                qs[g][2] = ck;
            }else{
                qs[g][2] = root(ck);
            }
        }
        root[j] = fa[j];

        clr[j] = 2;
    }


    int clr[];
    List[] qr;
    int qs[][];




    void solve() {
//        int n = ni();
//        for(int i=0;i<n;++i){
//            char c =nc();
//            int k = ni();
//            if(c=='Q'){
//                ans = -1000000000;
//                findX(rt,k);
//                println(ans);
//            }else{
//                rt =  insert(rt,k);
//            }
//        }

       int x = ni();
       long n = nl();
       long p[] = new long[1000000];
       int f = 0;
       for(int i=2;i*i<=x;++i){
           if(x%i==0){
               p[f++] = i;
               while(x%i==0) x/=i;
           }
       }
       if(x>1){
           p[f++] = x;
       }
        BigInteger s =BigInteger.ONE;
       BigInteger zz = new BigInteger("1000000007");
       for(int i=0;i<f;++i){
           long cj = p[i];long sum = 0;long nn = n;
           while(cj<=nn){
               sum += (nn/cj);
               nn/= cj;
           }
           BigInteger bg = new BigInteger(""+p[i]);
           bg = bg.modPow(new BigInteger(""+sum),zz);
           s = s.multiply(bg);
           s = s.mod(zz);
       }
       println(s);






//        int n = ni();
//
//        int id = 0 ;
//
//        clr = new int[2*n];
//        h = new int[2*n+1];
//        to = new int[2*n+1];
//        ne = new int[2*n+1];
//        int ct = 0;
//
//        Map<String,Integer> mp = new HashMap<>();
//        Map<Integer,String> nmp = new HashMap<>();
//
//        for(int i=0;i<n;++i){
//            String f = ns();
//            String c = ns();
//            int fa,ch;
//            if(mp.containsKey(f)){
//                fa = mp.get(f);
//            }else{
//                fa = id++;
//                mp.put(f,fa);
//            }
//            if(mp.containsKey(c)){
//                ch = mp.get(c);
//            }else{
//                ch = id++;
//                mp.put(c,ch);
//            }
//            nmp.put(fa,f);
//            nmp.put(ch,c);
//            to[++ct] = ch;
//            ne[ct] = h[fa];
//            h[fa] = ct;
//        }
//        int m = ni();
//        qs = new int[m][3];
//
//        qr = new List[id];
//
//        for(int i=0;i<id;++i){
//            qr[i] = new ArrayList();
//        }
//
//        for(int i=0;i<m;++i){
//            String na = ns();
//            String nb = ns();
//            int i1 = mp.get(na);
//            int i2 = mp.get(nb);
//            qs[i][0] = i1;
//            qs[i][1] = i2;
//            qr[i1].add(i);
//            qr[i2].add(i);
//        }
//
//        dfs(0);




    }




























































    static void pushdown(int num,int le,int ri){

    }


    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
}