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 55796523
77 503251710
78 1038883299
79 1677472165
80 292638324
81 1200608679
82 135235938
83 1421155593
84 803321501
85 470970651
86 478598867
87 884024636
88 1762282320
89 1046625175
90 986686985
91 1693814797
92 1160548434
93 1688839489
94 1321144860
95 268769759
96 938630017
97 1474386148
98 78566726
99 1444577962
100 1753183006
101 1548943888
102 1471715399
103 114628035
104 492482512
105 1463508374
106 2045107187
107 1451229397
108 1254090576
109 1146474388
110 1084108099
111 1396604083
112 619876725
113 2080885468
114 971852236
115 1753703876
116 900904735
117 84188617
118 1752680929
119 981264291
120 327304418
121 1797634300
122 162252278
123 914411010
124 610720096
125 742244095
126 850853636
127 2023844455
128 2027009875
129 1273334126
130 2118913981
131 333471827
132 1394425387
133 1754743258
134 645741312
135 1522309131
136 2145727804
137 1134659399
138 733425470
139 1732617754
140 1633147406
141 1591724755
142 38620461
143 1543980022
144 1539672518
145 1374216166
146 1511374831
147 35195098
148 630039608
149 1117475848
150 1517760218
151 1033174433
152 1795862848
153 1620717843
154 529487310
155 1687397915
156 1338828931
157 539873329
158 966030843
159 2054609889
160 691566393
161 116045570
162 347870442
163 810535272
164 1102343339
165 887081008
166 1063689303
167 1683180728
168 15352860
169 1353746634
170 1814850867
171 1894811870
172 1379277884
173 2104060379
174 978472921
175 1279652152
176 626044247
177 816691053
178 1232583638
179 250669057
180 1963468812
181 1792236717
182 1411919754
183 2145754291
184 1971190661
185 662530550
186 1490069362
187 671959622
188 718588905
189 1527677588
190 402798693
191 959003606
192 720423731
193 267585508
194 1612914468
195 619056893
196 718181937
197 552998088
198 1838768038
199 1951468436
200 1939871449
201 1187486033
202 1949545712
203 671574464
204 877307365
205 1917158745
206 1139502374
207 49488005
208 1205568812
209 1210882524
210 1972742833
211 842294991
212 524903026
213 538156225
214 627392747
215 1760208760
216 1584080848
217 1681731640
218 817103414
219 826115201
220 246696463
221 816243279
222 607012637
223 632306407
224 320886248
225 1062007843
226 426761205
227 1383950480
228 887120744
229 1523888647
230 766513480
231 599614213
232 883910324
233 561187446
234 864273434
235 753707337
236 1957306078
237 992753284
238 1672825027
239 1329629818
240 346934034
241 1248269182
242 2095463450
243 1612375650
244 368587870
245 1004094433
246 443108156
247 837505236
248 1578576893
249 155041662
250 1055182534
251 1713148175
252 1111678320
253 2091084142
254 1268808947
255 297775641
256 1825944704
257 383115390
258 1837364053
259 19887399
260 27737676
261 1313268072
262 1258556602
263 1185245797
264 697161761
265 1509920327
266 157706955
267 194507419
268 1386279961
269 259538440
270 1939468663
271 198032164
272 2028125001
273 1127941919
274 1870588462
275 382126256
276 1706035559
277 1942088422
278 1499561856
279 1247145771
280 1798372086
281 2051834689
282 793181055
283 2115065413
284 196477807
285 1704157246
286 887998355
287 1875256975
288 1817656655
289 152034177
290 1081985466
291 2108351621
292 1557689616
293 686149590
294 1690475228
295 1960087037
296 511105052
297 998128207
298 241249973
299 492699802
300 600630298
301 1429703335
302 1924902103
303 1111456769
304 646475118
305 763782419
306 1793475814
307 1575043525
308 1929544903
309 1882852547
310 35163018
311 2002940141
312 187391930
313 1787023208
314 509752872
315 157119256
316 473895267
317 1606674599
318 61628831
319 306986938
320 2132266869
321 1724827495
322 242020020
323 282515941
324 1457256547
325 1738142990
326 76057495
327 2067000513
328 558668491
329 73530662
330 1747599988
331 1350307980
332 1606646944
333 810337027
334 2132028779
335 1338663763
336 768870105
337 158626001
338 1288151272
339 1479859093
340 132415828
341 760812560
342 823485215
343 1722018169
344 315027670
345 2016304571
346 1861556529
347 1635151102
348 1989724911
349 1476573619
350 2127226413
351 533896420
352 878371609
353 692042117
354 16840891
355 1676468205
356 1327060954
357 1846083552
358 842763316
359 1491121540
360 1535008926
361 1101658303
362 1527282180
363 1384992501
364 1138081632
365 1595176741
366 221999317
367 680321575
368 1830153976
369 737695528
370 2070221364
371 45533934
372 1483048600
373 1285497845
374 62921132
375 1289776571
376 190516938
377 525021828
378 199982231
379 1213273424
380 1769725457
381 1892487490
382 1199826846
383 161957260
384 2088316603
385 1675244953
386 1132160024
387 1873288863
388 1648598889
389 2033075591
390 769117345
391 366349385
392 1135296491
393 1628904992
394 856755385
395 1004633846
396 1964900305
397 1158532260
398 791000719
399 525145886
400 902148216
401 497335399
402 1466733456
403 117911049
404 1579759248
405 428411747
406 553356796
407 1759200522
408 639328693
409 404644578
410 218147850
411 1349727588
412 1068961490
413 1995682175
414 280876592
415 1939388570
416 462658010
417 1815852649
418 148593603
419 1544344012
420 623635968
421 2027004400
422 1819041398
423 935835643
424 960166647
425 280870243
426 1563670629
427 1081650783
428 771088840
429 965535770
430 1566076734
431 934116906
432 463792139
433 1544797640
434 166059110
435 826012105
436 1821114701
437 1953424819
438 1112670970
439 623009292
440 289098965
441 689530655
442 737078273
443 898898912
444 392035501
445 698061988
446 23381499
447 1677767782
448 1544820520
449 1237601473
450 132598832
451 1100599811
452 955955078
453 1464889964
454 1717119438
455 26270441
456 1077612849
457 1883763556
458 1156898092
459 852945282
460 75867747
461 833367827
462 991694578
463 1641478084
464 809974591
465 1142221915
466 994596902
467 1640040337
468 731314182
469 1383626247
470 543975150
471 736113554
472 329227139
473 572761316
474 1958834494
475 1614338269
476 1665755983
477 915497919
478 68984865
479 1499510179
480 1811405716
481 1452436762
482 1606946576
483 1893494582
484 1787951251
485 1651875609
486 2035439242
487 948755852
488 427607783
489 1395556972
490 837401941
491 1184951701
492 1211883598
493 1825310240
494 1395692476
495 168560602
496 64629638
497 515703806
498 1990284922
499 1476537089
500 422049452
501 390658098
502 1489984095
503 1007820837
504 1824338362
505 1903863386
506 798459901
507 1578217573
508 1323259619
509 59759639
510 1980921975
511 1975805181
512 1133368973
513 461685077
514 2145996398
515 1195987404
516 1390001981
517 1438781246
518 941964872
519 1840329816
520 1092187688
521 1792346701
522 705667562
523 2139780359
524 913797295
525 651633524
526 1744918207
527 1618218202
528 349296390
529 774045554
530 1521479005
531 1168157336
532 1721056733
533 2054364085
534 512263560
535 893239033
536 1099448683
537 158659481
538 750459421
539 1218385405
540 498654631
541 1283744388
542 1792624702
543 2004879780
544 1637843738
545 665512616
546 1370208754
547 1615495007
548 741984685
549 1830707035
550 327664908
551 136288696
552 468506801
553 27882352
554 534105924
555 212733514
556 1592288592
557 472400917
558 1682646183
559 402480605
560 2118994597
561 836544650
562 1207648894
563 1993149532
564 68024466
565 1113367145
566 71037512
567 439347840
568 1395431775
569 1308457197
570 140229005
571 1426002084
572 1216710739
573 1753000723
574 1037300475
575 1951235743
576 2118533991
577 1081981977
578 1993830730
579 588690521
580 1663785949
581 1301207731
582 2070601510
583 570648112
584 43939755
585 1535097052
586 1820962658
587 2133225612
588 2054908948
589 1094290842
590 645142705
591 415993223
592 1015864826
593 894894329
594 970340133
595 576574242
596 1075057877
597 64935777
598 1875547297
599 1017186767
600 1448561977
601 1243149240
602 1571110482
603 89789170
604 740504449
605 1422734787
606 886621068
607 383439414
608 1421073365
609 1295774640
610 1290896151
611 1244129133
612 595341990
613 319029025
614 63182387
615 2042577348
616 239044693
617 1128035397
618 363501261
619 834914037
620 1866920099
621 73983785
622 796829892
623 16977281
624 1881485429
625 169526330
626 1782582347
627 1983632484
628 1580803056
629 2089270559
630 1118754831
631 632706059
632 368762065
633 1270189819
634 1507044075
635 46849730
636 612795596
637 1908045250
638 1644624340
639 1715233109
640 914273817
641 266295601
642 1823384703
643 1441229027
644 1950616363
645 1535860290
646 1215959902
647 596873204
648 1133052614
649 1304403872
650 1146987017
651 131454487
652 529328007
653 527996861
654 1927339128
655 1099885552
656 351098441
657 602156582
658 768150695
659 1700171335
660 1463326862
661 141729410
662 1447921371
663 339790494
664 49194816
665 733625307
666 1483363181
667 405625439
668 96986374
669 2135381036
670 201311633
671 124197682
672 794150787
673 1034324937
674 1505879337
675 90173228
676 445638042
677 879050173
678 598455225
679 2074453712
680 1456073773
681 902681362
682 773705076
683 367421799
684 1347633719
685 1671655508
686 1589550407
687 1457973254
688 1069261342
689 1208454190
690 1829215881
691 1426169258
692 766494004
693 179264209
694 1046852026
695 164468684
696 1966564072
697 561738869
698 770246664
699 92505414
700 909384373
701 1814225133
702 1513982254
703 1380283635
704 1412331471
705 1631952947
706 2133105417
707 1945163235
708 1872721531
709 82988948
710 1284706749
711 736555442
712 167836927
713 323453865
714 1142042947
715 1171325319
716 1409107467
717 957685731
718 1147510766
719 2117564957
720 1193493774
721 1316376588
722 43696925
723 1739950739
724 1929765593
725 1211777801
726 1424591575
727 1433328691
728 1852407675
729 676971289
730 349743612
731 543118870
732 2067015616
733 724544339
734 838209343
735 1604154156
736 2035763251
737 656889915
738 1864761366
739 339276045
740 2108214518
741 162806233
742 2108723882
743 766563047
744 111396674
745 462542993
746 927522682
747 635531619
748 1376414031
749 502253995
750 1827404242
