Pizza Stack

Kamaldeep is good at making pizzas. Generally he gets requests to serve N pizzas at once. He serves them in the form of a stack. A pizza should be treated as a circular disk with some radius.

Kamaldeep needs to take care that when he places a pizza on the top of the stack the radius of the pizza should not exceed the radius of the largest pizza in the stack by more than 1. Additionally all radii should be positive integers, and the bottom most pizza should have its radius as 1. Kamaldeep is week in maths :P, so he wants you to find out in how many ways can he create a stack containing N pizzas.

Input

First line of the input contains T (T <= 1000) denoting the number of test cases.

T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.

Output

For each case the output should be a single integer representing the number of ways a stack of size N can be created. As

the answer can be large print it modulo 1000000007.

ANS------->

dp[i][j] -> stack size of i with j different value .

dp[i][j] = j*dp[i-1][j] + dp[i-1][j-1];

1. #include <iostream>
2. using namespace std;
3.  
4. int main()
5. {
6. int t ;
7. cin >> t;
9. long long mo = 1000000007;
10.  
11. long long dp[1002][1002];
12. long long top[1002];
14. for(int i=0 ; i < 1002 ; i++)
15. for(int j=0 ; j < 1002 ; j++)
16. dp[i][j]=0;
17.  
18. dp[1][1]=1 ;
19. top[1]=1;
22. for(int i=2 ; i < 1002 ; i++){
23. long long temp = 0 ;
24. for(int j=1; j<=i; j++){
25. dp[i][j]=j*dp[i-1][j]%mo + dp[i-1][j-1]%mo;
26. temp=(temp+dp[i][j])%mo;
27. }
28. top[i]=temp;
29. }
33. while(t--){
35. int val ;
36. cin >> val ;
37. cout << top[val] << endl ;
39. }
41.  
42. return 0;
43. }