#include using namespace std; using ll = long long; using P = pair; using Graph= vector>; struct edge{ll to ; ll cost ;} ; using graph =vector> ; #define rep(i,n) for (ll i=0; i < (n); ++i) #define rep2(i,n,m) for(ll i=n;i<=m;i++) #define rep3(i,n,m) for(ll i=n;i>=m;i--) #define pb push_back #define eb emplace_back #define ppb pop_back #define mpa make_pair #define fi first #define se second const ll INF=1e18 ; inline void chmax(ll& a,ll b){a=max(a,b);} inline void chmin(ll& a,ll b){a=min(a,b);} struct UnionFind { vector d; UnionFind(int n=0): d(n,-1) {} int find(int x) { if (d[x] < 0) return x; return d[x] = find(d[x]); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (d[x] > d[y]) swap(x,y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y) { return find(x) == find(y);} int size(int x) { return -d[find(x)];} }; //  ダイクストラ ひーぷ  /* dijkstra(G,s,dis) 入力:グラフ G, 開始点 s, 距離を格納する dis 計算量:O(|E|log|V|) 副作用:dis が書き換えられる */ // グラフ スタート 距離 ひとつ前 void dijkstra(const graph & g, ll s ,vector & d,vector &prev ){ ll N = g.size() ; //頂点数 d.resize(N,INF) ; prev.resize(N,INF) ; priority_queue,greater

> pq ; d[s]=0 ; pq.emplace(d[s],s) ; while(!pq.empty()){ P p=pq.top() ; pq.pop() ; ll v= p.se; if(d[v]d[v]+e.cost){ d[e.to]=d[v]+e.cost ; prev[e.to]=v ; //頂点vを使ってe.toに辿り着いた pq.emplace(d[e.to],e.to) ; } } } } /* get_path(prev, t) 入力:dijkstra で得た prev, ゴール t 出力: t への最短路のパス */ vector get_path(const vector &prev, ll t) { vector path; for (ll cur = t; cur != -1; cur = prev[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); // 逆順なのでひっくり返す return path; } map factor(ll n){ //素因数とオーダーをマップで管理 map ord ; for(ll i=2;i*i<=n;i++){ if(n%i==0){ int res=0; while(n%i==0){ n/=i; res++; } ord[i]=res; } } if(n!=1) ord[n]++; return ord ; } vector< int > z_algorithm(const string &s) { vector< int > prefix(s.size()); for(int i = 1, j = 0; i < s.size(); i++) { if(i + prefix[i - j] < j + prefix[j]) { prefix[i] = prefix[i - j]; } else { int k = max(0, j + prefix[j] - i); while(i + k < s.size() && s[k] == s[i + k]) ++k; prefix[i] = k; j = i; } } prefix[0] = (int) s.size(); return prefix; } const ll mod=1e9+7; ll modpow(ll x, ll y){ if(y==0) return 1; else{ ll ans=modpow(x,y/2); ans=(ans*ans)%mod; if(y%2) return (ans*x)%mod; else return ans; } } int main(){ ll n,k; cin>>n>>k; map mp; ll nn=n; for(ll i=2;i*i<=nn;++i){ while(n%i==0){ n/=i; mp[i]++; } } if(n!=1) mp[n]++; ll MA=0ll; for(auto u:mp) chmax(MA,u.fi); while(k>0&&MA>3){ k--; map pm; for(auto u:mp){ ll num=u.fi+1; ll p=u.se; map f=factor(num); for(auto v:f) pm[v.fi]+=v.se*p; } mp=pm; MA=0ll; for(auto u:mp) chmax(MA,u.fi); } if(!k){ ll ans=1; for(auto u:mp){ ll p=modpow(u.fi,u.se); ans*=p; ans%=mod; } cout<