Advertisement
Guest User

Untitled

a guest
Sep 24th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int man=1000005;
  5. const int MAXM= 15000005;
  6. ll mod = 1e9+7;
  7. ll fac[man];
  8. ll n,m;
  9. void init()
  10. {
  11.    fac[0]=1;
  12.    for(ll i=1;i<man;i++)
  13.      fac[i]=(fac[i-1]*i)%mod;
  14. }
  15.  
  16. ll quickpow(ll a,ll b,ll p)
  17. {
  18.     ll ans=1%p;
  19.     while(b)
  20.     {
  21.         if(b&1) ans=ans*a%p;
  22.         a=a*a%p;
  23.         b>>=1;
  24.     }
  25.     return ans;
  26. }
  27. ll inv(ll a,ll  mod)
  28. {
  29.     return quickpow(a,mod-2,mod);
  30. }
  31.  
  32. ll Cal(ll n,ll m,ll mod)
  33. {
  34.     ll a=fac[n];
  35.     ll b=(fac[m]*fac[n-m])%mod;
  36.     return (a*inv(b,mod))%mod;
  37. }
  38.  
  39. map<ll,ll> prime_dection(ll x)
  40. {
  41.     map<ll,ll> res;
  42.     for(ll i=2;i*i<=x;i++)
  43.     {
  44.         while(x%i==0)
  45.         {
  46.             ++res[i];
  47.             x/=i;
  48.         }
  49.     }
  50.     if(x!=1) res[x]++;
  51.     return res;
  52. }
  53.  
  54. int main()
  55. {
  56.   ios::sync_with_stdio(false);
  57.   cin.tie(0);
  58.   cout.tie(0);
  59.   cin>>n>>m;
  60.   init();
  61.   auto ss=prime_dection(m);
  62.   ll ans=1;
  63.   for(auto &t: ss)
  64.   {
  65.       ll num = t.second;
  66.       ll tmp=Cal(n+num-1,num,mod);
  67.       ans=(ans*tmp)%mod;
  68.   }
  69.   cout<<ans<<endl;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement