-1 1
0 0
1 3
2 4
3 5
4 10
5 15
6 22
7 29
8 36
9 53
10 72
11 99
12 128
13 160
14 212
15 272
16 354
17 448
18 556
19 703
20 874
21 1096
22 1356
23 1662
24 2050
25 2501
26 3060
27 3716
28 4492
29 5444
30 6550
31 7882
32 9436
33 11262
34 13460
35 16013
36 19034
37 22536
38 26616
39 31450
40 37048
41 43602
42 51164
43 59905
44 70124
45 81905
46 95584
47 111302
48 129368
49 150271
50 174240
51 201861
52 233472
53 269636
54 311158
55 358531
56 412756
57 474544
58 544924
59 625259
60 716516
61 820374
62 938200
63 1071841
64 1223626
65 1395388
66 1589940
67 1809770
68 2058088
69 2338854
70 2655452
71 3012610
72 3414724
73 3867262
74 4376844
75 4949519
76 5593232
77 6315632
78 7125920
79 8035010
80 9053394
81 10194299
82 11470840
83 12898396
84 14494828
85 16277892
86 18269320
87 20491221
88 22969084
89 25732014
90 28809568
91 32237039
92 36051040
93 40293328
94 45011080
95 50252917
96 56075674
97 62539062
98 69710644
99 77666250
100 86484998
101 96257816
102 107080968
103 119062547
104 132323268
105 146990404
106 163208436
107 181131122
108 200929856
109 222795078
110 246929172
111 273559897
112 302930700
113 335311300
114 370999856
115 410314875
116 453612376
117 501274360
118 553722156
119 611419479
120 674863210
121 744605443
122 821240256
123 905420778
124 997863496
125 1099337657
126 1210693412
127 1332847057
128 1466803284
129 1613661622
130 1774604420
131 1950932471
132 2144048724
133 2355487548
134 2586924720
135 2840164619
136 3117185284
137 3420120580
138 3751298472
139 4113256337
140 4508728708
141 4940704866
142 5412409976
143 5927354748
144 6489358034
145 7102536908
146 7771381264
147 8500735608
148 9295863640
149 10162480600
150 11106747706
151 12135369394
152 13255578904
153 14475223332
154 15802809728
155 17247506554
156 18819270292
157 20528839140
158 22387846584
159 24408887913
160 26605533344
161 28992492500
162 31585621588
163 34402075987
164 37460407124
165 40780595406
166 44384264640
167 48294710096
168 52537103156
169 57138631745
170 62128565684
171 67538538817
172 73402609632
173 79757535060
174 86642971320
175 94101588877
176 102179447244
177 110926106934
178 120394996624
179 130643697017
180 141734127866
181 153733048446
182 166712248616
183 180749044582
184 195926678352
185 212334607500
186 230069173736
187 249233911175
188 269940220104
189 292307929636
190 316465734776
191 342552089323
192 370715682080
193 401116354550
194 433925893896
195 469328682787
196 507522894442
197 548721206076
198 593152047084
199 641060712728
200 692710319440
201 748383411154
202 808383008396
203 873034302722
204 942686211012
205 1017712762154
206 1098515264644
207 1185523831788
208 1279199681872
209 1380037294796
210 1488566398388
211 1605354897674
212 1731011072016
213 1866186702432
214 2011580053760
215 2167938688423
216 2336063422450
217 2516811459724
218 2711100648976
219 2919913601113
220 3144301644852
221 3385390163672
222 3644383022216
223 3922568358063
224 4221324257268
225 4542124287059
226 4886544694476
227 5256270603958
228 5653103881816
229 6078970937530
230 6535930427776
231 7026182971665
232 7552079773356
233 8116133278264
234 8721027855908
235 9369630473246
236 10065003810188
237 10810418200936
238 11609366052504
239 12465576420340
240 13383029715020
241 14365975395654
242 15418948439364
243 16546788834371
244 17754661411732
245 19048076009059
246 20432911302684
247 21915437422546
248 23502342280920
249 25200758499438
250 27018290945668
251 28963048779021
252 31043676361708
253 33269388764412
254 35650008252564
255 38196001774107
256 40918523990834
257 43829459350148
258 46941469866680
259 50268044441350
260 53823549748104
261 57623287954008
262 61683553780228
263 66021698667148
264 70656197257380
265 75606716257164
266 80894191768656
267 86540906453391
268 92570575539976
269 99008436205932
270 105881340462358
271 113217858603994
272 121048383270744
273 129405244549952
274 138322829864556
275 147837708878503
276 157988771632752
277 168817368483912
278 180367463895696
279 192685796916859
280 205822048694108
281 219829026579994
282 234762851773872
283 250683164434870
284 267653338063992
285 285740703624604
286 305016794501224
287 325557597410164
288 347443825419004
289 370761203735693
290 395600768884924
291 422059194115558
292 450239124080860
293 480249537528932
294 512206127445894
295 546231699499417
296 582456603629436
297 621019179460470
298 662066237227604
299 705753562337874
300 752246444773604
301 801720250541504
302 854361013174256
303 910366070338497
304 969944732194736
305 1033318983210006
306 1100724237429828
307 1172410122280827
308 1248641319821760
309 1329698450420464
310 1415879001161736
311 1507498322288891
312 1604890663568360
313 1708410284012318
314 1818432618103076
315 1935355501538062
316 2059600483602920
317 2191614194595868
318 2331869807059536
319 2480868572046728
320 2639141434341130
321 2807250758103906
322 2985792127533760
323 3175396267519918
324 3376731063586346
325 3590503686287636
326 3817462856599040
327 4058401212627274
328 4314157829808280
329 4585620871952780
330 4873730380020396
331 5179481241185635
332 5503926293880696
333 5848179629247664
334 6213420064362784
335 6600894796384574
336 7011923287404556
337 7447901330798822
338 7910305369117052
339 8400697036810422
340 8920727939791824
341 9472144730188140
342 10056794422078424
343 10676630029584466
344 11333716498637496
345 12030236947917906
346 12768499287399060
347 13550943155194448
348 14380147267538604
349 15258837151613822
350 16189893281161364
351 17176359695091751
352 18221453034568700
353 19328572109321792
354 20501307961944036
355 21743454455942351
356 23059019481705532
357 24452236710563220
358 25927578026364652
359 27489766603215887
360 29143790662835512
361 30894918022484311
362 32748711358567072
363 34711044337200368
364 36788118581228120
365 38986481517073750
366 41313045232746716
367 43775106267787823
368 46380366512281824
369 49136955186505434
370 52053451957099948
371 55138911345661646
372 58402888347565288
373 61855465469058284
374 65507281158173944
375 69369559700977946
376 73454142768459064
377 77773522530722844
378 82340876583732188
379 87170104671027302
380 92275867291703168
381 97673626415135728
382 103379688220210472
383 109411248148967670
384 115786438268018674
385 122524377054382720
386 129645221868676736
387 137170224037515190
388 145121786888392404
389 153523526746421804
390 162400337042223128
391 171778455845671000
392 181685536755878516
393 192150723554425950
394 203204728653448260
395 214879915529427608
396 227210385520896396
397 240232068935413180
398 253982820949491600
399 268502522363207699
400 283833185452594430
401 300019065375665046
402 317106777101281760
403 335145418437590067
404 354186699262369208
405 374285077263877343
406 395497900742516808
407 417885558477729866
408 441511637350236432
409 466443087876767394
410 492750398048290816
411 520507776137017413
412 549793342525934780
413 580689331388986768
414 613282302452346672
415 647663363332193714
416 683928403254909876
417 722178338280825244
418 762519369027112592
419 805063251216750879
420 849927579681320548
421 897236086796703258
422 947118955563956688
423 999713148534300738
424 1055162753030221572
425 1113619343457324876
426 1175242361899787448
427 1240199517334277557
428 1308667204909232264
429 1380830945902451268
430 1456885849360705160
431 1537037096877669394
432 1621500451008331928
433 1710502789070698706
434 1804282663154678176
435 1903090887603151671
436 2007191155745327268
437 2116860686594959416
438 2232390903637713572
439 2354088146793686124
440 2482274419147283428
441 2617288170622367613
442 2759485119593320672
443 2909239115014762318
444 3066943040497206652
445 3233009762331587878
446 3407873124130649252
447 3591988989435774141
448 3785836335433820716
449 3989918399646130162
450 4204763882108129320
451 4430928206313233159
452 4668994840729146992
453 4919576684719683112
454 5183317521284900376
455 5460893539782991721
456 5753014932657067904
457 6060427568564017078
458 6383914746584319496
459 6724299034620329220
460 7082444195950684672
461 7459257208890089512
462 7855690382704224192
463 8272743575500233865
464 8711466518076109352
465 9172961248697766052
466 9658384664895359972
467 10168951196384828886
468 10705935606119088448
469 11270675924556145280
470 11864576523359703256
471 12489111336032090554
472 13145827230793973564
473 13836347544296840248
474 14562375782644769624
475 15325699497494922792
476 16128194346474637352
477 16971828344751681324
478 17858666318289314968
479 18790874567005380748
480 19770725747540448754
481 20800603987020711648
482 21883010236566541784
483 23020567877471295423
484 24216028590448400306
485 25472278500058242606
486 26792344608355216486
487 28179401528911296505
488 29636778537086253184
489 31167966949660950742
490 32776627848930781368
491 34466600168577307693
492 36241909155491471568
493 38106775227047892532
494 40065623240335718400
495 42123092192142455874
496 44284045371050484552
497 46553580979593040432
498 48937043250441967776
499 51440034077355791932
500 54068425184267433062
501 56828370858851718078
502 59726321273225645044
503 62769036421261518160
504 65963600698497844532
505 69317438153704571496
506 72838328444581172832
507 76534423526098490811
508 80414265107740002044
509 84486802912157234152
510 88761413771324283072
511 93247921600237517142
512 97956618283955325068
513 102898285522564430896
514 108084217674683206492
515 113526245644276267565
516 119236761860153399224
517 125228746392997316748
518 131515794264750768040
519 138112144000996403226
520 145032707481830862420
521 152293101152091072090
522 159909678647006689836
523 167899564900707652741
524 176280691800619903396
525 185071835456480405572
526 194292655158956882672
527 203963734097856568642
528 214106621922842711988
529 224743879225022389579
530 235899124024444709028
531 247597080355860777528
532 259863629039931006512
533 272725860741828692992
534 286212131414539663716
535 300352120231991807326
536 315176890125706700384
537 330718951033401411558
538 347012325984848806476
539 364092620145655407133
540 381997092948834287108
541 400764733454085076158
542 420436339069419175872
543 441054597789094329856
544 462664174097293961492
545 485311798697865196062
546 509046362242225951672
547 533919013222393649906
548 559983260218241986176
549 587295078683833230070
550 615913022470537937948
551 645898340298560110263
552 677315097383622440448
553 710230302451003744212
554 744714040365321779356
555 780839610619685542888
556 818683671944268528360
557 858326393290023292028
558 899851611472528307000
559 943346995757872745002
560 988904219690534428164
561 1036619140482636818724
562 1086591986280471028688
563 1138927551657928442760
564 1193735401684456062312
565 1251130084936566956008
566 1311231355844945316656
567 1374164406766884678241
568 1440060110212815097464
569 1509055271655129502542
570 1581292893372990160832
571 1656922449814077878500
572 1736100174953604503656
573 1818989362176079583316
574 1905760677206804881288
575 1996592484650418144213
576 2091671188726220702714
577 2191191588791630585066
578 2295357250297480830380
579 2404380891823054171870
580 2518484788874955799632
581 2637901195172510763104
582 2762872782146988328172
583 2893653097442804873410
584 3030507043216533013040
585 3173711375072786236492
586 3323555222522046219140
587 3480340631854081598004
588 3644383132391451543696
589 3816012327099795507048
590 3995572508583281044596
591 4183423301548465196670
592 4379940332833549506792
593 4585515930182674012132
594 4800559850962932534804
595 5025500042083588504490
596 5260783432442502266992
597 5506876759245081594760
598 5764267429637715345568
599 6033464419123129893464
600 6314999208299102655574
601 6609426759540283777154
602 6917326535271511855376
603 7239303559594192630690
604 7575989525062204048864
605 7928043946492492270279
606 8296155363789227091192
607 8681042595799535709215
608 9083456047351583700216
609 9504179071672473786048
610 9944029390489845700072
611 10403860574233298936804
612 10884563584804138709352
613 11387068383537901109444
614 11912345607045540696904
615 12461408313746873358732
616 13035313804044410409600
617 13635165517154666447528
618 14262115007797568680892
619 14917364006024339257591
620 15602166563617529037784
621 16317831290658228815658
622 17065723685945061588968
623 17847268565165952442762
624 18663952590826158597604
625 19517326908120145672363
626 20409009891128444226144
627 21340690003835746531863
628 22314128780722008780336
629 23331163931808966582376
630 24393712577265673566668
631 25503774616908937735120
632 26663436240081175875096
633 27874873581690270087760
634 29140356530361373167140
635 30462252694916513931241
636 31843031535676722060852
637 33285268667266850548312
638 34791650339960780956648
639 36364978106812703351637
640 38008173684139886328456
641 39724284013257331615822
642 41516486531597894402592
643 43388094661775061803171
644 45342563527405823713440
645 47383495904895516654742
646 49514648420789005711712
647 51739938004584327041680
648 54063448607407446200932
649 56489438197270924034668
650 59022346042101527420924
651 61666800292205439338297
652 64427625874203151766360
653 67309852709062946854780
654 70318724267264085802700
655 73459706474676617683545
656 76738496983325806367940
657 80161034821660057462738
658 83733510439650687866432
659 87462376164549355569387
660 91354357083797295096780
661 95416462372278714284198
662 99655997081668090517720
663 104080574410465080981456
664 108698128473924209940816
665 113516927593890190156548
666 118545588129388743620348
667 123793088869509710887859
668 129268786011123864936800
669 134982428744729174162884
670 140944175472688668038880
671 147164610685130306926106
672 153654762519623612835860
673 160426121031944408653650
674 167490657206164206447488
675 174860842733462616327017
676 182549670590272689335094
677 190570676447404551449012
678 198937960943218794431520
679 207666212855053319536496
680 216770733204503749511716
681 226267460333613074278362
682 236172995990293193484096
683 246504632463001602584956
684 257280380806079381326480
685 268519000198834652822864
686 280240028483203969732968
687 292463813926371199627894
688 305211548256752220931072
689 318505301023439870752068
690 332368055331219612848280
691 346823745005365853465150
692 361897293242314383896992
693 377614652804727353298168
694 394002847821519570567800
695 411090017255836604780867
696 428905460106495875540880
697 447479682410696033855872
698 466844446118689488125728
699 487032819913607138104554
700 508079232052532550359564
701 530019525307948733897712
702 552891014091467654993984
703 576732543845202214069708
704 601584552789166990682892
705 627489136116585300341550
706 654490112732611547081508
707 682633094635358899224452
708 711965559042241246700436
709 742536923368306018990738
710 774398623167424137698312
711 807604193151560084276497
712 842209351407441345219056
713 878272086934865361061496
714 915852750635321128344744
715 955014149884628773593109
716 995821646828525408698044
717 1038343260545082024846792
718 1082649773223710711704768
719 1128814840515888078363869
720 1176915106218748485806786
721 1227030321458964920226404
722 1279243468550325309283924
723 1333640889705427848837709
724 1390312420788399784519812
725 1449351530302770622865708
726 1510855463816138520391918
727 1574925394030499572501431
728 1641666576715487922214824
729 1711188512729592791030513
730 1783605116363079138735176
731 1859034890245333938581368
732 1937601107068080278797144
733 2019431998385905964168344
734 2104660950764975156821620
735 2193426709561166698890519
736 2285873590619656397760016
737 2382151700198466710518384
738 2482417163430452669395560
739 2586832361649536708641830
740 2695566178919428922972656
741 2808794258115967781063324
742 2926699266926862443799048
743 3049471174146879170848946
744 3177307536660160242162296
745 3310413797516235045258928
746 3449003595521719130594276
747 3593299086784905247853589
748 3743531278667473979726712
749 3899940376613953295035528
750 4062776144347350126551482
751 4232298277937842819054970
752 4408776794269696805147528
753 4592492434451882664239274
754 4783737082737573813174880
755 4982814201538983475423876
756 5190039283146082014728332
757 5405740318779674494489024
758 5630258285633559847967360
759 5863947652584131311014714
760 6107176905271222341976344
761 6360329091280397138379946
762 6623802386183203978273292
763 6898010681220827199007398
764 7183384193444918557541880
765 7480370099159796411530568
766 7789433191541739314173224
767 8111056563342651621530436
768 8445742315619866043126696
769 8794012293467812241624962
770 9156408849763603703795456
771 9533495637976262797433400
772 9925858435127099843691612
773 10334105996029881378581412
774 10758870939980092341360344
775 11200810671105967733251236
776 11660608333638938539949128
777 12138973803406381826866064
778 12636644716898577854306308
779 13154387539310443733233634
780 13692998673010377504865492
781 14253305607942210045443848
782 14836168115520387824844256
783 15442479487636913537938479
784 16073167822456770242549506
785 16729197358740311234416944
786 17411569860495110145378492
787 18121326053824472801593410
788 18859547117909384525979680
789 19627356232130219674589190
790 20425920181408186503666024
791 21256451021922805608038536
792 22120207809439029210188316
793 23018498392560457692591648
794 23952681273308180947996300
795 24924167537512559001537969
796 25934422857596224442870912
797 26984969570418898906995300
798 28077388832953243614441328
799 29213322858660121212942590
800 30394477237536242992548872
801 31622623342915549188235122
802 32899600828215825826392672
803 34227320216939434062503542
804 35607765589355318059286128
805 37042997369414029419208444
806 38535155215576559986175472
807 40086461019369149972241849
808 41699222015615869883558044
809 43375834008441810417657902
810 45118784717288013422139256
811 46930657247332891693676838
812 48814133688871477960236408
813 50771998850369895766277416
814 52807144130080507076268936
815 54922571531279661962183245
816 57121397826372748797436404
817 59406858875297790574758656
818 61782314103856233488999880
819 64251251147799732132995306
820 66817290668711640037259444
821 69484191347939289356381484
822 72255855065055256272449040
823 75136332267560389630388139
824 78129827538779636652072100
825 81240705371151264813991410
826 84473496152368497742614912
827 87832902372096903452319708
828 91323805057269535766666400
829 94951270444245288045039094
830 98720556896412510851703888
831 102637122076127026700228572
832 106706630380188061265694560
833 110934960648386516377621240
834 115328214154997075055751448
835 119892722893437960660512125
836 124635058164686925109489424
837 129562039480415785208446744
838 134680743792198623011750068
839 139998515058549376398064198
840 145522974161962916863358012
841 151262029188566784612500337
842 157223886083434836817856328
843 163417059695080151277396690
844 169850385223120429264204504
845 176533030083605721984553373
846 183474506207012281393705464
847 190684682784433743334907923
848 198173799478053689836149408
849 205952480112548705642550418
850 214031746864660208762793196
851 222423034968783075928102066
852 231138207957045144992649384
853 240189573453007164506704092
854 249589899538783380691642136
855 259352431716081669908151313
856 269490910482385174288159088
857 280019589544240216213753696
858 290953254690392168832208728
859 302307243348306474095065787
860 314097464848440296302979664
861 326340421421487357970905132
862 339053229954699442908293568
863 352253644534308504509303846
864 365960079802016551079565130
865 380191635154501980186022788
866 394968119815906519758403392
867 410310078814311191169503117
868 426238819894299821238717088
869 442776441398826506079229684
870 459945861154765994995668768
871 477770846397728668097878280
872 496276044772959071935414544
873 515487016450427522153992978
874 535430267393548540546559936
875 556133283822336367417173691
876 577624567913231654888400376
877 599933674779298795799092228
878 623091250776020584208101632
879 647129073179484948248358936
880 672080091285387575649638484
881 697978468978959265223401934
882 724859628827661515792269116
883 752760297750300520637381032
884 781718554318065629124440776
885 811773877744925600033294574
886 842967198626809227975489480
887 875340951491049540650449684
888 908939129219707140834029744
889 943807339412583898390135364
890 979992862758017304702246664
891 1017544713481902745309879911
892 1056513701947818727456885644
893 1096952499483655407705657248
894 1138915705512743216929939824
895 1182459917070172488869466579
896 1227643800787780874531090644
897 1274528167434155614116614628
898 1323176049098981647967229264
899 1373652779114135696956017544
900 1426026074807109861280259702
901 1480366123185639853137867276
902 1536745669655804998554284856
903 1595240109879391594488971582
904 1655927584879937593001885468
905 1718889079510636703942187798
906 1784208524401167532358844848
907 1851972901504520280251360172
908 1922272353369054872296402528
909 1995200296265307383200523316
910 2070853537301501201363737272
911 2149332395666308959956599625
912 2230740828142142591652022264
913 2315186559037160301449897920
914 2402781214689235722840692376
915 2493640462700374245460612306
916 2587884156065477860414074044
917 2685636482364944299110299368
918 2787026118196380822172683624
919 2892186389026680191755212224
920 3001255434651888071758463184
921 3114376380458680682553789574
922 3231697514687860234405063588
923 3353372471907109630755739388
924 3479560422907287017094445824
925 3610426271243830996347415124
926 3746140856652382114976258604
927 3886881165575496679120381603
928 4032830549045385743743797724
929 4184178948175912366039458410
930 4341123127525674503808238904
931 4503866916602882792373990682
932 4672621459791902974188809608
933 4847605474990827623164279080
934 5029045521259225323113852672
935 5217176275785343218465083273
936 5412240820492504650087853604
937 5614490938615238656210524158
938 5824187421586863614556588048
939 6041600386591774647471048466
940 6267009605147614759971853720
941 6500704843094837259111268588
942 6742986212383883310097504400
943 6994164535063370785626506466
944 7254561719886267303623492716
945 7524511151965068853931823160
946 7804358095921520551408789104
947 8094460112991389770985123738
948 8395187492560308253669741864
949 8706923698622684127598481976
950 9030065831672221356058093256
951 9365025106549668658528005087
952 9712227346791045092113538136
953 10072113496037836777017750844
954 10445140147089471031594377060
955 10831780089197832267457956883
956 11232522874223685325113714760
957 11647875402295610134085654112
958 12078362527633516564565922840
959 12524527685220939353716884861
960 12986933539033200339211329188
961 13466162652552167399199747387
962 13962818182322731452083943904
963 14477524595331363830000699568
964 15010928411013142531582647940
965 15563698968720547035308806478
966 16136529221515117960929842448
967 16730136557171756634427194771
968 17345263647315110144019637796
969 17982679325638083072089502060
970 18643179496184148059649240336
971 19327588072707796624278226041
972 20036757950161178201517134912
973 20771572009389840397909233588
974 21532944156156437473898899180
975 22321820395648439233136915593
976 23139179943664254789527621156
977 23986036375711786972700323784
978 24863438815294387532266498112
979 25772473162701418828637840386
980 26714263365664279686948677098
981 27689972733283831379293757542
982 28700805294681669747128104276
983 29748007203875779859406541070
984 30832868192430706137112057188
985 31956723071483623697106001860
986 33120953284800620319195309712
987 34326988514572102857383649342
988 35576308341712691888519649584
989 36870443962489187971446719736
990 38210979963360348806995501428
991 39599556155974329109331696632
992 41037869474333719576535041304
993 42527675936204360967646931308
994 44070792670912426836203279104
995 45669100015744849300545806930
996 47324543683241033540578834176
997 49039137001738990686268939264
998 50814963231616718831810318840
999 52654177959749800543479272758
1000 54559011574788968759767591172