Tom the cat is brushing up his Math skills. He has a bag containing N balls of different colors. Now Tom can randomly pick any even number of balls from the bag. Tom wants to find out the sum of all such combinations of balls that he can pull out from the bag. He can pull out at max K balls in one pick.
Input Format:
First line contains two space separated numbers N and K.
Output Format:
The output is the sum of all the combinations of balls he can pull out modulo 10^9+7 i.e. (1000000007)
Constraints:
0<=N
k<=10^14
N >= k
Example 1
Input:
4 4
Output:
8
Explanation:
We need 4C0 + 4C2+ 4C4= 1+6+1=8
Solution: In C
#include<stdio.h>
unsigned long long int fact(unsigned long long int);
int main()
{
unsigned long long int k,s=0,i,n;
scanf("%llu %llu",&n,&k);
if(n>0 && n>=k && k<=100000000000000)
{
for(i=0;i<=k;i+=2)
s+=(fact(n)/(fact(i)*fact(n-i)));
s = s % 1000000007;
printf("%llu",s);
}
return 0;
}
unsigned long long int fact(unsigned long long int n)
{
if(n==1)
return 1;
else if(n==0)
return 1;
else
return(n*fact(n-1));
}Solution: In Java
import java.util.*;
public class Main
{
public static void main(String []args)
{
int k,s=0,i,n;
Scanner ip=new Scanner(System.in);
n=ip.nextInt();
k=ip.nextInt();
if(n>0 && n>=k && k<=10000000)
{
for(i=0;i<=k;i+=2)
s+=(fact(n)/(fact(i)*fact(n-i)));
s = s % 1000000007;
System.out.printf("%d",s);
}
}
public static int fact(int n)
{
if(n==1)
return 1;
else if(n==0)
return 1;
else
return(n*fact(n-1));
}
}Solution: In Python 3
def nCr(n, r):
res = fact(r) * fact(n-r)
return fact(n)/res
def fact(n):
res = 1
for i in range(2, n+1):
res = res * i
return res
n, k = map(int, input().split())
ans = 0
for i in range(0,k+1):
if i%2 == 0:
ans = ans + nCr(n,i)
print(int(ans%1000000007))Also Checkout