1 1 2 3 3 7 4 13 5 21 6 33 7 49 8 67 9 91 10 123 11 159 12 207 13 261 14 325 15 397 16 493 17 601 18 729 19 873 20 1035 21 1227 22 1443 23 1699 24 1987 25 2311 26 2695 27 3127 28 3613 29 4125 30 4701 31 5349 32 6117 33 6981 34 7953 35 8977 36 10129 37 11425 38 12883 39 14419 40 16147 41 18091 42 20139 43 22443 44 25035 45 27951 46 31023 47 34479 48 38367 49 42463 50 46837 51 51445 52 56629 53 62461 54 68605 55 75517 56 83293 57 91485 58 100233 59 109449 60 119817 61 131481 62 143769 63 156891 64 170715 65 186267 66 202651 67 220147 68 238579 69 259315 70 282643 71 307219 72 333463 73 361111 74 392215 75 424983 76 459975 77 496839 78 536205 79 577677 80 624333 81 673485 82 725973 83 781269 84 843477 85 909013 86 978997 87 1052725 88 1131457 89 1214401 90 1307713 91 1406017 92 1510993 93 1621585 94 1739683 95 1864099 96 1995171 97 2135139 98 2282595 99 2440059 100 2605947 101 2792571 102 2989179 103 3199131 104 3420315 105 3656511 106 3905343 107 4167487 108 4447423 109 4742335 110 5057263 111 5389039 112 5743333 113 6116581 114 6509797 115 6929701 116 7372069 117 7844461 118 8342125 119 8866413 120 9426285 121 10016109 122 10645965 123 11309517 124 12018105 125 12764601 126 13551033 127 14390841 128 15275577 129 16220361 130 17215689 131 18264265 132 19327147 133 20446891 134 21626539 135 22886251 136 24213355 137 25630531 138 27123523 139 28696387 140 30376003 141 32145475 142 34035043 143 36025699 144 38122851 145 40248615 146 42488103 147 44847399 148 47366823 149 50021031 150 52855383 151 55841367 152 58987095 153 62175741 154 65534973 155 69073917 156 72853053 157 76834365 158 81028669 159 85280197 160 89759173 161 94477765 162 99516613 163 104825029 164 110493733 165 116465701 166 122757157 167 129134449 168 135852913 169 142930801 170 150489073 171 158451697 172 166840305 173 175343361 174 184301313 175 193738497 176 203304435 177 213382131 178 223998963 179 235336371 180 247280307 181 259863219 182 272617803 183 286054731 184 300210507 185 315327051 186 331252299 187 348029515 188 365035627 189 382951531 190 401825899 191 420957775 192 441113167 193 462346831 194 485021647 195 508909519 196 534075343 197 559584511 198 586458367 199 614769919 200 643467733 201 673700821 202 705551317 203 739105749 204 773117973 205 808949781 206 846698517 207 884962269 208 925273053 209 967740381 210 1013090013 211 1060865757 212 1111197405 213 1162215741 214 1215963453 215 1272586557 216 1329982185 217 1390448361 218 1454149353 219 1521258217 220 1589282665 221 1660946281 222 1736443753 223 1812971257 224 1893592825 225 1978527481 226 2064620923 227 2155320187 228 2250871675 229 2351534971 230 2453571643 231 2561067067 232 2674313275 233 2789104531 234 2910036883 235 3037438867 236 3171656595 237 3307705491 238 3451032723 239 3602027667 240 3755082675 241 3916325811 242 4086195123 243 4258382007 244 4439780535 245 4630883511 246 4832210103 247 5036283447 248 5251274295 249 5477766711 250 5707349223 251 5949213927 252 6204017895 253 6462298221 254 6730733677 255 7002831469 256 7289485933 257 7591475821 258 7897585837 259 8220072109 260 8559810733 261 8904184501 262 9266981557 263 9649187509 264 10051840693 265 10459987381 266 10889969077 267 11342953909 268 11802118933 269 12285848341 270 12795456277 271 13312016929 272 13848887841 273 14393083425 274 14966392353 275 15570372129 276 16182592161 277 16827564705 278 17507041953 279 18195789489 280 18921383601 281 19685795505 282 20460636483 283 21265942851 284 22082236227 285 22942199619 286 23848169283 287 24766499331 288 25733958147 289 26753174019 290 27786295323 291 28860037147 292 29948428315 293 31095046171 294 32303005723 295 33527445787 296 34817390875 297 36176345371 298 37553840443 299 39005028667 300 40533852475 301 42083534431 302 43694147167 303 45326733919 304 47046660703 305 48858600031 306 50695260127 307 52630177759 308 54668609503 309 56734852111 310 58882335759 311 61059118095 312 63352353807 313 65676876741 314 68092795845 315 70541675973 316 73121566149 317 75839475141 318 78594465285 319 81496841733 320 84554489349 321 87653853261 322 90875078733 323 94140252237 324 97580105805 325 101203984461 326 104877304653 327 108747139917 328 112824003405 329 116956488621 330 121251455917 331 125605020589 332 130191492013 333 134840537881 334 139672376089 335 144570136345 336 149729916697 337 155165734681 338 160675714969 339 166480467865 340 172595763097 341 178794490921 342 185236941865 343 191767288873 344 198646996009 345 205620564811 346 212868322123 347 220214962507 348 227954633035 349 236108360011 350 244373330443 351 252963265035 352 261670394379 353 270843337227 354 280141428963 355 289805105379 356 299600625891 357 309920186595 358 320791822563 359 331811783139 360 343421288931 361 355651879395 362 368049335043 363 380934236931 364 393994930947 365 407754345219 366 421701482823 367 436196997447 368 450890278215 369 466369619271 370 482677073223 371 499207014087 372 516386883271 373 533801141959 374 552147027655 375 570743211127 376 590070563959 377 609661604983 378 630300726391 379 651221432797 380 672964704733 381 695004625885 382 718223637469 383 742684818397 384 767479729693 385 793249533469 386 819370921501 387 846889750045 388 874784025253 389 903775054501 390 933161616037 391 964120298149 392 996735206053 393 1029795087781 394 1064154826149 395 1098983343525 396 1135675114917 397 1172867481861 398 1211522187525 399 1250704269573 400 1291982512389 401 1333823925201 402 1377310469073 403 1421390311377 404 1467828334545 405 1516750696401 406 1566340518993 407 1617880126545 408 1670122902609 409 1725160559697 410 1780949110113 411 1838931168609 412 1897704291681 413 1959621655905 414 2022383775123 415 2087613590931 416 2153733354387 417 2222452831123 418 2292109865875 419 2365493408659 420 2439878142547 421 2517187553875 422 2595551717971 423 2678108203603 424 2761791029227 425 2848764116971 426 2936923801579 427 3029799847915 428 3127644571627 429 3226824216811 430 3329903431915 431 3434388984043 432 3544464298219 433 3656041399051 434 3772005516043 435 3889551762187 436 4013386490635 437 4138910729071 438 4269370360687 439 4401609887599 440 4539048841071 441 4678362910575 442 4825129996143 443 4973899463919 444 5128518286575 445 5285246614767 446 5450359586031 447 5617725237279 448 5791671412767 449 5967990781983 450 6153742874655 451 6342029232309 452 6537718679733 453 6736077970101 454 6942236400309 455 7151207504565 456 7371358132917 457 7594512334581 458 7826440568565 459 8061533060853 460 8309202517749 461 8560250994621 462 8821170257853 463 9085649311677 464 9360527218621 465 9639155357629 466 9932689528765 467 10230228464317 468 10539466109629 469 10852922766013 470 11183148708541 471 11517880011037 472 11865772362013 473 12218411100445 474 12589915285789 475 12966488001097 476 13357866895945 477 13754585476681 478 14166902337097 479 14584844545609 480 15025145802313 481 15471454205641 482 15935310673609 483 16405495658185 484 16900834571977 485 17402931525721 486 17924770052185 487 18453728159833 488 19003483973721 489 19560740251737 490 20125599324699 491 20712667666971 492 21307745538075 493 21926220828699 494 22553134141467 495 23213586026523 496 23883048631515 497 24578833333467 498 25284110810331 499 26027119181019 500 26780264611635 501 27563022401331 502 28356459562803 503 29181093283635 504 30016977700659 505 30897580214067 506 31790197020723 507 32717909956659 508 33658279925811 509 34648957753395 510 35653151660883 511 36696828713811 512 37754744929107 513 38854256556883 514 39968769112915 515 41098487258839 516 42272623943383 517 43462779685591 518 44699730266839 519 45953556892375 520 47274460662487 521 48613385872471 522 50004955276375 523 51415510230103 524 52901526971479 525 54407817832711 526 55973333412103 527 57560207735047 528 59209475176711 529 60881244010759 530 62575821229645 531 64337026256461 532 66122259869773 533 67977685741645 534 69858425679949 535 71839781335117 536 73848169150093 537 75935523255949 538 78051355686541 539 80250378942093 540 82479404054157 541 84738840346005 542 87087113715093 543 89467425199509 544 91941326362005 545 94448979613077 546 97090787153301 547 99768637573269 548 102551776381077 549 105372886288533 550 108344919771285 551 111357501493749 552 114488532652533 553 117662281298421 554 120960816181749 555 124304353849845 556 127693508287617 557 131215918341249 558 134786385567873 559 138497237311617 560 142258717188225 561 146221428498561 562 150238204128513 563 154412912340225 564 158644577201409 565 163042623712513 566 167500673936641 567 172019546520337 568 176716093258513 569 181476716227345 570 186424518552337 571 191439825054481 572 196523556711139 573 201807171791587 574 207162872631523 575 212729150247139 576 218371370062051 577 224315437027555 578 230340600472483 579 236602662790051 580 242950160081827 581 249547229848483 582 256234305184675 583 263012614060219 584 270057434167483 585 277198368620731 586 284620072108219 587 292143031861435 588 300068454482107 589 308102005742011 590 316451422165435 591 324914751887803 592 333710844910011 593 342626945358267 594 351664690525659 595 361057784002011 596 370579029939675 597 380474634589659 598 390505247593947 599 400672710907263 600 411239941068159 601 421951342748031 602 433083897979263 603 444368337609087 604 456256471540095 605 468306798429951 606 480830923065087 607 493525917648639 608 506720057181951 609 520094207854335 610 533650825605423 611 547740465819951 612 562022334726447 613 576865741701423 614 591911661207855 615 607162856177829 616 623013701419173 617 639080803938981 618 655779636785829 619 672706296230565 620 690298482274981 621 708130683171493 622 726206173506277 623 744992360458981 624 764034852334309 625 783826061634277 626 803887287642853 627 824222214269485 628 845356674591277 629 866779477951021 630 889044588413485 631 911613467673133 632 935389735535149 633 959490389314861 634 984538638585133 635 1009928627752237 636 1036316906818861 637 1063065208163629 638 1090178443665805 639 1118357724094861 640 1146921461907853 641 1176608275857805 642 1206700114870669 643 1237202504810617 644 1268904195293305 645 1301038400332921 646 1334436066026617 647 1368289384916089 648 1403473757004921 649 1439138158797945 650 1475289139467513 651 1512861513372921 652 1550946497123577 653 1590528915723513 654 1630651367740665 655 1671321220993929 656 1713590141637513 657 1756435748357001 658 1800965969281929 659 1846103727801225 660 1891857312711147 661 1939409848435179 662 1987611155994603 663 2037707654535147 664 2088487632869355 665 2141264191002603 666 2194760793692139 667 2248987264696491 668 2305345825554603 669 2362473301180587 670 2421846929080491 671 2482030607106219 672 2543035386986115 673 2606438767951491 674 2670707178030723 675 2737502509418115 676 2805209147197059 677 2875577891374723 678 2946906694960771 679 3019208656299907 680 3094353404110723 681 3170523371612035 682 3249688208811907 683 3329933112846211 684 3411272819352739 685 3495810660639907 686 3581501874078883 687 3670562315928739 688 3760837832967331 689 3852345002787175 690 3947450074235239 691 4043852689354087 692 4144045686435175 693 4245605643103591 694 4351158759370087 695 4458151964749159 696 4566604906757863 697 4679322028474087 698 4793576979726055 699 4912324235525863 700 5032691591577319 701 5154701151337111 702 5281507913267863 703 5410044733426327 704 5543635396201111 705 5679048671758999 706 5816309426488765 707 5957046914844093 708 6099704522016189 709 6244308444694461 710 6394597940316093 711 6546937875318717 712 6705267549718461 713 6865757357787069 714 7028436770800125 715 7197512453374461 716 7368894880252413 717 7547015763952125 718 7727566798029309 719 7910581137668997 720 8100791280565125 721 8293596510802821 722 8493982504964997 723 8697102418301829 724 8908208650834821 725 9122195061592965 726 9339100945610373 727 9564535189042821 728 9793045091546757 729 10030539603146373 730 10271274315249285 731 10515293434768869 732 10768906958630373 733 11025980598947301 734 11293161924496869 735 11563988475612645 736 11838509985072177 737 12119984961782833 738 12405300176127025 739 12694508021483569 740 12995087012726833 741 13299766882732081 742 13616426231531569 743 13937405847668785 744 14262764673694897 745 14600916038843569 746 14943680892599473 747 15299922659998897 748 15661024728153265 749 16027053407432641 750 16407473693224897 751 16793084153700289 752 17193856142024641 753 17600095968698305 754 18011878232887603 755 18434090697953587 756 18862063519469875 757 19295875287504691 758 19746743774369587 759 20203763579377459 760 20678752602576691 761 21160222026782515 762 21648260265821683 763 22155487313544691 764 22669634594178547 765 23203997245277683 766 23745650347509235 767 24294693366428299 768 24857643319849611 769 25428273748537995 770 26006689439251083 771 26607847421737611 772 27217207161748107 773 27850525859347083 774 28492485091621515 775 29143202743673739 776 29819505473971083 777 30505035181482891 778 31217518716281739 779 31939722852590475 780 32671780211149227 781 33432620782733739 782 34203841703684523 783 35005385680333227 784 35817865333680555 785 36641429862059151 786 37485854792191119 787 38341800435223695 788 39209423971293327 789 40111160945023119 790 41025200555038863 791 41975178601437327 792 42938117449848975 793 43914193927927311 794 44928648023373327 795 45956942584641039 796 47025667886839311 797 48108974091302415 798 49207060129140543 799 50332960035983167 800 51474220893359935 801 52631052274786111 802 53833368239759167 803 55052087719780159 804 56287434512348053 805 57554071907546005 806 58837990372094869 807 60139425676199317 808 61492031136794005 809 62863090551817621 810 64288057621415317 811 65732465894032789 812 67196580611150293 813 68718261754319317 814 70260703596220885 815 71863791549518293 816 73488750856212949 817 75135879912970141 818 76824729773234077 819 78536621059299229 820 80271868131438493 821 82075342078898077 822 83903421298929565 823 85803377391726493 824 87729255088549789 825 89681408044706461 826 91710316235598493 827 93766905358133917 828 95904355962530461 829 98070968371456669 830 100267140447132925 831 102518940260818173 832 104801461975571709 833 107115124738424061 834 109519756668370173 835 111957195628412157 836 114427889213547945 837 116961164003943849 838 119529000933041577 839 122131871541250473 840 124837082462439849 841 127579201292487081 842 130429135431682473 843 133317951976917417 844 136246181411152425 845 139289543697490473 846 142374427381293609 847 145580603287888425 848 148830521901277737 849 152124780014792121 850 155502479735319993 851 158926262307450297 852 162396756451728825 853 166003704346647993 854 169659862786710969 855 173365903164414651 856 177165815350008507 857 181017570743655099 858 184921876655968443 859 188979693037752507 860 193092871282823355 861 197367772491616443 862 201700997309468859 863 206093341460821371 864 210596941088191867 865 215161984517698939 866 219789310043403643 867 224598573903295867 868 229473451823379835 869 234414838993651411 870 239481388574443219 871 244617062432638675 872 249822803649056467 873 255233225491435219 874 260717463151529683 875 266417331429920467 876 272194964520390355 877 278051423388860371 878 284138147961536467 879 290307915329142739 880 296720267142332371 881 303220104369110995 882 309808620596139763 883 316564020037195507 884 323411585181456115 885 330352573470013171 886 337566469259851507 887 344878786139977459 888 352290866895384823 889 359890691266572535 890 367594202053865719 891 375402813878492407 892 383518446642060535 893 391744803132202231 894 400294605549788407 895 408961055185493239 896 417745743488198263 897 426752942742939255 898 435883029601953399 899 445137680653362807 900 454756208373147255 901 464505964213315191 902 474388738553858343 903 484521837715441959 904 494793185431832871 905 505204667864668455 906 516025511549425959 907 526993986869614887 908 538112108002725933 909 549511844559507501 910 561067110740447277 911 572780028477387309 912 584953477622739501 913 597293012357952045 914 610117715984331309 915 623117390437888557 916 636294422891946093 917 649805221774057581 918 663500352062578797 919 677382328639692909 920 691810120219369581 921 706434753979621485 922 721258915490436213 923 736458564232811637 924 751865585807398005 925 767482809456651381 926 783714074983787637 927 800166787964071029 928 817266392799243381 929 834599292070653045 930 852168668676063093 931 870183067185545077 932 888443240903573365 933 906952543006392181 934 926189598445961077 935 945689110126296949 936 965454658807383253 937 985720857130550485 938 1006263552563332309 939 1027086517429003477 940 1048728204798518485 941 1070665155438896341 942 1092901397705118433 943 1115700870818681569 944 1138811403180561121 945 1162237238654441185 946 1186584136945145569 947 1211263206415570657 948 1236912613668329185 949 1262911962575443681 950 1289266027483558753 951 1316287625247781729 952 1343677885824824161 953 1371441838979052385 954 1400297422138405729 955 1429546689658909537 956 1459195012680538993 957 1489594310165289841 958 1520408353314462577 959 1551642800612969329 960 1584105331667241841 961 1617010757627808625 962 1650365121027141763 963 1684564330697486467 964 1719230129240305795 965 1754368882451125891 966 1790397679470089859 967 1826918026906146435 968 1863936631111784067 969 1902410741990921859 970 1941409765351593603 971 1980940862713766211 972 2021473259360100675 973 2062558650225664323 974 2104204579957006659 975 2147487954696036675 976 2191361855976792387 977 2235834340509236571 978 2281433286736362843 979 2327654351460121947 980 2374506022407882075 981 2423199818989290843 982 2472557957930141019 983 2523856772435658075 984 2575855470249887067 985 2628563600066117211 986 2682606795594563163 987 2737387316748648027 988 2792915223057104475 989 2850626389375811163 990 2909124924416818779 991 2968421570460077691 992 3029220165429579387 993 3090848251727924859 994 3153317146324938363 995 3218242208433483387 996 3284053060354616955 997 3350761787153283231 998 3419160206493972639 999 3488491803579611295 1000 3558769310001251487