-1 1
0 1
1 1
2 3
3 2
4 3
5 6
6 5
7 7
8 12
9 12
10 15
11 21
12 21
13 27
14 36
15 40
16 48
17 62
18 69
19 81
20 102
21 112
22 132
23 164
24 183
25 212
26 258
27 286
28 330
29 396
30 440
31 507
32 600
33 668
34 765
35 893
36 994
37 1133
38 1311
39 1462
40 1659
41 1906
42 2123
43 2396
44 2736
45 3044
46 3423
47 3893
48 4324
49 4848
50 5487
51 6080
52 6798
53 7660
54 8478
55 9457
56 10614
57 11732
58 13053
59 14593
60 16107
61 17878
62 19926
63 21970
64 24330
65 27040
66 29768
67 32892
68 36462
69 40084
70 44205
71 48893
72 53678
73 59087
74 65208
75 71482
76 78552
77 86510
78 94714
79 103922
80 114228
81 124904
82 136833
83 150121
84 163951
85 179346
86 196431
87 214288
88 234078
89 255972
90 278919
91 304256
92 332220
93 361596
94 393945
95 429562
96 467038
97 508200
98 553404
99 601038
100 653250
101 710450
102 770821
103 836865
104 909042
105 985324
106 1068594
107 1159398
108 1255494
109 1360194
110 1474155
111 1594892
112 1726179
113 1868838
114 2020092
115 2184267
116 2362404
117 2551388
118 2756208
119 2978138
120 3213674
121 3468579
122 3744390
123 4037198
124 4353696
125 4695694
126 5058887
127 5450999
128 5874138
129 6323616
130 6808299
131 7330686
132 7885726
133 8483560
134 9127194
135 9811172
136 10547052
137 11338490
138 12179571
139 13083531
140 14054820
141 15087032
142 16195359
143 17385163
144 18649499
145 20005836
146 21460575
147 23006278
148 24663090
149 26438576
150 28324897
151 30345187
152 32508372
153 34806300
154 37265481
155 39896495
156 42691020
157 45679398
158 48874209
159 52267042
160 55892526
161 59765704
162 63878144
163 68269470
164 72957684
165 77934444
166 83245188
167 88911327
168 94924772
169 101337670
170 108175386
171 115430426
172 123162732
173 131402226
174 140142466
175 149452233
176 159366726
177 169881116
178 181074204
179 192987504
180 205618459
181 219057283
182 233352999
183 248505952
184 264619338
185 281751082
186 299905184
187 319199838
188 339703512
189 361424780
190 384499146
191 409007305
192 434963504
193 462523218
194 491781315
195 522759280
196 555635622
197 590521646
198 627447969
199 666619368
200 708166212
201 752130484
202 798746946
203 848168345
204 900450714
205 955863038
206 1014584322
207 1076687504
208 1142480622
209 1212173462
210 1285859177
211 1363890801
212 1446514080
213 1533846344
214 1626292398
215 1724139621
216 1827534164
217 1936940342
218 2052693729
219 2174975106
220 2304317241
221 2441111426
222 2585579956
223 2738333792
224 2899828692
225 3070336452
226 3250557396
227 3441022266
228 3642061690
229 3854478192
230 4078889589
231 4315695778
232 4565816070
233 4829969366
234 5108636909
235 5402872042
236 5713510854
237 6041129996
238 6386936601
239 6751901915
240 7136714292
241 7542757188
242 7971157689
243 8422735334
244 8899075734
245 9401485496
246 9930937975
247 10489249749
248 11077934196
249 11698144608
250 12351961383
251 13041136632
252 13767033774
253 14532034607
254 15338166609
255 16187037426
256 17081373048
257 18023518378
258 19015364523
259 20060031331
260 21160229250
261 22318178076
262 23537448174
263 24821169796
264 26171943449
265 27593854518
266 29090515137
267 30664967196
268 32321884698
269 34065432614
270 35899163936
271 37828424091
272 39858011976
273 41992071656
274 44236714257
275 46597466193
276 49079154326
277 51688762780
278 54432652401
279 57316436798
280 60348095064
281 63534944462
282 66883504239
283 70402888461
284 74101509846
285 77986929312
286 82069555014
287 86359052387
288 90864179416
289 95596819150
290 100568068749
291 105788062100
292 111270362640
293 117027702968
294 123071797109
295 129418120564
296 136081273278
297 143074782212
298 150416297922
299 158122552860
300 166209152286
301 174696220266
302 183602923137
303 192947245124
304 202752122034
305 213039496576
306 223830073997
307 235149987193
308 247024344012
309 259476959928
310 272537601570
311 286234981300
312 300596467267
313 315655954266
314 331446257616
315 347998802692
316 365352172530
317 383543850378
318 402609891971
319 422594200218
320 443539566528
321 465487327400
322 488487420078
323 512588671666
324 537838437126
325 564293496126
326 592009535151
327 621040761558
328 651451710798
329 683305860904
330 716665216305
331 751603102935
332 788191844856
333 826502313404
334 866617793862
335 908620645764
336 952591818164
337 998625875427
338 1046816556723
339 1097256261492
340 1150052322780
341 1205311377854
342 1263138828752
343 1323656454708
344 1386985505664
345 1453246140288
346 1522576475943
347 1595114313585
348 1670996550072
349 1750379773868
350 1833420523863
351 1920274668946
352 2011119672252
353 2106133276946
354 2205492844659
355 2309399424816
356 2418054744924
357 2531660502960
358 2650444388262
359 2774635241454
360 2904462302874
361 3040183339146
362 3182057827956
363 3330346169296
364 3485340075513
365 3647333628656
366 3816622463664
367 3993536585414
368 4178409145410
369 4371575602264
370 4573409141148
371 4784287010820
372 5004589658482
373 5234738944032
374 5475161867547
375 5726289670838
376 5988599062056
377 6262573148614
378 6548700496133
379 6847519601043
380 7159576820154
381 7485425382908
382 7825673366892
383 8180938395255
384 8551846609086
385 8939084414138
386 9343349701698
387 9765350794714
388 10205862242424
389 10665672308000
390 11145581905238
391 11646464730255
392 12169210754772
393 12714725166084
394 13283993145213
395 13878019094393
396 14497825581908
397 15144523104038
398 15819244757691
399 16523145185534
400 17257475696268
401 18023514069140
402 18822563493643
403 19656033458122
404 20525364337158
405 21432026327668
406 22377606545781
407 23363728016694
408 24392048625698
409 25464354887388
410 26582474932158
411 27748277502102
412 28963772873520
413 30231019414660
414 31552122661392
415 32929343897847
416 34364999850648
417 35861461874920
418 37421272733016
419 39047038972277
420 40741430237917
421 42507304836076
422 44347594314450
423 46265302911048
424 48263642548050
425 50345909096232
426 52515481969830
427 54775969254987
428 57131075085174
429 59584599405320
430 62140593988416
431 64803220302537
432 67576749492050
433 70465730079803
434 73474835666214
435 76608865194096
436 79872923167536
437 83272256491892
438 86812255098955
439 90498645557267
440 94337316344946
441 98334318908504
442 102496075600314
443 106829192646215
444 111340461695618
445 116037083098266
446 120926465785533
447 126016229363236
448 131314443836472
449 136829415566498
450 142569689962299
451 148544308857333
452 154762581623808
453 161234088542464
454 167968957119525
455 174977617369809
456 182270805985130
457 189859862955476
458 197756469973905
459 205972655554082
460 214521113384874
461 223414922761224
462 232667554821824
463 242293214146365
464 252306540087420
465 262722614302612
466 273557327207553
467 284827059039045
468 296548688840648
469 308739987513332
470 321419277375090
471 334605442759714
472 348318351564438
473 362578491986556
474 377406984913012
475 392826036018589
476 408858548248002
477 425528136214424
478 442859611047000
479 460878567085182
480 479611398572071
481 499085819585094
482 519330423322896
483 540374701435804
484 562249601492796
485 584987057172606
486 608620010614412
487 633183010019352
488 658711709013972
489 685242892424148
490 712815116789454
491 741468177101745
492 771243136402862
493 802183012205316
494 834332208718860
495 867736550690770
496 902444018986110
497 938504146297218
498 975968055690643
499 1014889248858492
500 1055322963149280
501 1097326215366640
502 1140958646449593
503 1186281837526228
504 1233359359625916
505 1282257678784332
506 1333045428705594
507 1385793467153532
508 1440575845699578
509 1497469036485912
510 1556551996148621
511 1617907204686498
512 1681619843763078
513 1747777869074708
514 1816473123131241
515 1887800462450929
516 1961857839320064
517 2038747493643228
518 2118575026268448
519 2201449491152080
520 2287484671866684
521 2376798098144158
522 2469511149565030
523 2565750422748050
524 2665646687998476
525 2769335005798960
526 2876956191132852
527 2988655706951027
528 3104583794955990
529 3224897043931414
530 3349757216601462
531 3479331396399856
532 3613793667085668
533 3753323869464900
534 3898107766018669
535 4048338839553612
536 4204216976204772
537 4365948649951080
538 4533748848596442
539 4707839679389148
540 4888450575575192
541 5075820358638035
542 5270195762744961
543 5471831665665772
544 5680993296927597
545 5897954677132570
546 6122998875809091
547 6356420375882307
548 6598523423683092
549 6849622316614992
550 7110043935088482
551 7380125998858672
552 7660217387793680
553 7950680853172458
554 8251891175858166
555 8564235523848672
556 8888116355585610
557 9223949475397674
558 9572164431895018
559 9933207626784104
560 10307540263021410
561 10695638788472064
562 11097998224694289
563 11515130003216646
564 11947562459210432
565 12395844395807976
566 12860542803847932
567 13342243410726494
568 13841554497066798
569 14359104495161408
570 14895542598686970
571 15451542849836562
572 16027801611509208
573 16625038244213456
574 17243999483095428
575 17885456778819315
576 18550207048760794
577 19239077364717552
578 19952922157403871
579 20692624049823338
580 21459098877823236
581 22253292753203196
582 23076182987949643
583 23928783471333959
584 24812141586838824
585 25727339236722504
586 26675498601099477
587 27657778904065029
588 28675377548837702
589 29729536286207262
590 30821537825384685
591 31952707090899492
592 33124417829986038
593 34338089063802688
594 35595186478356254
595 36897229502684573
596 38245787596146252
597 39642481786942864
598 41088992255322483
599 42587054452828706
600 44138460803510808
601 45745068828830060
602 47408797095098865
603 49131627094045166
604 50915611948645956
605 52762872185493806
606 54675597813016846
607 56656057650280626
608 58706594921738478
609 60829629553087788
610 63027668168222763
611 65303299504563379
612 67659196948250167
613 70098129247923930
614 72622955749571313
615 75236629194746160
616 77942207203737426
617 80742847329627144
618 83641810145508537
619 86642471553694890
620 89748317659436496
621 92962948175723420
622 96290089619478156
623 99733590006366381
624 103297422604767124
625 106985700084395526
626 110802669034909185
627 114752714103789458
628 118840373167555092
629 123070331678440858
630 127447427224259647
631 131976665797564773
632 136663215976617192
633 141512413948793212
634 146529780958798521
635 151721017332200681
636 157092008007617398
637 162648841251420040
638 168397802534292468
639 174345380621569582
640 180498287648868192
641 186863452864450350
642 193448029331746086
643 200259415467776454
644 207305248666531956
645 214593412672972072
646 222132060693956097
647 229929608920741161
648 237994744639661814
649 246336451033600060
650 254964000625119429
651 263886964195333876
652 273115237402738902
653 282659034172482100
654 292528896501645321
655 302735723031892917
656 313290762415034328
657 324205624090079760
658 335492308956754185
659 347163202752516040
660 359231087894337810
661 371709176411756265
662 384611103375894903
663 397950939907374920
664 411743228540331780
665 426002976749790660
666 440745671236523777
667 455987315907079060
668 471744425552071392
669 488034041529278940
670 504873772559222922
671 522281788614035289
672 540276838131737246
673 558878291842353916
674 578106136935109767
675 597980995949333674
676 618524173862538072
677 639757652612867930
678 661704111825484393
679 684386979411998052
680 707830426535509512
681 732059390345691028
682 757099628358613023
683 782977713962995336
684 809721061352596351
685 837357983976949242
686 865917690699645006
687 895430313133632780
688 925926968476869480
689 957439756446668402
690 990001789242277618
691 1023647259104608001
692 1058411436164949768
693 1094330701279907656
694 1131442618681288281
695 1169785934893465766
696 1209400614708606754
697 1250327919321612030
698 1292610406488295179
699 1336291969933450562
700 1381417923396574380
701 1428035002222982936
702 1476191406523784607
703 1525936891591691697
704 1577322771139490880
705 1630401964559517636
706 1685229094205494566
707 1741860490516960288
708 1800354243756557276
709 1860770308693740990
710 1923170511880016655
711 1987618608276060882
712 2054180393916656718
713 2122923715630060698
714 2193918533003984567
715 2267237039657857077
716 2342953675730491896
717 2421145195674566516
718 2501890798812490215
719 2585272144950704057
720 2671373428536846162
721 2760281519229403956
722 2852085981034782036
723 2946879153409457864
724 3044756302631455284
725 3145815644898103504
726 3250158435007419154
727 3357889129382334717
728 3469115413613271876
729 3583948299409020240
730 3702502300193083878
731 3824895463625363879
732 3951249477573271302
733 4081689859273955022
734 4216345993423846752
735 4355351247986841542
736 4498843177997089410
737 4646963569864283020
738 4799858567907984964
739 4957678893962783827
740 5120579898611320620
741 5288721699412809424
742 5462269417566084597
743 5641393236852855640
744 5826268554614749324
745 6017076236830653060
746 6214002685630172490
747 6417240004166791910
748 6626986271574473430
749 6843445619996365382
750 7066828414602481929
751 7297351550008334067
752 7535238537857367000
753 7780719703340483252
754 8034032504787407478
755 8295421632942782059
756 8565139225462532876
757 8843445211527534838
758 9130607424063391161
759 9426901833816883638
760 9732612920992259517
761 10048033801784215798
762 10373466483777427317
763 10709222266768274765
764 11055621885110161374
765 11412995786331371916
766 11781684563480160219
767 12162039114923308664
768 12554420948243448530
769 12959202646634129112
770 13376768047947613917
771 13807512576112194322
772 14251843744307190378
773 14710181355225511296
774 15182957862445460075
775 15670618913336024775
776 16173623572685044350
777 16692444716669709528
778 17227569618681478704
779 17779500198671761514
780 18348753452592011202
781 18935862084586636706
782 19541374784626216194
783 20165856696534528078
784 20809890100278649710
785 21474074720696263332
786 22159028237494914847
787 22865387021671401222
788 23593806478396173366
789 24344961602661359156
790 25119547774188191397
791 25918281137811085456
792 26741899208767493590
793 27591161730804433177
794 28466851097709534735
795 29369773012578129562
796 30300757414209850560
797 31260658943765934776
798 32250357662719106065
799 33270760053042573093
800 34322799533334563430
801 35407437240556759188
802 36525663109963489746
803 37678496445426577599
804 38866986770500703528
805 40092214994522913186
806 41355294042295809210
807 42657369780487692840
808 43999622276854737024
809 45383266494901088828
810 46809553302131059010
811 48279770829909814152
812 49795245239217844248
813 51357341817825175832
814 52967466448914321924
815 54627066454588995873
816 56337631789639910448
817 58100696627709538008
818 59917840289804627877
819 61790688542971395208
820 63720915313489081038
821 65710243708276652218
822 67760447427495916744
823 69873352615026129453
824 72050838981351601860
825 74294841339868677996
826 76607351605721487216
827 78990420029511380593
828 81446156867902232074
829 83976734542792873422
830 86584388996005904349
831 89271421505672675678
832 92040201018686460660
833 94893165637412357940
834 97832824594294190467
835 100861760771577503405
836 103982632332039311256
837 107198174865300031724
838 110511204109932818343
839 113924617741250254960
840 117441397703931891459
841 121064613152852720952
842 124797422412090364737
843 128643075509697127520
844 132604917354892472580
845 136686389883675931264
846 140891034812888969261
847 145222497072834345067
848 149684527156204834152
849 154280984110002355260
850 159015839244179689752
851 163893178702028608441
852 168917206710059944200
853 174092249584919340614
854 179422758544929102351
855 184913313239695228848
856 190568626079338568922
857 196393545308562089860
858 202393058839549525833
859 208572298929483987006
860 214936545540326313708
861 221491230500515843364
862 228241942558830986796
863 235194431055029097367
864 242354610437964741504
865 249728565726092917520
866 257322556516248664959
867 265143021888071453562
868 273196586303874176346
869 281490063985144615848
870 290030464235619251143
871 298824997815857128401
872 307881081719539605036
873 317206344950187241248
874 326808635408602542255
875 336696025103740613453
876 346876816420924131744
877 357359549563369067520
878 368153008235312866452
879 379266226442675096404
880 390708496533173401962
881 402489375392544838264
882 414618691821942060818
883 427106555224698022617
884 439963362359878416972
885 453199805344314957184
886 466826881037906445792
887 480855898402420112018
888 495298487179965914050
889 510166608032850167726
890 525472560559523039751
891 541228992705509448850
892 557448911718282434916
893 574145692876556813882
894 591333089694237107508
895 609025245755580585834
896 627236704218688893186
897 645982418877937382476
898 665277766949879855754
899 685138559416813621940
900 705581053018445409462
901 726621964064580636526
902 748278479690061736134
903 770568270852138347142
904 793509507252015296664
905 817120869578320494836
906 841421563592814400031
907 866431336249371887293
908 892170489009458001420
909 918659893105469159104
910 945921006952730547627
911 973975890627287041753
912 1002847222403354532210
913 1032558317561465306394
914 1063133144126257304148
915 1094596340782263916442
916 1126973237189476462512
917 1160289871086780289886
918 1194573007698668641026
919 1229850161678264378201
920 1266149615690652385752
921 1303500441432114430672
922 1341932523330110901924
923 1381476578730039011715
924 1422164180658301092323
925 1464027783418943852404
926 1507100744517383268729
927 1551417349309098651426
928 1597012838643618640314
929 1643923432669552891210
930 1692186357522007646801
931 1741839875176448921418
932 1792923309291028512876
933 1845477074098007097444
934 1899542706642780142776
935 1955162894832053400930
936 2012381508707704997498
937 2071243635259998231611
938 2131795608863720699493
939 2194085045127083881788
940 2258160878482943599914
941 2324073395209643537802
942 2391874270062817161275
943 2461616606864378631968
944 2533354974320588167950
945 2607145445661070512504
946 2683045642462514098059
947 2761114773493483125724
948 2841413677602689106722
949 2924004871032837570138
950 3008952589540043710761
951 3096322834792493242102
952 3186183425449804924146
953 3278604042824664271396
954 3373656281073592238315
955 3471413702338648527207
956 3571951886240189347536
957 3675348484163640100856
958 3781683278783463706962
959 3891038237698898892968
960 4003497572144527455984
961 4119147801241297686872
962 4238077810111835821095
963 4360378913368331155044
964 4486144924462169761758
965 4615472218642069234060
966 4748459801600514501305
967 4885209384322373255622
968 5025825451277829310536
969 5170415334638437525756
970 5319089295056114630193
971 5471960595513786726249
972 5629145581554253204074
973 5790763768454340776958
974 5956937921189502841305
975 6127794141153271432714
976 6303461960227306824726
977 6484074427352070449496
978 6669768202251887023337
979 6860683656940298287939
980 7056964969427569547004
981 7258760225006480700740
982 7466221525774004456289
983 7679505092048017065725
984 7898771371812101838610
985 8124185158879338837630
986 8355915702635397252324
987 8594136826287087274396
988 8839027054342204926030
989 9090769731344426804234
990 9349553149620331468317
991 9615570686801053567117
992 9889020934266339902484
993 10170107835138543601036
994 10459040832627579080829
995 10756035008957396611883
996 11061311234413314390884
997 11375096327351722423128
998 11697623204442386534370
999 12029131041637741186510
1000 12369865446753280357716