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 195796515
77 643251702
78 1178883291
79 1817472157
80 572638308
81 1480608663
82 555235914
83 1841155569
84 1363321469
85 1170970611
86 1318598819
87 1864024580
88 874798619
89 439141458
90 659203252
91 1646331048
92 1533064661
93 473872055
94 666177394
95 313802253
96 1683662471
97 1051934917
98 776115431
99 1254642966
100 955764293
101 424041442
102 299329204
103 1322241704
104 345128755
105 381187167
106 587818498
107 318973186
108 1146866803
109 896799368
110 1671981776
111 1934542756
112 500396677
113 696502982
114 282567200
115 1712032541
116 11879683
117 1147809688
118 1826497036
119 1977791573
120 564091716
121 152230423
122 647173245
123 72238260
124 259002270
125 1811046133
126 1655273124
127 411495254
128 1820473008
129 365255948
130 641940719
131 1500249532
132 1180181765
133 54705791
134 1555137242
135 1711463614
136 1877482039
137 1089403306
138 561614021
139 1314770901
140 332366372
141 1521175599
142 1579083079
143 868880785
144 1025018684
145 1661177575
146 1878800132
147 1759611557
148 1615718408
149 376431833
150 942268040
151 678350063
152 764696022
153 1049104388
154 1996294228
155 1562077444
156 1748901670
157 1943574897
158 1027409433
159 1753590912
160 536598929
161 1444232280
162 1582646513
163 66830751
164 1359229072
165 545577897
166 1544446603
167 1809317582
168 105234286
169 681373629
170 1577733948
171 1221974999
172 994229459
173 1820410812
174 368068283
175 428321551
176 2006895887
177 418636383
178 973762795
179 214718676
180 1828305559
181 1874068320
182 341902461
183 1769361143
184 707840397
185 387926967
186 1148866399
187 1448234501
188 921673322
189 1490894539
190 547622146
191 249803089
192 1584631006
193 1761674331
194 1241416048
195 1664419947
196 1091543705
197 1478380367
198 988378988
199 379722219
200 871224559
201 543382107
202 476920085
203 1293308220
204 257278319
205 1845049690
206 975758881
207 38167797
208 1475343552
209 312195494
210 1193833375
211 1857256601
212 789132311
213 1106679333
214 1574399351
215 15280198
216 1365891755
217 55169614
218 459616154
219 251811602
220 529499300
221 1095456223
222 1592347789
223 1046571887
224 1965513910
225 1141169758
226 1896034039
227 1619277457
228 1388423294
229 1473979795
230 516193366
231 321659814
232 1203498194
233 1102749706
234 944405756
235 514706564
236 1285812619
237 180266885
238 1333172470
239 799568481
240 1530800223
241 110144913
242 164058688
243 1258869564
244 1587826399
245 1768540622
246 1596637809
247 1084889150
248 1187471699
249 778196748
250 911691431
251 1574760457
252 748822877
253 373905081
254 1871122308
255 1975239048
256 1061360078
257 334538554
258 1121182428
259 1944908428
260 1651706440
261 515275632
262 1147724850
263 1565466995
264 125916596
265 1384638688
266 339970774
267 1949940956
268 1915773906
269 963032492
270 137223080
271 32431976
272 1100546848
273 469139443
274 250228463
275 602951941
276 1930829702
277 2004316008
278 746715706
279 1560432794
280 1249439856
281 295736358
282 145720407
283 756264561
284 1340298004
285 709994638
286 811960326
287 334938894
288 1719689253
289 1044715769
290 1883227515
291 142500627
292 1995827224
293 147497487
294 801405317
295 1415656939
296 1742998392
297 1029509540
298 371896356
299 1018105731
300 1298735443
301 1555770611
302 1540969213
303 151711475
304 1012787727
305 1087622429
306 1079938090
307 1066509670
308 281439511
309 519187812
310 529029725
311 483072548
312 424604076
313 933660730
314 1047013319
315 92068013
316 1604213252
317 1028389149
318 985603834
319 449700800
320 947062672
321 156795414
322 1169637784
323 1876368872
324 1142288608
325 1578905014
326 1361563395
327 192841685
328 1669355364
329 1522761756
330 1965811871
331 82252555
332 815072356
333 133888932
334 556729319
335 1196783287
336 617211517
337 1265733672
338 271950672
339 385960301
340 1242308618
341 1999369881
342 624853414
343 1227323879
344 1922169110
345 387684735
346 1888727160
347 1810873983
348 968914904
349 1231349761
350 884043820
351 1006317193
352 185149259
353 1412587471
354 1580432767
355 494283464
356 1967327757
357 556380343
358 1831433961
359 1037293476
360 1179070031
361 559833837
362 1798542067
363 625867183
364 277186367
365 282308461
366 952562324
367 251980808
368 675773470
369 1730036477
370 924926450
371 1445917929
372 297354584
373 414611060
374 1987837459
375 1386614629
376 1389353045
377 1013195477
378 1133380154
379 1449651528
380 1610278888
381 1853914012
382 1546651061
383 931127250
384 1206763232
385 1967659627
386 893035788
387 829525976
388 984972462
389 903970685
390 1905151358
391 570572531
392 1749061826
393 1999771856
394 1771385509
395 37852614
396 197988338
397 94534796
398 1380421133
399 615416495
400 508637324
401 420330697
402 1119858827
403 1000895432
404 380302744
405 489131200
406 765476886
407 230255356
408 975089761
409 1297258863
410 803326725
411 936397632
412 1285893753
413 376559920
414 23270749
415 1116862810
416 264250567
417 920096486
418 1674730049
419 1774204313
420 101311288
421 235723850
422 1866373304
423 1382782696
424 346691375
425 1926896973
426 1436148049
427 1199178044
428 163489470
429 915847112
430 412135887
431 1085032639
432 433748464
433 52652790
434 1084631806
435 1692065774
436 1559144363
437 1089668121
438 941333509
439 1826345707
440 1283769202
441 1316542859
442 1265336598
443 925264009
444 1486194264
445 1178978199
446 247954455
447 461439697
448 1825233279
449 872650941
450 152793295
451 1558915292
452 1305094136
453 1145367727
454 392857498
455 435736566
456 1022585630
457 895229860
458 1373690161
459 169150280
460 574488309
461 161371325
462 974129729
463 919131792
464 1466251863
465 233929658
466 1421569209
467 683386318
468 1166936008
469 50493645
470 886406937
471 1276384644
472 1512728677
473 1518473149
474 1513704901
475 1432353717
476 1579181602
477 1113804998
478 1846403257
479 1445613145
480 1543180079
481 842154572
482 979539041
483 1999952056
484 1258591929
485 785935309
486 1565879315
487 544927892
488 479858995
489 766624489
490 1253325230
491 1063210426
492 555807478
493 1259335625
494 1582688897
495 673943976
496 130067027
497 1483897171
498 870206300
499 407958719
500 1331613628
501 1005034469
502 850067404
503 25239699
504 1025888308
505 1390392081
506 699620664
507 518450439
508 1145417430
509 1997590453
510 1495071408
511 958014718
512 124730569
513 616553365
514 1730730172
515 1791066458
516 4657306
517 1200489285
518 809229741
519 732616996
520 610304004
521 1943911761
522 1561306278
523 1065772542
524 1845247742
525 950624324
526 322448669
527 1743903620
528 703452319
529 298520009
530 1824144617
531 108236932
532 172980079
533 292392956
534 1917672676
535 124786993
536 1925544715
537 736736320
538 191227727
539 1198005279
540 379951649
541 1036338323
542 242744813
543 1146762071
544 653245693
545 1050068289
546 1598111455
547 1958148144
548 479468308
549 1296672717
550 422380316
551 78511383
552 1897919768
553 627319324
554 1906399544
555 1946757785
556 1533509392
557 385822896
558 746488867
559 133807904
560 1807272457
561 962837776
562 817068769
563 1714550485
564 1006576901
565 1015516103
566 965149492
567 1512141678
568 407624170
569 961683709
570 213800553
571 2007478339
572 1898405940
573 303078549
574 687920865
575 1184999699
576 934430283
577 1423780317
578 616054273
579 1883659615
580 1933438117
581 1065098270
582 1093421925
583 1420464009
584 647300384
585 45538865
586 607212312
587 105671732
588 1073625398
589 12242181
590 27390913
591 863694690
592 1548882543
593 1131992253
594 997487258
595 1062454544
596 852403843
597 982088696
598 837299838
599 1051540324
600 2004455452
601 645775845
602 73683622
603 1466381892
604 1784369369
605 1072720209
606 943012870
607 633541208
608 45111950
609 240673884
610 866747761
611 1063920606
612 1915448563
613 141829090
614 1696717144
615 676042763
616 1913434343
617 1477891728
618 578528474
619 739001849
620 1080145682
621 1917523583
622 397498296
623 688984617
624 1376665617
625 1238888669
626 272185426
627 215321332
628 354695695
629 68887348
630 1837757146
631 1480243550
632 1280836199
633 330528985
634 209450744
635 1963702585
636 558983098
637 398395631
638 17992952
639 1756000896
640 1396578825
641 1659921162
642 604771378
643 1128039161
644 701407757
645 1323691035
646 361099054
647 741938330
648 1199384753
649 1342739328
650 1814128113
651 186247232
652 591440347
653 1357384655
654 1830057485
655 1644187187
656 1451193632
657 790645699
658 409598436
659 1922240941
660 1931655495
661 949437016
662 1640620941
663 1750450930
664 1209062569
665 1837805469
666 421490102
667 463895370
668 289272686
669 1183033813
670 506316827
671 904538820
672 817004939
673 1709132444
674 1783214309
675 1110141021
676 1303711287
677 844824360
678 400023561
679 1605298176
680 1422376892
681 1753008250
682 582826249
683 160588305
684 1106137463
685 1448594611
686 395857597
687 735880069
688 986259547
689 461075222
690 623357700
691 26480387
692 1267734610
693 745985759
694 1658318692
695 51480999
696 1528776749
697 255088023
698 501153196
699 1695545615
700 1787586834
701 2005048762
702 1724262783
703 1521377808
704 540903861
705 1156381789
706 1840090695
707 1248354567
708 1150036427
709 1904106866
710 978799127
711 1754171474
712 1909524212
713 1304540512
714 304681788
715 1675351244
716 1039098246
717 544202196
718 1951401723
719 1674576091
720 654706004
721 1192837600
722 1064637213
723 951765110
724 1923395226
725 1959753785
726 1073076796
727 1421099431
728 1794609536
729 1258132412
730 1328020628
731 2003556475
732 744857811
733 670350534
734 878027076
735 1702466871
736 1215861274
737 1215210056
738 1825919707
739 1269677387
740 1237934678
741 301992270
742 1125258891
743 1372548769
744 174445718
745 1280197056
746 1590997151
747 1189942202
748 1280896130
749 1068958714
750 1764525349
