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 65796543
77 513251730
78 1048883319
79 1687472185
80 312638364
81 1220608719
82 165235998
83 1451155653
84 843321581
85 520970751
86 538598987
87 954024776
88 1842282480
89 1146625375
90 1106687225
91 1833815077
92 1330548774
93 1888839889
94 1561145340
95 558770339
96 1278630697
97 1874386948
98 558567686
99 2004579082
100 275700717
101 191461839
102 254233630
103 1204630215
104 1772485072
105 826027765
106 1667627098
107 1383749928
108 1546611827
109 1858996479
110 149147561
111 1031644685
112 924918667
113 1018445341
114 819413929
115 513784060
116 890987379
117 1504274121
118 547802515
119 1706389737
120 1154950735
121 940318579
122 187458988
123 154657482
124 1763491059
125 172573611
126 1436226794
127 339295737
128 1200024870
129 306431505
130 174612735
131 1069258605
132 117852802
133 465815310
134 1644462601
135 1026234090
136 1047378884
137 786559971
138 850616296
139 482657167
140 1078708
141 1332592788
142 1649988218
143 100961649
144 1827318917
145 937646423
146 1513194601
147 1220529867
148 1379051464
149 2040331339
150 1449663674
151 1689335944
152 1709048137
153 916216484
154 1385113648
155 383557830
156 1723422772
157 1963395780
158 1199056092
159 435277257
160 1283065983
161 121719093
162 2108631882
163 599972472
164 1474139366
165 2037600208
166 814497932
167 228535781
168 514723922
169 366920746
170 1361873982
171 791095519
172 1793091625
173 2001640683
174 1901518061
175 32950240
176 712454772
177 1599809200
178 584307581
179 906254001
180 1576713763
181 2070544084
182 1201488179
183 1446710675
184 1010274303
185 1795782946
186 200626190
187 1492685917
188 1374981330
189 618127786
190 1906412292
191 421109905
192 1277897074
193 804441574
194 953335306
195 1020497221
196 974619989
197 825689250
198 27146892
199 1804074284
200 2130525091
201 848978794
202 850003748
203 2008472965
204 1516748972
205 1985711338
206 1436343156
207 108796878
208 1356657074
209 531164673
210 856006925
211 347379878
212 1974789414
213 32064207
214 1105765763
215 957955306
216 1956794116
217 920258971
218 1627774261
219 569482773
220 344624878
221 935162895
222 1332349659
223 486744469
224 1219091485
225 1622024285
226 1328207537
227 883222380
228 594845669
229 2012319528
230 164780295
231 1261802276
232 1375787752
233 462868141
234 979772728
235 1289833427
236 1562884999
237 1175593125
238 1998316149
239 1518244651
240 1232263653
241 532985207
242 1574536547
243 1206021984
244 1999659505
245 1492310026
246 893865475
247 1197650849
248 232561992
249 248533411
250 1945675583
251 661841262
252 766938879
253 1795564328
254 841428836
255 2054925155
256 697216370
257 1217968166
258 1635034012
259 1478586784
260 1312249723
261 1897174026
262 689729488
263 1738434248
264 1277320076
265 85162023
266 111133265
267 2101526445
268 672627949
269 389195837
270 130077336
271 130327418
272 1197136566
273 1033208979
274 899119104
275 1152057528
276 1684206862
277 542289258
278 1407992239
279 1800912172
280 2135498842
281 1393593398
282 936327540
283 2092313219
284 2083613827
285 936393768
286 1989634442
287 895015164
288 1944525738
289 270924746
290 1775808301
291 260890136
292 1271823985
293 2000588705
294 396638272
295 784767964
296 449292178
297 1536673221
298 668062680
299 1410414284
300 1999479496
301 271206456
302 958955362
303 1425733856
304 63449785
305 1143978586
306 1956465501
307 281232419
308 1046172962
309 991743534
310 1249533431
311 696077076
312 468347605
313 1237500671
314 1615004263
315 1580405217
316 399009989
317 937898173
318 1842362256
319 643840713
320 878373010
321 523850014
322 357160779
323 993519504
324 1535468125
325 188470102
326 1736436821
327 1481820679
328 486830643
329 35889023
330 779848875
331 680370230
332 1050109828
333 1788771774
334 365983203
335 1151781763
336 1077868525
337 1832483455
338 2113897911
339 936451351
340 1854202856
341 916859065
342 658973887
343 1341886150
344 1952989085
345 1268274948
346 1808574000
347 101045682
348 992118222
349 85603232
350 1690365784
351 1088131559
352 1949547650
353 1951795840
354 1093873426
355 924831205
356 808620252
357 1494764372
358 1246471895
359 967558553
360 728128760
361 1666222181
362 2078317343
363 960435972
364 2073685674
365 1999044729
366 505433121
367 1860377946
368 5418094
369 1105086127
370 94760645
371 1371535105
372 1673200848
373 320529157
374 236718895
375 5009895
376 451387708
377 1600587700
378 2030295257
379 1573838219
380 572788828
381 1838664140
382 1767906856
383 1868286050
384 2092208409
385 1538000923
386 757126507
387 912646703
388 1755786036
389 1094758568
390 1680347448
391 557653719
392 706575999
393 1619113877
394 278086486
395 1611804183
396 1734657600
397 707208401
398 1290418048
399 1188763766
400 492358576
401 1566664966
402 169889618
403 1500840431
404 336329745
405 651786561
406 276475190
407 1286245940
408 1975043330
409 1971790232
410 2011458436
411 1558771922
412 531425830
413 1766512630
414 741562908
415 2130273677
416 1128239483
417 1151637434
418 2062646101
419 1805510599
420 131046447
421 1144854280
422 460674769
423 74883723
424 1625462911
425 1340100929
426 447289326
427 461907796
428 1842972856
429 967930885
430 550652160
431 1141752620
432 2090225214
433 664985333
434 311363908
435 1324367085
436 416484482
437 959158291
438 1600388298
439 1007962646
440 849729073
441 424825474
442 1743511266
443 1664532428
444 31733644
445 1502234842
446 2061068753
447 1103075021
448 1128876157
449 449197812
450 646328504
451 1355971985
452 1012331496
453 1031308380
454 676547390
455 1329347329
456 1828400819
457 1410163277
458 230862625
459 1858875489
460 1977416379
461 397101146
462 381354900
463 1928061466
464 459351133
465 1805590961
466 929296183
467 2006160698
468 1819056265
469 908457712
470 238607247
471 621212236
472 1779353568
473 1234613294
474 1284416834
475 191056946
476 938931855
477 1326285209
478 1300643323
479 932514215
480 1086725757
481 1027400639
482 1025502111
483 1381762510
484 737165471
485 246289516
486 1969937130
487 29516606
488 1908810255
489 836569002
490 1723364060
491 526438725
492 538011437
493 1850682581
494 902446917
495 1219149096
496 318844026
497 386086311
498 386344559
499 2112838863
500 1755858322
501 1689783798
502 1433944521
503 801032842
504 2037310907
505 1217011272
506 956798232
507 277074919
508 73789843
509 448870130
510 1146638471
511 891913870
512 436560082
513 1847238756
514 1581614082
515 1288007572
516 536207613
517 1962408780
518 2027541947
519 925083423
520 909789198
521 261360673
522 308263364
523 1477956258
524 761830873
525 316840232
526 551807087
527 1939640969
528 438758680
529 478114331
530 1333756690
531 1818686687
532 1470188044
533 74035515
534 280406756
535 326010370
536 1557384420
537 1764341860
538 1499242203
539 1981889427
540 967721476
541 424896330
542 169728875
543 805804759
544 790863775
545 523065714
546 1893573545
547 1090161675
548 1936991417
549 430635455
550 1604254887
551 922382237
552 1500962685
553 1590101227
554 1588659815
555 426137371
556 1839331085
557 1024057227
558 1482906749
559 966705648
560 546184368
561 1903765206
562 1659734839
563 126939453
564 274275140
565 784307547
566 772055713
567 1056392812
568 1976103376
569 1060000291
570 1675958177
571 863887821
572 719564568
573 1342682595
574 1195010166
575 383124929
576 1390422963
577 874831340
578 1387035388
579 1203296978
580 1963239666
581 2046122986
582 1699738958
583 1047292491
584 1906524177
585 1813994156
586 691310502
587 10244751
588 1054185374
589 952218433
590 1328632946
591 197917211
592 1169134844
593 1382088505
594 1795317905
595 689971765
596 394874556
597 814676521
598 1577130455
599 1627087126
600 161012779
601 2009886830
602 1858004693
603 2017516869
604 1471414528
605 504050736
606 441064852
607 470644670
608 833174269
609 1555332789
610 1830913348
611 166614839
612 1520913072
613 636619802
614 582393258
615 273902530
616 201468483
617 1062120800
618 876880521
619 362438419
620 1573056138
621 1773755707
622 274852437
623 1269150537
624 1735903460
625 616690861
626 1980490400
627 1775171849
628 659621505
629 1121920830
630 43656115
631 1980091860
632 1528725313
633 600468960
634 1562954121
635 1135551042
636 805743643
637 2008777784
638 177428982
639 951591085
640 1943147808
641 1101083987
642 101973198
643 1635207370
644 744117694
645 717260866
646 276304423
647 1651952865
648 1668450489
649 147472329
650 591030661
651 1668926328
652 716893291
653 1640517585
654 538287909
655 448055906
656 1338716581
657 134512794
658 1717009041
659 1466991484
660 2095250559
661 269373286
662 619062817
663 1785590860
664 870651618
665 1139621387
666 1367136473
667 2100715520
668 733697033
669 1024232033
670 156540158
671 910862233
672 1722188604
673 1133174824
674 295837064
675 2107016338
676 1605497233
677 2059041465
678 155686793
679 1945639732
680 2065148899
681 146610669
682 1145562256
683 1115390946
684 1726196334
685 325511017
686 196412
687 730471652
688 1328934762
689 735329551
690 1071705446
691 1749602147
692 437104018
693 99576974
694 900643643
695 1093311732
696 1301847580
697 119040232
698 2120377849
699 935321241
700 881594644
701 1953779013
702 296231732
703 1844760342
704 628549094
705 2109198036
706 1571996354
707 1004366925
708 853882880
709 251632400
710 1769082786
711 1575197743
712 1288258838
713 1955765506
714 170492621
715 652472975
716 216609050
717 1418210511
718 314020491
719 1546802491
720 605160884
721 173979137
722 1801540271
723 1445744204
724 1734574857
725 470248814
726 1897808851
727 1957838212
728 1003752488
729 1646400082
730 1362053935
731 1740517145
732 657839432
733 394013489
734 1300626320
735 147028390
736 1309880721
737 990184707
738 518077272
739 1639926999
740 1238295428
741 1383768324
742 774472027
743 311873970
744 638080317
745 469146327
746 975448002
747 2014607357
748 2087369764
749 1385637976
750 551894687
