0 1
1 1
2 2
3 4
4 6
5 10
6 16
7 31
8 43
9 68
10 98
11 153
12 213
13 317
14 443
15 704
16 971
17 1415
18 1975
19 2818
20 3865
21 5401
22 7366
23 10142
24 13639
25 18438
26 24583
27 32861
28 43345
29 57268
30 75175
31 99119
32 129278
33 168796
34 219614
35 284887
36 368546
37 475919
38 614379
39 788845
40 1012117
41 1293980
42 1654090
43 2104744
44 2677531
45 3393574
46 4305104
47 5434435
48 6858872
49 8625950
50 10845387
51 13584140
52 17007379
53 21224181
54 26474103
55 32912316
56 40885157
57 50644187
58 62684210
59 77366414
60 95402658
61 117358139
62 144243483
63 176859771
64 216641373
65 264809668
66 323376028
67 394085520
68 479791149
69 583076304
70 707934824
71 857970202
72 1038816470
73 1255771998
74 1516621936
75 1828813578
76 175796513
77 623251700
78 1158883289
79 1797472155
80 532638304
81 1440608659
82 495235908
83 1781155563
84 1283321461
85 1070970601
86 1198598807
87 1724024566
88 694798601
89 219141436
90 399203226
91 1346331018
92 1173064625
93 33872011
94 146177342
95 1721285830
96 963662399
97 191934831
98 1783598968
99 54642846
100 1563247790
101 771524913
102 346812645
103 1029725111
104 1660095759
105 1216154123
106 862785398
107 1961423659
108 1833561
109 879249675
110 614431979
111 1684476476
112 837813892
113 1401403670
114 1074951333
115 264416450
116 2006714245
117 102643946
118 1296298218
119 1382559621
120 1251310201
121 1361899269
122 1499292364
123 1554291187
124 1190988887
125 832966304
126 1222093967
127 710700224
128 772061897
129 1591679427
130 1363198510
131 523824952
132 868525359
133 182784409
134 1297917674
135 1491396211
136 1297017070
137 798474581
138 130155242
139 1080199283
140 1199582623
141 747596626
142 604576516
143 1000797689
144 1150709870
145 1902960854
146 1206476636
147 1565432969
148 1199419638
149 360198232
150 683251705
151 1463637029
152 1016338910
153 1366573218
154 101509041
155 1096826363
156 877422579
157 1789973466
158 1968175311
159 1317597517
160 1322521421
161 370612741
162 1240279136
163 1223794218
164 1488369843
165 1509411596
166 1080190294
167 53791039
168 1904793969
169 481977428
170 274744103
171 1275124484
172 1062588318
173 1682254141
174 1025776858
175 25798601
176 804401954
177 980140267
178 1071841462
179 422809561
180 1355540512
181 297525323
182 1113824395
183 566955858
184 935335041
185 456301694
186 1845391321
187 1771038614
188 799214738
189 1483880725
190 633380380
191 1699035279
192 1965651258
193 614448819
194 474052665
195 1374558116
196 1122579126
197 903040483
198 1254616616
199 1723959434
200 1688881545
201 606624809
202 829692200
203 1053581295
204 703938175
205 1239483772
206 880464409
207 79994359
208 88206255
209 1536675862
210 351347477
211 123298499
212 735919310
213 299968849
214 509247133
215 905836938
216 1884072858
217 2017935108
218 547440267
219 1225431759
220 660039694
221 195015705
222 492400688
223 1731533407
224 106104876
225 517252385
226 1243748140
227 204534499
228 1893709557
229 1210984299
230 135587457
231 1782740914
232 1717472669
233 1877007661
234 569042460
235 1486127717
236 613313872
237 1645392605
238 249927440
239 702706894
240 87350211
241 1991459056
242 790304037
243 1400863794
244 4822329
245 1879644903
246 1343275625
247 1979682934
248 480851979
249 245728822
250 1966945826
251 1478589964
252 1397890645
253 1489786052
254 125670194
255 1293544474
256 1638581861
257 1402771084
258 552111510
259 419912733
260 1359262043
261 1904870056
262 80932140
263 1466040422
264 1325173671
265 173665602
266 1056379289
267 1691360121
268 593308096
269 501305398
270 509131885
271 734573275
272 1390876740
273 1851636251
274 1574671577
275 1508427002
276 1928352356
277 1587381153
278 1677410234
279 690181442
280 1581685667
281 1530547472
282 1450238700
283 223703151
284 974833625
285 1782775125
286 44434653
287 36318452
288 1529231979
289 262988695
290 751301899
291 1164352025
292 767112575
293 1892929469
294 610754394
295 267216933
296 1716703680
297 449314997
298 155873124
299 61604686
300 1475457443
301 437039777
302 692705866
303 938976936
304 1153462253
305 1703070844
306 1952371142
307 1288670592
308 1248848846
309 1719660196
310 946367456
311 391244512
312 1267094098
313 627990766
314 100799107
315 299062226
316 206290129
317 1771349850
318 284923411
319 708598443
320 1022296092
321 1750945536
322 1178775073
323 120804787
324 1339506843
325 1941289508
326 668182334
327 837345210
328 1087716806
329 546670054
330 559063330
331 166980698
332 575991702
333 165613589
334 748118886
335 783386864
336 1458120799
337 1645301637
338 1874269188
339 493992282
340 574109769
341 944949244
342 1601812632
343 776648046
344 721646292
345 1679706271
346 849190073
347 1662513190
348 1101093106
349 1676971999
350 1928841672
351 782299619
352 1129255885
353 1605495056
354 105881865
355 1423720249
356 248129643
357 104248941
358 1058813843
359 249666389
360 424329605
361 499464210
362 1584139441
363 474243067
364 654312870
365 1170570484
366 1068254661
367 1428162855
368 356637560
369 980958608
370 1624793839
371 1794209872
372 699424163
373 1201499612
374 987329852
375 1925941016
376 524657916
377 784155913
378 1458996339
379 37206504
380 1768339283
381 39082231
382 937353432
383 1691460371
384 621119631
385 870294603
386 710195647
387 368078850
388 172408526
389 260496436
390 74104253
391 1386776377
392 735602428
393 1549448362
394 1391367118
395 1540298695
396 864602684
397 1849908051
398 1017909929
399 503802216
400 1808871839
401 1553323185
402 1311753569
403 938458826
404 1449208110
405 1581500383
406 849520245
407 993460343
408 581909824
409 1230040382
410 969797072
411 86046678
412 1794709421
413 1367283617
414 1769953495
415 211967415
416 1784593069
417 172319722
418 65517429
419 1972656995
420 1929015556
421 1724098271
422 1650407120
423 1809422920
424 341265937
425 866225807
426 1896711942
427 576165854
428 829106183
429 1119801547
430 1922108434
431 149583548
432 840402105
433 1609825569
434 1244452670
435 603588440
436 30528057
437 878469423
438 273453790
439 102215050
440 1774830262
441 662038711
442 494899916
443 221551717
444 1261917049
445 750728692
446 1421906969
447 272039674
448 852256396
449 808256082
450 2023004096
451 1232287603
452 96863465
453 619266192
454 1364973859
455 886119386
456 1181207958
457 1450634546
458 1191118594
459 88422584
460 781252117
461 283994289
462 1933334
463 1079247275
464 882305778
465 317309557
466 1346865379
467 916856432
468 796049576
469 715119623
470 940510839
471 843885434
472 357264402
473 574897239
474 1894407420
475 121681921
476 980424282
477 1225531669
478 340942514
479 70128317
480 524873063
481 1253737500
482 956088084
483 837887834
484 431731847
485 1147782319
486 1465883958
487 481813509
488 31610490
489 557186713
490 230728324
491 1399277009
492 1422538211
493 393132083
494 1151069766
495 970574354
496 235020689
497 1160152545
498 1075350488
499 420834739
500 418859878
501 786868631
502 1599545313
503 1203216724
504 101220905
505 1141352521
506 1053316889
507 797907538
508 1801269380
509 523263229
510 642508994
511 276183668
512 1773825481
513 1037815355
514 593274395
515 1403136451
516 835180793
517 306712829
518 1877162212
519 239341755
520 1353607232
521 1602837777
522 487792562
523 1688635713
524 1511509854
525 1574455656
526 588285213
527 75738118
528 252637858
529 1131987683
530 6276795
531 1931075235
532 812681259
533 1953836365
534 1059435338
535 382136349
536 12489205
537 1738935399
538 895174138
539 1581116726
540 890809462
541 1864060245
542 388573548
543 332161436
544 943766632
545 1988105301
546 1249747884
547 818153068
548 1992614854
549 849037162
550 1342224348
551 95046147
552 822189886
553 1107164086
554 1828041663
555 1000544997
556 1685770563
557 6173707
558 1914871109
559 208710955
560 1154682180
561 1701975286
562 114110264
563 1062874846
564 1528826326
565 1158380154
566 1339454637
567 1068675586
568 180754942
569 1041089292
570 813136285
571 413307991
572 647290166
573 1858610613
574 1205493517
575 980448655
576 61646532
577 1771910721
578 735256260
579 1614231234
580 410292228
581 50813454
582 6175138
583 1406960662
584 1578517009
585 1990232416
586 1920168200
587 22721098
588 683042128
589 313305289
590 1289033387
591 1683687054
592 1739087385
593 1077872731
594 267047745
595 1741244605
596 373286735
597 849570324
598 623922800
599 431936279
600 1517317228
601 1264142741
602 936605394
603 1625858632
604 83961959
605 64600790
606 1060649471
607 1047198291
608 1158662960
609 1917821476
610 1415053924
611 740833840
612 1192425525
613 978620401
614 1008548777
615 166940590
616 1546014717
617 835799997
618 1567403702
619 199865354
620 1960996637
621 398525790
622 642640974
623 186415810
624 586472239
625 244648920
626 758594289
627 1204145518
628 1007637990
629 1621614743
630 1838946658
631 772076753
632 141338750
633 1929330417
634 1941205921
635 1612996476
636 1426116802
637 1070008801
638 189441005
639 131563567
640 50605499
641 422278898
642 801072318
643 637617952
644 73391845
645 644560982
646 1869158228
647 955337239
648 1501239959
649 911057359
650 1439423729
651 1773840471
652 1376462758
653 1168992296
654 296014907
655 1070172603
656 1530373317
657 613828932
658 1229751315
659 1271164587
660 187429036
661 581949188
662 166165673
663 1621346614
664 1961454061
665 1259979421
666 599994270
667 902677764
668 1036617768
669 1617195654
670 1362598498
671 233795150
672 24779214
673 1187848543
674 1305031851
675 1013482403
676 1017831595
677 1776297513
678 1093467980
679 1883497695
680 1668957810
681 613521404
682 1881008437
683 1521162122
684 89818452
685 1233516102
686 694348137
687 1442465414
688 1275534637
689 667559486
690 958735727
691 1836009658
692 357892037
693 565870147
694 1378667302
695 1331370678
696 1601696921
697 1816772051
698 722316016
699 1264985636
700 543861580
701 619469491
702 1216954254
703 928407540
704 437576156
705 779921935
706 313508417
707 1543424964
708 1181011756
709 619594956
710 444437861
711 1269512107
712 664228708
713 873886036
714 1858595144
715 588985516
716 554738629
717 1767879798
718 493961635
719 1712982890
720 1403500223
721 914156511
722 1024182813
723 682484640
724 1287740595
725 1308140018
726 1544634801
727 182679784
728 967561910
729 774130077
730 1717412086
731 1043538513
732 1180133482
733 968340369
734 218153550
735 1548827131
736 1945806142
737 1582203007
738 1505273574
739 953458962
740 553493958
741 933172828
742 585419223
743 1498140683
744 914371593
745 882214005
746 2000704199
747 239689332
748 994745196
749 1838031809
750 1859969868
