PROBLEM LINK:
Author: Divyesh Savaliya
Editorialist: Divyesh Savaliya
DIFFICULTY:
EASY  MEDIUM
PREREQUISITES:
Math
PROBLEM:
You are given N. You have to count the number of binary strings (consists of only ‘0’ and ‘1’) of length 2*N such that the number of '1’s in first string of length N is double of the number of '1’s in second string of length N. Print the answer modulo 10^9+7.
EXPLANATION:
Lets try to solve this step by step and then sum all the value. Half string means the string of length N.

Find the number of strings which contain two ‘1’ in first half string and one ‘1’ in second half string.

Find the number of strings which contain four ‘1’ in first half string and two ‘1’ in second half string.

Find the number of strings which contain six ‘1’ in first half string and three ‘1’ in second half string.
Do above step upto the number of ‘1’ in first half string become N if N is even or N1 if N is odd.
Now, how to compute the required number of strings. Simple, just by using Permutation and Combination.

The number of strings which contain two ‘1’ in first half string are nothing but binomialCoeff(N,2).The number of strings which contain one ‘1’ in second half string are nothing but binomialCoeff(N,1). So, the answer for step 1 is binomialCoeff(N,2) * binomialCoeff(N,1).

Similarly, the answer for second step is binomialCoeff(N,4)*binomialCoeff(N,2).
So, the final answer is :
for(int i=2;i<=N;i=i+2)
sum = ( sum + ( ( binomialCoeff(N,i) * binomialCoeff(N,i/2) ) % 10^9+7) ) % 10^9+7;
Now, how to compute binomialCoeff(N,r). Since, the value of N <= 1000. You can use Dynamic Programming technique to precompute it.
Time complexity is O(N) if we precompute binomialCoeff in O(N*N).
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.