0 0
1 1
2 1
3 1
4 3
5 3
6 5
7 9
8 10
9 14
10 22
11 28
12 37
13 53
14 66
15 85
16 120
17 147
18 188
19 252
20 308
21 394
22 509
23 621
24 783
25 990
26 1210
27 1500
28 1872
29 2272
30 2793
31 3447
32 4152
33 5064
34 6184
35 7414
36 8984
37 10856
38 12964
39 15592
40 18711
41 22250
42 26576
43 31690
44 37520
45 44565
46 52856
47 62292
48 73629
49 86863
50 101991
51 119993
52 140894
53 164828
54 193090
55 225776
56 263230
57 307108
58 357760
59 415702
60 483258
61 560968
62 649774
63 752820
64 871047
65 1005941
66 1161830
67 1340140
68 1543408
69 1777316
70 2044304
71 2348098
72 2696500
73 3093275
74 3544085
75 4059348
76 4645010
77 5309164
78 6066272
79 6924970
80 7897225
81 9002517
82 10253781
83 11668088
84 13272198
85 15084552
86 17129992
87 19444411
88 22054947
89 24996333
90 28317637
91 32057405
92 36264745
93 41005959
94 46336176
95 52323254
96 59058058
97 66617185
98 75095892
99 84616392
100 95286343
101 107237055
102 120634157
103 135626738
104 152396278
105 171164931
106 192140486
107 215569755
108 241753592
109 270976284
110 303575503
111 339954802
112 380504159
113 425681283
114 476028810
115 532076172
116 594445356
117 663859809
118 741040943
119 826824772
120 922179720
121 1028079255
122 1145648384
123 1276175954
124 1420975395
125 1581550291
126 1759618724
127 1956938876
128 2175522667
129 2417645950
130 2685663994
131 2982251671
132 3310426064
133 3673323182
134 4074497991
135 4517931990
136 5007798886
137 5548798101
138 6146185820
139 6805485750
140 7532908772
141 8335364305
142 9220156727
143 10195458386
144 11270348383
145 12454442329
146 13758485804
147 15194363599
148 16774721799
149 18513633735
150 20426647120
151 22530328654
152 24843090544
153 27385206007
154 30178351418
155 33246532699
156 36616162618
157 40315502623
158 44375817817
159 48831416739
160 53719097167
161 59079456890
162 64957008953
163 71399521463
164 78459643989
165 86194971751
166 94667431047
167 103945109257
168 114102442879
169 125219490691
170 137384186056
171 150692497792
172 165247772586
173 181163297478
174 198562642173
175 217578880813
176 238357769102
177 261058046981
178 285850825969
179 312923206127
180 342478836378
181 374737240768
182 409938249164
183 448342583291
184 490231464674
185 535911667163
186 585716534446
187 640005559329
188 699170608026
189 763637033552
190 833863724175
191 910350268045
192 993638679574
193 1084313590373
194 1183011034075
195 1290420414908
196 1407285510568
197 1534414580317
198 1672683322792
199 1823036252907
200 1986499085603
201 2164182234480
202 2357283450993
203 2567102187329
204 2795044595183
205 3042626959633
206 3311493310022
207 3603421384556
208 3920328103551
209 4264290075275
210 4637551858672
211 5042532958647
212 5481852917871
213 5958341309707
214 6475047927410
215 7035272125464
216 7642576366667
217 8300799047985
218 9014090397671
219 9786928978305
220 10624139429598
221 11530934677662
222 12512937845289
223 13576204418997
224 14727273894729
225 15973196509433
226 17321563023963
227 18780565660466
228 20359033058686
229 22066467341521
230 23913118535559
231 25910027409534
232 28069074115958
233 30403066314005
234 32925794585190
235 35652092575920
236 38597944670389
237 41780553876575
238 45218419492094
239 48931465115953
240 52941125411790
241 57270441971198
242 61944219495099
243 66989132110060
244 72433845739190
245 78309204131686
246 84648363803549
247 91486944460873
248 98863255826437
249 106818463008072
250 115396776448642
251 124645722967143
252 134616353943183
253 145363478259438
254 156945992577932
255 169427136046834
256 182874782392064
257 197361835141633
258 212966546393172
259 229772874217714
260 247870963633937
261 267357536395092
262 288336336030179
263 310918704378783
264 335224066807203
265 361380475426332
266 389525310228338
267 419805871396543
268 452380052175319
269 487417180281851
270 525098751591909
271 565619249997299
272 609187169419915
273 656025908185719
274 706374779899899
275 760490240774232
276 818646992955561
277 881139213835043
278 948282045164695
279 1020412935993872
280 1097893152242665
281 1181109565879103
282 1270476305359935
283 1366436588134096
284 1469464889000934
285 1580068945659291
286 1698792001204826
287 1826215409917779
288 1962961093596445
289 2109694259419186
290 2267126553938614
291 2436019043218776
292 2617185528564943
293 2811496336312050
294 3019881956963174
295 3243337057092907
296 3482925060762788
297 3739782557784461
298 4015124184212894
299 4310248126265016
300 4626541488035375
301 4965486187714831
302 5328665602836985
303 5717771061757006
304 6134608998863661
305 6581108934008165
306 7059331356851232
307 7571476358361748
308 8119893252047405
309 8707090094643485
310 9335744135924916
311 10008713365377990
312 10729048048411307
313 11500003313403817
314 12325053056739374
315 13207903851205594
316 14152510152649886
317 15163090976308959
318 16244146712137817
319 17400477416244291
320 18637202866510373
321 19959782805553795
322 21374038995177213
323 22886179250100915
324 24502821862057200
325 26231022090771004
326 28078301030911028
327 30052674971105319
328 32162687275559428
329 34417442947876870
330 36826643985044794
331 39400627621198720
332 42150407788466441
333 45087717552613343
334 48225055059382585
335 51575733131835611
336 55153930278359830
337 58974745734855438
338 63054258882617136
339 67409590387247296
340 72058968217648838
341 77021798656441444
342 82318739662483321
343 87971779857002643
344 94004323486677873
345 100441278235300684
346 107309149813514285
347 114636143397514853
348 122452268823893609
349 130789453614967500
350 139681664196646352
351 149165031641752996
352 159277986821438836
353 170061404981051207
354 181558756139994810
355 193816266383653700
356 206883090415164977
357 220811491097544331
358 235657032043581977
359 251478783204186856
360 268339535294762172
361 286306029354413339
362 305449201817569009
363 325844440158211845
364 347571856616887338
365 370716579887350553
366 395369059991942042
367 421625394163689560
368 449587674132336241
369 479364349147388701
370 511070614044314140
371 544828822151365343
372 580768917625112347
373 619028896913997260
374 659755299790175757
375 703103723509385461
376 749239371623310729
377 798337637178264531
378 850584714226907638
379 906178249690029690
380 965328036093525667
381 1028256737941071009
382 1095200666000297694
383 1166410599198636280
384 1242152647417424979
385 1322709170123297121
386 1408379751518895022
387 1499482224192908096
388 1596353758957241306
389 1699352020599824369
390 1808856382272304139
391 1925269217062497968
392 2049017267714892834
393 2180553085766837278
394 2320356562032325675
395 2468936548309568121
396 2626832562610055137
397 2794616600965940028
398 2972895057247549426
399 3162310741709354631
400 3363545025483195993
401 3577320111238233693
402 3804401422145335377
403 4045600137837514215
404 4301775879560696271
405 4573839534970458409
406 4862756256399702065
407 5169548633470645043
408 5495300032449617481
409 5841158138103741227
410 6208338701455992689
411 6598129484101383580
412 7011894441187311820
413 7451078145063417778
414 7917210442906330156
415 8411911392971995878
416 8936896484721376401
417 9493982134418399499
418 10085091508710193223
419 10712260680039314285
420 11377645109069253272
421 12083526509997214342
422 12832320106794133681
423 13626582274000320702
424 14469018627705472377
425 15362492573466456415
426 16310034309620299666
427 17314850356077955182
428 18380333620793896367
429 19510074001157650059
430 20707869602542334796
431 21977738585191315038
432 23323931643187320959
433 24750945203649606351
434 26263535364440462467
435 27866732573535533127
436 29565857153371436987
437 31366535687974631504
438 33274718284738146424
439 35296696822015032720
440 37439124209637032684
441 39709034674645519401
442 42113865202408398607
443 44661478160660529901
444 47360185130412289696
445 50218772084357441148
446 53246525952545605649
447 56453262601260255191
448 59849356389615753356
449 63445771345517394035
450 67254094002494721680
451 71286568075855034091
452 75556131035920934775
453 80076452624213942494
454 84861975521143875305
455 89927958227064329379
456 95290520223313531600
457 100966689640384232761
458 106974453516380022658
459 113332810720169185514
460 120061827804474789782
461 127182697879450266139
462 134717802608785953534
463 142690777618389355857
464 151126581436371911946
465 160051568079113694784
466 169493563621800013581
467 179481946884346774875
468 190047734384236684429
469 201223669927770851609
470 213044319008003336022
471 225546168180582139344
472 238767729850560265491
473 252749652657499522325
474 267534837678901285803
475 283168560929237389944
476 299698602391450725592
477 317175381830405295077
478 335652101944186767927
479 355184899118879834123
480 375833002101075487818
481 397658899203031696865
482 420728514371870310853
483 445111392480021804114
484 470880894552548297999
485 498114403305065470532
486 526893539435355549034
487 557304389463065976046
488 589437745578528930077
489 623389358005317476995
490 659260200800280418635
491 697156751613269976329
492 737191286024935086748
493 779482187491404639024
494 824154273534003575920
495 871339138879271600779
496 921175516744667159999
497 973809658995208307899
498 1029395736026906023101
499 1088096257712463818358
500 1150082516288400745402
501 1215535052160842513067
502 1284644144180400205016
503 1357610325387914114948
504 1434644925407470249503
505 1515970641223747143330
506 1601822137549739795339
507 1692446678129291419819
508 1788104789989485633274
509 1889070962019884834631
510 1995634379486265309833
511 2108099696742368472547
512 2226787849787604352796
513 2352036910509244527004
514 2484202985232790497558
515 2623661159464860220265
516 2770806491014772816426
517 2926055054448961942690
518 3089845039121784901547
519 3262637903284160620882
520 3444919587691542305825
521 3637201791279545597198
522 3840023311867428874640
523 4053951455750027307649
524 4279583519222346007337
525 4517548345425168061731
526 4768507960979617335583
527 5033159295898350012197
528 5312235990766732479325
529 5606510296244790827914
530 5916795069007545706754
531 6243945868695927417529
532 6588863161719120571304
533 6952494636628497718130
534 7335837636432563834534
535 7739941714466601422289
536 8165911319370347461059
537 8614908615322463368734
538 9088156445174229131592
539 9586941442850784791917
540 10112617302218406485855
541 10666608211083920826754
542 11250412457795506181644
543 11865606218688944864479
544 12513847536385894935514
545 13196880497511364227625
546 13916539619455613619243
547 14674754457541410129025
548 15473554442617169157739
549 16315073960099511522744
550 17201557683573683571371
551 18135366174446250393202
552 19118981760489356027939
553 20155014708174821026003
554 21246209702209217185140
555 22395452646973796162650
556 23605777807046623070063
557 24880375302190137487684
558 26222598973893244074943
559 27635974643007897811138
560 29124208776388596063325
561 30691197582103850286329
562 32341036555732433838546
563 34078030498283796341609
564 35906704028442469447379
565 37831812614764242211804
566 39858354151686977945559
567 41991581105346391018666
568 44237013258702575303628
569 46600451083340783460667
570 49087989768042530693237
571 51706033937735101998860
572 54461313094552385101361
573 57360897815459485713362
574 60412216745107699437360
575 63623074420298829285262
576 67001669965891308579665
577 70556616706210762426647
578 74296962734082523884935
579 78232212483074394945334
580 82372349353609274460322
581 86727859441217496977848
582 91309756419560672559268
583 96129607635976318844770
584 101199561475341736087101
585 106532376052479204076209
586 112141449299452916515256
587 118040850511685452956773
588 124245353422329288287692
589 130770470880547756387380
590 137632491207499725534446
591 144848516309455220288855
592 152436501634906189424128
593 160415298060186992305098
594 168804695795073036144915
595 177625470407417525233724
596 186899431064257495801919
597 196649471093988326094579
598 206899620983269815772324
599 217675103920205517564002
600 229002394004117325489730
601 240909277251546451722331
602 253424915526914073211137
603 266579913535392197512594
604 280406389026629726008719
605 294938046356306872375381
606 310210253563580201912934
607 326260123133946556214303
608 343126596616565457859740
609 360850533276673267986589
610 379474802977359784105075
611 399044383484065691661610
612 419606462399169205627364
613 441210543948213243307098
614 463908560839927848565336
615 487754991436943516919443
616 512806982490923528096519
617 539124477696118267695989
618 566770352333051974551693
619 595810554291668187483583
620 626314251765475974893309
621 658353987926981476325179
622 692005842915547926856342
623 727349603470871546214085
624 764468940567652998348676
625 803451595429007635591538
626 844389574300687331700164
627 887379352392019233004541
628 932522087415411156701163
629 979923843160873568442828
630 1029695823570339727552563
631 1081954617804047454504554
632 1136822456799027894240010
633 1194427481850055525757837
634 1254904025775797531085773
635 1318392907241109757365098
636 1385041738842292990678503
637 1455005249596622485735306
638 1528445622489744817342540
639 1605532847773089017863983
640 1686445092743990936826226
641 1771369088754449298291317
642 1860500536239863066223837
643 1954044528602535239667620
644 2052215995803158217269916
645 2155240168562544953591094
646 2263353064126800203768515
647 2376801994569210742700034
648 2495846098659711517246216
649 2620756898387615116157936
650 2751818881250041293468635
651 2889330109480899891013834
652 3033602857459414050247879
653 3184964278566562387146219
654 3343757102830830985572518
655 3510340366774039601837740
656 3685090176905921082079771
657 3868400508395576919807311
658 4060684040528881280826843
659 4262373030602808335122170
660 4473920228000287436502004
661 4695799830277139380361417
662 4928508483145444491761253
663 5172566326338829034095784
664 5428518087447540734933396
665 5696934225869783592884563
666 5978412129143354439621122
667 6273577364033309679873956
668 6583084984823912586879236
669 6907620901391883475543244
670 7247903309767699297844009
671 7604684187972438327329247
672 7978750860066958454066456
673 8370927631492227437665101
674 8782077498878157476857352
675 9213103937662278797106180
676 9664952771024197805879826
677 10138614123751767478608791
678 10635124464844536870792397
679 11155568742840872154590820
680 11701082617987833403595694
681 12272854795581731520573581
682 12872129465016430047823041
683 13500208849224848042007601
684 14158455869440081799130122
685 14848296930432992076355074
686 15571224831560480655755655
687 16328801809224664555060373
688 17122662716609140583578041
689 17954518346757194817074945
690 18826158905363059363899022
691 19739457639941162000735462
692 20696374632273956936824089
693 21698960761377693472841741
694 22749361844564028175312775
695 23849822964439617512446459
696 25002692990075120348668481
697 26210429300949938277866233
698 27475602722590411669116075
699 28800902683250644471053626
700 30189142601416301428331877
701 31643265514261215971192192
702 33166349957681563681030344
703 34761616109010826197529303
704 36432432203928374772111354
705 38182321239623960431259103
706 40014967976829765361860720
707 41934226253791735924748289
708 43944126625881154803088824
709 46048884345158172589636363
710 48252907694735664129968512
711 50560806693491422271919195
712 52977402187376859392301093
713 55507735344173490296572656
714 58157077569348485119830742
715 60930940861440246898998971
716 63835088626105583524729298
717 66875546968850784667934345
718 70058616487361370672023069
719 73390884585133007690003262
720 76879238329123172533500745
721 80530877875138353785020690
722 84353330485583403834772416
723 88354465165333445851133380
724 92542507942626323485227646
725 96926057822899123970258342
726 101514103444785231794326632
727 106316040468758468050216637
728 111341689730094268619495436
729 116601316189260648155481551
730 122105648714301598417213885
731 127865900731106870662504291
732 133893791779105405094064067
733 140201570011540162185943478
734 146802035681014090741932647
735 153708565652832450844028080
736 160935138990514325751275460
737 168496363659569889108422894
738 176407504397728222841742329
739 184684511801867322691631936
740 193344052683876637557897022
741 202403541750016779641356747
742 211881174660694831175412243
743 221795962529800270840928886
744 232167767925399483017236986
745 243017342436221870925394216
746 254366365870920971117923672
747 266237487160061550673919180
748 278654367033781281876403926
749 291641722550945594626327542
750 305225373558983690899505289
751 319432291166951634684708358
752 334290648317649342767977357
753 349829872548389514154895831
754 366080701033832547302193688
755 383075238007993575310589778
756 400847014666805649073716749
757 419431051656900015930433060
758 438863924260477691667846110
759 459183830390936971820846762
760 480430661518777177448657487
761 502646076652039977819658252
762 525873579500979039723434695
763 550158598962093167165192439
764 575548573062059763874615398
765 602093036508187878275641683
766 629843711998185552530032473
767 658854605448114047932696534
768 689182105304289660157567740
769 720885086111820403198970766
770 754025016519379568983829769
771 788666071907537378818535587
772 824875251835821766155370972
773 862722502511458782928757644
774 902280844491478198487033328
775 943626505838676685703494530
776 986839060960769948147007881
777 1032001575371856753749351334
778 1079200756625290364780666899
779 1128527111676995806961272986
780 1180075110949343647510099343
781 1233943359376881358283566634
782 1290234774726506818986169360
783 1349056773497082537336817209
784 1410521464716150913499988208
785 1474745851964101636554827162
786 1541852043970170325643510058
787 1611967474138857373666837751
788 1685225129379741734104463152
789 1761763788629394802159226440
790 1841728271470165862117216731
791 1925269697266787641770881865
792 2012545755259514566197282029
793 2103720986070538293080336115
794 2198967075098744093624296405
795 2298463158297793507645678873
796 2402396140852892196366429933
797 2510961029292197866038655021
798 2624361277591306602794012692
799 2742809147852122676088787955
800 2866526086160717732523731393
801 2995743114254001306541403543
802 3130701237650843300145345689
803 3271651870929480570282948640
804 3418857280861481295015669498
805 3572591048141518633316256854
806 3733138548481810413466492812
807 3900797453871980330111984519
808 4075878254837793991254778447
809 4258704804565493579334639450
810 4449614885794413649917124473
811 4648960801417257348945424250
812 4857109989764988304869564990
813 5074445665593622443673246564
814 5301367487831586343430632240
815 5538292255188526705444808875
816 5785654630771892851415432738
817 6043907896904053573780896462
818 6313524741380354518736400042
819 6594998076459479254314273553
820 6888841891929815509153465590
821 7195592143649045549003001653
822 7515807679011561233463662909
823 7850071200857031879647419195
824 8198990271393806445674074084
825 8563198357775178643247575190
826 8943355921032693757259558578
827 9340151550138451068534203462
828 9754303143040779265337654967
829 10186559136591877499944454888
830 10637699787362395109392562417
831 11108538505419129478852639381
832 11599923243225571658885685677
833 12112737941910779746394677304
834 12647904037243414595711891242
835 13206382027741494119325006224
836 13789173107444998467762069425
837 14397320865980878693863135905
838 15031913058655476632352945009
839 15694083449417758118242586144
840 16385013729651926995643767061
841 17105935515876259696611638379
842 17858132429547004807583841236
843 18642942262295288308698203933
844 19461759230057977636997084634
845 20316036319700354904936428703
846 21207287731873544326460502731
847 22137091423998788848249185904
848 23107091757424668402415901536
849 24119002252965971400883276577
850 25174608459200587919400185515
851 26275770938073539944152519371
852 27424428372539955316132772547
853 28622600801166750131741544171
854 29872392984807002777801646356
855 31175997910665722379415053758
856 32535700439286895489434932070
857 33953881100209498093718167228
858 35433020042270049263520027043
859 36975701144765982925420558536
860 38584616295938860536157650513
861 40262569845494005845833407314
862 42012483238138966989297954129
863 43837399835397599554388663353
864 45740489933245667626455968672
865 47725055983411736764768961610
866 49794538026495308890755312443
867 51952519345377981412561170191
868 54202732347737792956491424985
869 56549064686822318588414386525
870 58995565629999423315047382135
871 61546452684979191511005118932
872 64206118493988294689339597367
873 66979138006584964789472788725
874 69870275942223074130113287537
875 72884494554108277071715395540
876 76026961706345541062117767056
877 79303059276848181033640276393
878 82718391898965999600873507347
879 86278796055301103156277014939
880 89990349537707993476181644520
881 93859381288020587723128478107
882 97892481634621682807062317095
883 102096512940561636972805635849
884 106478620679545477112901020194
885 111046244956748882958135260454
886 115807132492086376574358496970
887 120769349084240855067211444395
888 125941292574482248700872655486
889 131331706330045143866565113837
890 136949693267604057682159311619
891 142804730438189280951543820974
892 148906684195717818836513526200
893 155265825972174665217015429335
894 161892848683380614570942891411
895 168798883790213514755395004017
896 175995519041114378791276376949
897 183494816922717790083166869018
898 191309333846488650345565166403
899 199452140100326752401985232763
900 207936840595229512454784034537
901 216777596438269723372047278137
902 225989147364354317178151068640
903 235586835060492781332917536355
904 245586627417610175372753075340
905 256005143746292484002959555940
906 266859680994265550583663443310
907 278168241004869987258225268075
908 289949558857309182636330295044
909 302223132331028171833296135183
910 315009252538216752697352955731
911 328329035770124428598491629197
912 342204456604643617147376200057
913 356658382324446565207638757450
914 371714608696857675782166423579
915 387397897168620446414774310109
916 403734013530764859819414524930
917 420749768110901385099963101108
918 438473057552479941054451495669
919 456932908242840154298756838669
920 476159521454251558915335840114
921 496184320264614847390292047387
922 517039998327054600857572829719
923 538760570560285758400852918819
924 561381425834401044350838078767
925 584939381729586884268903917210
926 609472741448241243390694248019
927 635021352964056257097751853431
928 661626670494826918203583618003
929 689331818389061470947383033796
930 718181657519922915613559048851
931 748222854283604570652504510557
932 779503952302948228024684379789
933 812075446940971458820051188080
934 845989862732965171472286442915
935 881301833849962290953296249019
936 918068187710689966163254701066
937 956348031863579529167156150424
938 996202844265035185784602441619
939 1037696567084977320497756076149
940 1080895704175662067353821253787
941 1125869422344946151299912015032
942 1172689656580545142932132025105
943 1221431219377400686808092410589
944 1272171914326045487827152424348
945 1324992654125860345209147953799
946 1379977583193336639447937922081
947 1437214205041903574854821362588
948 1496793514616586569298469337924
949 1558810135773705868545476354461
950 1623362464103023692647719895052
951 1690552815297234259564337600789
952 1760487579281443840172647347673
953 1833277380323323720994009322268
954 1909037243352976862357927743441
955 1987886766730211412641566997298
956 2069950301705886100607500868913
957 2155357138833318553360520245713
958 2244241701595406441563883587041
959 2336743747523122778253606957540
960 2433008577091455608917350869965
961 2533187250689638866635886433870
962 2637436813973695224696866020436
963 2745920531920923187774304104177
964 2858808131917986917055388672242
965 2976276056226732486902329820012
966 3098507724184809892063828375805
967 3225693804511594227611310136537
968 3358032498103807765408407976606
969 3495729831719693012499723482616
970 3638999962965551796781623311654
971 3788065497013976366644705542193
972 3943157815499214524884022391441
973 4104517418051798068729189529026
974 4272394276951864950932946422320
975 4447048205398573560610707295318
976 4628749239911618246756470833521
977 4817778037400144449742516381392
978 5014426287454397605143741179678
979 5218997140436186773900211180363
980 5431805651965752729725951552065
981 5653179244424962297602969779888
982 5883458186119881802968030198830
983 6122996088769756081392053848791
984 6372160424014314112468356205166
985 6631333059657101105709230629232
986 6900910816389260741850019702953
987 7181306045765931422998508858926
988 7472947230236152974537210816634
989 7776279606056958170463989393463
990 8091765809953237511293434439984
991 8419886550416978252539203287398
992 8761141304572662662851147312287
993 9116049041570048731886737112208
994 9485148973501226516470265049970
995 9869001334875809268288349233994
996 10268188191726485693400335649933
997 10683314281456890587101229590801
998 11115007884584932883874433544842
999 11563921729577449586669464768947
1000 12030733932016310999302914644946