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 125796603
77 573251790
78 1108883379
79 1747472245
80 432638484
81 1340608839
82 345236178
83 1631155833
84 1083321821
85 820971051
86 898599347
87 1374025196
88 244799411
89 1746625975
90 1826687945
91 596332368
92 273066245
93 1011357540
94 923663231
95 221288530
96 1241149188
97 119422250
98 1361087017
99 1209615344
100 140737639
101 776499481
102 1679272112
103 1512186108
104 1142558556
105 1576102629
106 1900219973
107 1398861114
108 1644241624
109 321661698
110 1611815780
111 1759349226
112 1517660130
113 58740837
114 1164747787
115 986673631
116 433950134
117 1317311260
118 2070915478
119 267129437
120 750802641
121 1653801302
122 383607950
123 635992014
124 1675047363
125 1396872098
126 43337648
127 1549224178
128 505359033
129 452211192
130 710911610
131 668667983
132 970448987
133 29225459
134 1253799220
135 21644747
136 1049013427
137 2019603910
138 367807554
139 1014220816
140 2064793193
141 1756306978
142 524072773
143 1558309800
144 100962223
145 438108092
146 928621818
147 1309146001
148 2014190170
149 1932954809
150 1965847926
151 700338786
152 26278545
153 1016270384
154 1859842480
155 1857555937
156 2024096684
157 1040969134
158 1591607154
159 803843628
160 394167110
161 492396971
162 946590222
163 1961070330
164 992598215
165 1603500087
166 578954736
167 1738815567
168 301940310
169 1556120643
170 1252321618
171 1633912924
172 1934064756
173 853965267
174 486096591
175 1826244864
176 471957859
177 986873947
178 379696083
179 508211132
180 1701562788
181 155941730
182 1899620682
183 1685316436
184 673543936
185 223023071
186 409968008
187 1865077701
188 740712847
189 1596093842
190 623659113
191 1799962671
192 573572501
193 2005215887
194 501270444
195 174862441
196 745814838
197 374651743
198 1680175932
199 1330897013
200 1575275892
201 1269603154
202 2010854628
203 2021352071
204 1822842734
205 68774557
206 276936987
207 1650067217
208 1569078294
209 213892546
210 150216332
211 1029166960
212 952955102
213 218360884
214 1783199152
215 1127175064
216 993594793
217 541973259
218 1016698878
219 96019181
220 1088492872
221 1624985139
222 1194579141
223 1689262073
224 2000872936
225 861489862
226 1404612785
227 948859866
228 1215116872
229 841508572
230 1182738680
231 761878367
232 94718787
233 1937928356
234 1170222114
235 197216113
236 1643626754
237 930498737
238 930986639
239 1754399345
240 1556263897
241 2070615473
242 1710618079
243 642957197
244 1592891036
245 1828632482
246 1786521815
247 923693621
248 1889830806
249 1605112774
250 973433785
251 1901145017
252 307130019
253 134949475
254 2060389553
255 1007925788
256 438885832
257 1229268191
258 1316104581
259 610618036
260 580565027
261 1332704397
262 116182914
263 1021598911
264 2033291876
265 1747041931
266 945966207
267 1646808471
268 1199558791
269 706149489
270 1880318203
271 803500225
272 1356728214
273 335809234
274 1006501912
275 142588243
276 151287005
277 1683679070
278 508093447
279 981612113
280 119716141
281 882917992
282 608280181
283 1620388509
284 2012649769
285 1134641920
286 1612956820
287 849777981
288 227325469
289 905090296
290 790704435
291 714613005
292 1584259415
293 562337502
294 1085204262
295 662526854
296 1542353375
297 1938216983
298 1510417488
299 1623460701
300 1171919703
301 1396091991
302 1326220285
303 78665623
304 1430031696
305 603824215
306 2030574547
307 1503913701
308 1839209927
309 1934465246
310 1086612405
311 1816963880
312 1234151050
313 1636186307
314 1764852861
315 750774779
316 370353921
317 1680563952
318 1253607468
319 1203698925
320 1773358163
321 916373491
322 625725854
323 224055722
324 1606889609
325 1695943972
326 262485316
327 1249925071
328 128783351
329 1568179761
330 38171777
331 1758868439
332 520706707
333 1607500978
334 197285558
335 310715230
336 837106970
337 689784607
338 1746933614
339 502259009
340 1934925135
341 1760493824
342 483104807
343 460989445
344 1780216015
345 1985543379
346 1557125041
347 784228660
348 1353446834
349 1605846204
350 2026312733
351 1459791302
352 63809185
353 1799160029
354 1526736352
355 417435366
356 1823036206
357 68018257
358 130941115
359 2074682218
360 886262998
361 1720429829
362 433713320
363 430989685
364 1583581071
365 1554710665
366 140466145
367 2064654182
368 1593541802
369 225027492
370 192817520
371 1100100778
372 1086493568
373 1639058867
374 186179187
375 1961383505
376 250616259
377 401784995
378 1512291231
379 843593433
380 1330018224
381 1778107296
382 262625855
383 2055640366
384 785288698
385 1314575514
386 1527474705
387 556506965
388 1717545374
389 1832571363
390 1669699060
391 614225209
392 298638081
393 1270170171
394 1971920904
395 627475177
396 1298728040
397 841198799
398 1461791278
399 1846346
400 1895459495
401 643237935
402 53956942
403 1203190950
404 1396146362
405 1784143794
406 1491765857
407 311670478
408 2064806592
409 1535967436
410 331095976
411 1990777530
412 904576645
413 236228540
414 1275693476
415 1697966470
416 640293108
417 1570300269
418 986991357
419 1861257610
420 302142602
421 1027513230
422 1158344244
423 554594772
424 1269418644
425 1278219763
426 1656848342
427 1686196471
428 1942418401
429 2028083279
430 787553290
431 1651043549
432 849749791
433 306603302
434 1072872774
435 1213233932
436 930018499
437 1662424783
438 155260543
439 1248263206
440 627827434
441 454867998
442 138786194
443 1211080023
444 971084007
445 231662826
446 1125659412
447 1868220482
448 886978075
449 1951605689
450 1168735255
451 1409280330
452 1012976904
453 853707671
454 592116975
455 2068843688
456 1724750228
457 518412558
458 1711025201
459 1358067778
460 1146109008
461 871835386
462 504007124
463 1064206864
464 51522612
465 241432573
466 22979684
467 891643761
468 1899306303
469 1968280883
470 359498682
471 1483487640
472 235266270
473 1164162531
474 1867128250
475 1986110714
476 1608900428
477 1592439386
478 1853015853
479 711867325
480 265222983
481 1062272335
482 1177810341
483 1432863990
484 817497479
485 1622498271
486 263899570
487 1919175293
488 281208468
489 1260850762
490 1920973970
491 1069456372
492 25570171
493 1335351726
494 23171001
495 841136370
496 868642448
497 1801900414
498 941591599
499 1416283024
500 1122307603
501 1617840745
502 1326403542
503 631304564
504 749431155
505 54534726
506 1729376755
507 1642342745
508 1176906418
509 304181253
510 1889218530
511 595144256
512 1948684267
513 1037181774
514 633927657
515 863406560
516 1324952516
517 354071600
518 1825785858
519 1548649465
520 216909725
521 1435221347
522 660456434
523 1784701126
524 12308727
525 472764323
526 1465839944
527 734421429
528 1586998784
529 1380268662
530 1220781309
531 1412106093
532 738668451
533 993860247
534 764388166
535 1419856431
536 183677675
537 201745045
538 106976493
539 675996828
540 1247882780
541 1415354535
542 1137599588
543 12386500
544 1855202402
545 771557983
546 1641591745
547 1075013274
548 896664703
549 566909952
550 256278494
551 16442559
552 1410702511
553 1489304212
554 695102389
555 1753674427
556 1840440450
557 1849312038
558 1972399829
559 1445911864
560 1574216932
561 1971047792
562 906885630
563 1276968963
564 1058594223
565 565051146
566 519077344
567 867885670
568 981236510
569 412993706
570 1549319073
571 944128008
572 816422175
573 259609712
574 765522335
575 454368074
576 916726061
577 76421241
578 1841921936
579 1052646280
580 467113577
581 984730960
582 566381327
583 775081204
584 501084289
585 1105458689
586 1004984466
587 494778306
588 1756087673
589 804322868
590 1296678090
591 2034966193
592 662091437
593 824775530
594 913398092
595 739379405
596 186706074
597 1741369085
598 1723799061
599 2047580936
600 1864504011
601 628274699
602 1217478200
603 1987120355
604 1977799462
605 1503106203
606 578272197
607 1400740937
608 983928059
609 353449572
610 435553943
611 1703799977
612 556518997
613 464106085
614 2002447198
615 348804379
616 199197857
617 752635340
618 296767271
619 298140204
620 1506689226
621 1737442662
622 1461906978
623 410518959
624 1919660301
625 2051208178
626 1178315767
627 1211187171
628 282919811
629 1704105663
630 625374235
631 760078158
632 1746615914
633 1041860850
634 1350952768
635 1842788254
636 1479852051
637 482998250
638 488687314
639 169055054
640 34202393
641 399033219
642 1746608387
643 635947384
644 796586837
645 1553996844
646 857456801
647 1160678978
648 930736982
649 2055604802
650 257869401
651 1919648486
652 85101634
653 396758403
654 630592647
655 1780741691
656 1289386089
657 1017846060
658 982177446
659 176768688
660 1227829878
661 2024685025
662 1120012695
663 1149757698
664 1848224280
665 2059412276
666 1434968723
667 1194733453
668 286736583
669 872899396
670 277456977
671 1129617626
672 1804791378
673 1936610541
674 1570359780
675 2003109520
676 585893535
677 1168129047
678 1349816358
679 996585865
680 474900556
681 1388899521
682 79271322
683 1530921733
684 1472512066
685 1406168574
686 174875361
687 126381318
688 135242058
689 1603886382
690 1823165707
691 693632894
692 905062243
693 908522539
694 428533993
695 892637812
696 1444157409
697 398821217
698 1345839305
699 1261583551
700 1379238230
701 466838834
702 846999966
703 662254176
704 201038560
705 382707877
706 246754413
707 647483418
708 1795990958
709 151346134
710 1038851339
711 1698773681
712 272722835
713 1695030158
714 747925163
715 222860457
716 1984479255
717 395278006
718 1059285784
719 1993384526
720 64814253
721 1308202937
722 849666496
723 1785785804
724 1705849255
725 1035575839
726 1774515243
727 935701300
728 501209587
729 329588701
730 871182281
731 1678406152
732 1952086481
733 393770979
734 1870818655
735 1042408231
736 1722743179
737 883028831
738 1879466932
739 1960272124
740 491344865
741 2023362532
742 1729053003
743 291888732
744 1783499453
745 941627033
746 1125642513
747 1720137051
748 1818524706
749 1688338084
750 318563994
