0 1
1 1
2 2
3 3
4 5
5 7
6 10
7 13
8 18
9 24
10 30
11 38
12 49
13 59
14 73
15 90
16 108
17 129
18 159
19 184
20 216
21 258
22 298
23 347
24 410
25 466
26 538
27 626
28 707
29 807
30 931
31 1043
32 1181
33 1351
34 1506
35 1691
36 1924
37 2132
38 2382
39 2688
40 2971
41 3300
42 3704
43 4073
44 4500
45 5021
46 5510
47 6065
48 6740
49 7362
50 8078
51 8937
52 9744
53 10652
54 11736
55 12745
56 13900
57 15261
58 16545
59 17986
60 19692
61 21294
62 23089
63 25196
64 27195
65 29409
66 32017
67 34481
68 37213
69 40399
70 43447
71 46787
72 50678
73 54393
74 58467
75 63180
76 67721
77 72653
78 78357
79 83849
80 89815
81 96673
82 103306
83 110474
84 118704
85 126660
86 135269
87 145080
88 154620
89 164875
90 176575
91 187935
92 200150
93 214003
94 227528
95 241996
96 258396
97 274396
98 291510
99 310816
100 329749
101 349911
102 372616
103 394870
104 418569
105 445159
106 471339
107 499088
108 530193
109 560799
110 593266
111 629513
112 665301
113 703121
114 745299
115 786957
116 830989
117 879903
118 928349
119 979392
120 1036072
121 1092219
122 1151363
123 1216805
124 1281791
125 1350084
126 1425605
127 1500598
128 1579375
129 1666215
130 1752675
131 1843297
132 1943068
133 2042413
134 2146529
135 2260860
136 2374967
137 2494293
138 2625171
139 2755796
140 2892414
141 3041884
142 3191323
143 3347326
144 3517851
145 3688379
146 3866396
147 4060497
148 4254902
149 4457499
150 4678245
151 4899408
152 5129807
153 5380285
154 5631613
155 5893081
156 6177101
157 6462144
158 6758588
159 7079913
160 7402890
161 7738380
162 8101669
163 8466851
164 8846150
165 9256123
166 9668770
167 10096835
168 10559079
169 11024393
170 11507068
171 12027424
172 12551784
173 13095093
174 13680306
175 14270159
176 14881279
177 15538423
178 16201402
179 16887613
180 17624947
181 18368990
182 19138969
183 19964997
184 20799273
185 21661927
186 22586690
187 23520821
188 24486518
189 25520262
190 26565379
191 27645003
192 28799754
193 29967335
194 31173315
195 32461552
196 33765130
197 35110555
198 36546582
199 37999915
200 39499786
201 41098712
202 42717924
203 44387815
204 46166697
205 47968448
206 49826467
207 51803366
208 53806771
209 55871485
210 58066887
211 60292070
212 62584993
213 65020279
214 67489917
215 70033403
216 72733131
217 75471229
218 78290716
219 81280224
220 84313833
221 87436156
222 90744505
223 94101980
224 97557179
225 101214743
226 104928366
227 108748302
228 112789277
229 116892537
230 121112887
231 125573468
232 130104558
233 134762832
234 139683308
235 144682061
236 149820686
237 155243735
238 160754977
239 166418118
240 172391388
241 178462457
242 184700052
243 191273638
244 197957072
245 204821464
246 212051726
247 219403277
248 226952899
249 234898579
250 242980153
251 251276877
252 260004031
253 268880847
254 277992996
255 287570932
256 297315949
257 307316122
258 317821827
259 328511352
260 339479791
261 350994837
262 362714204
263 374735607
264 387349691
265 400188408
266 413356999
267 427165472
268 441222807
269 455637293
270 470745120
271 486126108
272 501896355
273 518414383
274 535234406
275 552475834
276 570526774
277 588908377
278 607748449
279 627461075
280 647538696
281 668112458
282 689629310
283 711545057
284 734000216
285 757471345
286 781381957
287 805875568
288 831465971
289 857536070
290 884239767
291 912124222
292 940535514
293 969630906
294 1000000008
295 1030943781
296 1062630306
297 1095686696
298 1129372713
299 1163860286
300 1199824679
301 1236475121
302 1273994453
303 1313100472
304 1352957190
305 1393751370
306 1436254741
307 1479574587
308 1523909378
309 1570079330
310 1617141554
311 1665298445
312 1715429848
313 1766530155
314 1818814767
315 1873218583
316 1928679631
317 1985416614
318 2044431526
319 2104593197
320 2166134549
321 2230119426
322 2295353174
323 2362071859
324 2431415243
325 2502112450
326 2574414167
327 2649528756
328 2726115159
329 2804427650
330 2885759803
331 2968686076
332 3053475183
333 3141497862
334 3231251330
335 3323008334
336 3418234483
337 3515332518
338 3614590314
339 3717560943
340 3822562020
341 3929884923
342 4041187548
343 4154683405
344 4270680313
345 4390934599
346 4513565509
347 4638882703
348 4768759313
349 4901200841
350 5036534622
351 5176743509
352 5319727546
353 5465815528
354 5617121231
355 5771419795
356 5929058460
357 6092272032
358 6258719357
359 6428749134
360 6604742817
361 6784221308
362 6967550892
363 7157248314
364 7350707213
365 7548295148
366 7752691403
367 7961137010
368 8174016925
369 8394162353
370 8618675181
371 8847940585
372 9084968019
373 9326692044
374 9573516815
375 9828621380
376 10088787001
377 10354415484
378 10628883340
379 10908789241
380 11194555266
381 11489746401
382 11790790710
383 12098106345
384 12415478543
385 12739136293
386 13069517568
387 13410615090
388 13758470848
389 14113518022
390 14479994058
391 14853722913
392 15235155667
393 15628759277
394 16030154457
395 16439786613
396 16862392758
397 17293352998
398 17733130377
399 18186717582
400 18649272991