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 10^9+7.

Constraints :
1 ≤ T ≤10^5
1 ≤ N ≤10^6
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)

Difficulty: EASY
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
mod = 10**9 + 7
MAX = 10**6 + 5


def precompute(A):
	for i in range(2, MAX):
		A[i] = (A[i - 1] + A[i - 2] * (i - 1)) % mod

if __name__ == '__main__':
	A = [1] * MAX
	precompute(A)
	for _ in range(eval(input())):
		print(A[eval(input())])


mod = 10**9 + 7
arr = [1 , 1]
for i in range(2 , 10**6 + 1):
	d = arr[i-1] + (i-1)*arr[i-2]
	d = d %  mod
	arr.append(d)
t = int(input())
for i in range(t):
	n = int(input())
	print(arr[n])


MAXM = 10**6+5
dp = [1]*MAXM
dp[2] = 2
dp[3] = 4
for i in range(4,MAXM):
	dp[i] = (dp[i-1] + (i-1)*dp[i-2])%(10**9+7)

for tc in range(eval(input())):
	print(dp[eval(input())])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T=int(input())
A=[-1 for i in range(1000001)]
A[0]=1
A[1]=1
maxn=1
for i in range(T):
	n=int(input())
	if n>maxn:
		for j in range(maxn+1,n+1):
			A[j]=(A[j-1]+(j-1)*A[j-2])%1000000007
		maxn=n
	print(A[n])



a = [0,1,2,4]
for i in range(4,(10**6)+10):
	x = a[-1]
	y = a[-2]
	z = (x + (i-1)*y)%((10**9)+7)
	a += [z]
t = eval(input())
for _ in range(t):
	n = eval(input())
	print(a[n])


MOD = 1000000007

def solve(xs):
	n = max(xs)
	dp = [1] * (n + 1)
	for i in range(2, n + 1):
		dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD
	return '\n'.join((str(dp[x]) for x in xs))

if __name__ == '__main__':
	t = int(input())
	print(solve([int(input()) for _ in range(t)]))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
table = [None] * 1000006
table[0] = 1
table[1] = 1

for i in range(2, 1000006):
	table[i] = (table[i-1] + (i-1)*table[i-2]) % 1000000007

for _ in range(eval(input())):
	people = eval(input())
	print(table[people])


arr = []
t=int(input())
for k in range(t):
	arr.append(int(input()))
maximum = max(arr)

table=[0 for x in range(maximum+1)]
table[1]=1
table[2]=2
for i in range(3,maximum+1):
	table[i]=(table[i-1]+(i-1)*table[i-2])%1000000007
for i in range(t):
	print(table[arr[i]])


t=int(eval(input()))
a=[None for i in range(1000003)]
a[0]=0
a[1]=1
a[2]=2
a[3]=4
for i in range(4,1000003):
	a[i]=a[i-1]+(i-1)*a[i-2]
	a[i]%=1000000007
	
while t>0:
	n=int(eval(input()))
	print(a[n])
	t-=1


T = int(input())
P = 1000000007
N = 1000000
A = [0]*(N+1)
A[0] = 0
A[1] = 1
A[2] = 2
#X = pow(2,P-2,P)
for i in range(3,N+1):
	A[i] = (A[i-1] + ((i-1)*A[i-2]))%P
#print A
for _ in range(T):
	N = int(input())
	print(A[N])


mod = 10**9 + 7
MAX = 10**6 + 5


def precompute(A):
	for i in range(2, MAX):
		A[i] = (A[i - 1] + A[i - 2] * (i - 1)) % mod

if __name__ == '__main__':
	A = [1] * MAX
	precompute(A)
	for _ in range(eval(input())):
		print(A[eval(input())])


T=int(input())

cache=[-1]*10000000

modulo=1000000000+7

maxIndex=1

def makePairs(N):
	global maxIndex
	if(N<=maxIndex):
		return cache[N]
	else:
		for i in range(maxIndex,N+1):
			cache[i]=(cache[i-1]+((i-1)*cache[i-2])%(modulo))%modulo
	 
		maxIndex=N
		return cache[N]



for _ in range(0,T):
	N=int(input())
	cache[1]=1
	cache[0]=1

	print(makePairs(N))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = 10**6
DP = []
DP.append(1)  #For N =0 
DP.append(1)   # For N = 1
for i in range(2,n+1):
	DP.append((DP[i-1] + (i-1)*DP[i-2])%(10**9+7))
case = eval(input())
for x in range(case):
	n = eval(input())
	print(DP[n])



def dp():
   
	d = [0]*1000002
	
	d[1]=1
	d[2]=2
	d[3]=4
	
	
	for i in range(4,1000001):
		d[i] =d[i-1] + (i-1)*d[i-2];
		d[i]=d[i]%(10**9+7)
	return d

T = int(input())
a=[]
for i in range(T):
	data = int(input())
	a.append(data)
	
Array = dp()
for item in a:
	print(Array[item])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
print 'Hello World!'
import sys
def fact(a):
	j=1
	for i in xrange(1,a+1):
		j=j*i
	return j
data=sys.stdin.readlines()
for i in xrange(1,len(data)):
	count=0;
	N=int(data[i])
	if N%2==0:
		count=N*(N-1)/2
	else:
		count=N
		N=N-1
	n_fact=fact(N)
	for j in range(N,0,-2):
		b=j;c=N-j
		d=fact(j)*fact(c)
		e=n_fact/d
		if c>0:
			f=c*c-1/2
		else:
			f=0
		count=count+e+f
	print count
'''
N_max=10**6
total=[0,1,2,4]
for i in range(4,N_max):
	total.append((total[i-1]+(i-1)*total[i-2])%(10**9+7))
import sys
data=sys.stdin.readlines()
for i in range(1,len(data)):
	N=int(data[i])
	print(total[N])
				


MAXM = 10**6+5
dp = [1]*MAXM
dp[2] = 2
dp[3] = 4
for i in range(4,MAXM):
	dp[i] = (dp[i-1] + (i-1)*dp[i-2])%(10**9+7)

for tc in range(eval(input())):
	print(dp[eval(input())])


arr = {}
mod = 10**9+7
arr[0] = arr[1] = 1
for i in range(2,1000007):
	arr[i] = (arr[i-1] + (i-1)*arr[i-2] )% mod
test = eval(input())
while test:
	test-=1
	n = eval(input())
	print(arr[n])