1 0 2 1 3 1 4 1 5 2 6 2 7 3 8 4 9 4 10 7 11 6 12 10 13 11 14 13 15 18 16 19 17 25 18 30 19 33 20 45 21 47 22 61 23 70 24 81 25 100 26 111 27 135 28 157 29 177 30 218 31 238 32 288 33 328 34 374 35 443 36 495 37 579 38 663 39 747 40 878 41 973 42 1134 43 1281 44 1448 45 1670 46 1863 47 2135 48 2414 49 2705 50 3103 51 3445 52 3929 53 4407 54 4940 55 5601 56 6230 57 7036 58 7880 59 8783 60 9918 61 10985 62 12360 63 13769 64 15325 65 17178 66 19025 67 21264 68 23643 69 26207 70 29271 71 32313 72 36004 73 39867 74 44114 75 49024 76 54057 77 59952 78 66254 79 73070 80 80965 81 89041 82 98480 83 108488 84 119434 85 131836 86 144780 87 159573 88 175444 89 192632 90 212112 91 232402 92 255549 93 280247 94 307154 95 337222 96 368928 97 404551 98 442846 99 484289 100 530557 101 579290 102 633940 103 692449 104 755993 105 826257 106 900809 107 983570 108 1072567 109 1168752 110 1275001 111 1387630 112 1512406 113 1646207 114 1791091 115 1950034 116 2119302 117 2305496 118 2505646 119 2721630 120 2958299 121 3210104 122 3486606 123 3783195 124 4103508 125 4452777 126 4825431 127 5232503 128 5669754 129 6140749 130 6653687 131 7200529 132 7796932 133 8436421 134 9125455 135 9873107 136 10671452 137 11538816 138 12469458 139 13470114 140 14554649 141 15711833 142 16967228 143 18312299 144 19758431 145 21321349 146 22990441 147 24795886 148 26730645 149 28807315 150 31049253 151 33441679 152 36026227 153 38792547 154 41760795 155 44958186 156 48371559 157 52050509 158 55987850 159 60206754 160 64746673 161 69589800 162 74803719 163 80377903 164 86348042 165 92760996 166 99602732 167 106954654 168 114812443 169 123218404 170 132239309 171 141856753 172 152180509 173 163204282 174 174990986 175 187621261 176 201085014 177 215515580 178 230918673 179 247370858 180 264985061 181 283749126 182 303841560 183 325269977 184 348145091 185 372605459 186 398655768 187 426514552 188 456212426 189 487886461 190 521727875 191 557746092 192 596231510 193 637225795 194 680923101 195 727560695 196 777180847 197 830141978 198 886528422 199 946583611 200 1010631342 201 1078733515 202 1151363428 203 1228635828 204 1310889259 205 1398529089 206 1491679690 207 1590928912 208 1696469340 209 1808729684 210 1928257358 211 2055226622 212 2190410026 213 2334067718 214 2486787086 215 2649258566 216 2821771493 217 3005290582 218 3200216147 219 3407296465 220 3627455544 221 3861090894 222 4109464397 223 4373113010 224 4653049978 225 4950446423 226 5265907523 227 5601016625 228 5956558461 229 6333828712 230 6734383197 231 7159041626 232 7609866481 233 8087904062 234 8594890770 235 9132805081 236 9702835374 237 10307578510 238 10948513082 239 11627864877 240 12348244417 241 13111244175 242 13920235039 243 14777175963 244 15685023724 245 16647105618 246 17665657281 247 18744933840 248 19887639931 249 21097568623 250 22379083821 251 23735156253 252 25171290348 253 26691048367 254 28299432132 255 30002009166 256 31802856978 257 33708936953 258 35725081695 259 37857706636 260 40114075694 261 42499566762 262 45023156180 263 47691175264 264 50512028113 265 53494983452 266 56647301508 267 59980345747 268 63502589315 269 67224803200 270 71159021381 271 75314757110 272 79706619644 273 84345652986 274 89245884758 275 94422663706 276 99888667117 277 105662395880 278 111758471648 279 118194847331 280 124991362063 281 132164532249 282 139738073566 283 147730952859 284 156166430735 285 165069785021 286 174462797333 287 184375496795 288 194832770389 289 205864334580 290 217502729680 291 229776184164 292 242723082114 293 256375563459 294 270771948102 295 285953638352 296 301957545124 297 318832239918 298 336619577455 299 355368414932 300 375131845216 301 395957473926 302 417907217052 303 441034899367 304 465403250511 305 491079709905 306 518126075602 307 546620618227 308 576632981217 309 608242965439 310 641536741422 311 676593661942 312 713513231708 313 752384656080 314 793309987919 315 836398472986 316 881752479526 317 929497636241 318 979748712653 319 1032635229756 320 1088296304234 321 1146862842646 322 1208494132423 323 1273336632495 324 1341555364499 325 1413326335031 326 1488817500394 327 1568229662473 328 1651750306756 329 1739588368873 330 1831967257544 331 1929100927130 332 2031243320731 333 2138632842435 334 2251534769409 335 2370231144731 336 2494995145156 337 2626146357479 338 2763988596703 339 2908856910163 340 3061108200551 341 3221089209816 342 3389203071898 343 3565834814250 344 3751408443532 345 3946373530244 346 4151170861046 347 4366306861608 348 4592270190137 349 4829595054790 350 5078848683915 351 5340588667784 352 5615452227389 353 5904056667661 354 6207075940144 355 6525222937221 356 6859203669963 357 7209817101250 358 7577843742878 359 7964130638292 360 8369574719142 361 8795066217991 362 9241607992340 363 9710183030983 364 10201856808250 365 10717754034261 366 11258997793870 367 11826843015284 368 12422528266721 369 13047389428999 370 13702837737668 371 14390285027549 372 15111302709359 373 15867446118344 374 16660390913476 375 17491902710068 376 18363756613095 377 19277915066278 378 20236331460035 379 21241101709855 380 22294435468134 381 23398557774092 382 24555920223993 383 25768968977146 384 27040325982036 385 28372749553199 386 29769028443739 387 31232218097112 388 32765381410485 389 34371790249471 390 36054887954395 391 37818160503234 392 39665416191605 393 41600480352851 394 43627435492291 395 45750570410386 396 47974241364831 397 50303185010878 398 52742177489994 399 55296301578101 400 57970898220232 401 60771398456803 402 63703692823609 403 66773731118826 404 69987839760409 405 73352656547808 406 76874949513479 407 80562030307782 408 84421307535283 409 88460640012840 410 92688274595341 411 97112627841773 412 101742772690516 413 106587915621650 414 111657815052707 415 116962698297419 416 122513026265195 417 128320038131641 418 134395168286877 419 140750512322322 420 147398747932696 421 154352852549441 422 161626742981803 423 169234594851565 424 177191392991286 425 185512826557521 426 194214984787359 427 203315072973461 428 212830654141061 429 222780262362739 430 233183303099804 431 244059689648243 432 255430681949810 433 267318003906654 434 279744565936098 435 292734333645578 436 306311936343721 437 320503606118816 438 335336195136293 439 350837981255527 440 367038543793058 441 383968297607513 442 401659590880365 443 420145564365350 444 439461098175774 445 459642649046292 446 480727749061404 447 502756234862975 448 525768978867534 449 549808945526473 450 574921038361684 451 601151505824584 452 628549375296446 453 657164984129585 454 687051218226209 455 718263312741412 456 750858213580648 457 784896183459600 458 820439169793633 459 857552187305407 460 896303132528069 461 936762030065108 462 979002902601172 463 1023101886270428 464 1069138848553261 465 1117197147662267 466 1167362823808163 467 1219726694165311 468 1274382261261913 469 1331427520221572 470 1390964737929773 471 1453099502135065 472 1517943156406595 473 1585610391224535 474 1656221354659012 475 1729901367037937 476 1806779902727085 477 1886993318817536 478 1970682185014289 479 2057993643010004 480 2149081149766629 481 2244103285207529 482 2343226918578555 483 2446624141235394 484 2554475017315086 485 2666967253026269 486 2784294923083573 487 2906662020361158 488 3034279060785113 489 3167366160374557 490 3306152746359875 491 3450876072139531 492 3601785330057750 493 3759137761625979 494 3923202239134814 495 4094258894045799 496 4272597535729965 497 4458522264101807 498 4652347170474899 499 4854400347419102 500 5065023578581876 501 5284570502841368 502 5513411951450145 503 5751931035640811 504 6000527807148583 505 6259618859046314 506 6529635378588170 507 6811029135884925 508 7104267063690621 509 7409836479769107 510 7728244778049210 511 8060017178491126 512 8405703647949944 513 8765872723610608 514 9141117574885267 515 9532055604241609 516 9939326072161376 517 10363597867243935 518 10805562703984527 519 11265941921763403 520 11745486218673299 521 12244972920791849 522 12765214951894458 523 13307053103944138 524 13871363919993941 525 14459059345047782 526 15071083861400815 527 15708424565389143 528 16372102672821006 529 17063182369357571 530 17782770656979841 531 18532014078739426 532 19312110340167905 533 20124298685279051 534 20969870147474735 535 21850167335213765 536 22766581022946864 537 23720563215931928 538 24713616599036512 539 25747306058208670 540 26823258753059672 541 27943160244444403 542 29108769549648657 543 30321907225654615 544 31584468702384398 545 32898424340160847 546 34265815439830288 547 35688771181104657 548 37169495593545982 549 38710282559501326 550 40313516291435740 551 41981666834886546 552 43717309573717716 553 45523110564516893 554 47401843886342126 555 49356392184899225 556 51389742101945236 557 53505006239200789 558 55705407174412711 559 57994297007552523 560 60375158517383549 561 62851600059753078 562 65427380845937366 563 68106393017232761 564 70892684235345815 565 73790459043218071 566 76804073777602533 567 79938065060182602 568 83197130332899147 569 86586153340862669 570 90110206382949563 571 93774544706725034 572 97584639284880685 573 101546155075505520 574 105664980460624299 575 109947229920969204 576 114399238601098903 577 119027599288849951 578 123839138911855117 579 128840951789677677 580 134040403596909820 581 139445125487388981 582 145063056622364815 583 150902418041879219 584 156971751066142091 585 163279922023958320 586 169836116807059159 587 176649888903497478 588 183731131297103689 589 191090119903830705 590 198737520158548793 591 206684381306990801 592 214942191636029629 593 223522847402999404 594 232438702987764467 595 241702578763114737 596 251327756231923191 597 261328040477842864 598 271717726964320503 599 282511658343523491 600 293725234997041526 601 305374410248188409 602 317475762164129422 603 330046457081197460 604 343104315190731618 605 356667823137011144 606 370756130718367254 607 385389132173522081 608 400587427519708065 609 416372396952247160 610 432766217265834082 611 449791859209391911 612 467473180946325272 613 485834885915903204 614 504902608727555234 615 524702934778477431 616 545263400074783243 617 566612597168628322 618 588780130955955518 619 611796716258092122 620 635694202893951680 621 660505577092365506 622 686265083309633074 623 713008176538069901 624 740771634973327087 625 769593589942867831 626 799513531244022528 627 830572445400959504 628 862812766332812485 629 896278503541745471 630 931015279795714054 631 967070339522893537 632 1004492707826579897 633 1043333137977748800 634 1083644259444363730 635 1125480622826933188 636 1168898714328364383 637 1213957136464627931 638 1260716554813784935 639 1309239866686453235 640 1359592257048442936 641 1411841218277600909 642 1466056758063841798 643 1522311343823892688 644 1580680097522324785 645 1641240862279966998 646 1704074231339365659 647 1769263784643329786 648 1836896034129197483 649 1907060646040004912 650 1979850523049916251 651 2055361841846851698 652 2133694325398900158 653 2214951187575196841 654 2299239389992961274 655 2386669739715279017 656 2477356940566431587 657 2571419903365808238 658 2668981694141702985 659 2770169827638861348 660 2875116386861722637 661 2983958087905734925 662 3096836637129293037 663 3213898681594675486 664 3335296148275352914 665 3461186386086301170 666 3591732250928848972 667 3727102513204665081 668 3867471816169842253 669 4013021064092326866 670 4163937594945442883 671 4320415286087481320 672 4482655023631447211 673 4650864667766994973 674 4825259501501632143 675 5006062435575422638 676 5193504143576832988 677 5387823598158142791 678 5589268050926953678 679 5798093546622170804 680 6014565170944122271 681 6238957216546783369 682 6471553800922438956 683 6712648860688787792 684 6962546746217018084 685 7221562515325587518 686 7490022141754243552 687 7768263221926734661 688 8056634993825821983 689 8355499019181190880 690 8665229537058205196 691 8986213717822329443 692 9318852477922656587 693 9663560524466087593 694 10020767144409869872 695 10390916623054356667 696 10774468558843878622 697 11171898796469560898 698 11583699510840214125 699 12010380113544081982 700 12452467754711072622 701 12910507704007805898 702 13385064426850015509 703 13876721710913666918 704 14386083715117665688 705 14913775562863696772 706 15460443809572179419 707 16026757676582894242 708 16613409238645029799 709 17221114630079039260 710 17850614753760675702 711 18502675844000791108 712 19178090890329248608 713 19877679892207506297 714 20602291255250832879 715 21352802628274902384 716 22130121588558247360 717 22935187275987998585 718 23768970739850472599 719 24632476545855258140 720 25526743773471118848 721 26452846837354292411 722 27411897373779465941 723 28405044690359421209 724 29433477626799348101 725 30498425730967548511 726 31601160252487093604 727 32742996310036119447 728 33925293477533858828 729 35149457927748165307 730 36416943829812253483 731 37729254535874526857 732 39087945083991816785 733 40494622938358505704 734 41950950471948180629 735 43458646612550239316 736 45019488270479085628 737 46635313216741212434 738 48308021022581246396 739 50039575921788186529 740 51832008761957984437 741 53687418704207607068 742 55607976548212953088 743 57595925898323837780 744 59653586479216535362 745 61783356431521929169 746 63987714347632730818 747 66269223098433093299 748 68630531287117096610 749 71074377074561358536 750 73603590894709650744 751 76221097871513080466 752 78929922241220149649 753 81733189134903641177 754 84634129010378595385 755 87636080843247995712 756 90742495010619135584 757 93956938384378941443 758 97283096524979817949 759 100724778797741427551 760 104285922139907336874 761 107970594475804876143 762 111783000604398521050 763 115727484864710808021 764 119808537063967277167 765 124030796899729743169 766 128399058021025791346 767 132918274813571619024 768 137593565648262229667 769 142430219728185880543 770 147433702299525219782 771 152609659450488344447 772 157963925956408105612 773 163502529198746464594 774 169231697099009744979 775 175157864229334840136 776 181287677502436480722 777 187628005217837129450 778 194185941801741622563 779 200968816974463952394 780 207984202938916567423 781 215239921090816020204 782 222744052479749540933 783 230504943494929550159 784 238531216487932902735 785 246831778193626887952 786 255415827665638705904 787 264292868344667658541 788 273472714892864548132 789 282965505472039520731 790 292781711634699403790 791 302932147665308704325 792 313427984537732285462 793 324280758075088117740 794 335502383176508132316 795 347105165392313194867 796 359101811945368350505 797 371505447839033035613 798 384329625615655310473 799 397588341804317067870 800 411296050497179829627 801 425467676301476875680 802 440118632970152939400 803 455264835007024253275 804 470922716723101232799 805 487109248109012601846 806 503841950084591336512 807 521138916006373358955 808 539018825487149770128 809 557500966430646239652 810 576605253622914888384 811 596352246625305868677 812 616763174650613014179 813 637859952942324681464 814 659665208300565795966 815 682202300796981972066 816 705495344801827895403 817 729569237707554790976 818 754449679362287774686 819 780163201587655038951 820 806737193581176561044 821 834199926552413471189 822 862580586944200523046 823 891909299398105959976 824 922217160943187973185 825 953536270638541570902 826 985899758474453709659 827 1019341823737155885008 828 1053897762170600801523 829 1089604005512318598237 830 1126498156128135201109 831 1164619020827865370727 832 1204006655233587404493 833 1244702395795179209141 834 1286748905572499074778 835 1330190214614590237701 836 1375071759566174484216 837 1421440434908929100648 838 1469344630722226387747 839 1518834285622907849451 840 1569960933891225765189 841 1622777751753043814996 842 1677339616631891279504 843 1733703151555318506127 844 1791926786443216405452 845 1852070813001274396038 846 1914197438848646527347 847 1978370855949042791057 848 2044657292857488973739 849 2113125085582747120559 850 2183844741583345328787 851 2256889002942132962853 852 2332332925481802050123 853 2410253940080052361771 854 2490731934683397702581 855 2573849328786690560036 856 2659691147214916643484 857 2748345111490004359730 858 2839901711813794728640 859 2934454301878262517513 860 3032099185605798773240 861 3132935703164279868347 862 3237066336576869712888 863 3344596794041271682573 864 3455636119624968989150 865 3570296794129308086915 866 3688694835417444578789 867 3810949920364934994961 868 3937185483653650801951 869 4067528844556036469432 870 4202111324287248948465 871 4341068362840398014070 872 4484539659912602451435 873 4632669290432803946452 874 4785605851199983169422 875 4943502597230508032532 876 5106517577869789487619 877 5274813799497795170539 878 5448559360646154782060 879 5627927621438021563234 880 5813097362073309988325 881 6004252941170434515395 882 6201584483735497324083 883 6405288038918412833440 884 6615565775913338771416 885 6832626167947825491013 886 7056684176538376865181 887 7287961468465260092637 888 7526686599975599526930 889 7773095243080064188038 890 8027430399219837625949 891 8289942613401868661274 892 8560890224785249701223 893 8840539581436436164346 894 9129165301861876742938 895 9427050522862012907918 896 9734487148441788217224 897 10051776138994551693202 898 10379227761681191719501 899 10717161892445062010133 900 11065908303591594467187 901 11425806952786871932983 902 11797208316925023124171 903 12180473683642667628065 904 12575975500214138808055 905 12984097706884911051177 906 13405236072457569444933 907 13839798579476357759674 908 14288205763623362047275 909 14750891116476619967372 910 15228301471939988364479 911 15720897395518506719496 912 16229153628857244384157 913 16753559484400665922842 914 17294619310466487382306 915 17852852938815154290181 916 18428796136233988263073 917 19023001117243487725192 918 19636037002982357193854 919 20268490357876562603278 920 20920965708073332797954 921 21594086064808688133270 922 22288493515888566246496 923 23004849758663196921476 924 23743836719451438078096 925 24506157153551144582208 926 25292535251808792221934 927 26103717322567700270444 928 26940472410623009983869 929 27803593011715190363502 930 28693895766984101423196 931 29612222165356485282033 932 30559439329951398809164 933 31536440736168505684942 934 32544147035974332871032 935 33583506861040908002549 936 34655497636061769583201 937 35761126485105375185710 938 36901431064593758913276 939 38077480513699001665470 940 39290376383174341378525 941 40541253576366687744904 942 41831281393956222146745 943 43161664499328910786997 944 44533644014493022767452 945 45948498593503420498012 946 47407545511144848894187 947 48912141866553643704669 948 50463685701837296797287 949 52063617265103981740967 950 53713420250937701785481 951 55414623059000712744735 952 57168800180819225360494 953 58977573494899547900439 954 60842613722437322355713 955 62765641859888416544510 956 64748430633864539835656 957 66792806098165801116806 958 68900649132956402758834 959 71073897121689302471908 960 73314545605395530536098 961 75624649963344251454838 962 78006327252273959314729 963 80461757940454225174831 964 82993187839473724633445 965 85602930013382955426198 966 88293366719904300781794 967 91066951527602894914179 968 93926211321220907145720 969 96873748525990257089679 970 99912243310661167977630 971 103044455828239525895299 972 106273228653106415158616 973 109601489098427972592669 974 113032251777237447684629 975 116568621143122401873526 976 120213794076317981240437 977 123971062687883247510694 978 127843816997162102236883 979 131835547879276291068437 980 135949849994847888048418 981 140190424772919504819208 982 144561083637371382174099 983 149065751098353542778873 984 153708468144315851304518 985 158493395618508166314701 986 163424817659037660984345 987 168507145409540777347215 988 173744920587765283042791 989 179142819387488184999154 990 184705656369346192352502 991 190438388425899833428675 992 196346119048986660301015 993 202434102446595701151791 994 208707748030965746052501 995 215172624899809752876796 996 221834466405665310422694 997 228699175061467247787815 998 235772827288814082833841 999 243061678578172040905828 1000 250572168649220298710388