Chef is good at making pancakes. Generally he gets requests to serve N pancakes at once.
He serves them in the form of a stack.
A pancake can be treated as a circular disk with some radius.
Chef needs to take care that when he places a pancake on the top of the stack the radius of the pancake should not exceed the radius of the largest pancake in the stack by more than 1. 
Additionally all radii should be positive integers, and the bottom most pancake should have its radius as 1.
Chef wants you to find out in how many ways can he create a stack containing N pancakes.
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.
Example
Input
2
1
2

Output
1
2

Difficulty: interview

Starter code:

Solutions:
t=[[1]]
def bell_numbers(start, stop):
 ## Swap start and stop if start > stop
 if stop < start: start, stop = stop, start
 if start < 1: start = 1
 if stop < 1: stop = 1
 c = 1 ## Bell numbers count
 while c <= stop:
  if c >= start:
   yield t[-1][0] ## Yield the Bell number of the previous                 row
  row = [t[-1][-1]] ## Initialize a new row
  for b in t[-1]:
   row.append((row[-1] + b)%1000000007)
  c += 1 ## We have found another Bell number
  t.append(row) ## Append the row to the triangle

ar=[0]*1001
i=0
for b in bell_numbers(1,1001):
 ar[i]=b
 i+=1
T=eval(input())
while T:
 N=eval(input())
 print(ar[N])
 T-=1


def bell_numbers(start, stop):
 ## Swap start and stop if start > stop
 if stop < start: start, stop = stop, start
 if start < 1: start = 1
 if stop < 1: stop = 1
 t = [[1]] ## Initialize the triangle as a two        -dimensional array
 c = 1 ## Bell numbers count
 while c <= stop:
  if c >= start:
   yield t[-1][0] ## Yield the Bell number of the previous                 row
  row = [t[-1][-1]] ## Initialize a new row
  for b in t[-1]:
   row.append(row[-1] + b) ## Populate the new row
  c += 1 ## We have found another Bell number
  t.append(row) ## Append the row to the triangle

be = []
be1 = [275408655
,665183437
,130342900
,699431744
,117550047
,460234251
,56770880
,306091228
,912949106
,626369877
,852501236
,241076503
,262988042
,737247015
,831044258
,475123008
,928949542
,332750699
,696284377
,689111142
,196862045
,570365577
,187156806
,451528865
,635110126
,385331290
,263486377
,200189955
,206842029
,457862597
,450522487
,818984909
,710634976
,461356455
,71985964
,781500456
,467334209
,46762760
,97663653
,870671823
,255977331
,79650379
,32876340
,636190780
,364339752
,597149326
,452604321
,748186407
,302032725
,779013981
,111971627
,175687535
,399961122
,451853028
,798326812
,902775588
,362836436
,498862780
,160000437
,629259604
,919729986
,5994845
,631476109
,371320167
,76164236
,448643023
,945220853
,111192011
,150577654
,827274836
,17668451
,938388515
,88566735
,27940328
,882026632
,712756966
,83642744
,873585716
,638987456
,405271094
,822216133
,345587303
,668558160
,314983205
,826678060
,563583341
,516998387
,77703032
,726563479
,155257773
,49705622
,891556456
,164127879
,842558039
,189099480
,956148983
,992226557
,671472701
,137476493
,871069222
,78241093
,728497057
,278888712
,332713952
,222597908
,235198692
,876216003
,167364357
,722341150
,519365334
,604855967
,834816722
,850786742
,416385106
,608404143
,311628039
,507077268
,571796589
,506398832
,305540948
,556971113
,444565912
,866477296
,411983920
,905854221
,901986568
,512703782
,684027511
,596294441
,916862272
,495347444
,802477106
,235968146
,257527513
,528476230
,969655767
,772044489
,682345813
,66418556
,603372280
,439233253
,278244332
,590581374
,353687769
,321352820
,245676729
,325255315
,91010070
,923699200
,837616604
,736177081
,528261400
,876353388
,339195128
,377206087
,769944080
,772953529
,123785293
,35984916
,461119619
,236140329
,884137913
,625494604
,791773064
,661436140
,308509072
,54134926
,279367618
,51918421
,149844467
,308119110
,948074070
,941738748
,890320056
,933243910
,430364344
,903312966
,574904506
,56353560
,861112413
,440392450
,937276559
,944662107
,599470900
,458887833
,962614595
,589151703
,997944986
,642961512
,63773929
,737273926
,110546606
,654813100
,374632916
,327432718
,307869727
,387738989
,133844439
,688886605
,989252194
,303514517
,79062408
,79381603
,941446109
,189307316
,728764788
,619946432
,359845738
,216171670
,690964059
,337106876
,762119224
,226624101
,401879891
,47069454
,41411521
,429556898
,188042667
,832342137
,770962364
,294422843
,991268380
,137519647
,903275202
,115040918
,521250780
,783585266
,98267582
,337193737
,717487549
,510794369
,206729333
,248526905
,412652544
,146948138
,103954760
,132289464
,938042429
,185735408
,640754677
,315573450
,956487685
,454822141
,783819416
,882547786
,976850791
,307258357
,929434429
,832158433
,334518103
,700273615
,734048238
,48618988
,693477108
,12561960
,598093056
,154072663
,174314067
,345548333
,479759833
,658594149
,282072153
,57970886
,905112877
,584117466
,472359245
,776860470
,324216896
,334199385
,321245477
,508188925
,521442872
,286692969
,245141864
,59342176
,896413224
,573301289
,869453643
,87399903
,60102262
,835514392
,493582549
,649986925
,576899388
,20454903
,271374500
,589229956
,505139242
,789538901
,243337905
,248443618
,39334644
,831631854
,541659849
,159802612
,524090232
,855135628
,542520502
,967119953
,597294058,
465231251]
for b in bell_numbers(1, 700):
 be.append(b%1000000007);
t = eval(input())
t=t-1;
while (t>=0):
 nb = eval(input())
 if nb>=700:
  print(be1[int(nb)-700])
 else:
  print(be[int(nb)])
 t=t-1

def bell_numbers(start, stop):
 ## Swap start and stop if start > stop
 if stop < start: start, stop = stop, start
 if start < 1: start = 1
 if stop < 1: stop = 1
 t = [[1]] ## Initialize the triangle as a two        -dimensional array
 c = 1 ## Bell numbers count
 while c <= stop:
  if c >= start:
   yield t[-1][0] ## Yield the Bell number of the previous                 row
  row = [t[-1][-1]] ## Initialize a new row
  for b in t[-1]:
   row.append(row[-1] + b) ## Populate the new row
  c += 1 ## We have found another Bell number
  t.append(row) ## Append the row to the triangle

be = []
be1 = [275408655
,665183437
,130342900
,699431744
,117550047
,460234251
,56770880
,306091228
,912949106
,626369877
,852501236
,241076503
,262988042
,737247015
,831044258
,475123008
,928949542
,332750699
,696284377
,689111142
,196862045
,570365577
,187156806
,451528865
,635110126
,385331290
,263486377
,200189955
,206842029
,457862597
,450522487
,818984909
,710634976
,461356455
,71985964
,781500456
,467334209
,46762760
,97663653
,870671823
,255977331
,79650379
,32876340
,636190780
,364339752
,597149326
,452604321
,748186407
,302032725
,779013981
,111971627
,175687535
,399961122
,451853028
,798326812
,902775588
,362836436
,498862780
,160000437
,629259604
,919729986
,5994845
,631476109
,371320167
,76164236
,448643023
,945220853
,111192011
,150577654
,827274836
,17668451
,938388515
,88566735
,27940328
,882026632
,712756966
,83642744
,873585716
,638987456
,405271094
,822216133
,345587303
,668558160
,314983205
,826678060
,563583341
,516998387
,77703032
,726563479
,155257773
,49705622
,891556456
,164127879
,842558039
,189099480
,956148983
,992226557
,671472701
,137476493
,871069222
,78241093
,728497057
,278888712
,332713952
,222597908
,235198692
,876216003
,167364357
,722341150
,519365334
,604855967
,834816722
,850786742
,416385106
,608404143
,311628039
,507077268
,571796589
,506398832
,305540948
,556971113
,444565912
,866477296
,411983920
,905854221
,901986568
,512703782
,684027511
,596294441
,916862272
,495347444
,802477106
,235968146
,257527513
,528476230
,969655767
,772044489
,682345813
,66418556
,603372280
,439233253
,278244332
,590581374
,353687769
,321352820
,245676729
,325255315
,91010070
,923699200
,837616604
,736177081
,528261400
,876353388
,339195128
,377206087
,769944080
,772953529
,123785293
,35984916
,461119619
,236140329
,884137913
,625494604
,791773064
,661436140
,308509072
,54134926
,279367618
,51918421
,149844467
,308119110
,948074070
,941738748
,890320056
,933243910
,430364344
,903312966
,574904506
,56353560
,861112413
,440392450
,937276559
,944662107
,599470900
,458887833
,962614595
,589151703
,997944986
,642961512
,63773929
,737273926
,110546606
,654813100
,374632916
,327432718
,307869727
,387738989
,133844439
,688886605
,989252194
,303514517
,79062408
,79381603
,941446109
,189307316
,728764788
,619946432
,359845738
,216171670
,690964059
,337106876
,762119224
,226624101
,401879891
,47069454
,41411521
,429556898
,188042667
,832342137
,770962364
,294422843
,991268380
,137519647
,903275202
,115040918
,521250780
,783585266
,98267582
,337193737
,717487549
,510794369
,206729333
,248526905
,412652544
,146948138
,103954760
,132289464
,938042429
,185735408
,640754677
,315573450
,956487685
,454822141
,783819416
,882547786
,976850791
,307258357
,929434429
,832158433
,334518103
,700273615
,734048238
,48618988
,693477108
,12561960
,598093056
,154072663
,174314067
,345548333
,479759833
,658594149
,282072153
,57970886
,905112877
,584117466
,472359245
,776860470
,324216896
,334199385
,321245477
,508188925
,521442872
,286692969
,245141864
,59342176
,896413224
,573301289
,869453643
,87399903
,60102262
,835514392
,493582549
,649986925
,576899388
,20454903
,271374500
,589229956
,505139242
,789538901
,243337905
,248443618
,39334644
,831631854
,541659849
,159802612
,524090232
,855135628
,542520502
,967119953
,597294058,
465231251]
for b in bell_numbers(1, 700):
 be.append(b%1000000007);
t = eval(input())
t=t-1;
while (t>=0):
 nb = eval(input())
 if nb>=700:
  print(be1[int(nb)-700])
 else:
  print(be[int(nb)])
 t=t-1

bell_nums = [1]
t = [[1]]

def generate_num():
 nonlocal bell_nums
 nonlocal t
 for i in range(1,1001):
  t.append([])
  t[i].append(t[i-1][i-1])
  for j in range(1,i+1):
   t[i].append((t[i][j-1] + t[i-1][j-1]) % 1000000007)
  bell_nums.append(t[i][i])

generate_num()
tc = int(input())
while tc:
 n = int(input())
 print(bell_nums[n-1])
 tc -= 1


#!/usr/bin/env python

BELL = []
for i in range(1000): BELL.append([0] * 1000)
BELL[0][0] = 1

for r in range(1, 1000):
 BELL[r][0] = BELL[r-1][r-1]
 for c in range(1, r + 1):
  BELL[r][c] = (BELL[r-1][c-1] + BELL[r][c-1]) % 1000000007

def main():
 T = int(input())
 for t in range(T):
  N = int(input())
  print(BELL[N-1][N-1])

main()




b=[]
def bell(a):
 nonlocal b
 l=[[1]]
 if a==1: return 1
 b.append(1)
 if a==2: return 2
 b.append(2)
 l.append([1])
 l[1].append(2)
 for j in range(2,a):
  l.append([(l[j-1][j-1])%1000000007])
  for k in range(1,j+1):
   l[j].append((l[j][k-1]+l[j-1][k-1])%1000000007)
  b.append((l[j][j])%1000000007)
 return l[a-1][a-1]

n=eval(input())
bell(1000)
for i in range(0,n):
 x=eval(input())
 print(b[x-1])

ans=[1]
def bell_numbers(start, stop):
     ## Swap start and stop if start > stop
 if stop < start: start, stop = stop, start
 if start < 1: start = 1
 if stop < 1: stop = 1

 t = [[1]] ## Initialize the triangle as a two        -dimensional array
 c = 1 ## Bell numbers count
 while c <= stop:
  if c >= start:
   yield t[-1][0] ## Yield the Bell number of the previous                 row
  row = [t[-1][-1]] ## Initialize a new row
  for b in t[-1]:
   row.append((row[-1]%1000000007 + b%1000000007)%1000000007) ##                 Populate the new row
  c += 1 ## We have found another Bell number
  t.append(row) ## Append the row to the triangle
  ans.append(row[-1])
 t=list(t)
 
b=[]
b=bell_numbers(1,1001)
x=eval(input())
count=1
for i in b:
 count+=1
while(x > 0):
 y=eval(input())
 print(ans[y-1]%1000000007)
 x=x-1