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 135796523
77 583251710
78 1118883299
79 1757472165
80 452638324
81 1360608679
82 375235938
83 1661155593
84 1123321501
85 870970651
86 958598867
87 1444024636
88 334798691
89 1846625175
90 1946686985
91 746331168
92 453064805
93 1221355860
94 1173661231
95 521286130
96 1591146388
97 539418890
98 1851083097
99 1789610704
100 830732119
101 1586493001
102 561780883
103 564693519
104 395064367
105 1058606600
106 1652721784
107 1471360365
108 19254286
109 1204154469
110 926820922
111 1664349648
112 45171403
113 1463729259
114 1432245140
115 276678635
116 993944978
117 1279810715
118 1675917624
119 1872115583
120 530803049
121 2046296641
122 1828594700
123 1555982626
124 572553648
125 1009372325
126 1140825657
127 866725751
128 1140349559
129 1507197682
130 1468399635
131 621161434
132 1907933544
133 1954200933
134 323795844
135 1044124230
136 941499922
137 247101359
138 1070282837
139 651701577
140 1932268734
141 1891276492
142 1864028253
143 1935767741
144 615913149
145 1463048178
146 241067661
147 524083667
148 601622547
149 1662866385
150 985751662
151 137723803
152 213639986
153 1991105414
154 1797162657
155 1834849430
156 438872426
157 633201149
158 1963793721
159 1548482430
160 46263445
161 1984420450
162 543562275
163 1267968991
164 414409766
165 367718709
166 1033048298
167 1672786201
168 2000752498
169 687288934
170 833299733
171 1849674033
172 582097580
173 871714027
174 1268529285
175 2000830729
176 1163640913
177 5618306
178 1610410841
179 60859133
180 1828549455
181 349684426
182 1417527496
183 469777471
184 1691911237
185 315181310
186 1743241830
187 121823013
188 705690935
189 1936589075
190 706921868
191 1435707844
192 2038959589
193 2029908038
194 277350321
195 604364327
196 623232923
197 274402433
198 244119606
199 1638278951
200 1875290106
201 533837659
202 1218269332
203 860791466
204 980502893
205 885689143
206 268994165
207 747939454
208 1620703186
209 531982243
210 1942193706
211 979684328
212 351286223
213 1980884726
214 1170929029
215 548092051
216 787665676
217 703575746
218 154561643
219 1545597759
220 1504475574
221 1103619291
222 1111083773
223 1812735065
224 1801651611
225 1980988590
226 1660211069
227 443677702
228 1207827073
229 823642645
230 2020919509
231 422586379
232 1481431305
233 1588379624
234 1448439196
235 1558174835
236 1470308929
237 773336709
238 312356833
239 1615483076
240 1848884377
241 916493495
242 935491187
243 608199469
244 1304486036
245 1013527889
246 2061362703
247 275983334
248 1361338564
249 302720700
250 957214449
251 47355590
252 1378305744
253 710000418
254 779205280
255 1743258955
256 1952998121
257 1597621627
258 465648471
259 550183191
260 253291807
261 1337892232
262 630575685
263 110058811
264 1556164328
265 1779371341
266 680752307
267 557361502
268 1555745008
269 1252114105
270 428306794
271 626324099
272 886253257
273 1059690952
274 410593382
275 1021266844
276 238087948
277 1226920193
278 248738584
279 648264063
280 1140153965
281 864727349
282 525254328
283 242329474
284 677612905
285 1846150299
286 443757514
287 1229297763
288 1087108928
289 1354181989
290 399878316
291 864129345
292 131226826
293 1362134971
294 1618011574
295 1324132260
296 419978800
297 860514958
298 539420618
299 300017688
300 524349439
301 1781031813
302 1658323680
303 375290920
304 1584606446
305 106133839
306 1444434462
307 1922607323
308 563389811
309 1122175794
310 1619427478
311 136232971
312 922459465
313 1532626069
314 1945227625
315 1425243407
316 1615923710
317 1854511626
318 486033858
319 1661380621
320 1763641753
321 2011227171
322 670022489
323 1088468749
324 619204417
325 248456802
326 1263510237
327 1049156201
328 232736770
329 1356942435
330 1715131744
331 1034992554
332 144644267
333 1825153261
334 1485900957
335 129361018
336 733819552
337 896793260
338 245621851
339 1919614616
340 1038293907
341 5566863
342 1680128588
343 138550842
344 2026673149
345 1066790118
346 981551435
347 551834506
348 1825401852
349 1210917146
350 284931051
351 852712622
352 1148804225
353 1432816671
354 425129069
355 1802515147
356 745419902
357 1849791142
358 1080073167
359 343683985
360 145957897
361 586168556
362 1199839792
363 1301577494
364 721686243
365 1354446782
366 1925775572
367 1269928815
368 395006632
369 1910174479
370 1799576379
371 870386562
372 689184620
373 48501729
374 1992201231
375 778782533
376 796865173
377 638995258
378 1703985639
379 1096187438
380 1619514683
381 1465974373
382 901696695
383 160392846
384 1004034532
385 1690306083
386 1054379364
387 660502073
388 1430116321
389 1529379865
390 1073257387
391 1763790644
392 1186104146
393 739293085
394 1913121961
395 713578216
396 2018083726
397 455054263
398 1524164215
399 2047518672
400 2035837763
401 1504694309
402 276127474
403 867349957
404 1581340322
405 1174501784
406 1206384044
407 375607834
408 144866397
409 683399913
410 89300394
411 703000641
412 22324939
413 1335609132
414 1177059907
415 1846784092
416 364827501
417 1828588119
418 1994423965
419 1407076792
420 2024989196
421 525250822
422 1226892403
423 1864338266
424 16692277
425 933313115
426 1082886764
427 1105283792
428 1351910261
429 1349857356
430 1636921938
431 987310555
432 261474245
433 1653102994
434 1394006121
435 814363866
436 2896037
437 1526997788
438 1725619968
439 1198050479
440 1059304232
441 70091819
442 1650546526
443 2041873681
444 1104267448
445 536406110
446 983919713
447 70318270
448 502554560
449 599538028
450 437814337
451 1713119306
452 28242913
453 946946331
454 1449169653
455 291595008
456 1104716225
457 202761935
458 1460772359
459 1484088372
460 152876603
461 1189649009
462 799009466
463 274629018
464 1465563119
465 652301928
466 522722925
467 1395985625
468 1090579256
469 946189740
470 1013551717
471 877364823
472 1290202811
473 1985100876
474 473031799
475 868357319
476 292473327
477 647007244
478 200861098
479 1394852139
480 1983222728
481 388647133
482 1599704188
483 1689041315
484 1739200849
485 231034944
486 15378804
487 473354125
488 249179125
489 266115914
490 2020982989
491 1305031028
492 1455490930
493 249829340
494 1426582139
495 1939457606
496 1163570599
497 1666549174
498 922882291
499 297361454
500 1507561206
501 505941307
502 1464678292
503 1788508380
504 1973066113
505 827289026
506 1063580664
507 113352220
508 720295182
509 33020722
510 1827202420
511 2026998937
512 950914433
513 354171073
514 887209442
515 840831300
516 1692202027
517 580482070
518 305571899
519 1214490310
520 1894139689
521 1099404864
522 272372468
523 268724573
524 156585975
525 1658202533
526 691559468
527 485784836
528 1094657801
529 63223312
530 1663390450
531 724517632
532 1602383264
533 1500703925
534 1798343745
535 1077029554
536 1978460411
537 1926544493
538 2014324279
539 1430135138
540 949851342
541 1010880856
542 54950862
543 335765786
544 541176917
545 705301666
546 1632221187
547 1212314739
548 1636310950
549 1120762184
550 1201042855
551 709004821
552 1919338358
553 1765339806
554 1764797333
555 1707236254
556 969396316
557 1623190874
558 1326877349
559 228563380
560 1927463569
561 1304860956
562 1596750528
563 1101046668
564 250795658
565 134142517
566 1685005490
567 241832063
568 1483119486
569 1890831722
570 912460281
571 1280086457
572 71764953
573 1675225195
574 215049841
575 717788815
576 198739838
577 598564474
578 1354985264
579 960151580
580 219137228
581 776694204
582 355219980
583 1946661244
584 189348368
585 492624733
586 1990498281
587 1962751152
588 475769704
589 1417579742
590 1994719065
591 2053357934
592 1499146581
593 1889225587
594 269593195
595 99265353
596 1535399653
597 1695789789
598 1311460386
599 2046875547
600 1831185957
601 774757675
602 437989384
603 1332766613
604 559733800
605 847440596
606 238851580
607 1952168904
608 797978888
609 670512182
610 1803525190
611 1687625686
612 1299287292
613 149220566
614 32082190
615 1875236596
616 141814472
617 1470041348
618 308987226
619 853406312
620 1736372321
621 1744346516
622 346466397
623 1776767943
624 1350906082
625 1684626008
626 1366756373
627 611803194
628 419291672
629 648093901
630 470816378
631 1361738840
632 1942961097
633 558756501
634 683826059
635 1176263685
636 550436205
637 352495011
638 1967706668
639 810315890
640 468524515
641 1356284658
642 937220410
643 1555940303
644 462139096
645 729639974
646 1757485170
647 1882070696
648 1518145157
649 193912492
650 693659901
651 134708430
652 1730854197
653 1109406070
654 176826250
655 910283583
656 805471901
657 2024579022
658 2050795893
659 499837668
660 1316817437
661 1346505466
662 349552041
663 839413081
664 1868942016
665 1048208954
666 1854745816
667 2004610037
668 1050803033
669 1963298848
670 88799762
671 404991955
672 428030304
673 357117126
674 790755845
675 1430295644
676 1053117465
677 1081819881
678 849574491
679 2008140040
680 1864239900
681 1776447238
682 1953281460
683 903427277
684 2013368222
685 1494893667
686 15119054
687 233988861
688 1930318840
689 26505557
690 778994289
691 1131655599
692 1967056244
693 291920389
694 992186000
695 980984118
696 81357902
697 1440757986
698 1856987409
699 79395994
700 907623586
701 1431638148
702 1316917290
703 368513069
704 285515431
705 369834249
706 1007022185
707 2045011796
708 1063984540
709 217182958
710 1264010419
711 605664206
712 1052588356
713 1026864477
714 362498054
715 1169481058
716 1601984592
717 476499209
718 85539243
719 398064893
720 712409437
721 1247171338
722 1381279160
723 365937648
724 1944779710
725 174430705
726 1475884081
727 539454954
728 1808291306
729 1323166448
730 1677090065
731 749184604
732 33800806
733 979357337
734 1654663001
735 45123110
736 624611013
737 943871692
738 963691633
739 1330613462
740 633207419
741 205775284
742 1856376520
743 641368325
744 1647874357
745 659307358
746 1585577304
747 1642330109
748 1796870841
749 1132761685
750 1510315251
