Advertisement
Guest User

Untitled

a guest
Jul 30th, 2015
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.03 KB | None | 0 0
  1. int fast_pow(long long base, long long n,long long M)
  2. {
  3. if(n==0)
  4. return 1;
  5. if(n==1)
  6. return base;
  7. long long halfn=fast_pow(base,n/2,M);
  8. if(n%2==0)
  9. return ( halfn * halfn ) % M;
  10. else
  11. return ( ( ( halfn * halfn ) % M ) * base ) % M;
  12. }
  13. int findMMI_fermat(int n,int M)
  14. {
  15. return fast_pow(n,M-2,M);
  16. }
  17. int main()
  18. {
  19. long long fact[100001];
  20. fact[0]=1;
  21. int i=1;
  22. int MOD=1000000007;
  23. while(i<=100000)
  24. {
  25. fact[i]=(fact[i-1]*i)%MOD;
  26. i++;
  27. }
  28. while(1)
  29. {
  30. int n,r;
  31. printf("Enter n: ");
  32. scanf(" %d",&n);
  33. printf("Enter r: ");
  34. scanf(" %d",&r);
  35. long long numerator,denominator,mmi_denominator,ans;
  36. //I declared these variable as long long so that there is no need to use explicit typecasting
  37. numerator=fact[n];
  38. denominator=(fact[r]*fact[n-r])%MOD;
  39. mmi_denominator=findMMI_fermat(denominator,MOD);
  40. ans=(numerator*mmi_denominator)%MOD;
  41. printf("%lld\n",ans);
  42. }
  43. return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement