Problem of The Day 1 January — Vibhu and his Mathematics

Vibhu and his Mathematics

In code world all genders are considered equal ( It means their is nothing like male or female). Now their are N distinct persons living in this hypothetical world. Each person can pair up with any other person or can even remain single.
One day Vbhu planned to visit code world. Being a maths guy , he always try to be mathematical. So he started counting the ways in which N persons living in code world can make pairs or remain single. A single person can make pair with at most one other person.
Seeing that N can be large , Vibhu ask you for help. Now being a great programmer you need to help Vbhu count the number of ways in which N persons living in code world can make pairs or remain single.

Note : Its not necessary that everyone is required to make pair with someone. Person can remain single also.

Input Format :
First line contain number of test cases T. Then next T lines contain a single integer N , denoting the number of persons living in code world.

Output Format :
You need to print the number of ways in which N different persons can make their pairs or stay single. As answer can be large so print it modulo 109+7.

Constraints :
1 <= T <=105
1 <= N <=106

Warning: Large Input/Output data, be careful with certain languages

SAMPLE INPUT

2
2
3

SAMPLE OUTPUT

2
4

Explanation

In first test case , For N=2 answer will be 2. Possible ways are : {1},{2} (It means Person 1 and Person 2 are single) {1,2} (It means Person 1 and Person 2 had formed a pair)

For second test case , For N=3 , answer will be 4. Possible ways are : {1},{2},{3} (It means all three Persons are single) {1,2},{3} (It means Person 1 and Person 2 had formed a pair and Person 3 is single) {1},{2,3} (It means Person 2 and Person 3 had formed a pair and Person 1 is single) {1,3},{2} (It means Person 1 and Person 3 had formed a pair and Person 2 is single)

Problem Link: Vibhu and his Mathematics

Hint: Apply Recursion then see how you can apply DP.
Solution will be posted tomorrow.

SOLUTION

If we see this problem carefully then it is a problem of recursion.
For each n then number of ways will be the F(n) = F(n-1) + (n-1)F(n-2)
where F(0)=1 and F(1) =1
But by recursion time complexity will be O(n) but if we use precomputation for each test case it will be O(1).

CODE

#include<iostream>
using namespace std;
#define ll long long
#define mod 1000000007
ll a[1000001];
int main()
{
	int T,N,i;
        cin>>T;
	a[0]=1;
	a[1]=1;
	a[2]=2;
	a[3]=4;
	for(i=4;i<1000000;i++) { 
             a[i]=a[i-1]+(i-1)*a[i-2]; 
             a[i]%=mod; 
        } 
        while(T--) { 
           cin>>N;
           cout<<a[N]<<endl;
	}
	return 0;
}