1 1
2 2
3 3
4 5
5 7
6 10
7 14
8 20
9 27
10 36
11 48
12 63
13 82
14 106
15 136
16 173
17 218
18 273
19 341
20 423
21 522
22 641
23 784
24 955
25 1158
26 1399
27 1685
28 2023
29 2421
30 2889
31 3437
32 4079
33 4828
34 5701
35 6716
36 7893
37 9257
38 10834
39 12655
40 14754
41 17169
42 19944
43 23128
44 26775
45 30948
46 35716
47 41157
48 47358
49 54416
50 62441
51 71554
52 81891
53 93604
54 106862
55 121854
56 138789
57 157900
58 179446
59 203714
60 231023
61 261728
62 296220
63 334933
64 378348
65 426997
66 481466
67 542405
68 610530
69 686631
70 771581
71 866340
72 971966
73 1089625
74 1220598
75 1366296
76 1528268
77 1708218
78 1908016
79 2129714
80 2375564
81 2648035
82 2949834
83 3283926
84 3653559
85 4062286
86 4513996
87 5012942
88 5563773
89 6171569
90 6841879
91 7580762
92 8394831
93 9291299
94 10278034
95 11363613
96 12557382
97 13869522
98 15311119
99 16894242
100 18632023
101 20538746
102 22629945
103 24922504
104 27434771
105 30186678
106 33199868
107 36497838
108 40106087
109 44052279
110 48366417
111 53081030
112 58231377
113 63855661
114 69995267
115 76695011
116 84003409
117 91972971
118 100660511
119 110127483
120 120440342
121 131670930
122 143896892
123 157202124
124 171677250
125 187420135
126 204536438
127 223140202
128 243354489
129 265312059
130 289156098
131 315040999
132 343133198
133 373612072
134 406670895
135 442517867
136 481377216
137 523490373
138 569117232
139 618537500
140 672052136
141 729984897
142 792683986
143 860523813
144 933906885
145 1013265817
146 1099065486
147 1191805332
148 1292021814
149 1400291035
150 1517231543
151 1643507324
152 1779830996
153 1926967217
154 2085736320
155 2257018197
156 2441756437
157 2640962743
158 2855721638
159 3087195487
160 3336629849
161 3605359183
162 3894812926
163 4206521972
164 4542125576
165 4903378704
166 5292159866
167 5710479454
168 6160488622
169 6644488739
170 7164941452
171 7724479393
172 8325917576
173 8972265523
174 9666740161
175 10412779543
176 11214057441
177 12074498859
178 12998296534
179 13989928472
180 15054176592
181 16196146536
182 17421288727
183 18735420734
184 20144751040
185 21655904285
186 23275948076
187 25012421460
188 26873365154
189 28867353643
190 31003529250
191 33291638297
192 35742069486
193 38365894625
194 41174911834
195 44181691386
196 47399624332
197 50842974071
198 54526931040
199 58467670706
200 62682415051
201 67189497750
202 72008433260
203 77159990046
204 82666268178
205 88550781555
206 94838545021
207 101556166650
208 108731945501
209 116395975153
210 124580253348
211 133318798092
212 142647770577
213 152605605317
214 163233147900
215 174573800788
216 186673677620
217 199581766493
218 213350102728
219 228033951653
220 243692001960
221 260386570230
222 278183817241
223 297153976731
224 317371597285
225 338915798092
226 361870539331
227 386324907996
228 412373420006
229 440116339507
230 469660016300
231 501117242396
232 534607628735
233 570258003188
234 608202830983
235 648584658792
236 691554583754
237 737272748796
238 785908865668
239 837642767199
240 892664990343
241 951177391684
242 1013393797134
243 1079540687674
244 1149857923058
245 1224599505523
246 1304034385633
247 1388447312513
248 1478139730833
249 1573430727026
250 1674658027359
251 1782179050600
252 1896372018173
253 2017637124836
254 2146397773073
255 2283101874557
256 2428223222210
257 2582262936561
258 2745750990298
259 2919247815107
260 3103345995090
261 3298672051285
262 3505888322021
263 3725694944098
264 3958831940023
265 4206081416797
266 4468269882023
267 4746270683403
268 5041006577974
269 5353452437782
270 5684638098995
271 6035651361829
272 6407641149014
273 6801820830911
274 7219471725808
275 7661946784322
276 8130674467293
277 8627162827019
278 9153003802150
279 9709877737091
280 10299558137272
281 10923916672229
282 11584928438991
283 12284677498917
284 13025362701737
285 13809303811243
286 14638947947773
287 15516876363363
288 16445811566228
289 17428624812021
290 18468343980188
291 19568161854604
292 20731444828608
293 21961742055539
294 23262795066868
295 24638547881107
296 26093157627776
297 27631005711881
298 29256709545574
299 30975134874945
300 32791408731224
301 34710933037086
302 36739398900195
303 38882801627665
304 41147456496720
305 43540015318498
306 46067483833707
307 48737239980676
308 51557053078244
309 54535103967957
310 57680006162130
311 61000828046522
312 64507116188670
313 68208919805326
314 72116816444949
315 76241938943825
316 80596003717129
317 85191340449116
318 90040923249612
319 95158403347117
320 100558143392113
321 106255253447569
322 112265628747237
323 118605989306059
324 125293921470910
325 132347921503989
326 139787441295440
327 147632936306229
328 155905915846973
329 164628995803285
330 173825953923266
331 183521787788105
332 193742775592289
333 204516539865715
334 215872114276054
335 227840013656051
336 240452307407021
337 253742696436730
338 267746593797023
339 282501209194111
340 298045637552253
341 314420951819789
342 331670300215044
343 349839008118544
344 368974684827336
345 389127335396938
346 410349477806619
347 432696265694326
348 456225616918651
349 480998348216810
350 507078316239665
351 534532565257425
352 563431481842819
353 593848956852240
354 625862555039686
355 659553692653268
356 695007823379638
357 732314633017956
358 771568243281987
359 812867425146627
360 856315822173612
361 902022184270449
362 950100612356686
363 1000670814432621
364 1053858373567390
365 1109795028346204
366 1168618966340271
367 1230475131187743
368 1295515543899903
369 1363899639033768
370 1435794616400424
371 1511375809007712
372 1590827067966484
373 1674341165121513
374 1762120214201385
375 1854376111316342
376 1951330995669169
377 2053217731381880
378 2160280411380185
379 2272774884318654
380 2390969305572110
381 2515144713363247
382 2645595631142762
383 2782630697386579
384 2926573324025025
385 3077762384771248
386 3236552934670783
387 3403316962251072
388 3578444175709064
389 3762342824636775
390 3955440558849085
391 4158185325945079
392 4371046309304114
393 4594514908290560
394 4829105762516966
395 5075357822094363
396 5333835465880664
397 5605129669823769
398 5889859227585213
399 6188672025723099
400 6502246375809820
401 6831292405960848
402 7176553514355791
403 7538807887442179
404 7918870085626224
405 8317592699373245
406 8735868078763787
407 9174630139679879
408 9634856249929543
409 10117569198756854
410 10623839253329714
411 11154786305948322
412 11711582115874302
413 12295452649843846
414 12907680525498315
415 13549607562142745
416 14222637443426930
417 14928238496735497
418 15667946594272906
419 16443368181036955
420 17256183435090438
421 18108149565765437
422 19001104255668680
423 19936969252599803
424 20917754117747637
425 21945560136793112
426 23022584400821522
427 24151124064232076
428 25333580787129331
429 26572465369989745
430 27870402588717594
431 29230136238538442
432 30654534395525688
433 32146594904916958
434 33709451105752860
435 35346377801761382
436 37060797488817612
437 38856286849731093
438 40736583527552623
439 42705593189049338
440 44767396890472141
441 46926258758233693
442 49186633997628968
443 51553177243264591
444 54030751265418564
445 56624436047129439
446 59339538247414288
447 62181601066638890
448 65156414530712293
449 68270026211452301
450 71528752401169396
451 74939189760245274
452 78508227457239488
453 82243059821844864
454 86151199531830460
455 90240491355961088
456 94519126475766069
457 98995657409948158
458 103679013566177875
459 108578517446010099
460 113703901529690205
461 119065325868687724
462 124673396414907998
463 130539184116688202
464 136674244812885054
465 143090639957609252
466 149800958209457934
467 156818337920443116
468 164156490561213005
469 171829725120616319
470 179852973519169341
471 188241817077553462
472 197012514082899726
473 206182028497308603
474 215768059854810291
475 225789074394795753
476 236264337481843973
477 247213947363839243
478 258658870322316366
479 270620977271094408
480 283123081861463925
481 296188980154481555
482 309843491923302644
483 324112503650950459
484 339023013291482958
485 354603176865178578
486 370882356961124678
487 387891173223460035
488 405661554900499960
489 424226795539063368
490 443621609909529639
491 463882193250483795
492 485046282925265913
493 507153222586329502
494 530244028947038661
495 554361461264400309
496 579550093640240823
497 605856390252501499
498 633328783632649983
499 662017756109691041
500 691975924545915766
501 723258128494359873
502 755921521912955509
503 790025668575563814
504 825632641325474217
505 862807125322558358
506 901616525441079081
507 942131077981185888
508 984423966863385553
509 1028571444481768655
510 1074652957398508114
511 1122751277069133394
512 1172952635795333054
513 1225346868109558365
514 1280027557803501674
515 1337092190820615330
516 1396642314241230931
517 1458783701597545399
518 1523626524764771339
519 1591285532684116092
520 1661880237182969075
521 1735535106167753051
522 1812379764475345029
523 1892549202679810097
524 1976183994162430700
525 2063430520764669261
526 2154441207355788643
527 2249374765659388385
528 2348396447696111065
529 2451678309213249253
530 2559399483485956650
531 2671746465889255083
532 2788913409655050609
533 2911102433243946239
534 3038523939777785679
535 3171396948995602546
536 3309949442213004059
537 3454418720783009308
538 3605051778575012703
539 3762105689007876710
540 3925848007193198996
541 4096557187765572906
542 4274523018998193025
543 4460047073824476562
544 4653443178409504470
545 4855037898939062665
546 5065171047318913529
547 5284196206502682090
548 5512481276193432212
549 5750409039691668980
550 5998377752691168830
551 6256801754853744442
552 6526112105024833972
553 6806757240983702025
554 7099203664655092381
555 7403936653743420828
556 7721461000786082774
557 8052301780659218499
558 8397005147607374121
559 8756139162907965619
560 9130294654322344906
561 9520086108527631274
562 9926152597767360325
563 10349158742004469503
564 10789795707907240067
565 11248782246047607208
566 11726865767741792473
567 12224823463015567150
568 12743463461230685376
569 13283626035965197206
570 13846184855798532736
571 14432048282712508963
572 15042160719881824127
573 15677504010692245076
574 16339098890891639540
575 17028006495848337566
576 17745329924963108009
577 18492215865355392927
578 19269856277021444063
579 20079490141741743284
580 20922405278097658125
581 21799940225042782868
582 22713486196562946610
583 23664489110050537814
584 24654451691113708686
585 25684935657639294863
586 26757563986030032678
587 27874023262641997959
588 29036066123557251200
589 30245513785939582669
590 31504258674338140371
591 32814267145424731264
592 34177582314775853697
593 35596326989440193582
594 37072706710166550084
595 38609012907306105565
596 40207626174546781298
597 41871019664786292778
598 43601762612604609587
599 45402523987956013842
600 47276076285866023456
601 49225299457089293093
602 51253184984861424666
603 53362840113060614865
604 55557492231284450876
605 57840493422543155455
606 60215325179473404581
607 62685603295186728221
608 65255082935083698326
609 67927663896189857129
610 70707396060801900494
611 73598485051473271494
612 76605298094617313362
613 79732370100263762536
614 82984409965770925109
615 86366307111571676872
616 89883138257316771602
617 93540174447074158015
618 97342888332548427365
619 101296961723600486614
620 105408293415674433468
621 109683007304076768204
622 114127460795402894298
623 118748253526767729023
624 123552236403871573209
625 128546520969319596448
626 133738489113013814204
627 139135803136850715021
628 144746416186386202464
629 150578583062572726077
630 156640871427131882762
631 162942173415599885044
632 169491717672573643083
633 176299081824192337649
634 183374205403413834179
635 190727403244187684554
636 198369379361187383487
637 206311241332344610226
638 214564515202028033799
639 223141160923329552372
640 232053588358562257227
641 241314673857737664507
642 250937777435475571409
643 260936760567509019844
644 271326004628680066368
645 282120429995080164166
646 293335515833772789198
647 304987320604346343277
648 317092503297383224696
649 329668345435797183805
650 342732773865886617837
651 356304384365877278306
652 370402466100684968909
653 385047026952618238160
654 400258819758763888681
655 416059369486855438648
656 432471001382517620506
657 449516870121909764923
658 467220990004958709372
659 485608266225578945257
660 504704527256525370382
661 524536558387813581788
662 545132136458975507824
663 566520065826795762533
664 588730215611597880753
665 611793558266621076929
666 635742209516548931572
667 660609469712823064108
668 686429866654999069105
669 713239199929080497851
670 741074586815501237612
671 769974509821219112445
672 799978865892235796872
673 831129017364772152597
674 863467844715305886920
675 897039801171722072508
676 931890969249938711262
677 968069119282551388585
678 1005623770008295437712
679 1044606251293453279448
680 1085069769058741158647
681 1127069472487695880904
682 1170662523595150957285
683 1215908169237045470442
684 1262867815645550746347
685 1311605105576332404519
686 1362185998157691509036
687 1414678851534351389653
688 1469154508401779380181
689 1525686384530158462845
690 1584350560380455948093
691 1645225875918478300679
692 1708394028736356595302
693 1773939675594579511747
694 1841950537501484039441
695 1912517508451032053463
696 1985734767943747670419
697 2061699897419869942625
698 2140514000738092283224
699 2222281828837718448956
700 2307111908726669496352
701 2395116676942531570104
702 2486412617638745526162
703 2581120405453111236593
704 2679365053321017125582
705 2781276065401214365759
706 2886987595287540708242
707 2996638609685766787787
708 3110373057740693773567
709 3228340046204781446900
710 3350694020645936389308
711 3477594952898647361922
712 3609208534969425755618
713 3745706379614500002351
714 3887266227814931087451
715 4034072163381769035299
716 4186314834931564928724
717 4344191685480497371081
718 4507907189913574255459
719 4677673100593838462080
720 4853708701385248112728
721 5036241070371926983463
722 5225505351565797599153
723 5421745035904227670499
724 5625212251849249439769
725 5836168065910161026263
726 6054882793421899163709
727 6281636319922494272265
728 6516718433484192405806
729 6760429168364465394116
730 7013079160355141938539
731 7274990014220290353364
732 7546494683626280275629
733 7827937863980658572694
734 8119676398610106829207
735 8422079698721817563340
736 8735530177607147490438
737 9060423699561392930529
738 9397170044008999493402
739 9746193385339480572442
740 10107932788975792503299
741 10482842724213914543038
742 10871393594389925641486
743 11274072284948974360612
744 11691382730009220826227
745 12123846498033108386413
746 12572003397238216377238
747 13036412101400473306919
748 13517650796723691704307
749 14016317850471242285260
750 14533032502078237047394
751 15068435577485860132575
752 15623190227463494185862
753 16197982690709061563793
754 16793523082543557884866
755 17410546210042124579366
756 18049812414471212542588
757 18712108441929456755253
758 19398248343118838633100
759 20109074403202586548883
760 20845458102737083922680
761 21608301110696847857726
762 22398536310644439761133
763 23217128861131003905823
764 24065077291448032584931
765 24943414633886960483811
766 25853209593700330255351
767 26795567757996581176348
768 27771632844840029398851
769 28782587993868369003094
770 29829657099782066252849
771 30914106190103384761050
772 32037244848647507505636
773 33200427686194354841881
774 34405055859897279160669
775 35652578643013891276410
776 36944495046594886978165
777 38282355494818941818163
778 39667763555715576950282
779 41102377729073418948491
780 42587913293388533831104
781 44126144213766563353394
782 45718905112753284980462
783 47368093306131012443020
784 49075670905783009745911
785 50843666991794868034061
786 52674179856030653723161
787 54569379319492641534442
788 56531509125846663213223
789 58562889413570599411718
790 60665919269261388161814
791 62843079364716190328887
792 65096934680486114352043
793 67430137318686235585210
794 69845429407933628084900
795 72345646103375839521095
796 74933718684865766212743
797 77612677756435310793236
798 80385656550319617941123
799 83255894338886174851909
800 86226739957928726278266
801 89301655444894885423187
802 92484219795728621005410
803 95778132844124569661726
804 99187219267110466787538
805 102715432720997016363179
806 106366860111861342916195
807 110145726004860901499439
808 114056397176809482812442
809 118103387316585862270866
810 122291361878088829470714
811 126625143090599927364724
812 131109715131567361669918
813 135750229466981347609798
814 140552010364672784179038
815 145520560586033731003327
816 150661567261829859157897
817 155980907957952009041638
818 161484656937136374175266
819 167179091622870802889630
820 173070699271898438410068
821 179166183861929574909640
822 185472473201378370895704
823 191996726268153115269736
824 198746340784747274432220
825 205728961037103755336536
826 212952485944956899603800
827 220425077391595883768566
828 228155168821239652576142
829 236151474112467474383438
830 244422996736410904939318
831 252979039208682609560721
832 261829212844295362202508
833 270983447825110858365402
834 280452003589652999620976
835 290245479555424290586820
836 300374826184177201911491
837 310851356400915070521553
838 321686757377729614402716
839 332893102693924725193810
840 344482864884229168064049
841 356468928387264473702375
842 368864602906808969790243
843 381683637198784896369444
844 394940233297293217930602
845 408649061193430431549070
846 422825273981043731815976
847 437484523484015696895588
848 452642976380117583736494
849 468317330836931753238834
850 484524833675819088328614
851 501283298080396931363380
852 518611121866497476029555
853 536527306331096139159771
854 555051475698234658651101
855 574203897180514976900229
856 594005501675307850305674
857 614477905115405063637404
858 635643430494446626852805
859 657525130588074909256594
860 680146811392406854788268
861 703533056302073771144659
862 727709251050756258760967
863 752701609437840224070018
864 778537199865539202425142
865 805243972711569014372939
866 832850788563223727132789
867 861387447339487641987758
868 890884718328627247416121
869 921374371169540456118663
870 952889207805998690422375
871 985463095443801224100936
872 1019131000541771379697318
873 1053929023868461490825926
874 1089894436657398762756020
875 1127065717894698118771727
876 1165482592773891644802012
877 1205186072353878205214457
878 1246218494456982087912879
879 1288623565845227061961204
880 1332446405714082937133434
881 1377733590544126570330620
882 1424533200352279264750432
883 1472894866385538678637739
884 1522869820301416755339033
885 1574510944880626889369102
886 1627872826318934669450402
887 1683011808146498236088552
888 1739986046824477738092486
889 1798855569070189783155078
890 1859682330963623400476492
891 1922530278889720152385721
892 1987465412372453967595148
893 2054555848858427379387967
894 2123871890509431534705528
895 2195486093065199031610772
896 2269473336839412820733564
897 2345910899913922590918421
898 2424878533598063813523271
899 2506458540221975551262774
900 2590735853334872899473382
901 2677798120381350220518727
902 2767735787930973904382577
903 2860642189538670038601769
904 2956613636315724947908871
905 3055749510293596970090533
906 3158152360665188025363807
907 3263928002990745523208924
908 3373185621458161001236361
909 3486037874290103732042662
910 3602601002393177553059344
911 3722994941347119619935414
912 3847343436834972968428454
913 3975774163618163070890721
914 4108418848163494436188068
915 4245413395032259240293830
916 4386898017144918573838049
917 4533017370038180810483025
918 4683920690234763569018773
919 4839761937849688572446115
920 5000699943560625288135719
921 5166898560073572534882330
922 5338526818219050319401075
923 5515759087817970156560690
924 5698775243460464262755409
925 5887760835345185609379307
926 6082907265330945295746724
927 6284411968357034556206343
928 6492478599393189561321568
929 6707317226084901715743050
930 6929144527264658207690174
931 7158183997504721045568205
932 7394666157892221754775656
933 7638828773212667443645734
934 7890917075733426339112570
935 8151183995784391516638984
936 8419890399338814904153754
937 8697305332803264350981172
938 8983706275231789374013663
939 9279379398185691011492830
940 9584619833466783052991180
941 9899731948958710935991119
942 10225029632817766112352366
943 10560836586261703147456703
944 10907486625212339828491425
945 11265323991055202889978961
946 11634703670787179538586594
947 12015991726831053864667777
948 12409565636803953723524659
949 12815814643535114187724017
950 13235140115636984824445530
951 13667955918942576633996226
952 14114688799131067481217212
953 14575778775873069438347858
954 15051679548836615012982404
955 15542858915904849339648761
956 16049799203966629860045990
957 16572997712651741812806868
958 17112967171393245228326415
959 17670236210210585535091063
960 18245349844618534022490045
961 18838869975078785203154747
962 19451375901423134754290303
963 20083464852689603624763857
964 20735752532825670766010298
965 21408873682725938740892387
966 22103482659085093421231481
967 22820254030560941619935888
968 23559883191756629625694309
969 24323086995545872323208862
970 25110604404280168302070881
971 25923197160432552809101156
972 26761650477248459631581556
973 27626773749990737393165969
974 28519401288382808021792090
975 29440393070871378380801338
976 30390635521348033671114989
977 31371042308987467013048313
978 32382555171879047779414713
979 33426144765147916344362962
980 34502811534281829901935741
981 35613586614400588272104808
982 36759532756226055949003677
983 37941745279532583288094099
984 39161353054880032352463263
985 40419519514454648676271547
986 41717443692866706657290454
987 43056361298778211543660549
988 44437545818258983610027899
989 45862309650795199210346322
990 47332005278900938555467605
991 48848026472310511435144793
992 50411809527757320377945561
993 52024834545373797175015628
994 53688626742776535120502559
995 55404757807931158173811437
996 57174847291922742568949966
997 59000564042789759853821237
998 60883627681612567251600181
999 62825810122081456573080349
1000 64828937134804212328245802