What is logic behind this problem?

Problem link-https://www.codechef.com/TSCO2017/problems/TSECJ105/

Question- A teacher wants every student to work on a project. A student can work on a single project, either alone or with a partner (group of 2). The teacher is okay with any number of pairs or sole workers.

The teacher is curious to know that how many possible ways can N students form pairs or stay solo. Can you help?

Note: Since the answer can be large, print it modulo 10^9+7



My approach is use nc2(im getting WA),please explain your approach?

This problem can be solved using Dynamic Programming.

Let f(n) denote the numbers of ways to partition n students into sets of size 1 and 2.

Now, the n^{th} student has two options:

  1. Case 1: “He stays alone” - This case doesn’t increase the number of ways. So, f(n) = f(n-1)
  2. Case 2: “He pairs up” - Suppose he pairs up with i^{th} student. The remaining n-2 students can be partitioned in f(n-2) ways. But, the i^{th} student can be chosen in n-1 ways. So, f(n) = (n-1) \times f(n-2)

Thus, f(n) = f(n-1) + (n-1) \times f(n-2) for n > 1

And, the base cases are f(0) = 1,\ f(1) = 1


I have also used the nC2 approach here. I am getting the write answer. This is the code:

using namespace std;

int fact(int);//returns factorial of a number

int comb(int, int);//returns the number of ways of selecting r students (2nd parameter) among n students (1st parameter)

int proj(int);//computes the final answer

const unsigned int M=1000000007;

int main()


int tc;//stores number of test cases


int arr[tc];//stores values of test cases

for(int i=0; i<tc;i++)




for(int i=0; i<tc;i++)




return 0;

}//end of main

int fact(int num)


int factor;


     return 1;





return factor;


int comb(int k, int r)


int combo;


return combo;


int proj(int t)


int prob=0;

    for(int n=t/2, p=t; n>=1; n--, p-=2)//t is the total number of students


        prob=(prob%M)+((n*comb(p,2))%M); //used this property of modulo: (a+b)%c=((a%c)+(b%c))%c


    return ((prob%M)+1);// +1 for the case when all students are alone


Sorry this works only for very small values. There’s some problem when I run it with large values. I need to rectify that.

i also used bigintegers but nc2 doesn’t work.is my logic is correct? one more way is to find (n-((n*(n+1))/2)+1(for individual case))%1000000007.is this correct way?

please explain in detail.as iam not getting how the ways are calculated