0 1
1 0
2 1
3 1
4 2
5 2
6 3
7 3
8 5
9 5
10 7
11 8
12 11
13 12
14 16
15 18
16 23
17 26
18 33
19 37
20 46
21 52
22 63
23 72
24 87
25 98
26 117
27 133
28 157
29 178
30 209
31 236
32 276
33 312
34 361
35 408
36 471
37 530
38 609
39 686
40 784
41 881
42 1004
43 1126
44 1279
45 1433
46 1621
47 1814
48 2048
49 2286
50 2574
51 2871
52 3223
53 3590
54 4022
55 4472
56 5000
57 5553
58 6194
59 6871
60 7652
61 8474
62 9420
63 10422
64 11564
65 12778
66 14157
67 15623
68 17284
69 19053
70 21045
71 23174
72 25565
73 28117
74 30977
75 34037
76 37449
77 41106
78 45175
79 49534
80 54376
81 59567
82 65313
83 71483
84 78299
85 85612
86 93679
87 102342
88 111872
89 122111
90 133358
91 145437
92 158688
93 172923
94 188505
95 205253
96 223561
97 243227
98 264703
99 287776
100 312928
101 339953
102 369381
103 400988
104 435371
105 472297
106 512409
107 555491
108 602245
109 652435
110 706857
111 765273
112 828540
113 896441
114 969918
115 1048746
116 1133981
117 1225403
118 1324158
119 1430065
120 1544381
121 1666921
122 1799101
123 1940760
124 2093430
125 2257009
126 2433185
127 2621877
128 2824974
129 3042436
130 3276326
131 3526698
132 3795820
133 4083793
134 4393156
135 4724097
136 5079385
137 5459346
138 5867037
139 6302880
140 6770288
141 7269818
142 7805213
143 8377243
144 8990032
145 9644512
146 10345290
147 11093525
148 11894267
149 12748980
150 13663248
151 14638805
152 15681873
153 16794525
154 17983605
155 19251642
156 20606195
157 22050208
158 23592107
159 25235352
160 26989217
161 28857810
162 30851395
163 32974715
164 35239186
165 37650309
166 40220673
167 42956720
168 45872374
169 48975003
170 52280104
171 55796152
172 59540240
173 63522169
174 67760860
175 72267480
176 77063052
177 82160323
178 87582514
179 93344250
180 99471227
181 105980015
182 112899166
183 120247505
184 128056561
185 136347784
186 145156078
187 154505670
188 164435295
189 174972341
190 186159616
191 198028173
192 210625380
193 223986180
194 238163120
195 253195577
196 269141605
197 286045645
198 303971937
199 322970361
200 343112116
201 364453213
202 387072332
203 411032475
204 436420646
205 463307374
206 491789036
207 521944636
208 553880630
209 587685583
210 623477199
211 661354414
212 701447494
213 743866979
214 788756733
215 836240368
216 886476837
217 939603935
218 995797473
219 1055211091
220 1118038855
221 1184452143
222 1254665288
223 1328869001
224 1407300132
225 1490170896
226 1577742638
227 1670251601
228 1767986218
229 1871208912
230 1980238211
231 2095365633
232 2216942431
233 2345292491
234 2480803255
235 2623833973
236 2774812141
237 2934136175
238 3102277250
239 3279677276
240 3466855603
241 3664301649
242 3872588051
243 4092256795
244 4323938592
245 4568233639
246 4825836684
247 5097411580
248 5383723722
249 5685507211
250 6003604571
251 6338827587
252 6692103643
253 7064329444
254 7456525917
255 7869683410
256 8304924928
257 8763344121
258 9246176265
259 9754627988
260 10290058080
261 10853797513
262 11447339966
263 12072153428
264 12729879673
265 13422136470
266 14150728410
267 14917437957
268 15724247421
269 16573120404
270 17466234249
271 18405750591
272 19394060836
273 20433544049
274 21526825354
275 22676522718
276 23885517404
277 25156688406
278 26493197922
279 27898211277
280 29375197249
281 30927635306
282 32559330014
283 34274104031
284 36076129713
285 37969605724
286 39959105781
287 42049240685
288 44245023261
289 46551514253
290 48974207126
291 51518655195
292 54190876119
293 56996962467
294 59943505026
295 63037184912
296 66285219553
297 69694933675
298 73274228002
299 77031131245
300 80974290498
301 85112502330
302 89455229320
303 94012107098
304 98793486919
305 103809921251
306 109072731455
307 114593469585
308 120384515940
309 126458513818
310 132828997131
311 139509800633
312 146515716465
313 153861877565
314 161564448580
315 169639978673
316 178106126824
317 186980987067
318 196283847237
319 206034483788
320 216253959875
321 226963885825
322 238187256898
323 249947682416
324 262270262016
325 275180780693
326 288706630207
327 302875965450
328 317718671287
329 333265483787
330 349549001599
331 366602768652
332 384462337245
333 403164307543
334 422747442985
335 443251670176
336 464719245463
337 487193711848
338 510721124972
339 535348961557
340 561127405420
341 588108211654
342 616346051826
343 645897329901
344 676821595440
345 709180305729
346 743038308030
347 778462552132
348 815523640671
349 854294488098
350 894851949209
351 937275418042
352 981648535705
353 1028057734236
354 1076594023099
355 1127351473344
356 1180429093663
357 1235929248265
358 1293959624213
359 1354631588054
360 1418062243799
361 1484372723611
362 1553690348875
363 1626146847413
364 1701880619429
365 1781034887327
366 1863760066363
367 1950211841598
368 2040553656795
369 2134954710798
370 2233592567391
371 2336651077221
372 2444323108458
373 2556808388945
374 2674316373026
375 2797063995255
376 2925278676300
377 3059195995494
378 3199062836473
379 3345134972332
380 3497680367868
381 3656976668529
382 3823314663270
383 3996995684872
384 4178335234185
385 4367660285888
386 4565313093250
387 4771648389436
388 4987037377352
389 5211864835439
390 5446533294556
391 5691460041404
392 5947081503460
393 6213850140181
394 6492239041987
395 6782738718756
396 7085861915155
397 7402140289972
398 7732129471809
399 8076405618252
400 8435570718907
401 8810249045637
402 9201092706805
403 9608777981392
404 10034011150843
405 10477524706426
406 10940083467591
407 11422480674583
408 11925544398113
409 12450133510619
410 12997144417566
411 13567506895618
412 14162191155930
413 14782203563679
414 15428594040198
415 16102451656859
416 16804912409576
417 17537154675875
418 18300407374986
419 19095945303740
420 19925097690794
421 20789243405335
422 21689819943886
423 22628318500027
424 23606293399140
425 24625357048083
426 25687189829395
427 26793534924805
428 27946208711863
429 29147095450562
430 30398158201813
431 31701433398031
432 33059042297543
433 34473185434919
434 35946154660631
435 37480327460397
436 39078179602809
437 40742279352900
438 42475300746281
439 44280017693243
440 46159317935016
441 48116197029615
442 50153773018465
443 52275280322481
444 54484085141528
445 56783679260221
446 59177696244199
447 61669905147739
448 64264227540340
449 66964731150481
450 69775647751540
451 72701366742889
452 75746453967616
453 78915645226675
454 82213866069550
455 85646225281023
456 89218035679845
457 92934807584145
458 96802270702101
459 100826367574041
460 105013276604200
461 109369405527330
462 113901415625823
463 118616215230745
464 123520985219982
465 128623172557783
466 133930517133892
467 139451045397186
468 145193098589570
469 151165326491070
470 157376717159847
471 163836590797740
472 170554631067935
473 177540879148545
474 184805766694864
475 192360110105500
476 200215145256866
477 208382522000237
478 216874340755837
479 225703147320088
480 234881971400581
481 244424321769509
482 254344226888560
483 264656230436100
484 275375434126180
485 286517493706135
486 298098664069985
487 310135795774220
488 322646382617856
489 335648558718488
490 349161148685992
491 363203665373090
492 377796362764096
493 392960234465724
494 408717069512491
495 425089451655415
496 442100818235816
497 459775460410970
498 478138585245493
499 497216316958533
500 517035762467311
501 537625013735889
502 559013216954980
503 581230576158132
504 604308426217985
505 628279237841732
506 653176694659370
507 679035699703232
508 705892456808868
509 733784478780229
510 762750673323659
511 792831353040264
512 824068326214949
513 856504908775258
514 890186020202398
515 925158197698106
516 961469697483621
517 999170511356845
518 1038312473759026
519 1078949280900028
520 1121136603913059
521 1164932110841409
522 1210395586205100
523 1257588956077441
524 1306576414509080
525 1357424451924342
526 1410201988789416
527 1464980407680755
528 1521833694588189
529 1580838474944174
530 1642074163088980
531 1705623002549925
532 1771570224132565
533 1840004090877783
534 1911016065253049
535 1984700859146239
536 2061156610777643
537 2140484940097090
538 2222791135976531
539 2308184217524824
540 2396777132132458
541 2488686823152458
542 2584034439533011
543 2682945410321053
544 2785549666554083
545 2891981723210566
546 3002380914052525
547 3116891481575772
548 3235662825672827
549 3358849602154041
550 3486611986039897
551 3619115779403916
552 3756532690126958
553 3899040449747300
554 4046823108709251
555 4200071164926155
556 4358981876493317
557 4523759401873362
558 4694615131079181
559 4871767838321973
560 5055444032887476
561 5245878125120846
562 5443312798163400
563 5647999188369260
564 5860197279111759
565 6080176096666241
566 6308214127540336
567 6544599530896064
568 6789630580803471
569 7043615896525751
570 7306874911154230
571 7579738121018915
572 7862547582430767
573 8155657181537884
574 8459433160856648
575 8774254411166962
576 9100513029583363
577 9438614635034035
578 9788978959926345
579 10152040190821716
580 10528247595711075
581 10918065891808922
582 11321975910545848
583 11740474994360640
584 12174077701851119
585 12623316235536110
586 13088741189583487
587 13570922010855242
588 14070447791741528
589 14587927766776768
590 15123992153487695
591 15679292686978212
592 16254503511688263
593 16850321756735801
594 17467468481624309
595 18106689295115775
596 18768755358345311
597 19454464050143522
598 20164640031031571
599 20900135958343158
600 21661833614742009
601 22450644676508293
602 23267511910699029
603 24113410000135724
604 24989346813363877
605 25896364290374041
606 26835539789728897
607 27807987039084874
608 28814857564390586
609 29857341709496324
610 30936670152401813
611 32054114998793124
612 33210991390570755
613 34408658678232090
614 35648522127522035
615 36932034175841252
616 38260696242971006
617 39636060077321932
618 41059729676999742
619 42533362731823320
620 44058672661685750
621 45637430160600152
622 47271465359475834
623 48962669479163716
624 50712997125142701
625 52524468056713746
626 54399169621880404
627 56339258650232235
628 58346964036525287
629 60424588765618102
630 62574512653719409
631 64799194513974789
632 67101175065241386
633 69483079247409884
634 71947619307869522
635 74497597276580798
636 77135908240944023
637 79865542990963576
638 82689591494261304
639 85611245722251512
640 88633803337429939
641 91760670712555248
642 94995366843013932
643 98341526571419711
644 101802904739024809
645 105383379628858920
646 109086957370665226
647 112917775616925601
648 116880108216597935
649 120978369138920104
650 125217117432577112
651 129601061413020859
652 134135063924330509
653 138824146807207107
654 143673496481756423
655 148688468713998469
656 153874594539349420
657 159237585346513565
658 164783339162246869
659 170517946073126018
660 176447694893325496
661 182579078945626100
662 188918803135729370
663 195473790115089912
664 202251187786283716
665 209258375872141407
666 216502973878071023
667 223992848093035490
668 231736120036792189
669 239741173919735293
670 248016665604250171
671 256571530552618245
672 265414993333328228
673 274556576087573428
674 284006108613755971
675 293773737384861319
676 303869936245898390
677 314305516016972590
678 325091635840377469
679 336239813405808917
680 347761936986588898
681 359670276325574756
682 371977495401845690
683 384696664018791789
684 397841271344934335
685 411425238247676301
686 425462931655145997
687 439969177681594630
688 454959276859393034
689 470449018105482612
690 486454694875452862
691 502993120022865724
692 520081642931069575
693 537738165320218447
694 555981159415202687
695 574829684759149582
696 594303407479167377
697 614422618168055000
698 635208252313904884
699 656681909315305582
700 678865874144127755
701 701783137564138472
702 725457419100246496
703 749913188533983889
704 775175690257537814
705 801270966123801961
706 828225881267482132
707 856068148392805955
708 884826355148669374
709 914529989941370113
710 945209470956662149
711 976896173589905229
712 1009622461212636748
713 1043421714318833693
714 1078328363139173994
715 1114377918607226809
716 1151607006931443805
717 1190053402491078110
718 1229756064481642673
719 1270755171857699458
720 1313092162174101244
721 1356809768698947394
722 1401952061580955055
723 1448564487262955175
724 1496693912112535898
725 1546388664275050612
726 1597698579912480258
727 1650675047642264483
728 1705371057538694555
729 1761841248312282846
730 1820141959236125120
731 1880331280230553567
732 1942469106886124787
733 2006617193627084764
734 2072839212013595738
735 2141200807167468568
736 2211769659545908917
737 2284615544824723215
738 2359810399346779028
739 2437428383668333180
740 2517545951898194729
741 2600241919124587283
742 2685597534872517863
743 2773696554642310884
744 2864625317725563619
745 2958472823098936502
746 3055330811854052300
747 3155293847704005180
748 3258459404296223610
749 3364927950605244951
750 3474803043412782535
751 3588191417875074264
752 3705203085471894419
753 3825951430053199698
754 3950553311575050789
755 4079129167949080603
756 4211803124901229742
757 4348703103965098717
758 4489960938819894448
759 4635712489788072831
760 4786097767028099498
761 4941261051918823064
762 5101351027503821470
763 5266520907165700330
764 5436928572742755192
765 5612736710919229963
766 5794112959457774134
767 5981230051757462448
768 6174265971670450525
769 6373404106704146035
770 6578833411918523033
771 6790748572275723773
772 7009350176141365327
773 7234844887315045899
774 7467445628688345810
775 7707371764518753729
776 7954849294829876540
777 8210111048522997032
778 8473396889136767845
779 8744953919425929553
780 9025036699132306352
781 9313907461694541911
782 9611836344720631826
783 9919101619529811767
784 10235989935054314602
785 10562796560955919874
786 10899825645725272197
787 11247390474156072425
788 11605813740455227555
789 11975427820901542623
790 12356575062824148380
791 12749608073320948532
792 13154890025010529489
793 13572794961733361123
794 14003708122034988880
795 14448026262824536030
796 14906158001598989098
797 15378524159090221204
798 15865558121296314732
799 16367706202204523161
800 16885428026757083583
801 17419196914798133721
802 17969500286162704056
803 18536840067061887030
804 19121733118549582829
805 19724711666626392473
806 20346323755410662896
807 20987133702312694425
808 21647722577308625744
809 22328688684614123885
810 23030648069536995060
811 23754235028157306505
812 24500102643318752085
813 25268923323905657362
814 26061389371617762170
815 26878213551525262852
816 27720129691362367427
817 28587893285132966992
818 29482282126756732590
819 30404096948595908020
820 31354162091387082298
821 32333326179665701919
822 33342462830023001551
823 34382471365512167897
824 35454277564384924904
825 36558834415678091606
826 37697122910700960014
827 38870152842124992830
828 40078963640617716578
829 41324625219884299729
830 42608238860978129643
831 43930938105877488732
832 45293889692139753717
833 46698294497741364382
834 48145388528888517936
835 49636443918996336510
836 51172769972625982019
837 52755714221636454827
838 54386663528378396245
839 56067045202221299088
840 57798328165305059274
841 59582024132818537534
842 61419688844793397686
843 63312923313694296589
844 65263375125927335590
845 67272739760500016367
846 69342761964116492123
847 71475237144868190056
848 73672012825002264074
849 75934990113819488778
850 78266125242422197545
851 80667431120227046860
852 83140978956232409375
853 85688899903791007440
854 88313386773186827981
855 91016695769564803849
856 93801148301864553510
857 96669132819073985945
858 99623106720840356022
859 102665598297492347623
860 105799208747940759223
861 109026614229208411523
862 112350567987533625175
863 115773902523461970562
864 119299531842384833838
865 122930453741571756872
866 126669752186716866815
867 130520599727634876280
868 134486260007739738335
869 138570090315494511407
870 142775544234119323954
871 147106174336264735225
872 151565634981643123514
873 156157685162797286622
874 160886191458760115879
875 165755131040218256945
876 170768594787739953656
877 175930790465076815844
878 181246046010962625174
879 186718812889765510591
880 192353669566340042850
881 198155325043741204240
882 204128622531119693803
883 210278543178726438971
884 216610209949380468295
885 223128891561540205436
886 229840006575432915800
887 236749127555550555778
888 243861985383121724024
889 251184473649993561266
890 258722653209755628584
891 266482756815607701472
892 274471193923097729985
893 282694555585252870745
894 291159619520583735054
895 299873355279460018293
896 308842929591765132929
897 318075711819241887370
898 327579279597942637960
899 337361424592059337222
900 347430158447118337449
901 357793718861629846809
902 368460575867828615263
903 379439438238344666734
904 390739260112177882143
905 402369247754510238352
906 414338866546538765112
907 426657848117505680927
908 439336197718005791018
909 452384201744320433576
910 465812435515848329080
911 479631771212897812065
912 493853386079980316330
913 508488770799328967471
914 523549738142947493827
915 539048431805298299931
916 554997335528202122301
917 571409282417381735105
918 588297464565576372571
919 605675442878923418378
920 623557157224993109726
921 641956936796357852211
922 660889510811652167909
923 680370019445124566705
924 700414025110303427176
925 721037523985834597760
926 742256957912893429548
927 764089226549201425469
928 786551699912952422657
929 809662231198581614137
930 833439170001689830673
931 857901375831892273559
932 883068232055037062131
933 908959660140309759522
934 935596134357935014945
935 962998696799664904348
936 991188972872146831947
937 1020189187131962841320
938 1050022179616952151796
939 1080711422539116912026
940 1112281037498387330157
941 1144755813078976582453
942 1178161222992393571400
943 1212523444625199098469
944 1247869378160515823072
945 1284226666127633429153
946 1321623713553820689026
947 1360089708568859650851
948 1399654643641655543646
949 1440349337295532194375
950 1482205456486973179176
951 1525255539490408374008
952 1569533019479386993394
953 1615072248642640399390
954 1661908523031111442850
955 1710078107970273926203
956 1759618264239735330293
957 1810567274850156745534
958 1862964472625590346502
959 1916850268416888171414
960 1972266180160560507495
961 2029254862604270283025
962 2087860137919817908012
963 2148127027020220282398
964 2210101781808423868141
965 2273831918169578325098
966 2339366249941284290864
967 2406754923668973575564
968 2476049454387926714225
969 2547302762234197482119
970 2620569210133270228651
971 2695904642363732463795
972 2773366424252317304630
973 2853013482792516579054
974 2934906348450886976057
975 3019107197948042918537
976 3105679898286478449518
977 3194690051806902676650
978 3286205042553480341095
979 3380294083724255199778
980 3477028266495659966297
981 3576480609991853540393
982 3678726112696578346002
983 3783841805072636278202
984 3891906803695718682063
985 4003002366661946285641
986 4117211950585186212924
987 4234621268937624994700
988 4355318352059300964014
989 4479393608584090121760
990 4606939888617765282517
991 4738052548409535209696
992 4872829516862918392880
993 5011371363621132774211
994 5153781369083425901763
995 5300165596081191585507
996 5450632963581177384660
997 5605295322138190006955
998 5764267531475833494804
999 5927667539911107243723
1000 6095616466012998288248