Cheese and Random Toppings

Problem Link

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define LL long long int

LL lucas(LL n,LL r,LL p)
{
LL ans=1,ncr[p][p];
memset(ncr, 0, sizeof ncr);
for (int i = 0; i < p; ++i)
{
ncr[i][0]=1;
}
for (int i = 1; i < p; ++i)
{
for (int j = 1; j <= i; ++j)
{
ncr[i][j]=(ncr[i-1][j] + ncr[i-1][j-1])%p;
}
}
while(n && r)
{
ans=(ans * ncr[n%p][r%p])%p;
n/=p;
r/=p;
}
return ans;
}

LL fastExpo(LL a, LL b, LL P) {
  LL res = 1;

  if(b==0)
return 1;
if(b==1)
return a;

  while (b) {
    if (b & 1) {
      res = (res * a) % P;
    }
    a = (a * a) % P;
    b = b >> 1;
  }
  return res;
}

int main()
{
int t;
cin>>t;
while(t--)
{
long long int n,r,m,tm,ans=0;
cin>>n>>r>>m;
tm=m;
for (int i = 2; i <= 50; ++i)
{
if(tm%i == 0)
{
long long int temp=lucas(n,r,i);
temp=(temp * (m/i))%m;
temp=(temp * fastExpo(m/i,i-2,i))%m;
ans=(ans + temp)%m;
tm/=i;
}
}
cout<<ans<<"\n";
}
return 0;
}