0 0
1 0
2 1
3 1
4 2
5 3
6 5
7 7
8 10
9 14
10 20
11 27
12 37
13 49
14 66
15 86
16 113
17 146
18 190
19 242
20 310
21 392
22 497
23 623
24 782
25 973
26 1212
27 1498
28 1851
29 2274
30 2793
31 3411
32 4163
33 5059
34 6142
35 7427
36 8972
37 10801
38 12989
39 15572
40 18646
41 22267
42 26561
43 31602
44 37556
45 44533
46 52743
47 62338
48 73593
49 86716
50 102064
51 119918
52 140736
53 164903
54 193011
55 225566
56 263333
57 306993
58 357521
59 415814
60 483129
61 560641
62 649960
63 752622
64 870677
65 1006132
66 1161604
67 1339677
68 1543687
69 1776980
70 2043780
71 2348384
72 2696156
73 3092594
74 3544485
75 4058848
76 4644241
77 5309608
78 6065739
79 6923959
80 7897846
81 9001747
82 10252687
83 11668765
84 13271328
85 15083146
86 17130918
87 19443237
88 22053415
89 24997285
90 28316370
91 32055418
92 36266093
93 41004230
94 46333953
95 52324747
96 59056128
97 66614382
98 75097925
99 84613725
100 95283359
101 107239203
102 120631254
103 135622955
104 152399071
105 171161152
106 192136373
107 215572796
108 241749411
109 270970998
110 303579637
111 339949238
112 380498578
113 425685678
114 476022556
115 532069294
116 594451027
117 663851774
118 741033636
119 826830709
120 922170954
121 1028069997
122 1145656219
123 1276164654
124 1420965540
125 1581558720
126 1759606135
127 1956926660
128 2175533518
129 2417629854
130 2685651311
131 2982263029
132 3310408366
133 3673307317
134 4074512536
135 4517909823
136 5007782198
137 5548813432
138 6146161389
139 6805464937
140 7532928545
141 8335333558
142 9220135073
143 10195479211
144 11270314440
145 12454415595
146 13758512241
147 15194321234
148 16774694260
149 18513661361
150 20426600638
151 22530294442
152 24843125486
153 27385148539
154 30178316087
155 33246569505
156 36616099292
157 40315458727
158 44375864634
159 48831338330
160 53719052545
161 59079505752
162 64956922535
163 71399466780
164 78459704991
165 86194865956
166 94667375548
167 103945172648
168 114102327226
169 125219421613
170 137384265759
171 150692356248
172 165247702967
173 181163380983
174 198562486204
175 217578795417
176 238357872709
177 261057857148
178 285850741772
179 312923312758
180 342478628789
181 374737136247
182 409938381443
183 448342332806
184 490231360871
185 535911804332
186 585716259725
187 640005430863
188 699170778533
189 763636701449
190 833863599420
191 910350443224
192 993638316401
193 1084313436127
194 1183011249309
195 1290419979618
196 1407285361444
197 1534414801252
198 1672682847961
199 1823036066020
200 1986499358230
201 2164181666225
202 2357283273065
203 2567102466808
204 2795043974057
205 3042626737181
206 3311493653526
207 3603420644332
208 3920327895383
209 4264290424439
210 4637551051529
211 5042532696911
212 5481853346425
213 5958340351357
214 6475047685202
215 7035272560447
216 7642575323118
217 8300798740512
218 9014090932118
219 9786927741019
220 10624139151255
221 11530935219155
222 12512936497419
223 13576204064666
224 14727274556605
225 15973194917134
226 17321562713039
227 18780566325055
228 20359031328722
229 22066466937811
230 23913119348587
231 25910025374084
232 28069073768483
233 30403067129724
234 32925792372436
235 35652092120540
236 38597945669677
237 41780551274844
238 45218419119376
239 48931466108724
240 52941122589176
241 57270441474229
242 61944220705169
243 66989128806555
244 72433845348672
245 78309205329627
246 84648360225397
247 91486943919174
248 98863257294121
249 106818458823410
250 115396776053836
251 124645724412543
252 134616349409697
253 145363477695104
254 156945994342394
255 169427130763551
256 182874782022904
257 197361836861762
258 212966540683460
259 229772873645703
260 247870965742260
261 267357529754616
262 288336335710235
263 310918706425387
264 335224059632175
265 361380474876506
266 389525312739187
267 419805863065542
268 452380051961602
269 487417182694402
270 525098742603510
271 565619249519999
272 609187172382474
273 656025897775021
274 706374779857052
275 760490243595778
276 818646981735067
277 881139213487980
278 948282048644352
279 1020412923021273
280 1097893152456114
281 1181109569160913
282 1270476291387940
283 1366436588007316
284 1469464893062171
285 1580068929531253
286 1698792001804765
287 1826215413696334
288 1962961076249695
289 2109694259637610
290 2267126558628187
291 2436019023241565
292 2617185529704191
293 2811496340618673
294 3019881935500995
295 3243337057795974
296 3482925066150782
297 3739782533097967
298 4015124186097030
299 4310248131133290
300 4626541461530177
301 4965486189130200
302 5328665608955017
303 5717771031335221
304 6134609001773796
305 6581108939414254
306 7059331324242740
307 7571476360738980
308 8119893258923029
309 8707090057269933
310 9335744140174361
311 10008713371329583
312 10729048008373348
313 11500003317085346
314 12325053064390141
315 13207903805378874
316 14152510158701948
317 15163090982721167
318 16244146663115651
319 17400477421671388
320 18637202874879430
321 19959782749545640
322 21374039003548443
323 22886179256869755
324 24502821802193240
325 26231022098466166
326 28078301039949787
327 30052674902788869
328 32162687286937682
329 34417442954824019
330 36826643912100015
331 39400627631875801
332 42150407798002223
333 45087717469491145
334 48225055074623020
335 51575733138671944
336 55153930189710199
337 58974745749357200
338 63054258892410676
339 67409590286349994
340 72058968237796864
341 77021798662782558
342 82318739554982446
343 87971779876391940
344 94004323496376370
345 100441278113091302
346 107309149839882065
347 114636143402804330
348 122452268693810773
349 130789453640582245
350 139681664205717336
351 149165031494064973
352 159277986855633016
353 170061404984502316
354 181558755982974841
355 193816266417099786
356 206883090422879924
357 220811490919469394
358 235657032087527265
359 251478783204819624
360 268339535105609947
361 286306029397680560
362 305449201822952043
363 325844439943910048
364 347571856673023437
365 370716579883781819
366 395369059764581907
367 421625394219217805
368 449587674134015894
369 479364348890098971
370 511070614115498789
371 544828822141857158
372 580768917352403386
373 619028896984681949
374 659755299786483915
375 703103723201044046
376 749239371713072893
377 798337637160565588
378 850584713900420592
379 906178249779495260
380 965328036082153098
381 1028256737572313785
382 1095200666112868479
383 1166410599169829599
384 1242152647027396400
385 1322709170235778087
386 1408379751496978306
387 1499482223752741187
388 1596353759097684853
389 1699352020556295505
390 1808856381807204423
391 1925269217203188978
392 2049017267678726593
393 2180553085242406849
394 2320356562206788935
395 2468936548246657095
396 2626832562056501613
397 2794616601141035614
398 2972895057192452118
399 3162310741085699958
400 3363545025698964905
401 3577320111150156951
402 3804401421487713028
403 4045600138054433470
404 4301775879480791364
405 4573839534230118797
406 4862756256665494627
407 5169548633350202045
408 5495300031669753174
409 5841158138371323207
410 6208338701343941504
411 6598129483224046135
412 7011894441513529154
413 7451078144901648657
414 7917210441983121567
415 8411911393300775754
416 8936896484567997687
417 9493982133380560809
418 10085091509109124038
419 10712260679825155004
420 11377645107978274030
421 12083526510399608076
422 12832320106588180216
423 13626582272774652609
424 14469018628191675328
425 15362492573186346394
426 16310034308333182605
427 17314850356568790583
428 18380333620521385288
429 19510073999712547155
430 20707869603133059005
431 21977738584828555646
432 23323931641671395577
433 24750945204246240812
434 26263535364084318335
435 27866732571834489733
436 29565857154086910586
437 31366535687508994262
438 33274718282955543138
439 35296696822737974338
440 37439124209176423689
441 39709034672646308574
442 42113865203272523819
443 44661478160067287285
444 47360185128319403266
445 50218772085230796425
446 53246525951955124790
447 56453262598914280584
448 59849356390656452911
449 63445771344766626250
450 67254094000041376472
451 71286568076907025289
452 75556131035169785520
453 80076452621465176111
454 84861975522393894682
455 89927958226119909551
456 95290520220441972408
457 100966689641647897744
458 106974453515430930110
459 113332810716953183403
460 120061827805972476935
461 127182697878268590363
462 134717802605429814419
463 142690777619903329741
464 151126581435179847087
465 160051568075356521116
466 169493563623590070029
467 179481946882875373580
468 190047734380319897611
469 201223669929580060725
470 213044319006514289722
471 225546168176198897987
472 238767729852694651726
473 252749652655675613100
474 267534837674336562975
475 283168560931394261794
476 299698602389599787838
477 317175381825298619532
478 335652101946726064978
479 355184899116628112701
480 375833002095763134994
481 397658899205596985305
482 420728514369579673903
483 445111392474080516625
484 470880894555562555002
485 498114403302296224257
486 526893539429181544859
487 557304389466109963322
488 589437745575705932027
489 623389357998414225548
490 659260200803850999792
491 697156751609876243889
492 737191286017769058224
493 779482187495008986845
494 824154273530537513590
495 871339138871261151257
496 921175516748888083872
497 973809658991062716164
498 1029395736018599697176
499 1088096257716722498340
500 1150082516284160195228
501 1215535052151559153695
502 1284644144185379730847
503 1357610325382866080667
504 1434644925397854279201
505 1515970641228768672736
506 1601822137544568870284
507 1692446678118545987920
508 1788104789995349063877
509 1889070962013755559680
510 1995634379475147217445
511 2108099696748277812080
512 2226787849781318011225
513 2352036910496822339102
514 2484202985239681487827
515 2623661159457438580930
516 2770806491001933879934
517 2926055054455902271162
518 3089845039114165090006
519 3262637903269816950747
520 3444919587699626163784
521 3637201791270582538704
522 3840023311852620267520
523 4053951455758163686735
524 4279583519213134698092
525 4517548345408625087711
526 4768507960989083934055
527 5033159295887551653122
528 5312235990749672570529
529 5606510296254311763885
530 5916795068996439139970
531 6243945868676870012668
532 6588863161730186941949
533 6952494636615519067663
534 7335837636412932897259
535 7739941714477722681159
536 8165911319356988623191
537 8614908615300533712562
538 9088156445187144157315
539 9586941442835220236422
540 10112617302195842515986
541 10666608211096889261012
542 11250412457779475207451
543 11865606218663738240613
544 12513847536400942542792
545 13196880497492737860072
546 13916539619429707920819
547 14674754457556506539565
548 15473554442597974138261
549 16315073960070569806055
550 17201557683591187210221
551 18135366174424005850702
552 19118981760459645860075
553 20155014708192365723308
554 21246209702186282092097
555 22395452646940600715723
556 23605777807066952421208
557 24880375302163622912433
558 26222598973859207708065
559 27635974643028255112998
560 29124208776361246426379
561 30691197582065816781556
562 32341036555756007872574
563 34078030498252251417850
564 35906704028403518436778
565 37831812614787824681679
566 39858354151654428208784
567 41991581105302858027092
568 44237013258729870925770
569 46600451083303321513767
570 49087989767998000853332
571 51706033937762379463783
572 54461313094513716925128
573 57360897815409708683792
574 60412216745139257498220
575 63623074420254416476082
576 67001669965840454287106
577 70556616706242264324339
578 74296962734036669341681
579 78232212483017534729404
580 82372349353645706688557
581 86727859441164932623949
582 91309756419502652632346
583 96129607636012645555951
584 101199561475287452352028
585 106532376052414315186600
586 112141449299494917036082
587 118040850511623339342714
588 124245353422263158954416
589 130770470880589585375202
590 137632491207435568010865
591 144848516309381240761484
592 152436501634954540406115
593 160415298060113708611731
594 168804695794997737313630
595 177625470407465619837187
596 186899431064181789240714
597 196649471093904060601627
598 206899620983325400923391
599 217675103920119184694145
600 229002394004031667131562
601 240909277251601672241748
602 253424915526824874489771
603 266579913535296304288192
604 280406389026693541560050
605 294938046356205313096776
606 310210253563482851100127
607 326260123134009868989265
608 343126596616460516696779
609 360850533276564242872666
610 379474802977432949592235
611 399044383483946388097474
612 419606462399058669164670
613 441210543948285732223797
614 463908560839804564190105
615 487754991436819671253030
616 512806982491007302968677
617 539124477695978309576253
618 566770352332926580196422
619 595810554291751070536921
620 626314251765331338721889
621 658353987926840920106046
622 692005842915643724379123
623 727349603470707571980529
624 764468940567510879673455
625 803451595429102271923234
626 844389574300517873819582
627 887379352391859849536137
628 932522087415520559163978
629 979923843160681705075923
630 1029695823570178794275403
631 1081954617804155366629294
632 1136822456798829611977156
633 1194427481849874945721794
634 1254904025775922313547734
635 1318392907240885536763820
636 1385041738842110913273942
637 1455005249596745370696950
638 1528445622489513098689343
639 1605532847772884596485287
640 1686445092744133077862572
641 1771369088754187581247061
642 1860500536239657243811286
643 1954044528602674988370221
644 2052215995802887756600106
645 2155240168562313731635297
646 2263353064126961916680941
647 2376801994568905615360381
648 2495846098659479051064264
649 2620756898387773834663385
650 2751818881249725985263201
651 2889330109480638569338615
652 3033602857459597799856667
653 3184964278566207054052926
654 3343757102830568648294100
655 3510340366774219626854515
656 3685090176905553914495426
657 3868400508395281816529572
658 4060684040529089811511635
659 4262373030602394994658054
660 4473920227999991634336049
661 4695799830277343305104902
662 4928508483145017415245470
663 5172566326338496045246453
664 5428518087447777097123025
665 5696934225869303294400066
666 5978412129143021176660971
667 6273577364033540376120891
668 6583084984823416367768699
669 6907620901391508030684652
670 7247903309767966876854621
671 7604684187971880810447709
672 7978750860066583292492655
673 8370927631492488076573156
674 8782077498877581534954826
675 9213103937661855809565059
676 9664952771024500351037182
677 10138614123751120995740185
678 10635124464844114878958234
679 11155568742841166237568673
680 11701082617987165623774441
681 12272854795581255330039077
682 12872129465016771712525869
683 13500208849224099143518756
684 14158455869439607508786797
685 14848296930433323458869286
686 15571224831559707174845247
687 16328801809224128874681454
688 17122662716609525949088990
689 17954518346756328129024744
690 18826158905362526710229727
691 19739457639941534919432161
692 20696374632273061911292693
693 21698960761377091311132804
694 22749361844564462300548659
695 23849822964438615466076483
696 25002692990074522611210746
697 26210429300950357384510324
698 27475602722589376993615487
699 28800902683249968073115380
700 30189142601416789879539725
701 31643265514260058507838230
702 33166349957680893422281326
703 34761616109011296579109726
704 36432432203927179785717060
705 38182321239623201190241563
706 40014967976830314258194669
707 41934226253790400160319732
708 43944126625880403790553542
709 46048884345158699808458435
710 48252907694734285262788295
711 50560806693490570646818806
712 52977402187377475447172767
713 55507735344171950138548265
714 58157077569347644255467770
715 60930940861440837016838489
716 63835088626103993911558154
717 66875546968849830085926032
718 70058616487362061237586099
719 73390884585131233412485980
720 76879238329122231766081397
721 80530877875139013392917681
722 84353330485581572874857753
723 88354465165332376606184572
724 92542507942627096595138500
725 96926057822897081733218875
726 101514103444784180025401951
727 106316040468759204295677896
728 111341689730092161485478986
729 116601316189259451289954445
730 122105648714302462837519095
731 127865900731104521961748385
732 133893791779104230080154757
733 140201570011540982802085211
734 146802035681011667815860536
735 153708565652831112033981517
736 160935138990515291014468389
737 168496363659567190168127169
738 176407504397726911089252427
739 184684511801868236012381768
740 193344052683873853814041992
741 202403541750015283047163873
742 211881174660695907633925630
743 221795962529797171925467812
744 232167767925398019655514911
745 243017342436222885916543936
746 254366365870917775402606905
747 266237487160059878801774058
748 278654367033782480744510806
749 291641722550942039257484785
750 305225373558982059563888277
751 319432291166952760943568530
752 334290648317645677016358800
753 349829872548387647692485872
754 366080701033833880689204868
755 383075238007989499406754956
756 400847014666803831752957239
757 419431051656901263701254198
758 438863924260473490012135163
759 459183830390934889453374127
760 480430661518778658401752606
761 502646076652035308706549693
762 525873579500977016616460179
763 550158598962094547338400941
764 575548573062054951632032045
765 602093036508185556500797944
766 629843711998187195057772139
767 658854605448108703245033669
768 689182105304287409515682100
769 720885086111821927285978563
770 754025016519374061539012919
771 788666071907534791732878277
772 824875251835823585246755322
773 862722502511452669384008339
774 902280844491475696422277607
775 943626505838678365820690180
776 986839060960763649685286324
777 1032001575371853872811079824
778 1079200756625292376433262527
779 1128527111676988818953218139
780 1180075110949340867815741705
781 1233943359376883207107076384
782 1290234774726499621066939729
783 1349056773497079331134362383
784 1410521464716153134692849305
785 1474745851964093654615547231
786 1541852043970167239586312161
787 1611967474138859404354911936
788 1685225129379733514094036061
789 1761763788629391236110130865
790 1841728271470168310812182922
791 1925269697266778530826910361
792 2012545755259511142279757939
793 2103720986070540519205749814
794 2198967075098734712886734939
795 2298463158297789543720985032
796 2402396140852894891466543967
797 2510961029292187473442097566
798 2624361277591302806539384785
799 2742809147852125111490713322
800 2866526086160707034443096536
801 2995743114253996902942537090
802 3130701237650846261415731925
803 3271651870929468723648387078
804 3418857280861477088681193790
805 3572591048141521291960189515
806 3733138548481798221217911552
807 3900797453871975440896541599
808 4075878254837797239255661362
809 4258704804565480084067949177
810 4449614885794408992222605768
811 4648960801417260244738369569
812 4857109989764974418889650337
813 5074445665593617018398320888
814 5301367487831589899371459786
815 5538292255188511342007436571
816 5785654630771887697258497283
817 6043907896904056720284501353
818 6313524741380338713964117041
819 6594998076459473237599976265
820 6888841891929819394715899058
821 7195592143649028069879405152
822 7515807679011555533543598553
823 7850071200857035289815221786
824 8198990271393788468402832910
825 8563198357775171974313747540
826 8943355921032697994415593150
827 9340151550138431194744293425
828 9754303143040772965858698738
829 10186559136591881185719366489
830 10637699787362374673765851572
831 11108538505419122091072707987
832 11599923243225576269540370773
833 12112737941910757163731259864
834 12647904037243407637973185275
835 13206382027741498091176312916
836 13789173107444975251914898250
837 14397320865980870514146225772
838 15031913058655481638070586170
839 15694083449417732472952600550
840 16385013729651919315626553903
841 17105935515876263963032167088
842 17858132429546978449201954040
843 18642942262295279256987750445
844 19461759230057983058514364692
845 20316036319700325798947978470
846 21207287731873535854431146036
847 22137091423998793415019286025
848 23107091757424638493951397296
849 24119002252965961389469839340
850 25174608459200593776095715796
851 26275770938073506929782363962
852 27424428372539945976102494714
853 28622600801166755001213723835
854 29872392984806968861002167150
855 31175997910665711312250758629
856 32535700439286901798700622702
857 33953881100209460667674100566
858 35433020042270038972801446267
859 36975701144765988095551232465
860 38584616295938822096005170732
861 40262569845493993617808589694
862 42012483238138973765711468209
863 43837399835397557151181689888
864 45740489933245656295108230276
865 47725055983411742227988940364
866 49794538026495265348750612249
867 51952519345377967908657036331
868 54202732347737800210892356482
869 56549064686822270572983117125
870 58995565629999410845245249221
871 61546452684979197252970252660
872 64206118493988245395946543733
873 66979138006584949883873538888
874 69870275942223081868526029050
875 72884494554108222731115464923
876 76026961706345527347594704821
877 79303059276848187031663760032
878 82718391898965943827138763547
879 86278796055301086711465652670
880 89990349537708001698370213912
881 93859381288020526257473120564
882 97892481634621667732376275773
883 102096512940561643194065828091
884 106478620679545414041204857990
885 111046244956748864823699785120
886 115807132492086385272396343388
887 120769349084240785579379946297
888 125941292574482232140687671573
889 131331706330045150266097575638
890 136949693267603986395677650558
891 142804730438189260963207553359
892 148906684195717827992813143566
893 155265825972174586701317622868
894 161892848683380596389328909468
895 168798883790213521273503261147
896 175995519041114298262612289035
897 183494816922717768061404273344
898 191309333846488659930765021359
899 199452140100326663731568643073
900 207936840595229492504233306945
901 216777596438269729931676719803
902 225989147364354226256328129418
903 235586835060492757081676711112
904 245586627417610185343204061592
905 256005143746292383915625558204
906 266859680994265528704374966390
907 278168241004869993761543530205
908 289949558857309080032590923875
909 302223132331028145138518806650
910 315009252538216762992077236392
911 328329035770124315681216484401
912 342204456604643593166154197584
913 356658382324446571532336514412
914 371714608696857560054084016710
915 387397897168620417042739947227
916 403734013530764870356760850287
917 420749768110901257771436313114
918 438473057552479914783735391765
919 456932908242840160293664765633
920 476159521454251428449155821804
921 496184320264614815085923042697
922 517039998327054611531178692256
923 538760570560285614892201928659
924 561381425834401015587597535976
925 584939381729586889748954135769
926 609472741448241096381760883829
927 635021352964056221582722804706
928 661626670494826928877707482912
929 689331818389061309280790712758
930 718181657519922884138092885125
931 748222854283604575392936568920
932 779503952302948062455752164291
933 812075446940971419790600687264
934 845989862732965181976582851237
935 881301833849962108918172251681
936 918068187710689931737879063981
937 956348031863579532896982015366
938 996202844265034999401543635263
939 1037696567084977277622582091010
940 1080895704175662077477097681300
941 1125869422344945946426492604260
942 1172689656580545105299911876909
943 1221431219377400689202287030772
944 1272171914326045278112412396250
945 1324992654125860298126773467643
946 1379977583193336648931110320432
947 1437214205041903344384996933303
948 1496793514616586528181506509934
949 1558810135773705869216531417970
950 1623362464103023456790431377003
951 1690552815297234207880482591715
952 1760487579281443848700666076840
953 1833277380323323461848649434497
954 1909037243352976817456052905899
955 1987886766730211411129286213959
956 2069950301705885835470684805039
957 2155357138833318496645163569622
958 2244241701595406448756246293607
959 2336743747523122486996827592339
960 2433008577091455559906146902916
961 2533187250689638862396162481451
962 2637436813973694926780915237098
963 2745920531920923125558356395379
964 2858808131917986922455670422595
965 2976276056226732159701361228603
966 3098507724184809838592937106397
967 3225693804511594220003081475580
968 3358032498103807430810629474061
969 3495729831719692944271627222155
970 3638999962965551799845091399647
971 3788065497013975999225832023244
972 3943157815499214466575034483217
973 4104517418051798056999685987878
974 4272394276951864575302865470265
975 4447048205398573485812462798649
976 4628749239911618246836197601280
977 4817778037400144037342062023561
978 5014426287454397541588084311629
979 5218997140436186757168107043745
980 5431805651965752308215752079443
981 5653179244424962215625874861775
982 5883458186119881799298949808463
983 6122996088769755618702270237199
984 6372160424014314043224848431797
985 6631333059657101082945591894564
986 6900910816389260269059601626914
987 7181306045765931333178564701034
988 7472947230236152966218002189763
989 7776279606056957651572963293736
990 8091765809953237435885886484806
991 8419886550416978222545574601100
992 8761141304572662132767573920603
993 9116049041570048633499518007202
994 9485148973501226502442605372510
995 9869001334875808686613820336945
996 10268188191726485611314504174264
997 10683314281456890548485226621322
998 11115007884584932289804712473511
999 11563921729577449478924425722545
1000 12030733932016310978328193630340