1 1
2 5
3 15
4 44
5 85
6 216
7 343
8 806
9 1299
10 2155
11 2926
12 7162
13 9477
14 13209
15 17935
16 37824
17 47957
18 75600
19 93613
20 138074
21 170730
22 209000
23 249481
24 635974
25 764425
26 915551
27 1109772
28 1390375
29 1624029
30 2103690
31 2430431
32 5120488
33 5976553
34 6946897
35 8043245
36 12724965
37 14587990
38 16687852
39 19028919
40 25584040
41 28953749
42 33493516
43 37682534
44 42795665
45 48454605
46 54135445
47 60315523
48 171453792
49 192094749
50 215576285
51 240518771
52 268743124
53 298596806
54 348306408
55 385446655
56 446244316
57 491929551
58 541437453
59 594950690
60 735502497
61 804987415
62 879916400
63 962532207
64 2248009984
65 2472312193
66 2720275910
67 2983819004
68 3271717201
69 3580087954
70 3919057999
71 4278348743
72 6818360964
73 7417486273
74 8060918494
75 8755176135
76 9499480616
77 10292332985
78 11150093890
79 12057600387
80 15090463160
81 16314682689
82 17587217935
83 18942833613
84 20823268583
85 22385501536
86 24046131781
87 25810209061
88 27871444788
89 29868949397
90 32602155507
91 34881099994
92 37302979364
93 39856576031
94 42557186726
95 45411721951
96 152892065904
97 163759139641
98 175293658253
99 187517313159
100 200976567100
101 214694289636
102 229234620004
103 244581515151
104 261231377602
105 278416202169
106 296528491918
107 315641355470
108 359474606856
109 382057912576
110 405883209204
111 430930851231
112 472287198376
113 500825794953
114 530871724520
115 562403129149
116 595547891249
117 630351094503
118 666856875985
119 705158684727
120 832918938510
121 879464469763
122 928217591203
123 979264366750
124 1032723532974
125 1088638412000
126 1150383113376
127 1211654200639
128 3490615716368
129 3695965334385
130 3911879486307
131 4138672454762
132 4381009561874
133 4631294345734
134 4894002515555
135 5171223160746
136 5462052112513
137 5765373624372
138 6083426316188
139 6416630600842
140 6771221428832
141 7136995091800
142 7519945601167
143 7920760059641
144 12480606993570
145 13122434866435
146 13792809798102
147 14492865409365
148 15223654570573
149 15986256779444
150 16789694033360
151 17619871104006
152 18488385255857
153 19391052517836
154 20331929489509
155 21312169561266
156 22342776999738
157 23406579978289
158 24514233142876
159 25667267031123
160 30376949057396
161 31779864973997
162 33372412101486
163 34894245540934
164 36476190373358
165 38120255431027
166 39828220298538
167 41602379688012
168 44094294504883
169 46030807385784
170 48041117577974
171 50127285473580
172 52291844400208
173 54537175192347
174 56866178737349
175 59281143100585
176 62003365891346
177 64605991680319
178 67303192137199
179 70097877536705
180 74453166084429
181 77500962506395
182 80657076835517
183 83924209326348
184 87313225833243
185 90813194653766
186 94434983985132
187 98181577415702
188 102057089945174
189 106073269495767
190 110218049711371
191 114502805275527
192 476438539512560
193 495978632574833
194 516216492407823
195 537173732163718
196 558886255863677
197 581347469273306
198 604625741688606
199 628683304303759
200 654498490328870
201 680275734432411
202 706937135163678
203 734508565669432
204 763052507861878
205 792525028926915
206 822989033532122
207 854473210973043
208 887596664922604
209 921225699394209
210 956047236157960
211 991929200684448
212 1028984548240046
213 1067245503962980
214 1106745804014021
215 1147519707615395
216 1280965711715910
217 1327374143289649
218 1375246732745904
219 1424622886176368
220 1475595304944266
221 1528101536791336
222 1582235522211891
223 1638039069982751
224 1731583646071184
225 1792019874615825
226 1854262481856691
227 1918387856337879
228 1984507220546599
229 2052546319509430
230 2122617818510892
231 2194772797341245
232 2269086393034616
233 2345567750967089
234 2424365780320263
235 2505395688507856
236 2588785059507236
237 2674591727354737
238 2762876691616511
239 2853699393123615
240 3232261532219192
241 3336718003534189
242 3444113776652549
243 3554822530001898
244 3668316506541532
245 3784965286790156
246 3904844119862204
247 4028027888902069
248 4154627310035476
249 4284658180893049
250 4418266099840725
251 4555467369545126
252 4707279684332268
253 4852247779889653
254 5001103877847551
255 5153937991645439
256 20266456104268544
257 20953300145262689
258 21660766148127238
259 22389391823110818
260 23139850790798287
261 23912469205530101
262 24707940981330486
263 25526856279860396
264 26379458948789122
265 27247302603170684
266 28140442940604802
267 29059520557949962
268 30005194395532728
269 30978134444372618
270 31990053997476705
271 33019846084352857
272 34081930452224108
273 35171265707933303
274 36291451163616494
275 37443251112773330
276 38627604765098361
277 39844985777770921
278 41096364922385544
279 42382571237517370
280 43718152588871150
281 45076860235421520
282 46472990695393212
283 47907439959231158
284 49381128036796990
285 50894991352881675
286 52449984601928199
287 54047081005420075
288 81789605494973348
289 84202573884482193
290 86678429869397055
291 89218594635450311
292 91824523027207116
293 94497693327525053
294 97239837366745794
295 100052051289551103
296 102936197677971965
297 105893798062277049
298 108926398959257320
299 112035734820382529
300 115254419018708295
301 118522942985011921
302 121873372413793212
303 125307492045688827
304 128832787085722490
305 132439886466641793
306 136136504431793701
307 139924022566696433
308 143804944117014598
309 147780703754313444
310 151853607303203274
311 156025714436746205
312 160325297645635057
313 164702664880549667
314 169185665365569370
315 173776830132664028
316 178477794621306954
317 183291162310415767
318 188219274915772924
319 193264506656106655
320 218812872988382784
321 224610608902288569
322 230544033828049515
323 236615902293694562
324 243985262384653074
325 250367579214116455
326 256897374840250821
327 263577612897155438
328 270411435237931504
329 277401650160906248
330 284552289644322590
331 291864957543178977
332 299343654872500143
333 306991657126014385
334 314812294792488890
335 322808957262014005
336 333953876903136760
337 342375105787815775
338 350983978466027790
339 359784127158349011
340 368779708302465734
341 377973566183682073
342 387370444338108650
343 396973284573154338
344 406786659001438682
345 416814254896005126
346 427060299118507576
347 437528933829547506
348 448224880380596052
349 459151387509309454
350 470313836288713910
351 481715764506465411
352 494193842659525360
353 506105337746621405
354 518270600884395684
355 530694326563776642
356 543381297228958805
357 556336364676978687
358 569564450699845491
359 583070564353818654
360 606402257765963344
361 620666249178111884
362 635226871752773013
363 650089494675125582
364 665260208972198060
365 680743268049709827
366 696544931605904539
367 712670895032417585
368 729144684381032176
369 745937010763048271
370 763071287416224015
371 780553566436056829
372 798390722662850658
373 816587569904393451
374 835151160118049874
375 854088166866567700
376 873404878543292276
377 893107662660779072
378 913285948036562907
379 933782965032481864
380 954687595828621664
381 976005277718120672
382 997743930978625216
383 1019910790863846927
384 5346911410319964528
385 5471070958025794913
386 5597786902014237965
387 5727105193096052442
388 5859072477050641915
389 5993736114512791995
390 6131146012003396644
391 6271347381699149959
392 6414442984600316841
393 6560381116324698629
394 6709263479280973510
395 6861141921619845914
396 7016231952828294240
397 7174263708932797621
398 7335451843813579007
399 7499851394226450279
400 7672538198109732770
401 7843617086351884161
402 8018078768138608870
403 8195981620461633557
404 8377384905021123746
405 8562380163805532250
406 8750966032239140269
407 8943235361721931501
408 9139381181338665841
409 9339208702282094119
410 9542910898754957779
411 9750553343865331851
412 9962202584861016255
413 10177926112042395182
414 10397793626058330075
415 10621872141243282607
416 10852894897037580660
417 11085655072085674497
418 11322842499434900764
419 11564530680326252487
420 11811256190641371684
421 12062177260114789761
422 12317826032836482416
423 12578280280559743359
424 12843619320639259129
425 13113922208217754225
426 13389270489917406941
427 13669746374574749601
428 13955433241717956559
429 14246415617856616337
430 14542779197858591395
431 14844610858250662595
432 16240258709007668748
433 16573524898466236195
434 16912855480896411202
435 17258346773008947707
436 17610096404018137136
437 17968203330589172674
438 18332767861164730913
439 18703891625111732346
440 19081882250361900794
441 19466438572984522560
442 19857866559270077689
443 20256274237235714224
444 20661771999836354910
445 21074466475976232569
446 21494470937802757126
447 21921898415099843559
448 22652120223342888680
449 23100021342509107409
450 23556126271628193495
451 24019859586985738696
452 24491688602410153191
453 24971736681110224386
454 25460128809626538520
455 25956991605218109813
456 26462706666950523451
457 26976900516885859217
458 27499954806934259012
459 28032003510161360913
460 28573182333038164177
461 29123624558374834773
462 29683474956115357806
463 30252865360945659367
464 30832012839416840626
465 31420920496340281133
466 32019803915112335639
467 32628810630704513432
468 33248532891666325779
469 33878241950618053483
470 34518528222459632607
471 35169546787839267633
472 35831455500220725861
473 36504411801058785199
474 37188577487306924174
475 37884115548063509615
476 38591193481231759481
477 39309973483198675491
478 40040627131027990432
479 40783325674607214951
480 44569104976091226764
481 45387095354156998481
482 46218397074715867015
483 47063199215432029343
484 47921694450804231475
485 48794073803740267190
486 49688399236866430140
487 50589253381314188899
488 51504590491726082253
489 52434611913947168205
490 53379527062043756833
491 54339538377346233775
492 55314862173968583931
493 56305705774805754006
494 57312287709580227818
495 58334829143634392415
496 59373650464296644158
497 60428768226829247489
498 61500512761633352004
499 62589112739094320899
500 63695019983884273900
501 64818030417528787851
502 65958598683224365350
503 67116964400092846577
504 68393313947397581421
505 69589397799160336789
506 70804031474789241277
507 72037466082343300188
508 73289955669758583640
509 74561757203682103838
510 75853137565386476356
511 77164345884839268351
512 450778539709501959488
513 459401369871403877697
514 468172404737692264030
515 477093906114588965962
516 486168168429525992563
517 495397505559061989730
518 504784273194420684323
519 514330854487888299107
520 524040220346496389809
521 533913711417972656512
522 543954360230781191772
523 554164670427592452077
524 564547190261391126519
525 575104501442227002415
526 585839207404782064581
527 596753957634584709079
528 607920893115108521146
529 619204730152685764979
530 630676766842890861747
531 642339788949499653546
532 654196622583233545503
533 666250117455784858737
534 678503172910673257369
535 690958721212612063319
536 703619733822294096719
537 716489215775337091240
538 729570215029578114037
539 742865816970796600235
540 756540966173693368977
541 770277292084460755627
542 784237737862058010006
543 798425548969180995511
544 812861269550414398844
545 827513934798694928693
546 842403962115171903161
547 857534744503794749874
548 872909746913595220111
549 888532467935224172169
550 904406455015880813810
551 920535284728907678051
552 936923388747253604353
553 953572861790195628620
554 970488212822537027273
555 987673210328939706116
556 1005131669402541488576
557 1022867452333763039427
558 1040884474532606387787
559 1059186683272443929307
560 1077882834684688918874
561 1096768809686026171563
562 1115952159117691552647
563 1135437039027915132580
564 1155227661934799202829
565 1175328274452851559711
566 1195743192144272232209
567 1216477012156251535863
568 1237533684243468800203
569 1258917905465343560806
570 1280634212455396021931
571 1302687158278836084468
572 1325081393336356078852
573 1347821593303327079653
574 1370912508530079133354
575 1394358940032740103535
576 1978054021686871497736
577 2010997146973646683593
578 2044432463491369157742
579 2078366485952918888969
580 2112805810908085236604
581 2147757091062023535230
582 2183227075530322338692
583 2219222584223962342707
584 2255750517618382621277
585 2292817855165382465336
586 2330431642244044073762
587 2368599023038200408700
588 2407328954127632069682
589 2446625278127921503712
590 2486497098976715670249
591 2526951883892010154355
592 2567997488784694570486
593 2609640945597382950131
594 2651891512355546557602
595 2694754544220739781386
596 2738239160492678838977
597 2782353347779021735692
598 2827105182225249309384
599 2872502830211576660749
600 2918892365296826173665
601 2965610458701233480416
602 3012999455374709494766
603 3061067892128773553947
604 3109824400574137166337
605 3159277707936971830385
606 3209436637997150503526
607 3260310111915942304375
608 3311944633411772828452
609 3364274785336807548661
610 3417346842976880548916
611 3471170126605289680949
612 3525756267318019457672
613 3581110395054888934478
614 3637244326456362023402
615 3694167796104655300419
616 3751892178465274846849
617 3810424368044836222418
618 3869775939499858679724
619 3929957057193796749823
620 3990978004791131666765
621 4052849152444922263956
622 4115581000522404403747
623 4179184162574370681627
624 4243892347186775923874
625 4309272934231961634875
626 4375557378705663652501
627 4442756754778384734516
628 4510882254052489911190
629 4579945187597085571214
630 4649962232098189407679
631 4720934500615302225951
632 4792878867805604211537
633 4865807126584452932090
634 4939731204930983932647
635 5014663153521593185977
636 5090615160703503526094
637 5167599511875320542659
638 5245628653159666150016
639 5324715150922731304511
640 5819785740771689907648
641 5906867883552684599265
642 5995118897303009806351
643 6084552680094242907903
644 6175183285340795738525
645 6267024878468474573244
646 6360091804703098867388
647 6454398546141525462500
648 6577546532548926156111
649 6674718427503169387564
650 6773178189301106554335
651 6872940915898768381646
652 6974021894775145834827
653 7076436558053289417813
654 7180200495446457401312
655 7285329455402454292115
656 7391839908863337457954
657 7499746807326720279099
658 7609066941325498554683
659 7719816708836663037848
660 7832019605612262516192
661 7945678562645670319067
662 8060817349064818712711
663 8177453035251186653525
664 8295602867490894661707
665 8415284252448579289314
666 8536514797401790991847
667 8659312242195632951295
668 8783694543654211980506
669 8909679824636162359973
670 9037286388840668247882
671 9166532722045925002271
672 9341760323562930437604
673 9474871276393523123845
674 9609684078902331314939
675 9746219339721625530015
676 9884493890131628216956
677 10024528695417412416982
678 10166343618671134029609
679 10309958711104244165475
680 10455396994124437541075
681 10602673393054313732204
682 10751811303890347801088
683 10902831575716417159252
684 11055759562242051900975
685 11210607957880082121215
686 11367402496285128371610
687 11526164841344922910163
688 11686917630199035691518
689 11849681471307652656307
690 12014479447958516105396
691 12181334024299205048896
692 12350267975820164368230
693 12521304282210096114786
694 12694466096339934961209
695 12869776842039560840653
696 13047263339633312233039
697 13226943100847461430866
698 13408843373901432637134
699 13592988477160778879999
700 13779407901246274074960
701 13968116593539004263431
702 14159147828625647979300
703 14352520182616984341247
704 14559055975051541196496
705 14757316762826430526449
706 14958000442019710257334
707 15161133253634375131574
708 15366741704396152499328
709 15574852497406758990118
710 15785492641146494601763
711 15998689380121928216412
712 16214470221071282527688
713 16432862910389079126833
714 16653895510160719298773
715 16877596227151192551590
716 17103993643455304679523
717 17333116570678811896531
718 17564994088981417149279
719 17799655549148890094973
720 18228359272115816828286
721 18470808429939760693443
722 18716151971093950656954
723 18964420523459786828220
724 19215644997816869119474
725 19469856589835617697940
726 19727086802697266886036
727 19987367368471000979779
728 20250734544205292268089
729 20517234719937185134386
730 20786860217999341051399
731 21059666121510371265820
732 21335685706033814797421
733 21614952487207310178915
734 21897500349489865442033
735 22183363486037687598567
736 22472718501054447159500
737 22765317234500150478421
738 23061335641220218385781
739 23360809105614195380621
740 23663773420349182039659
741 23970264612283277475538
742 24280319099948383980847
743 24593973607445281530437
744 24911269942427243130233
745 25232236024192591554392
746 25556914290293430048237
747 25885342801220485468434
748 26217559981375785048477
749 26553604527934026744774
750 26893520541515410761625
751 27237337525249640917651
752 27585101489021715041678
753 27936850039831242455191
754 28292624939814625783211
755 28652467047048895383464
756 29018116052214217963146
757 29386232363453852517556
758 29758540763701169468377
759 30135083575761023761099
760 30515908894434255912313
761 30901049034947907794566
762 31290552804068201701395
763 31684464032664019855852
764 32082826936084430467759
765 32485686142859198267502
766 32893086592790983957826
767 33305073697156413574591
768 219261613560925082674528
769 222101591852906109140609
770 224974635165550863013729
771 227881085155826287662368
772 230821286730111875826172
773 233795587851705026317736
774 236804339646986591107754
775 239847896317997806527515
776 242926615343032263478171
777 246040857352617424542585
778 249190986237901243827734
779 252377369138410537557184
780 255600395343901027897399
781 258860400993628331038922
782 262157781873366000744794
783 265492918413504509826363
784 268866744350576011815658
785 272278551924264633786893
786 275729276855169512377448
787 279219313254998518942436
788 282749058723780172873036
789 286318914375716877176635
790 289929284866260834070002
791 293580578418293940922499
792 297275557938727935375457
793 301009957517005720067019
794 304786526660815307898687
795 308605688136403796751916
796 312467868413893888580005
797 316373497695465675946411
798 320323010008141170371939
799 324316842972527792843759
800 328444644492933604531280
801 332529341088912632497061
802 336659702486812411184774
803 340836181932203285830535
804 345059236636028168478467
805 349329327669158786803905
806 353646920193343784604324
807 358012483356595898118770
808 362426490368259417176622
809 366889418482416412107068
810 371403128545963843126410
811 375965359131434018214682
812 380577967565213538820083
813 385241447675149584016277
814 389956297627041378052479
815 394723019814044868604901
816 399543573370742790589864
817 404415576899023945024403
818 409340985825367762185902
819 414320319946698140140711
820 419354103407372249002953
821 424442864804054060180101
822 429587137293607581788540
823 434787458513723303305844
824 440044370666162406579434
825 445358420536717137446920
826 450730159451605944647716
827 456160143489239455546079
828 461648946888817634406542
829 467197108161896770007897
830 472805210919889171414275
831 478473830142924507159319
832 484244431386203923658600
833 490036221334298279709537
834 495890285060430848629000
835 501807217058835817808645
836 507787616825299810384253
837 513832088742141670260915
838 519941242304250232010344
839 526115692074128430536051
840 532363142381576385904187
841 538670107842234409907455
842 545044244344996238959960
843 551486187072662021722906
844 557996576457763454616227
845 564576058219521167908946
846 571225283444864436019906
847 577944908452354143704091
848 584735597703469533843490
849 591598013232134909766049
850 598532830396309456541555
851 605540727339717645946661
852 612622387937382650364709
853 619778501476967135735385
854 627009763012128217424933
855 634316873267680047965363
856 641700538556966017025897
857 649161471034077389802413
858 656700388736884010696892
859 664318015238980863036992
860 672015080310792227737101
861 679792319400323659470340
862 687650474049011773786309
863 695590291745624398036751
864 745942038329987132469912
865 754489337780088866158549
866 763124674816919461021845
867 771848854499764165922017
868 780662688370998418239935
869 789566994302876035854256
870 798562596937540741930636
871 807650327135225364834472
872 816831022683252664667464
873 826105527875366483856522
874 835474693757535870577799
875 844939378123150650192350
876 854500445559260179811701
877 864158767388213403660283
878 873915221955485232594322
879 883770694487036852638361
880 893728538931331302044780
881 903784750647216455777871
882 913942697936668027642623
883 924203254888157549675343
884 934567361752635980237063
885 945035946233742908055343
886 955609943462133219053399
887 966290295829171741087542
888 977077966810632229471648
889 987973886223268869773276
890 998979032324986296695693
891 1010094380770384958464152
892 1021320904256513554132099
893 1032659593588531433612607
894 1044111443743815253208544
895 1055677457412895539067663
896 1075824944338694771094288
897 1087707448208397955914209
898 1099707930388987258273559
899 1111827430870632854364699
900 1124075605293852410260730
901 1136436361546249876977886
902 1148919304802321419525455
903 1161525507421263051227755
904 1174256050007827381464367
905 1187112021385731072339325
906 1200094518772878993154567
907 1213204647754742995449642
908 1226443522360512158868295
909 1239812265117367269065425
910 1253312007231469505778913
911 1266943888144028280439891
912 1280712216042582913438914
913 1294611852884607785956549
914 1308647100102078862038948
915 1322819132389454589661030
916 1337129133333991030136744
917 1351578295474082348460707
918 1366167837101543510363781
919 1380898935451302857700769
920 1395772843863164677145431
921 1410790757443876690130481
922 1425953931215904247494037
923 1441263612650913478630411
924 1456721110681956967116764
925 1472327587709778159241685
926 1488084371237264802598671
927 1503992746551203018650487
928 1520054725744234052298292
929 1536270184389911621446673
930 1552641148737054407185580
931 1569168942587435556655183
932 1585854900013269484197719
933 1602700364864379268331211
934 1619706690970265199962120
935 1636875242203462147631965
936 1654214951058487298021905
937 1671712141291889850802351
938 1689375709530182956497549
939 1707207060460239758959153
940 1725207609208451673453536
941 1743378781111100117978453
942 1761722012221500690630411
943 1780238749081830622580003
944 1798930453831817142390638
945 1817798604356966537080785
946 1836844644509119790468704
947 1856070083545460456464165
948 1875476421904192234262693
949 1895065170760254906800374
950 1914837852631849027018410
951 1934796000832839726191691
952 1954941180905648796939653
953 1975274907224093252243559
954 1995798767759670880395665
955 2016514340939195197144513
956 2037423216881907975677336
957 2058526997154361784775648
958 2079827294920663410676324
959 2101325735015222592895311
960 2232297361221891927759856
961 2255223180317517067030073
962 2278360643981007348167951
963 2301711486822166422325466
964 2325277455875402488590812
965 2349060310675267387481034
966 2373061823502127831252426
967 2397283778784995723424504
968 2421727985707402009293348
969 2446396231608737150538346
970 2471290351129510454327595
971 2496412180428000753656393
972 2522185673185284221861091
973 2547771961988560073853187
974 2573591572697712992270234
975 2599646394370368176050815
976 2625938335229939174435966
977 2652469299051138033051901
978 2679241221170510216557083
979 2706256044504767973889880
980 2733515762776607759041070
981 2761022272368647151605035
982 2788777594407761961795579
983 2816783727074223305411711
984 2845042707957543578805089
985 2873556512755721802832509
986 2902327207206149478028478
987 2931356846093320670481299
988 2960647498660148257041926
989 2990201248316885386030235
990 3020020272082334361160793
991 3050106525612858113287271
992 3080463357385458990984044
993 3111090632347104153046233
994 3141991642323901299218845
995 3173168559442784855305899
996 3204623570993515797892803
997 3236358879124097967455764
998 3268376701519729602558572
999 3300679271134437273762249
1000 3333272846336818644542425