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 145796525
77 593251712
78 1128883301
79 1767472167
80 472638328
81 1380608683
82 405235944
83 1691155599
84 1163321509
85 920970661
86 1018598879
87 1514024650
88 424798709
89 1946625195
90 9203382
91 896331198
92 633064841
93 1431355902
94 1423661281
95 821286190
96 1941146458
97 959418974
98 283599568
99 312127193
100 1520732257
101 339009536
102 1521781075
103 1694693745
104 1725064633
105 561123285
106 1425238523
107 1563877168
108 491771165
109 49187807
110 281854362
111 1609383206
112 690205101
113 851279490
114 1759795559
115 1704229274
116 1634012244
117 1342394650
118 1401018276
119 1539733008
120 470937313
121 561464189
122 1416279247
123 658700645
124 1827788882
125 962157652
126 561161231
127 644611750
128 238302560
129 1105217921
130 869003757
131 1394349753
132 1728739164
133 845140643
134 674870122
135 1470366368
136 477943296
137 456263066
138 1977196451
139 853917171
140 707336517
141 1394230464
142 1034935340
143 764695079
144 282928112
145 383251156
146 447042983
147 1693448760
148 307027986
149 1834446832
150 2048675047
151 1382191398
152 174886481
153 1006882644
154 460256077
155 1603078237
156 170122435
157 1490392205
158 14945357
159 1161615839
160 517016297
161 893530779
162 1329319640
163 443829411
164 1683897836
165 264559004
166 1428583952
167 141077687
168 811029073
169 2004014817
170 8756686
171 13896741
172 1012940063
173 42465341
174 880365575
175 1510431226
176 1088222164
177 365517785
178 1031670692
179 682777505
180 568846600
181 797021862
182 16740227
183 2004393868
184 1209451544
185 1022194792
186 1890606271
187 89913978
188 214649764
189 1766591779
190 1585997812
191 87625000
192 1878528796
193 1633517800
194 1815888106
195 1676335960
196 1407817905
197 2027158589
198 467787775
199 1413590108
200 1929454861
201 1841620585
202 1515713536
203 1199012306
204 1524714527
205 496882895
206 438268822
207 1893615372
208 1218154961
209 2051158173
210 8117248
211 1450512892
212 669550185
213 1169900215
214 11745854
215 1511945114
216 1311546080
217 81308161
218 411135771
219 1882304169
220 1114848867
221 1767804368
222 963858468
223 17575598
224 728657086
225 1881247459
226 1261780092
227 1246723312
228 849396186
229 1514383486
230 1221967621
231 1857321313
232 653034757
233 1265252930
234 1433643963
235 2000052085
236 1750313802
237 1893472818
238 773416753
239 1293379670
240 153064036
241 547715357
242 1399815461
243 1384336369
244 46717955
245 1757355332
246 719720801
247 992784350
248 1778470238
249 1907189226
250 427619392
251 81415568
252 136394913
253 1973831386
254 1474141845
255 1160743680
256 1377621191
257 945577007
258 1570186204
259 1288349726
260 398596835
261 1325710103
262 945515311
263 1111845302
264 758130741
265 1573589640
266 416851364
267 726413128
268 1626906073
269 883804958
270 492859963
271 447632585
272 771202115
273 1588538297
274 1312454301
275 515304632
276 40226534
277 1016471163
278 1849493796
279 384621109
280 791286895
281 1989582728
282 419070798
283 1654316658
284 1687662997
285 966163586
286 1450188514
287 1969373814
288 1498598701
289 2007339868
290 1033088075
291 40975336
292 1542737992
293 1936961834
294 1824968764
295 543660244
296 794535335
297 1823378744
298 829949134
299 1447736317
300 1966836209
301 1642081406
302 482414011
303 105613467
304 717885925
305 1368496247
306 1988278054
307 624559979
308 236692521
309 1542682088
310 2039471535
311 1618967839
312 226420973
313 670603458
314 615054978
315 973038420
316 1999879645
317 1139876800
318 1211396605
319 1283919807
320 1584713798
321 733636978
322 1620378822
323 934740035
324 1872817070
325 1156681533
326 1283473192
327 1566955234
328 1027519683
329 236457038
330 66691898
331 1388696499
332 89222230
333 982613334
334 1075567778
335 563916546
336 78175890
337 1453900465
338 1948431252
339 1912900905
340 41034473
341 1631136318
342 1800802713
343 1274986095
344 439723530
345 217371776
346 1372819210
347 260996811
348 728239023
349 1292171871
350 1105676023
351 326311994
352 992151133
353 572991307
354 410987496
355 1489518551
356 1864474088
357 1720223421
358 1805485635
359 206400081
360 2020190052
361 1625369123
362 1928932280
363 138969126
364 1123108331
365 750576291
366 757285392
367 1864355905
368 1058030089
369 872918070
370 473931570
371 488326372
372 1152696801
373 1034235892
374 1027817663
375 1780558724
376 325757909
377 392482924
378 122204778
379 1640894038
380 1327684854
381 451474291
382 271671083
383 1357820525
384 189350596
385 1299972005
386 1987615956
387 1771814147
388 1907364760
389 1883099882
390 978405662
391 1991308106
392 19432991
393 1626314800
394 738358052
395 167182502
396 833424327
397 1231460644
398 1348565947
399 709647131
400 883620011
401 651293476
402 170412056
403 541636087
404 615033504
405 809443405
406 1684967664
407 1382243464
408 1691711514
409 437869553
410 1081368098
411 1073093965
412 56937496
413 1375566768
414 774572820
415 422270573
416 1060964607
417 709423776
418 978654793
419 1501903700
420 229564860
421 956683825
422 1166395716
423 1236402048
424 442205507
425 1640121293
426 559615690
427 1530993516
428 1646611341
429 157488297
430 1497757000
431 1125855690
432 530250681
433 1793947411
434 1402595570
435 73811692
436 437759645
437 618320604
438 1356256321
439 432560969
440 1044148136
441 1731173738
442 288457426
443 443059241
444 1508393060
445 1718002055
446 47900653
447 1531034243
448 944066534
449 315706677
450 564240839
451 156969075
452 1844297759
453 774280874
454 1804061408
455 956178263
456 1898376348
457 1812500409
458 1576920230
459 584851954
460 116238548
461 1018405100
462 237416191
463 522505669
464 1135836712
465 1021268036
466 1892713080
467 1601018168
468 860536767
469 505516345
470 197900740
471 115142879
472 1015944020
473 1907708997
474 1799841161
475 445741928
476 298488333
477 215345753
478 187216691
479 698123190
480 784071814
481 1235709215
482 637548746
483 471367203
484 2040377666
485 1509111731
486 254265906
487 207931652
488 1241565538
489 941148844
490 1446300486
491 1473870579
492 394499873
493 1142416118
494 990238735
495 1574038255
496 1348026697
497 26951102
498 1319653573
499 2008288404
500 633336741
501 811213395
502 531556924
503 1411990692
504 1993538896
505 1465711071
506 1542457579
507 42760589
508 905897245
509 1729500211
510 1601375612
511 110331339
512 1827494867
513 1577251950
514 1550243942
515 887329021
516 1999570009
517 1754547933
518 813829050
519 355284764
520 2014580331
521 1933648976
522 1407254883
523 1584467198
524 1001503144
525 191501257
526 218198246
527 1720031761
528 1878113548
529 464059904
530 1259468092
531 1317794776
532 516993258
533 345514126
534 737226425
535 237834156
536 251477878
537 268093583
538 205288055
539 1833704919
540 291899835
541 1452029668
542 1420254547
543 1947645665
544 964004598
545 1551855531
546 51815042
547 842773990
548 421458880
549 1374384256
550 282121266
551 565666287
552 804627607
553 1943442999
554 149458589
555 538268693
556 955809187
557 723901866
558 558984708
559 112212079
560 572810480
561 1725321545
562 1372118561
563 1291159173
564 1648786589
565 1494759834
566 1602543756
567 1831913475
568 515946466
569 463031741
570 1641290769
571 1543678551
572 480863980
573 547323779
574 2035966329
575 925827933
576 1369586560
577 697859291
578 520130169
579 1669200305
580 1948325107
581 1566188788
582 556387553
583 1055692232
584 1356262608
585 1542851917
586 274661738
587 253855583
588 847557196
589 1040526572
590 612294596
591 1434627816
592 1311907106
593 1626912121
594 243849743
595 558078722
596 403910498
597 1388079552
598 448356151
599 685627841
600 1681723264
601 944557753
602 114384746
603 650278438
604 1808382970
605 769290418
606 228999920
607 1350055840
608 555107837
609 2039946961
610 1703693224
611 839805267
612 1709227586
613 303126146
614 865244062
615 1404971506
616 626527779
617 1843659970
618 883520865
619 248692909
620 2021514643
621 1560687797
622 145847997
623 38926676
624 1320314882
625 137021618
626 1355025615
627 1575226744
628 610496436
629 1908721425
630 550817991
631 756279858
632 651458885
633 400637039
634 173082381
635 801512867
636 1478402157
637 396321802
638 1424498344
639 1538491056
640 1721869993
641 1927515201
642 1678930838
643 1208696533
644 553913640
645 1702632088
646 1517197211
647 1447652180
648 525261728
649 89039946
650 396408193
651 802847458
652 1383441209
653 459691756
654 128869950
655 1576706459
656 1548065172
657 875346045
658 65880883
659 413145820
660 233351615
661 443089367
662 912044841
663 1166026642
664 623930749
665 1424904892
666 952743863
667 1999638593
668 1983189418
669 365494662
670 1258804767
671 887747425
672 272806300
673 248272553
674 141966060
675 379862364
676 406649185
677 462259843
678 871275634
679 413232347
680 1909043190
681 1200873107
682 203548332
683 850083480
684 132367154
685 2057232237
686 359652352
687 2013496750
688 626854657
689 1915733372
690 957375564
691 741152179
692 296441327
693 1713258989
694 923066506
695 524159080
696 425089395
697 1601816703
698 1919762827
699 1385207928
700 452574741
701 1118214478
702 489799845
703 181921607
704 181398868
705 1702031459
706 37668743
707 1291212989
708 71589577
709 691107370
710 32785473
711 896648063
712 204186665
713 253835697
714 569252624
715 953099763
716 1703657294
717 1072105934
718 932032531
719 441480996
720 1745045713
721 298618667
722 313037407
723 18264689
724 1763043729
725 1240246538
726 1461394346
727 906698286
728 1945491178
729 128628028
730 1963411681
731 500787878
732 1800330880
733 1139798118
734 106816901
735 1135783684
736 1501815800
737 1175132987
738 931699327
739 1173630668
740 430629063
741 1696518018
742 398562100
743 1141491715
744 856381106
745 1873521053
746 1754355578
747 1363589355
748 1133901201
749 328936444
750 1008879243
