0 0
1 0
2 1
3 1
4 2
5 2
6 5
7 5
8 8
9 11
10 17
11 20
12 29
13 37
14 51
15 65
16 85
17 106
18 141
19 175
20 223
21 277
22 351
23 432
24 540
25 663
26 820
27 999
28 1226
29 1489
30 1817
31 2192
32 2654
33 3191
34 3847
35 4603
36 5517
37 6578
38 7853
39 9327
40 11084
41 13120
42 15533
43 18328
44 21621
45 25430
46 29905
47 35071
48 41111
49 48080
50 56206
51 65554
52 76420
53 88918
54 103394
55 120015
56 139214
57 161222
58 186593
59 215632
60 249006
61 287165
62 330938
63 380888
64 438075
65 503255
66 577713
67 662459
68 759105
69 868933
70 993978
71 1135894
72 1297168
73 1479984
74 1687435
75 1922241
76 2188293
77 2489083
78 2829378
79 3213635
80 3647768
81 4137365
82 4689803
83 5312116
84 6013337
85 6802385
86 7690431
87 8688516
88 9810514
89 11070228
90 12484640
91 14071005
92 15850240
93 17843669
94 20077094
95 22576927
96 25374695
97 28503186
98 32001080
99 35908619
100 40273283
101 45144668
102 50580648
103 56642270
104 63400231
105 70929216
106 79315619
107 88650853
108 99039931
109 110594774
110 123443160
111 137721350
112 153584795
113 171199561
114 190753998
115 212450250
116 236516666
117 263198449
118 292772299
119 325535550
120 361822429
121 401993316
122 446451934
123 495633663
124 550025840
125 610154372
126 676606082
127 750015577
128 831089270
129 920591187
130 1019371045
131 1128348125
132 1248542423
133 1381059141
134 1527122100
135 1688057247
136 1865331777
137 2060535596
138 2275424679
139 2511903551
140 2772072495
141 3058209321
142 3372824045
143 3718638809
144 4098648894
145 4516104668
146 4974578101
147 5477944593
148 6030460255
149 6636742400
150 7301855797
151 8031296730
152 8831087917
153 9707763942
154 10668480745
155 11721001164
156 12873817897
157 14136145223
158 15518054911
159 17030471643
160 18685330103
161 20495573194
162 22475328518
163 24639917142
164 27006050107
165 29591845505
166 32417054687
167 35503086910
168 38873264870
169 42552866915
170 46569412655
171 50952720875
172 55735238452
173 60952114308
174 66641571311
175 72845009171
176 79607422605
177 86977532152
178 95008264938
179 103756915160
180 113285689813
181 123661916131
182 134958656795
183 147254965187
184 160636592702
185 175196296388
186 191034642730
187 208260390264
188 226991399642
189 247355095419
190 269489511233
191 293543839622
192 319679622444
193 348071419900
194 378908160751
195 412393939923
196 448749569251
197 488213519387
198 531043687657
199 577518526684
200 627939054875
201 682630190260
202 741943057191
203 806256552017
204 875979975917
205 951554891653
206 1033458121099
207 1122203924799
208 1218347440610
209 1322487229567
210 1435269202175
211 1557389613700
212 1689599539892
213 1832708375363
214 1987588963327
215 2155181665755
216 2336500223508
217 2532636516035
218 2744767244870
219 2974159468687
220 3222178260009
221 3490293123551
222 3780086741751
223 4093262444403
224 4431654187026
225 4797235207405
226 5192129447054
227 5618621559464
228 6079169955544
229 6576418404902
230 7113210919405
231 7692605157053
232 8317889446196
233 8992598243611
234 9720531570269
235 10505772870641
236 11352711184206
237 12266061725776
238 13250891223448
239 14312641598083
240 15457158878385
241 16690720481439
242 18020068183045
243 19452439481893
244 20995605247445
245 22657905733687
246 24448293513521
247 26376374866047
248 28452458709655
249 30687604085530
250 33093675980735
251 35683399747798
252 38470424723682
253 41469386633741
254 44695980050476
255 48167029854351
256 51900573820853
257 55915944377849
258 60233862651570
259 64876532034553
260 69867745225675
261 75232991192798
262 80999577056361
263 87196750266866
264 93855837287491
265 101010383173862
266 108696309291749
267 116952072621737
268 125818845180016
269 135340695708772
270 145564793647812
271 156541616364673
272 168325180933532
273 180973280298545
274 194547746689148
275 209114720587305
276 224744949924092
277 241514096392250
278 259503075136705
279 278798403343185
280 299492585926389
281 321684512006862
282 345479892588424
283 370991711448792
284 398340721617979
285 427655957821514
286 459075299640597
287 492746053609373
288 528825591707248
289 567482012468885
290 608894864604243
291 653255897414695
292 700769880820620
293 751655456744167
294 806146067969703
295 864490923882087
296 926956052223231
297 993825393976364
298 1065401994113482
299 1142009242346922
300 1223992220679515
301 1311719109139181
302 1405582710237211
303 1506002040865519
304 1613424056598938
305 1728325453663831
306 1851214618517154
307 1982633667106660
308 2123160648414342
309 2273411851243480
310 2434044294315139
311 2605758334660034
312 2789300480498514
313 2985466339914788
314 3195103797310260
315 3419116345387259
316 3658466671403198
317 3914180420898713
318 4187350245195029
319 4479140051684202
320 4790789570439023
321 5123619152126218
322 5479034919121209
323 5858534179690728
324 6263711236481944
325 6696263494489314
326 7157998008772197
327 7650838372607680
328 8176832096763729
329 8738158374872415
330 9337136397175470
331 9976234102461767
332 10658077541798476
333 11385460738976566
334 12161356234247738
335 12988926190075558
336 13871534259897616
337 14812758093066634
338 15816402691211666
339 16886514484018100
340 18027396355913036
341 19243623485061612
342 20540060244170545
343 21921878018762930
344 23394574210387344
345 24963992275188945
346 26636343085699981
347 28418227459568538
348 30316660165674558
349 32339095245690778
350 34493452984282866
351 36788148361091307
352 39232121343408554
353 41834868846245774
354 44606478747140144
355 47557665777348903
356 50699809705678223
357 54044995632544658
358 57606056843075793
359 61396620031324294
360 65431153380376589
361 69725017306700457
362 74294518390360017
363 79156966297172553
364 84330734255822680
365 89835322892352395
366 95691428030722178
367 101921012260619057
368 108547380928385662
369 115595262352991832
370 123090892975757667
371 131062107245423006
372 139538433005549750
373 148551192188700820
374 158133607644992998
375 168320915915159299
376 179150486843442327
377 190661949845498013
378 202897327801288536
379 215901178397489159
380 229720743967578175
381 244406109667392314
382 260010371121472592
383 276589811391427728
384 294204088497680455
385 312916433365002786
386 332793859524401242
387 353907384466439236
388 376332264091174259
389 400148240175792548
390 425439802429163087
391 452296465088197879
392 480813059756685400
393 511090044482867623
394 543233830922441549
395 577357129627793018
396 613579315470954922
397 652026813296113456
398 692833505980419779
399 736141165064492311
400 782099906321372401
401 830868670496551131
402 882615731797023249
403 937519234447497894
404 995767760115525600
405 1057560926623646619
406 1123110020998297078
407 1192638667382974029
408 1266383533138415882
409 1344595073785931297
410 1427538320409872708
411 1515493710323985682
412 1608757964942216744
413 1707645015821868246
414 1812486983176974442
415 1923635208019086171
416 2041461342608459828
417 2166358500589383408
418 2298742471918537636
419 2439053004198559372
420 2587755155994512419
421 2745340724019134907
422 2912329750271391605
423 3089272111325242591
424 3276749196413220881
425 3475375676844620578
426 3685801374019301143
427 3908713228967563632
428 4144837381345298066
429 4394941361256241811
430 4659836402568409311
431 4940379881583670225
432 5237477890539580339
433 5552087950353963404
434 5885221872973531692
435 6237948778357604998
436 6611398277431821913
437 7006763826727957612
438 7425306267116125560
439 7868357553117439163
440 8337324686369581791
441 8833693860598735132
442 9359034832956587428
443 9915005530031511830
444 10503356904807949658
445 11125938053955594268
446 11784701613265355518
447 12481709441812582921
448 13219138614365595454
449 13999287733943705284
450 14824583585914242202
451 15697588147013708920
452 16621005972725504233
453 17597691978050560061
454 18630659637354526321
455 19723089620150835318
456 20878338890979656824
457 22099950292275888615
458 23391662641092364091
459 24757421360834453330
460 26201389681853056684
461 27727960434549725965
462 29341768472119284436
463 31047703749363916350
464 32850925098289804944
465 34756874730008075712
466 36771293507599083836
467 38900237022868543295
468 41150092525995859607
469 43527596744787820876
470 46039854647289524468
471 48694359188662579993
472 51499012101311972467
473 54462145773799966813
474 57592546283277723943
475 60899477632106285375
476 64392707259693472717
477 68082532885902592309
478 71979810763986039091
479 76095985405665706668
480 80443120863926638575
481 85033933643084908462
482 89881827330036479074
483 95000929023922665288
484 100406127667291303765
485 106113114364445228621
486 112138424800136458852
487 118499483853649935908
488 125214652532480068312
489 132303277330975770121
490 139785742150299383446
491 147683522896453699044
492 156019244906061740704
493 164816743329223185332
494 174101126633751624773
495 183898843373989206726
496 194237752404568970282
497 205147196697591718005
498 216658080961232962972
499 228802953235098218215
500 241616090679682707123
501 255133589753834803795
502 269393461018825621351
503 284435728783367434461
504 300302535851511234776
505 317038253610304543506
506 334689597744709283025
507 353305749841492085725
508 372938485197665784597
509 393642307122500769155
510 415474588079505475978
511 438495717987473681474
512 462769260060778497553
513 488362114541123710213
514 515344690738014602714
515 543791087766555080239
516 573779284440523532386
517 605391338749393807436
518 638713597421847684846
519 673836916048514101500
520 710856890315416154284
521 749874098869275835457
522 790994358419836104659
523 834328991653599260168
524 879995108622961261272
525 928115902243679583906
526 978820958629176063305
527 1032246582958893472735
528 1088536141679961094459
529 1147840421810038886281
530 1210318008218112464272
531 1276135679728728961958
532 1345468825011446101889
533 1418501879186179135693
534 1495428782199396799569
535 1576453459995427924219
536 1661790329639894312992
537 1751664829522277814542
538 1846313975906513622155
539 1945986947069338338142
540 2050945696417884604655
541 2161465595949986839738
542 2277836111582949532166
543 2400361511850026630359
544 2529361611637476559836
545 2665172552610338917202
546 2808147622160955950915
547 2958658112691740057038
548 3117094223242651478478
549 3283866005454050770378
550 3459404356068652514388
551 3644162058159624138929
552 3838614873500197188192
553 4043262688477164587280
554 4258630716195278928564
555 4485270757410971256276
556 4723762523196045481377
557 4974715022228381823467
558 5238768015887968310922
559 5516593544338716934665
560 5808897527078209244680
561 6116421441446363586102
562 6439944082907718861580
563 6780283410938406910475
564 7138298484696429572575
565 7514891492678830833230
566 7911009880942472592172
567 8327648584499963404721
568 8765852366903020878564
569 9226718273071399793891
570 9711398200856161928867
571 10221101596884366251237
572 10757098282695033867458
573 11320721417248682386720
574 11913370602390216217561
575 12536515137933113149734
576 13191697433567955060550
577 13880536584904147934291
578 14604732121529243179214
579 15366067935095946478076
580 16166416396066205776801
581 17007742667889465436217
582 17892109228058882116781
583 18821680605661587758278
584 19798728345756839083175
585 20825636211115723275283
586 21904905632629056390718
587 23039161419920375042558
588 24231157744533740172760
589 25483784408330181116223
590 26800073410623944666694
591 28183205827891544862294
592 29636519020853763895155
593 31163514184074180090214
594 32767864254260652738700
595 34453422193845720631565
596 36224229667546401624506
597 38084526130044592227328
598 40038758344142221225469
599 42091590349242361718573
600 44247913901316349860573
601 46512859406076276772623
602 48891807368484609570073
603 51390400382360934727493
604 54014555685370347328282
605 56770478305381986806418
606 59664674825832376193395
607 62703967798515715565854
608 65895510834000867329871
609 69246804400754460481494
610 72765712365969514723403
611 76460479312079858634034
612 80339748665015038128747
613 84412581671342636159920
614 88688477263686348012213
615 93177392855023036332779
616 97889766104884383909996
617 102836537701838091348488
618 108029175209242280795867
619 113479698022763805740971
620 119200703490982267273195
621 125205394252060973750474
622 131507606842527384311764
623 138121841636042837950782
624 145063294173352417789107
625 152347887946638135197494
626 159992308705079968403757
627 168014040350675751049130
628 176431402497245283711030
629 185263589768024741090084
630 194530712911449741293840
631 204253841817462773009521
632 214455050521217178874496
633 225157464284068517367477
634 236385308846653825944696
635 248163961952185381988199
636 260520007243400159584036
637 273481290640268705818886
638 287076979311320279036863
639 301337623355471949617401
640 316295220317477974559068
641 331983282664548872320694
642 348436908358434116447107
643 365692854662135237283138
644 383789615327719451953930
645 402767501317057706722736
646 422668725215220340504242
647 443537489502142143526880
648 465420078856735355921248
649 488364956674080911441661
650 512422865985607319387890
651 537646934979244539489134
652 564092787326591731144229
653 591818657531898631266150
654 620885511528549820579140
655 651357172757247279677136
656 683300453971884169944578
657 716785295028422380065217
658 751884906924868575462780
659 788675922370649669141614
660 827238553177538958514920
661 867656754775457149943353
662 910018398171480328763014
663 954415449682614328794521
664 1000944158789157945866123
665 1049705254468853343920104
666 1100804150389646417970690
667 1154351159353507345563635
668 1210461717402861378117210
669 1269256618017171385784677
670 1330862256847913261112220
671 1395410887457661639415068
672 1463040888551438013897205
673 1533897043207566769399780
674 1608130830639599571235563
675 1685900731041723174199316
676 1767372544096419251355899
677 1852719721745915753691094
678 1942123715857533554116757
679 2035774341437888700558325
680 2133870156081870573651110
681 2236618856369442908505709
682 2344237691956871809087460
683 2456953898138580348068868
684 2575005147692202556070880
685 2698640022851690596041180
686 2828118508292753685199098
687 2963712506050109651383812
688 3105706373328762559983413
689 3254397484209897733273843
690 3410096816298303994145515
691 3573129563400063402558671
692 3743835775369452814146125
693 3922571026309585720692570
694 4109707112365738133774988
695 4305632780399964956521298
696 4510754488894593244110534
697 4725497202486273585501012
698 4950305221596196304515640
699 5185643048680990335541615
700 5431996292698107344654545
701 5689872613443635754645813
702 5959802707495582055533210
703 6242341337565480697498523
704 6538068407142578431799612
705 6847590082390834294548353
706 7171539963347178126308034
707 7510580306552165807765733
708 7865403301339757713853187
709 8236732402102916488208137
710 8625323718955309444105307
711 9031967469307268102358437
712 9457489492986413945775850
713 9902752833639797322881846
714 10368659389276042659532431
715 10856151634921732510793390
716 11366214420498078164640241
717 11899876847149758126449949
718 12458214225400635053088600
719 13042350118647845715542904
720 13653458475660517390970808
721 14292765855898027593584685
722 14961553751630400461622401
723 15661161011004983377891255
724 16392986366385212301604145
725 17158491072462799248702460
726 17959201658841488473576335
727 18796712801981207537729362
728 19672690321604652516914469
729 20588874306875459536559824
730 21547082377888083994386317
731 22549213088234436222187972
732 23597249474662515727485736
733 24693262760086525163396249
734 25839416216478947551182467
735 27037969194440242560860709
736 28291281326535345248198185
737 29601816911774007879944724
738 30972149488929935607644752
739 32404966606706106813546946
740 33903074799097966617915353
741 35469404774645259793663158
742 37107016828636124998843258
743 38819106487695007250304684
744 40609010396589707370435541
745 42480212457492083092872144
746 44436350232364119369866160
747 46481221619574143852727954
748 48618791816321350475166814
749 50853200578916524836616175
750 53188769793479402859744857
751 55630011370122538952105567
752 58181635474246451103417644
753 60848559109123259903958010
754 63635915064546747448741507
755 66549061246925770482369865
756 69593590406848234617906424
757 72775340280792249323844068
758 76100404164364962713904947
759 79575141935153551738260450
760 83206191544034701910390688
761 87000480994551942390595840
762 90965240830794766081963432
763 95108017155040409281488125
764 99436685197311535826284309
765 103959463459899181250160785
766 108684928460866003951314369
767 113622030101515837913956720
768 118780107683860513151433783
769 124168906605166826558694922
770 129798595757797229103985403
771 135679785663697308549940879
772 141823547374106492085776551
773 148241432166302658416819742
774 154945492070514864572230825
775 161948301261475143552247187
776 169262978350512118090837279
777 176903209615536768832634158
778 184883273207819511821240421
779 193218064376025195419072432
780 201923121749647925422585494
781 211014654725684690803531886
782 220509572004198744873842689
783 230425511320260896634394021
784 240780870421716551367388648
785 251594839344215037727718823
786 262887434037057041766222049
787 274679531395568437572889734
788 286992905758000521461035608
789 299850266927286150166617334
790 313275299780459293447858475
791 327292705531066330078757413
792 341928244712576678897540949
793 357208781953527942774731693
794 373162332618037396212504330
795 389818111388262672624778980
796 407206582868525969808549167
797 425359514294008542521272527
798 444310030430307322375327296
799 464092670753598796998923739
800 484743449004814235948499417
801 506299915214965439744713878
802 528801220302714908550428674
803 552288183349323816793468881
804 576803361660385272498346538
805 602391123728118625148082583
806 629097725212619507834758106
807 656971388065183701488899897
808 686062382921814125593628493
809 716423114900127164898275844
810 748108212938267679229957208
811 781174622819963078082617146
812 815681704035673841825530956
813 851691330635766072959902443
814 889267996237926976050038471
815 928478923357495155222993210
816 969394177236178402848953844
817 1012086784351603854677349920
818 1056632855797491691839521893
819 1103111715731778420365370582
820 1151606035097950772915721243
821 1202201970832993445638272195
822 1254989310783924170802110214
823 1310061624563687281405423376
824 1367516420586432670837201206
825 1427455309531712129148501641
826 1489984174497120347409581419
827 1555213348109176358507531811
828 1623257796873034375670468617
829 1694237313052705211215845951
830 1768276714385123376784682821
831 1845506051943375980293364975
832 1926060826476991912838588917
833 2010082213570129719543464126
834 2097717297972086380495801055
835 2189119317468523563552912518
836 2284447916676471837860026945
837 2383869411161263523157645447
838 2487557062289373612887534921
839 2595691363247441958955371731
840 2708460336674834807788911961
841 2826059844374695605795004426
842 2948693909586874378769557286
843 3076575052325116728754506040
844 3209924638300793313082077760
845 3348973241975952005539600124
846 3493961024309949324717982617
847 3645138125786046809594802830
848 3802765075327529880051627932
849 3967113215736790856488329150
850 4138465146315819525020436745
851 4317115183352320883062358747
852 4503369839182653837210445475
853 4697548320570600615633707040
854 4899983047170076726466398490
855 5111020190869906011843538921
856 5331020236850176651058732272
857 5560358567212078590001382269
858 5799426068076983397453453712
859 6048629761085466400648252914
860 6308393460263492296856111929
861 6579158455260676973889052616
862 6861384222004926715546301462
863 7155549161858413819489813206
864 7462151370402325253272220719
865 7781709437021675124939082762
866 8114763276507277494984991521
867 8461874993939274070243055513
868 8823629784166002470621595572
869 9200636867242999075791233924
870 9593530461250183875257519050
871 10002970793960280134398904116
872 10429645154888935300573646087
873 10874268989316320659309225425
874 11337587035931881668622293462
875 11820374509817859769361096121
876 12323438332553926682727771346
877 12847618411294216209210920955
878 13393788968739955712799836911
879 13962859926005223108664419164
880 14555778340450868632091638362
881 15173529900641757577885104919
882 15817140480666029555650544443
883 16487677756141425010753592938
884 17186252884323757120918580225
885 17914022250825679398423642512
886 18672189285550911770368076087
887 19462006350549392054718366558
888 20284776702603351925153628640
889 21141856533462406368964165733
890 22034657090758372535189618823
891 22964646882747005212249517082
892 23933353970145176154229161936
893 24942368348457517810773270043
894 25993344424317270055187541038
895 27088003589501272683891894076
896 28228136896419857558176968120
897 29415607839028049994572017673
898 30652355243256161955265260158
899 31940396271214763268464632278
900 33281829543592378461759951874
901 34678838384833264653015457726
902 36133694195858564273502187610
903 37648759959276158961048298847
904 39226493882214021491208634096
905 40869453182107909387732749506
906 42580298020978273381249149136
907 44361795593942378526137150625
908 46216824377927327923172488588
909 48148378546777024778473117247
910 50159572559182649435213521023
911 52253645926111023656278281287
912 54433968164659898892082781300
913 56704043945532771290142907958
914 59067518441599984092803386839
915 61528182885296633551494715818
916 64089980342902917860785398635
917 66757011714058038392507769936
918 69533541965176433092152774090
919 72424006605763944407091424877
920 75433018416973441300179187909
921 78565374442093350508270935710
922 81826063249030541768070400530
923 85220272475229951627935685999
924 88753396665869353821729272894
925 92431045416577660047164151370
926 96259051832351299076132562554
927 100243481314784416407988229054
928 104390640690187204668475994537
929 108707087691641431842465830824
930 113199640808535637167196317517
931 117875389517633301827741597928
932 122741704910258149768982161971
933 127806250730730355824172593314
934 133076994841758535713053106552
935 138562221133083702903733964800
936 144270541890285734738564034193
937 150210910641299007705965485795
938 156392635498844712221952645159
939 162825393017671630404234886773
940 169519242586207975314263225158
941 176484641372962914282463066494
942 183732459848780905609389230225
943 191273997906843613303315117150
944 199121001603136364300108748303
945 207285680540947503461466119735
946 215780725923853190220680499504
947 224619329302555775917470915314
948 233815202041894689490999651824
949 243382595535333334306843809620
950 253336322195247837219621752822
951 263691777248402172056857606349
952 274464961367093380360861263650
953 285672504167588901040816946590
954 297331688608659785416676803120
955 309460476324237375428616118607
956 322077533925491470917055623198
957 335202260308943662483307743751
958 348854815008595204514234955296
959 363056147631463102899847491158
960 377828028417386086415154585492
961 393193079965482376767148167370
962 409174810171219023823469015308
963 425797646419686593886806566991
964 443086971082368819610383651304
965 461069158366453016777339954414
966 479771612567549566354812715892
967 499222807778576144011028425622
968 519452329109520881661481897955
969 540490915474826884271771842867
970 562370504007245052572754713346
971 585124276159181626473477981280
972 608786705554828160141224101529
973 633393607658703453309968615542
974 658982191328666551946374906594
975 685591112323976025839957690192
976 713260528841580971202449604823
977 742032159156532358121695156498
978 771949341445207490500775756524
979 803057095872944318812682761956
980 835402189030694616058327756283
981 869033200808424517965432674225
982 904000593796226564213963956332
983 940356785307458167307212330008
984 978156222121696782371259975157
985 1017455458048901061743337166150
986 1058313234419899861278980611548
987 1100790563612196339797300463317
988 1144950815724083002591075881878
989 1190859808514214729993206257049
990 1238585900728091612522956800828
991 1288200088937361273240757279154
992 1339776108022472904862007882731
993 1393390535434002132252074158793
994 1449122899372929273678936150945
995 1507055791035293444161646292141
996 1567274981071974136698206270420
997 1629869540419870459266944534818
998 1694931965666469723856887333806
999 1762558309115721827769859285423
1000 1832848313729278216858958831133