0 0
1 1
2 1
3 1
4 2
5 3
6 5
7 7
8 10
9 14
10 19
11 26
12 35
13 47
14 62
15 82
16 107
17 139
18 179
19 230
20 293
21 372
22 470
23 591
24 740
25 924
26 1148
27 1422
28 1756
29 2161
30 2651
31 3244
32 3957
33 4815
34 5844
35 7075
36 8545
37 10299
38 12383
39 14859
40 17794
41 21267
42 25368
43 30207
44 35902
45 42600
46 50462
47 59678
48 70465
49 83079
50 97800
51 114967
52 134956
53 158205
54 185209
55 216546
56 252859
57 294902
58 343518
59 399680
60 464487
61 539205
62 625246
63 724247
64 838042
65 968726
66 1118660
67 1290541
68 1487389
69 1712659
70 1970221
71 2264473
72 2600357
73 2983481
74 3420118
75 3917392
76 4483279
77 5126785
78 5858008
79 6688344
80 7630529
81 8698935
82 9909619
83 11280641
84 12832196
85 14586967
86 16570260
87 18810493
88 21339363
89 24192369
90 27409105
91 31033879
92 35116025
93 39710717
94 44879358
95 50690487
96 57220370
97 64554052
98 72786034
99 82021639
100 92377832
101 103984768
102 116986932
103 131544972
104 147837027
105 166061023
106 186436302
107 209206271
108 234640552
109 263038106
110 294729764
111 330082125
112 369500620
113 413434038
114 462378446
115 516882557
116 577552386
117 645057814
118 720138225
119 803610203
120 896374566
121 999425489
122 1113858868
123 1240883427
124 1381830778
125 1538168452
126 1711512298
127 1903641945
128 2116515550
129 2352288440
130 2613330788
131 2902249590
132 3221910173
133 3575462224
134 3966365363
135 4398420368
136 4875799726
137 5403084414
138 5985300779
139 6627964097
140 7337122322
141 8119408068
142 8982090692
143 9933137585
144 10981276611
145 12136068505
146 13407980851
147 14808474162
148 16350089673
149 18046550696
150 19912867307
151 21965455962
152 24222263215
153 26702907394
154 29428825009
155 32423437435
156 35712324713
157 39323421809
158 43287223612
159 47637016715
160 52409121310
161 57643163457
162 63382361133
163 69673844302
164 76568991529
165 84123806825
166 92399315881
167 101462008094
168 111384303557
169 122245071599
170 134130179128
171 147133099710
172 161355557401
173 176908239895
174 193911555100
175 212496466196
176 232805378126
177 254993115975
178 279227963489
179 305692806742
180 334586351164
181 366124458109
182 400541567901
183 438092262433
184 479052928555
185 523723581303
186 572429808511
187 625524897652
188 683392105041
189 746447136977
190 815140796679
191 889961874362
192 971440234557
193 1060150181193
194 1156714053255
195 1261806142717
196 1376156880379
197 1500557391432
198 1635864367436
199 1783005361285
200 1942984450651
201 2116888391019
202 2305893196147
203 2511271280479
204 2734399102923
205 2976765453900
206 3239980324902
207 3525784521090
208 3836059948141
209 4172840751685
210 4538325243851
211 4934888806335
212 5365097705219
213 5831724031676
214 6337761696275
215 6886443714745
216 7481260718503
217 8125980944068
218 8824671638261
219 9581722165709
220 10401868749151
221 11290221161267
222 12252291308167
223 13294024047247
224 14421830186724
225 15642622052899
226 16963851569589
227 18393551279148
228 19940378265174
229 21613661441237
230 23423452179922
231 25380578804722
232 27496704921371
233 29784392170791
234 32257167405782
235 34929594924193
236 37817353785002
237 40937320918825
238 44307660072067
239 47947917377861
240 51879123632893
241 56123904146670
242 60706596283009
243 65653375667880
244 70992391211653
245 76753910032966
246 82970472495100
247 89677058547376
248 96911265647600
249 104713499605793
250 113127178679475
251 122198952417857
252 131978935680652
253 142520959480878
254 153882839180063
255 166126661889154
256 179319093696670
257 193531708796403
258 208841341282340
259 225330461900753
260 243087580684818
261 262207678045233
262 282792665395260
263 304951878190333
264 328802602679322
265 354470639559798
266 382090906075091
267 411808080140060
268 443777288275252
269 478164841366785
270 515149020358757
271 554920916341908
272 597685327505713
273 643661717970053
274 693085241338216
275 746207834592411
276 803299385657065
277 864648980888417
278 930566236353322
279 1001382719929531
280 1077453468658140
281 1159158609233039
282 1246905086769652
283 1341128510646583
284 1442295123354393
285 1550903902232083
286 1667488800877179
287 1792621141310599
288 1926912164721806
289 2071015753168879
290 2225631331220775
291 2391506961444324
292 2569442643982646
293 2760293835821165
294 2964975201500249
295 3184464612708230
296 3419807410204551
297 3672120947655828
298 3942599432684810
299 4232519087101609
300 4543243643803942
301 4876230204923081
302 5233035481151493
303 5615322439852124
304 6024867384578153
305 6463567496966674
306 6933448866786347
307 7436675044793324
308 7975556147703767
309 8552558554189085
310 9170315225100529
311 9831636691565035
312 10539522748676155
313 11297174903639833
314 12108009621161388
315 12975672420908876
316 13904052875446815
317 14897300570137024
318 15959842079856624
319 17096399031390158
320 18312007313576263
321 19612037512457879
322 21002216641545844
323 22488651253804652
324 24077852014657585
325 25776759832985125
326 27592773639706129
327 29533779922685526
328 31608184119001144
329 33824943986446450
330 36193605068337595
331 38724338388068883
332 41427980502077499
333 44316076064151547
334 47400923045987928
335 50695620785333705
336 54214121025048904
337 57971282134858504
338 61982926699760053
339 66265902689920836
340 70838148419005258
341 75718761531505770
342 80928072252003522
343 86487721165540037
344 92420741791088628
345 98751648249525285
346 105506528320473303
347 112713142225364960
348 120401027467619768
349 128601610107256145
350 137348322841668104
351 146676730314810844
352 156624662072025765
353 167232353632860160
354 178542596150315081
355 190600895184620517
356 203455639117172036
357 217158277795271169
358 231763511997046108
359 247329494376930102
360 263918042552656895
361 281594865071737557
362 300429800998301009
363 320497073945177823
364 341875561381149834
365 364649080135118266
366 388906689026941187
367 414743009654466977
368 442258566377895289
369 471560146651562643
370 502761182868342610
371 535982157001081924
372 571351029345129768
373 609003692795803573
374 649084454119694381
375 691746543820610756
376 737152656231466413
377 785475521618824263
378 836898512124131937
379 891616283535120982
380 949835454926160386
381 1011775328391808037
382 1077668651151363403
383 1147762422505509142
384 1222318748189705166
385 1301615744890981095
386 1385948497769966870
387 1475630074073202042
388 1570992596008144778
389 1672388376320107345
390 1780191120112238511
391 1894797196741418860
392 2016626985741495945
393 2146126301045224898
394 2283767897912557181
395 2430053067324169045
396 2585513322756169435
397 2750712184636493112
398 2926247067964226699
399 3112751278995185495
400 3310896127103212290
401 3521393158390366257
402 3744996517854771479
403 3982505447433130037
404 4234766927503896464
405 4502678469995333094
406 4787191071547729099
407 5089312335792697135
408 5410109774158938220
409 5750714295287087604
410 6112323893529478500
411 6496207547750562628
412 6903709342087696492
413 7336252821145776396
414 7795345592601023624
415 8282584191082747184
416 8799659217768776156
417 9348360771112819169
418 9930584184759766185
419 10548336089786062490
420 11203740819120373216
421 11899047173187652075
422 12636635566627863054
423 13419025577247450081
424 14248883919268193076
425 15129032864376519663
426 16062459135093881853
427 17052323296570185872
428 18101969674043886815
429 19214936824952717261
430 20394968595956542314
431 21646025797049925208
432 22972298526372177019
433 24378219181430134869
434 25868476194049395455
435 27448028528689682390
436 29122120985547297703
437 30896300352422317045
438 32776432451324628913
439 34768720128603736122
440 36879722239616529185
441 39116373682042052102
442 41486006534437268435
443 43996372360036217381
444 46655665738565469715
445 49472549092599806450
446 52456178878069908087
447 55616233212664298344
448 58962941019304389060
449 62507112766420701786
450 66260172890583483222
451 70234193992048265203
452 74441932898033226650
453 78896868694059367675
454 83613242828414887217
455 88606101400878342648
456 93891339752092669094
457 99485749476667460089
458 105407067988928614198
459 111674030777596326485
460 118306426492156624259
461 125325155011799454345
462 132752288654993736393
463 140611136696694945381
464 148926313368167673525
465 157723809524233373550
466 167031068171608808765
467 176877064062823141003
468 187292387570019401621
469 198309333064858981468
470 209961992041629934719
471 222286351233776046396
472 235320395986116559117
473 249104219159468025812
474 263680135857728587819
475 279092804283380160219
476 295389353042144475174
477 312619515235026940981
478 330835769692337461484
479 350093489723540066693
480 370451099774879292083
481 391970240407929857614
482 414715942032233877213
483 438756807848521607334
484 464165206481142718447
485 491017474804014455974
486 519394131488857914143
487 549380101832748684324
488 581064954449047018664
489 614543150436864070089
490 649914305674089880645
491 687283466913220322201
492 726761402392211939348
493 768464907710228599781
494 812517127754576978577
495 859047895506530556839
496 908194088593957858986
497 960100004504216158393
498 1014917755415158088329
499 1072807683652189499069
500 1133938798828295684041
501 1198489237779043800590
502 1266646748458594999043
503 1338609199023345719696
504 1414585113389402376669
505 1494794234616708303274
506 1579468117538344775022
507 1668850752126770396425
508 1763199219161187329845
509 1862784379840746897728
510 1967891601068129185656
511 2078821518216542607592
512 2195890837281148341366
513 2319433178413202525532
514 2449799962932103923897
515 2587361346017461034926
516 2732507197390016150267
517 2885648132407760647920
518 3047216596121103462476
519 3217668002960060893239
520 3397481934855824342731
521 3587163400740912807944
522 3787244160514542896069
523 3998284116715672882158
524 4220872777302926562814
525 4455630793111766153107
526 4703211573731751057972
527 4964302985734714748388
528 5239629137374426898749
529 5529952254084754691032
530 5836074649312032204682
531 6158840795444039622206
532 6499139499827487844440
533 6857906191114803506510
534 7236125321433338735687
535 7634832890143365905409
536 8055119095228608091259
537 8498131118662983704591
538 8965076052402115312420
539 9457223971977345152398
540 9975911165005026957155
541 10522543522285118759320
542 11098600099531206636239
543 11705636858170494704551
544 12345290594056660235656
545 13019283063373401398428
546 13729425315450635048727
547 14477622242692424050071
548 15265877358303442923696
549 16096297813024149977224
550 16971099662620335898290
551 17892613398446732309184
552 18863289753992234055200
553 19885705800943765297736
554 20962571348951079258990
555 22096735663965010781127
556 23291194520729818785908
557 24549097605767015744942
558 25873756287965071558971
559 27268651774718962212449
560 28737443672415965466747
561 30283978970973425494526
562 31912301473069238812078
563 33626661689702419470814
564 35431527224746591448308
565 37331593672251371653031
566 39331796051371141234435
567 41437320804997353820165
568 43653618389403462199537
569 45986416483522585018374
570 48441733847829629743374
571 51025894864235752928868
572 53745544789884500725419
573 56607665759312032497365
574 59619593571057370708700
575 62789035296531422522463
576 66124087750732521440137
577 69633256866282780391990
578 73325478014208622604635
579 77210137316954473951860
580 81297094001253668363180
581 85596703840742042104064
582 90119843740538188502497
583 94877937518489807637931
584 99882982940346534965033
585 105147580068829089014685
586 110684960989368714639091
587 116509020978256117015129
588 122634351182009091243756
589 129076272880012752944756
590 135850873405846907884482
591 142975043806265221795194
592 150466518320469075516887
593 158343915766202829049943
594 166626782923222521064755
595 175335640008938408030417
596 184492028345436289160078
597 194118560321729168276330
598 204238971759909623658209
599 214878176798954821203344
600 226062325415207490435164
601 237818863704112719937555
602 250176597053556121273639
603 263165756345224124174533
604 276818067326712639996410
605 291166823303751860454102
606 306246961308809872290804
607 322095141909597501540284
608 338749832828535280089197
609 356251396552178003127516
610 374642182117833341553157
611 393966621273282114329051
612 414271329214515676189607
613 435605210115880794919133
614 458019567676867204444373
615 481568220920125046670654
616 506307625486057529267560
617 532297000680643147805925
618 559598462544896510447094
619 588277163226729794087019
620 618401436948818837183231
621 650042952879569677996029
622 683276875228309365269409
623 718182030900558776873178
624 754841085064566911908513
625 793340724996374568176157
626 833771852587408009246803
627 876229785916168755131609
628 920814470303856903622566
629 967630699292941425041145
630 1016788346007639799775373
631 1068402605376201104568790
632 1122594247716664634954598
633 1179489884210611772317326
634 1239222244813200588493119
635 1301930469172704357706591
636 1367760411158720188192791
637 1436864957625419035734790
638 1509404362064521965333172
639 1585546593832369936070062
640 1665467703666349015440401
641 1749352206238314654557266
642 1837393480526365648644317
643 1929794188821640869441492
644 2026766715223582897619482
645 2128533624515638679721738
646 2235328142353476156233142
647 2347394657739811200715883
648 2464989248803683733436836
649 2588380232947837512590126
650 2717848742475562362930889
651 2853689326858311727538404
652 2996210582857424737402727
653 3145735813767742422397691
654 3302603719107619351729334
655 3467169116139198583208731
656 3639803694664641590860637
657 3820896806608712523410848
658 4010856291965505091834933
659 4210109342757621977238602
660 4419103406729563437297708
661 4638307132573931162492283
662 4868211358569093602446988
663 5109330146590694870156548
664 5362201863546604856061187
665 5627390312376137813654417
666 5905485914849390244807771
667 6197106948501932052770933
668 6502900840143604051761437
669 6823545518488428689736380
670 7159750828565402429665614
671 7512260010687841755032142
672 7881851246881770537045401
673 8269339277802236079849579
674 8675577093300192905054120
675 9101457699942408527906284
676 9547915968932490905320206
677 10015930568033366809631664
678 10506525981250119938213555
679 11020774620197826114783424
680 11559799031251666553524546
681 12124774202757005743205851
682 12716929976765055054404110
683 13337553569956104978236347
684 13987992208616866798702250
685 14669655882752171232794193
686 15384020224633899402297313
687 16132629517322581065218232
688 16917099838939363057842676
689 17739122348719100143627709
690 18600466721138933472726376
691 19502984734692037291806909
692 20448614022163022865399732
693 21439381989560998576641981
694 22477409911178296765559292
695 23564917208568675114668379
696 24704225921578194548487611
697 25897765379916330709300514
698 27148077084124017456089786
699 28457819805180697712355784
700 29829774912393910988172961
701 31266851939634018660972252
702 32772094400413218148286420
703 34348685862763663315000836
704 35999956295344173872875301
705 37729388696700422694852372
706 39540626020119545456754504
707 41437478407058674689862520
708 43423930742687897855802167
709 45504150547673547803776477
710 47682496220937525418714400
711 49963525648764626251308160
712 52352005196292604835930691
713 54852919098111195898695022
714 57471479265416572842443139
715 60213135527919139167806818
716 63083586329485218767653281
717 66088789897309669323048085
718 69234975905266844602049684
719 72528657652974375386330995
720 75976644783028141009860859
721 79586056559830440324456592
722 83364335734437026898646289
723 87319263020895414025821543
724 91458972210637041239204863
725 95791965952622794573316229
726 100327132228125432717740427
727 105073761550267176809771164
728 110041564919716612391724117
729 115240692569289846759011369
730 120681753531597207310512855
731 126375836065332625053807081
732 132334528977318981135586627
733 138569943879003338544796808
734 145094738417742023322977784
735 151922140524931480814830301
736 159065973724827741147010015
737 166540683549760012402140279
738 174361365109383563682715762
739 182543791863638820060131029
740 191104445651188823242826995
741 200060548027301424121119717
742 209430092967427310885800017
743 219231880995106125795807362
744 229485554795312236887864008
745 240211636376935499416736578
746 251431565850782546294561335
747 263167741892287512562205711
748 275443563961039856931108570
749 288283476352278285422739485
750 301713014158666213174495003
751 315758851223963411945418728
752 330448850173643289283753817
753 345812114611083857837115337
754 361879043571686015700353428
755 378681388331154074209279913
756 396252311668214033936242793
757 414626449686254343459577849
758 433839976302755669271501966
759 453930670519940641976904683
760 474937986594825944718362866
761 496903127231808269898608104
762 519869119926067380527797681
763 543880896591435332134535771
764 568985376611966144974882528
765 595231553462257243325108294
766 622670585047628663587257002
767 651355887921571636619027238
768 681343235544441146728266839
769 712690860754201667010794607
770 745459562627148608942853972
771 779712817913935325920436502
772 815516897243944641147445368
773 852940986299071145012015704
774 892057312166334579731503184
775 932941275087442987313430332
776 975671585832476454353988644
777 1020330408934286990991146214
778 1067003512030017779132470491
779 1115780421566355818808173849
780 1166754585135757354162190450
781 1220023540721946928737319536
782 1275689093144501071731822412
783 1333857498004309572049700825
784 1394639653444174823554817977
785 1458151300051787623427093222
786 1524513229245821147145030373
787 1593851500499940214478858950
788 1666297667774146888907357795
789 1741989015538104464404975442
790 1821068804786918013059990996
791 1903686529466331528314408953
792 1989998183741448993154415525
793 2080166540560932306746036580
794 2174361441987194418630671190
795 2272760101782426533317722414
796 2375547420760397323844679265
797 2482916315434877610520406220
798 2595068060517301511352746876
799 2712212645838915320007044518
800 2834569148296216213898349477
801 2962366119442988000914187131
802 3095841989377730875810463607
803 3235245487601803461067700764
804 3380836081551181356441638585
805 3532884433533437364763450179
806 3691672876831400537723345646
807 3857495911766008266198455353
808 4030660722543167040163544053
809 4211487715743041301605320093
810 4400311081345138662953907914
811 4597479377218916048034018402
812 4803356138047441408939676987
813 5018320509690976595376002174
814 5242767910038249107235698997
815 5477110717435725843087075936
816 5721778987829445328321900135
817 5977221201799983618897081771
818 6243905042718982607430267133
819 6522318207305440918126834352
820 6812969249911721541584516500
821 7116388461923056135631463879
822 7433128787710293592078498970
823 7763766778633846007846194187
824 8108903586657304652655968852
825 8469165999192135022605282833
826 8845207516860296102145716919
827 9237709475929675359892673570
828 9647382217247977230410062632
829 10074966303574268002560740835
830 10521233787283861124593662945
831 10986989530501751972951517049
832 11473072579802485222719812714
833 11980357597700298712302904780
834 12509756353242748998199977475
835 13062219274113933561035749191
836 13638737062750006219910660032
837 14240342379070094731772952855
838 14868111592530106402605122884
839 15523166606315419729744319522
840 16206676756601252288818788484
841 16919860789926751001288953185
842 17663988921850727163544480977
843 18440384980183652692131690096
844 19250428636222215414944401874
845 20095557727549612243283620008
846 20977270676107023064885381913
847 21897129005389583467260345934
848 22856759960773859304033438518
849 23857859237143566053192390300
850 24902193818146285435010829500
851 25991604931586474687224698883
852 27128011125639372237737482285
853 28313411470756760912760348927
854 29549888892329207100952828209
855 30839613639370656407356536438
856 32184846894700404406533068135
857 33587944532314802998801441295
858 35051361027866901608651576718
859 36577653528406910527216609942
860 38169486087780227719016230303
861 39829634074333169354558185245
862 41560988757839830267236337311
863 43366562082837080908474032291
864 45249491635838951686904363259
865 47213045814197001879570835090
866 49260629204680117656992501351
867 51395788180166003131049307854
868 53622216723167850631661483097
869 55943762485263807989572784403
870 58364433091854366688146273971
871 60888402702044219724300330262
872 63520018833830984113383893795
873 66263809465184035445116020738
874 69124490422013102813580811416
875 72106973064458851016577179809
876 75216372283387018126821316407
877 78458014819434456832946137660
878 81837447917440278535675058817
879 85360448329598947292494730396
880 89033031681195297313408196104
881 92861462213324834630362835832
882 96852262917567065373632980403
883 101012226078165810257071335389
884 105348424237879309698298337038
885 109868221604295299986774283218
886 114579285914063002493840815803
887 119489600773176086357413606477
888 124607478492149061686370825690
889 129941573435665279188082579143
890 135500895907038746544647720441
891 141294826588625444160680666795
892 147333131560143803884054809461
893 153625977917719710353057623467
894 160183950017359949944254109013
895 167018066367480763617949530266
896 174139797196076301219000890032
897 181561082719106719789087481125
898 189294352137718757672459188527
899 197352543392984347748673598364
900 205749123707956651370132339602
901 214498110947999409667569709895
902 223614095831546276937683861725
903 233112265024693552368256071759
904 243008425154324137720972075506
905 253319027775804479631908540186
906 264061195332691511530005232397
907 275252748147335190586105743886
908 286912232482766074276694192848
909 299058949717818647071026395859
910 311712986679061884654654175581
911 324895247174791139274108999331
912 338627484778082100250434626147
913 352932336907720808912275910371
914 367833360257705915066653809651
915 383355067627973218009023959503
916 399522966211020652779302336371
917 416363597391217125840269976424
918 433904578115763787219182512301
919 452174643898544525619540106168
920 471203693520456717517979001294
921 491022835492256857032562415674
922 511664436348491899704320186254
923 533162170843719522425920397144
924 555551074124952541039541081471
925 578867595957098252825472557722
926 603149657081106257354136357381
927 628436707787592455715233455800
928 654769788791876495672970485956
929 682191594499659322982005588416
930 710746538755981085550016097539
931 740480823173642148319994491123
932 771442508140946112122277367528
933 803681586612438571129024380519
934 837250060790273945809086749950
935 872202021807950549887635686953
936 908593732532416527449942544836
937 946483713604972292742282223387
938 985932832845984467246749500110
939 1027004398153188332944165688273
940 1069764254028296794683945299071
941 1114280881871760530741448005224
942 1160625504190843169436359532860
943 1208872192871694223501970214799
944 1259097981671828411322499009153
945 1311382983095360694081425737783
946 1365810509819509674502225275391
947 1422467200847276310859244771298
948 1481443152567838599377921314444
949 1542832054913084961507779061958
950 1606731332805848568989595376330
951 1673242293102811404581342222455
952 1742470277242730194267135807902
953 1814524819818606824535938676976
954 1889519813300693905412642346586
955 1967573679145802886358502325425
956 2048809545537278785758372281189
957 2133355432009234104311617214445
958 2221344441218206901468934879652
959 2312914958135337149406769731786
960 2408210856942454280767378787317
961 2507381715926151084177353091207
962 2610583040674998677571842990419
963 2717976495896548984120439641204
964 2829730146182689883961811231142
965 2946018706064279881841805902066
966 3067023799708809759177920804130
967 3192934230628135296869941372043
968 3323946261777114994511500150874
969 3460263906438288047688864665784
970 3602099230302559185771612719595
971 3749672665171237930901440165695
972 3903213334720730291537239880109
973 4062959392787721898395507998568
974 4229158374649844472137589532430
975 4402067561794604866542078854400
976 4581954360687800678569069893828
977 4769096696071772793109919020953
978 4963783419343677845363702120272
979 5166314732584528441856095608423
980 5377002628831072504448385822416
981 5596171349204693190816575441353
982 5824157857534435865818361825564
983 6061312333135038484609103869332
984 6307998682425486950782919121748
985 6564595070099169644542270139958
986 6831494470583198062737203073748
987 7109105240551927824466224697450
988 7397851713288191255514962301291
989 7698174815715276326807922584124
990 8010532708953294539021983683156
991 8335401453285312056838019068661
992 8673275698451514410266745895070
993 9024669400223777913869068626649
994 9390116564248373969922798350658
995 9770172018181181219502507529302
996 10165412213177771615362299670623
997 10576436055840118818444544102259
998 11003865771762500789911380730963
999 11448347801861485510776212587002
1000 11910553732718752974456751586469