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 155796513
77 603251700
78 1138883289
79 1777472155
80 492638304
81 1400608659
82 435235908
83 1721155563
84 1203321461
85 970970601
86 1078598807
87 1584024566
88 514798601
89 2046625075
90 139203226
91 1046331018
92 813064625
93 1641355650
94 1673660981
95 1121285830
96 243662399
97 1379418470
98 783598968
99 902126485
100 163247790
101 1159008552
102 434296284
103 777208750
104 1007579398
105 83637762
106 1217752676
107 1676390937
108 984284478
109 981700592
110 1724366535
111 1594411032
112 1375232087
113 298821865
114 99853167
115 1144285562
116 306583357
117 1504963975
118 1246101886
119 1347330567
120 571048425
121 1324088410
122 1223932422
123 21382162
124 1315498057
125 1254893669
126 381439527
127 882431257
128 1923662042
129 1323148684
130 989504157
131 939934267
132 461921981
133 855919255
134 258274383
135 1328909339
136 1734137534
137 597653298
138 1068810407
139 1648265452
140 494477991
141 321706666
142 170286701
143 177977131
144 1234194959
145 1407587980
146 1629533106
147 804206090
148 1241131273
149 539553883
150 1197407791
151 504717247
152 133885152
153 392578293
154 205383953
155 1497916672
156 1579975679
157 1983138585
158 373487150
159 231427167
160 401109085
161 52518651
162 46383553
163 467231988
164 1794530397
165 503422589
166 1171819439
167 869962468
168 712039150
169 1486304277
170 1239186067
171 999609653
172 241357620
173 2001279537
174 1412695898
175 957267175
176 1490996126
177 1961192665
178 1455310390
179 1982566306
180 671238456
181 1324272723
182 942053495
183 774546586
184 1647353233
185 549639152
186 1295856788
187 575416027
188 927256037
189 1837782301
190 1447128635
191 25235825
192 804678145
193 528626485
194 376674276
195 1126256657
196 25116687
197 622901213
198 564017872
199 1249084793
200 1897982928
201 230379190
202 668780178
203 1278520251
204 177104570
205 576742781
206 1789955974
207 168010217
208 1066994331
209 399335637
210 1410972750
211 861662041
212 1011241302
213 1371449075
214 485713679
215 1795798704
216 2029757688
217 695502679
218 43304293
219 811142427
220 1365333668
221 389099142
222 430490797
223 64207634
224 1593385080
225 1765103976
226 1629561602
227 1426818352
228 622758513
229 620260836
230 663227815
231 1742923737
232 1055570467
233 1638586536
234 1636237606
235 763976499
236 441632247
237 871554827
238 255029455
239 494022450
240 1196651064
241 1584624658
242 97072203
243 1647827705
244 1807354567
245 653272070
246 1121653499
247 855186544
248 228588950
249 812023094
250 1806954828
251 54036903
252 1783167945
253 135091574
254 1548109010
255 360479544
256 1666646792
257 2029475569
258 1428318505
259 1932503443
260 34420961
261 376011628
262 625454631
263 1422673971
264 1473716171
265 1674037003
266 430774303
267 1633651790
268 1830944993
269 115782287
270 794743359
271 74177447
272 1264249068
273 1261446219
274 1685125829
275 683015464
276 896921110
277 1291645336
278 840536714
279 1789584033
280 1583843527
281 880088337
282 1629489929
283 1875665653
284 977058193
285 1300348325
286 592001869
287 1086916150
288 1329847484
289 435094209
290 766068949
291 1186984385
292 60665541
293 1839002136
294 628042083
295 10412208
296 1448386544
297 1363783890
298 901648738
299 233047659
300 364470818
301 121836006
302 1557490349
303 1372860562
304 1723026099
305 1620296530
306 529443234
307 1334454919
308 1387043797
309 503246656
310 1543576546
311 646388128
312 320806712
313 1261970960
314 1809348638
315 1281961188
316 1451950047
317 230408910
318 521441138
319 1991053965
320 1948929348
321 14701058
322 988194858
323 1902584962
324 1947489675
325 1722011766
326 1352431294
327 925101229
328 60160580
329 194671169
330 1032264486
331 1668445203
332 282432199
333 920255205
334 432772300
335 1435411145
336 952261562
337 1897447825
338 1412658162
339 850214260
340 1990936231
341 314504354
342 1052066142
343 655556607
344 549119511
345 2027406816
346 548553445
347 1757306342
348 1151222690
349 49102175
350 822041315
351 871002863
352 1074292997
353 1883638418
354 555198103
355 430092890
356 1576390605
357 1928839770
358 1263880383
359 1199663309
360 434727171
361 158374754
362 1802595719
363 986824723
364 787043840
365 29062935
366 451935012
367 977632109
368 996029494
369 803046009
370 729662283
371 529121424
372 666290110
373 540027498
374 1077906535
375 2007973667
376 537176953
377 1547725554
378 796513695
379 1731634203
380 1201189582
381 917956171
382 1772805706
383 619344562
384 566810039
385 1610002669
386 1181062319
387 559641493
388 1013944977
389 1922015187
390 1295833802
391 601809453
392 1571415565
393 776548363
394 832453911
395 1169130251
396 363835363
397 677645850
398 874259711
399 730462197
400 1928250024
401 638377446
402 1327296448
403 357287373
404 600381759
405 686020023
406 987853002
407 1294389592
408 873640420
409 1914218935
410 594953107
411 1308927382
412 1547214935
413 927622377
414 416332969
415 1167420852
416 1170893555
417 1178871536
418 1134055150
419 133482008
420 905550011
421 1026622524
422 455931844
423 676792139
424 194606736
425 1895057415
426 1627390501
427 686423667
428 215910367
429 1469367817
430 1182744744
431 1825008248
432 1664508720
433 2045342442
434 1133496489
435 1450419250
436 562307202
437 898595786
438 2042272885
439 1360435963
440 89637979
441 1938915733
442 662832279
443 539843598
444 1794187088
445 273797438
446 1079415500
447 490316328
448 1665475710
449 1628232253
450 551622572
451 1781769103
452 1661977841
453 1343477915
454 402125361
455 1490902876
456 1256099174
457 722026653
458 1732131964
459 1747217876
460 1016119979
461 756367013
462 572733373
463 1120229372
464 791585672
465 1441927148
466 1095948035
467 1056069657
468 1140601992
469 375192161
470 1115074871
471 852778402
472 138301467
473 1176961825
474 861753805
475 1439342027
476 802634233
477 1728046522
478 1448316442
479 1714817101
480 1200333661
481 1203185631
482 1902971840
483 1335528229
484 20918488
485 589281003
486 875531339
487 1822994317
488 887274277
489 156337923
490 956506721
491 1416607656
492 202598137
493 1907602058
494 926029748
495 1787079068
496 1470333982
497 43891023
498 1000076717
499 412121294
500 1147132073
501 655732784
502 679369762
503 1341212479
504 1273285129
505 1932947549
506 1392780371
507 66974215
508 143919504
509 727161885
510 1861889610
511 884557414
512 920139621
513 251480593
514 1949453266
515 287630274
516 292126342
517 43409070
518 655564418
519 573052551
520 1834795880
521 1049726682
522 1760337550
523 1512505813
524 659471381
525 1791437516
526 1727805334
527 1763553226
528 795693419
529 1772700054
530 207111290
531 993268477
532 669581446
533 1964597914
534 476257997
535 1768315928
536 101147607
537 790999919
538 1050683375
539 228914987
540 1232415001
541 797943931
542 1628471038
543 1843897755
544 696643360
545 618054540
546 984954454
547 1772827582
548 823473930
549 1954026622
550 450650596
551 12094590
552 1280047494
553 931455340
554 629260740
555 1800754943
556 1507927183
557 1015776650
558 1489641115
559 1035774776
560 547513775
561 1496786391
562 360474950
563 1532200354
564 487313608
565 164884718
566 1312933728
567 1777333703
568 1045983836
569 386231329
570 1308721157
571 1168127969
572 119327048
573 1087863375
574 2024858544
575 1876786937
576 2012734846
577 1517792857
578 1021927792
579 1353012606
580 22203553
581 1387313926
582 1376931619
583 945061891
584 703930280
585 322316858
586 49482007
587 1215710812
588 132753991
589 1877818698
590 1882505675
591 1368523128
592 1177314854
593 2002370771
594 902445725
595 1959585869
596 1552829644
597 1787195794
598 1164186347
599 464689065
600 1718484023
601 1757483131
602 1908967752
603 38205001
604 1466882492
605 366489234
606 557969080
607 817385338
608 99710759
609 1084653831
610 690091984
611 470053156
612 592353708
613 849842851
614 453777972
615 1654254158
616 846824058
617 617781187
618 1632202457
619 391529162
620 620100136
621 1256756591
622 1648413150
623 2045741596
624 540690433
625 1355433663
626 1428830469
627 1464373566
628 720699761
629 167019193
630 511813493
631 876838367
632 100906467
633 801802751
634 509293945
635 3397811
636 38567528
637 377529015
638 414690275
639 1156098655
640 794864208
641 261302498
642 658060804
643 1829646043
644 1409694834
645 1506890152
646 1198406906
647 1139772482
648 1946262895
649 840868784
650 1857363957
651 1816043099
652 1525565831
653 1214756969
654 695796648
655 1460052742
656 1914007594
657 469337233
658 217275805
659 1418959073
660 2032341860
661 31214307
662 901608036
663 1284517845
664 1418317434
665 1517684249
666 771919764
667 9153842
668 1556674479
669 1766683965
670 1430422483
671 165842854
672 3972547
673 592536953
674 781226880
675 1201138718
676 49300906
677 1470655304
678 1992317745
679 549249862
680 1866639220
681 1690907107
682 330174610
683 229377758
684 1186858600
685 456767058
686 1032938360
687 1324225170
688 1670690035
689 1689353644
690 1687502259
691 1977220932
692 44350441
693 1967714731
694 1022286812
695 1404210324
696 219343787
697 1858319319
698 771901197
699 22384990
700 947289746
701 2026078891
702 54260159
703 1637050147
704 1555465987
705 456451917
706 743761344
707 894334529
708 1538016476
709 1514525179
710 1353472209
711 994034541
712 1457701723
713 648171292
714 1081452023
715 1694233468
716 145627664
717 176537637
718 1044927822
719 1806756602
720 1675581837
721 830069138
722 505469503
723 430135044
724 170198086
725 1469631240
726 1690709296
727 976815904
728 89691843
729 1482858856
730 902240035
731 20109038
732 142235028
733 710043072
734 837777780
735 856352086
736 1217965206
737 1629556655
738 1836322921
739 1611682893
740 1278864478
741 1468735464
742 1824486148
743 664606254
744 1425251484
745 925669334
746 862762607
747 908391040
748 1073450274
749 347783098
750 1270550815
