Untitled
#include<bits/stdc++.h> using namespace std; #define all(v) ((v).begin()),((v).end()) #define sz(v) (v.size()) #define yes cout<<"Yes"<<'\n'; #define no cout<<"No"<<'\n'; #define endl '\n'; #define f(i,j,k) for(long long i=j;i<k;i++) #define fb(i,j,k) for(long long i=j;i>=k;i--) #define fs(i,j,k,p) for(long long i=j;i<k;i+=p) #define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p) #define pb push_back #define ppb pop_back #define mp make_pair #define ff first #define ss second #define pi 3.141592653589793238462 typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<vector<int>> vvi; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pp ; typedef vector<ll> vll; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} long long pow(long long a, long long b, long long m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } ll mod =1e9+7; void add_divs(ll x, map<ll, ll>&divs){ ll i = 2; while(i * i <= x){ while (x % i == 0){ divs[i]++; x /= i; } i++; } if(x > 1) divs[x]++; } #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define int long long int arr[105]; int arr1[105]; int n,k; ll c(ll a) { return (arr[a]*arr1[a])%mod; } void solve() { cin>>n>>k; arr[1]=k; ll tt=1; for (int i=2;i<100;++i) { arr[i]=((k+i-1)*arr[i-1])%mod; arr1[i-1]=pow(tt,mod-2,mod); tt*=i; tt%=mod; } vector<int>dvs; for (int i=1;i*i<=n;++i) { if (n%i==0) { dvs.push_back(i); if (i*i!=n)dvs.pb(n/i); } } map<ll,ll>m; vector<map<int,int>>h(sz(dvs)); add_divs(n,m); for (auto &x:m) { for (int i=0;i<sz(dvs);++i) { while(dvs[i]%x.ff==0) { h[i][x.ff]++; dvs[i]/=x.ff; } } } ll output=0; for (int i=0;i<sz(dvs);++i) { ll x=1; for (auto &t:h[i]) { x*=c(t.second); x%=mod; } output+=x; output%=mod; } cout<<output<<endl; } signed main() { #ifndef ONLINE_JUDGE freopen("Error.txt", "w", stderr); #endif fastio(); int t; t=1; while(t--) { solve(); } }
Leave a Comment