0 0 1 1 2 2 3 3 4 4 5 5 6 726 7 5047 8 20168 9 60489 10 151210 11 332651 12 665292 13 1235533 14 2162174 15 3603615 16 5765776 17 8910737 18 13366098 19 19535059 20 27907220 21 39070101 22 53721382 23 72681863 24 96909144 25 127512025 26 165765626 27 213127227 28 271252828 29 342014429 30 427518030 31 530122351 32 652458272 33 797448993 34 968330914 35 1168675235 36 1402410276 37 1673844517 38 1987690358 39 2349088599 40 2763633640 41 3237399401 42 3776965962 43 4389446923 44 5082517484 45 5864443245 46 6744109726 47 7731052607 48 8835488688 49 10068347569 50 11441304050 51 12966811251 52 14658134452 53 16529385653 54 18595558854 55 20872566055 56 23377273976 57 26127541497 58 29142257818 59 32441381339 60 36045979260 61 39978267901 62 44261653742 63 48920775183 64 53981545024 65 59471193665 66 65418313026 67 71852901187 68 78806407748 69 86311779909 70 94403509270 71 103117679351 72 112492013832 73 122565925513 74 133380565994 75 144978876075 76 157405636876 77 170707521677 78 184933148478 79 200133133279 80 216360144080 81 233668955601 82 252116504722 83 271761946643 84 292666711764 85 314894563285 86 338511655526 87 363586592967 88 390190490008 89 418397031449 90 448282533690 91 479926006651 92 513409216412 93 548816748573 94 586236072334 95 625757605295 96 667474778976 97 711484105057 98 757885242338 99 806781064419 100 858277728100 101 912484742501 102 969515038902 103 1029485041303 104 1092514737704 105 1158727752105 106 1228251417226 107 1301216847947 108 1377759015468 109 1458016822189 110 1542133177310 111 1630255073151 112 1722533662192 113 1819124334833 114 1920186797874 115 2025885153715 116 2136387980276 117 2251868411637 118 2372504219398 119 2498477894759 120 2629976731320 121 2767192908601 122 2910323576282 123 3059570939163 124 3215142342844 125 3377250360125 126 3546112878126 127 3721953186127 128 3905000064128 129 4095487872129 130 4293656640130 131 4499752158851 132 4714026071172 133 4936735964293 134 5168145462614 135 5408524321335 136 5658148520776 137 5917300361417 138 6186268559658 139 6465348344299 140 6754841553740 141 7055056733901 142 7366309236862 143 7688921320223 144 8023222247184 145 8369548387345 146 8728243318226 147 9099657927507 148 9484150515988 149 9882086901269 150 10293840522150 151 10719792543751 152 11160331963352 153 11615855716953 154 12086768786554 155 12573484308155 156 13076423680476 157 13596016674397 158 14132701543118 159 14686925133039 160 15259142995360 161 15849819498401 162 16459427940642 163 17088450664483 164 17737379170724 165 18406714233765 166 19096966017526 167 19808654192087 168 20542308051048 169 21298466629609 170 22077678823370 171 22880503507851 172 23707509658732 173 24559276472813 174 25436393489694 175 26339460714175 176 27269088739376 177 28225898870577 178 29210523249778 179 30223604980979 180 31265798256180 181 32337768482101 182 33440192407622 183 34573758251943 184 35739165833464 185 36937126699385 186 38168364256026 187 39433613899867 188 40733623149308 189 42069151777149 190 43440971943790 191 44849868331151 192 46296638277312 193 47782091911873 194 49307052292034 195 50872355539395 196 52478850977476 197 54127401269957 198 55818882559638 199 57554184608119 200 59334210936200 201 61159878965001 202 63032120157802 203 64951880162603 204 66920118955404 205 68937810984205 206 71005945313726 207 73125525770847 208 75297571090768 209 77523115063889 210 79803206683410 211 82138910293651 212 84531305739092 213 86981488514133 214 89490569913574 215 92059677183815 216 94689953674776 217 97382558992537 218 100138669152698 219 102959476734459 220 105846191035420 221 108800038227101 222 111822261511182 223 114914121276463 224 118076895256544 225 121311878688225 226 124620384470626 227 128003743325027 228 131463303955428 229 135000433209829 230 138616516242230 231 142312956675351 232 146091176764072 233 149952617559593 234 153898739074314 235 157931020447435 236 162050960111276 237 166260075958317 238 170559905508958 239 174952006079999 240 179437954953840 241 184019349548401 242 188697807587762 243 193474967273523 244 198352487456884 245 203332047811445 246 208415349006726 247 213604112882407 248 218900082623288 249 224305022934969 250 229820720220250 251 235448982756251 252 241191640872252 253 247050547128253 254 253027576494254 255 259124626530255 256 265343617566976 257 271686492887297 258 278155218908418 259 284751785364739 260 291478205491460 261 298336516208901 262 305328778307542 263 312457076633783 264 319723520276424 265 327130242753865 266 334679402202026 267 342373181562987 268 350213788774348 269 358203456959309 270 366344444617470 271 374639035816351 272 383089540383632 273 391698294100113 274 400467658893394 275 409400023032275 276 418497801321876 277 427763435299477 278 437199393431078 279 446808171308679 280 456592291848280 281 466554305488601 282 476696790390522 283 487022352637243 284 497533626435164 285 508233274315485 286 519123987336526 287 530208485286767 288 541489516888608 289 552969860002849 290 564652321833890 291 576539739135651 292 588634978418212 293 600940936155173 294 613460538991734 295 626196743953495 296 639152538655976 297 652330941514857 298 665735001956938 299 679367800631819 300 693232449624300 301 707332092667501 302 721669905356702 303 736249095363903 304 751072902653104 305 766144599696305 306 781467491690226 307 797044916773747 308 812880246246068 309 828976884785589 310 845338270669510 311 861967875994151 312 878869206895992 313 896045803773433 314 913501241509274 315 931239129693915 316 949263112849276 317 967576870653437 318 986184118165998 319 1005088606054159 320 1024294120819520 321 1043804485025601 322 1063623557526082 323 1083755233693763 324 1104203445650244 325 1124972162496325 326 1146065390543126 327 1167487173543927 328 1189241592926728 329 1211332768027529 330 1233764856324330 331 1256542053671851 332 1279668594536972 333 1303148752234893 334 1326986839166014 335 1351187207053535 336 1375754247181776 337 1400692390635217 338 1426006108538258 339 1451699912295699 340 1477778353833940 341 1504246025842901 342 1531107562018662 343 1558367637306823 344 1586030968146584 345 1614102312715545 346 1642586471175226 347 1671488285917307 348 1700812641810588 349 1730564466448669 350 1760748730398350 351 1791370447448751 352 1822434674861152 353 1853946513619553 354 1885911108681954 355 1918333649232355 356 1951219368933476 357 1984573546180197 358 2018401504353718 359 2052708612076439 360 2087500283467560 361 2122781978399401 362 2158559202754442 363 2194837508683083 364 2231622494862124 365 2268919806753965 366 2306735136866526 367 2345074225013887 368 2383942858577648 369 2423346872769009 370 2463292150891570 371 2503784624604851 372 2544830274188532 373 2586435128807413 374 2628605266777094 375 2671346815830375 376 2714665953384376 377 2758568906808377 378 2803061953692378 379 2848151422116379 380 2893843690920380 381 2940145189975101 382 2987062400453422 383 3034601855102543 384 3082770138516864 385 3131573887411585 386 3181019790897026 387 3231114590753667 388 3281865081707908 389 3333278111708549 390 3385360582203990 391 3438119448420151 392 3491561719639112 393 3545694459478473 394 3600524786171434 395 3656059872847595 396 3712306947814476 397 3769273294839757 398 3826966253434238 399 3885393219135519 400 3944561643792400 401 4004479035850001 402 4065152960635602 403 4126591040645203 404 4188800955830804 405 4251790443888405 406 4315567300546726 407 4380139379856647 408 4445514594481368 409 4511700915987289 410 4578706375135610 411 4646539062174651 412 4715207127132892 413 4784718780112733 414 4855082291584974 415 4926305992684015 416 4998398275503776 417 5071367593394337 418 5145222461259298 419 5219971455853859 420 5295623216083620 421 5372186443304101 422 5449669901620982 423 5528082418191063 424 5607432883523944 425 5687730251784425 426 5768983541095626 427 5851201833842827 428 5934394276978028 429 6018570082325229 430 6103738526886430 431 6189908953148351 432 6277090769389872 433 6365293449990193 434 6454526535737714 435 6544799634139635 436 6636122419732276 437 6728504634392117 438 6821956087647558 439 6916486656991399 440 7012106288194040 441 7108824995617401 442 7206652862529562 443 7305600041420123 444 7405676754316284 445 7506893293099645 446 7609260019823726 447 7712787367032207 448 7817485838077888 449 7923366007442369 450 8030438521056450 451 8138714096621251 452 8248203523930052 453 8358917665190853 454 8470867455349654 455 8584063902414455 456 8698518087779976 457 8814241166553097 458 8931244367879018 459 9049538995268139 460 9169136426923660 461 9290048116069901 462 9412285591281342 463 9535860456812383 464 9660784392927824 465 9787069156234065 466 9914726580011026 467 10043768574544787 468 10174207127460948 469 10306054304058709 470 10439322247645670 471 10574023179873351 472 10710169401073432 473 10847773290594713 474 10986847307140794 475 11127403989108475 476 11269455954926876 477 11413015903397277 478 11558096614033678 479 11704710947404079 480 11852871845472480 481 12002592331941601 482 12153885512596322 483 12306764575647843 484 12461242792078564 485 12617333515987685 486 12775050184937526 487 12934406320300567 488 13095415527607208 489 13258091496894249 490 13422448003054090 491 13588498906184651 492 13756258151940012 493 13925739771881773 494 14096957883831134 495 14269926692221695 496 14444660488452976 497 14621173651244657 498 14799480646991538 499 14979596030119219 500 15161534443440500 501 15345310618512501 502 15530939375994502 503 15718435626006503 504 15907814368488504 505 16099090693560505 506 16292279781883226 507 16487396905019547 508 16684457425796668 509 16883476798668989 510 17084470570081710 511 17287454378835151 512 17492443956449792 513 17699455127532033 514 17908503810140674 515 18119606016154115 516 18332777851638276 517 18548035517215237 518 18765395308432598 519 18984873616133559 520 19206486926827720 521 19430251823062601 522 19656184983795882 523 19884303184768363 524 20114623298877644 525 20347162296552525 526 20581937246128126 527 20818965314221727 528 21058263766109328 529 21299849966102929 530 21543741377928530 531 21789955565104851 532 22038510191322772 533 22289423020825493 534 22542711918789414 535 22798394851705735 536 23056489887762776 537 23317015197229017 538 23579989052836858 539 23845429830167099 540 24113356008034140 541 24383786168871901 542 24656738999120462 543 24932233289613423 544 25210287935965984 545 25490921938963745 546 25774154404952226 547 26060004546227107 548 26348491681425188 549 26639635235916069 550 26933454742194550 551 27229969840273751 552 27529200278078952 553 27831165911842153 554 28135886706497354 555 28443382736076555 556 28753674184106476 557 29066781344005997 558 29382724619484318 559 29701524524939839 560 30023201685859760 561 30347776839220401 562 30675270833888242 563 31005704631021683 564 31339099304473524 565 31675476041194165 566 32014856141635526 567 32357261020155687 568 32702712205424248 569 33051231340828409 570 33402840184879770 571 33757560611621851 572 34115414611038332 573 34476424289462013 574 34840611869984494 575 35207999692866575 576 35578610215949376 577 35952466015066177 578 36329589784454978 579 36710004337171779 580 37093732605504580 581 37480797641388101 582 37871222616819222 583 38265030824273143 584 38662245677120264 585 39062890710043785 586 39466989579458026 587 39874566063927467 588 40285644064586508 589 40700247605559949 590 41118400834384190 591 41540128022429151 592 41965453565320912 593 42394401983365073 594 42826997921970834 595 43263266152075795 596 43703231570571476 597 44146919200729557 598 44594354192628838 599 45045561823582919 600 45500567498568600 601 45959396750655001 602 46422075241433402 603 46888628761447803 604 47359083230626204 605 47833464698712605 606 48311799345699726 607 48794113482262447 608 49280433550191968 609 49770786122830689 610 50265197905507810 611 50763695735975651 612 51266306584846692 613 51773057556031333 614 52283975887176374 615 52799088950104215 616 53318424251252776 617 53842009432116137 618 54369872269685898 619 54902040676893259 620 55438542703051820 621 55979406534301101 622 56524660494050782 623 57074333043425663 624 57628452781711344 625 58187048446800625 626 58750148915640626 627 59317783204680627 628 59889980470320628 629 60466770009360629 630 61048181259450630 631 61634243799541351 632 62224987350335672 633 62820441774740793 634 63420637078321114 635 64025603409751835 636 64635371061273276 637 65249970469145917 638 65869432214106158 639 66493787021822799 640 67123065763354240 641 67757299455606401 642 68396519261791362 643 69040756491886723 644 69690042603095684 645 70344409200307845 646 71003888036560726 647 71668511013502007 648 72338310181852488 649 73013317741869769 650 73693566043812650 651 74379087588406251 652 75069915027307852 653 75766081163573453 654 76467618952125054 655 77174561500218655 656 77886942067912976 657 78604794068538897 658 79328151069169618 659 80057046791091539 660 80791515110275860 661 81531590057850901 662 82277305820575142 663 83028696741310983 664 83785797319499224 665 84548642211634265 666 85317266231740026 667 86091704351846587 668 86871991702467548 669 87658163573078109 670 88450255412593870 671 89248302829850351 672 90052341594083232 673 90862407635409313 674 91678537045308194 675 92500766077104675 676 93329131146451876 677 94163668831815077 678 95004415874956278 679 95851409181419479 680 96704685821016680 681 97564283028314601 682 98430238203122122 683 99302588910978443 684 100181372883641964 685 101066628019579885 686 101958392384458526 687 102856704211634367 688 103761601902645808 689 104673124027705649 690 105591309326194290 691 106516196707153651 692 107447825249781812 693 108386234203928373 694 109331462990590534 695 110283551202409895 696 111242538604169976 697 112208465133294457 698 113181370900346138 699 114161296189526619 700 115148281459176700 701 116142367342277501 702 117143594646952302 703 118152004356969103 704 119167637632243904 705 120190535809344705 706 121220740401996226 707 122258293101585347 708 123303235777667268 709 124355610478472389 710 125415459431413910 711 126482825043596151 712 127557749902323592 713 128640276775610633 714 129730448612692074 715 130828308544534315 716 131933899884347276 717 133047266128097037 718 134168450955019198 719 135297498228132959 720 136434451994755920 721 137579356487019601 722 138732256122385682 723 139893195504162963 724 141062219422025044 725 142239372852528725 726 143424700959633126 727 144618249095219527 728 145820062799611928 729 147030187802098329 730 148248670021452730 731 149475555566457851 732 150710890736428572 733 151954722021736093 734 153207096104332814 735 154468059858277935 736 155737660350263776 737 157015944840142817 738 158302960781455458 739 159598755821958499 740 160903377804154340 741 162216874765820901 742 163539294940542262 743 164870686758240023 744 166211098845705384 745 167560580027131945 746 168919179324649226 747 170286945958856907 748 171663929349359788 749 173050179115303469 750 174445745075910750 751 175850677251018751 752 177265025861616752 753 178688841330384753 754 180122174282232754 755 181565075544840755 756 183017596149199476 757 184479787330151797 758 185951700526934918 759 187433387383723239 760 188924899750171960 761 190426289681961401 762 191937609441342042 763 193458911497680283 764 194990248528004924 765 196531673417554365 766 198083239260324526 767 199644999359617487 768 201217007228590848 769 202799316590807809 770 204391981380787970 771 205995055744558851 772 207608594040208132 773 209232650838436613 774 210867280923111894 775 212512539291822775 776 214168481156434376 777 215835161943643977 778 217512637295537578 779 219200963070147179 780 220900195342008780 781 222610390402721101 782 224331604761505022 783 226063895145763743 784 227807318501643664 785 229561931994595985 786 231327793009939026 787 233104959153421267 788 234893488251785108 789 236693438353331349 790 238504867728484390 791 240327834870358151 792 242162398495322712 793 244008617543571673 794 245866551179690234 795 247736258793223995 796 249617799999248476 797 251511234638939357 798 253416622780143438 799 255334024717950319 800 257263500975264800 801 259205112303380001 802 261158919682551202 803 263124984322570403 804 265103367663341604 805 267094131375456805 806 269097337360772726 807 271113047752988247 808 273141324918222568 809 275182231455594089 810 277235830197800010 811 279302184211696651 812 281381356798880492 813 283473411496269933 814 285578412076687774 815 287696422549444415 816 289827507160921776 817 291971730395157937 818 294129156974432498 819 296299851859852659 820 298483880251940020 821 300681307591218101 822 302892199558800582 823 305116622076980263 824 307354641309818744 825 309606323663736825 826 311871735788105626 827 314150944575838427 828 316444017163983228 829 318751020934316029 830 321072023513934830 831 323407092775854351 832 325756296839601472 833 328119704071811393 834 330497383086824514 835 332889402747284035 836 335295832164734276 837 337716740700219717 838 340152197964884758 839 342602273820574199 840 345067038380434440 841 347546562009515401 842 350040915325373162 843 352550169198673323 844 355074394753795084 845 357613663369436045 846 360168046679217726 847 362737616572291807 848 365322445193947088 849 367922604946217169 850 370538168488488850 851 373169208738111251 852 375815798871005652 853 378478012322276053 854 381155922786820454 855 383849604219942855 856 386559130837965976 857 389284577118844697 858 392026017802780218 859 394783527892834939 860 397557182655548060 861 400347057621551901 862 403153228586188942 863 405975771610129583 864 408814763019990624 865 411670279408954465 866 414542397637389026 867 417431194833468387 868 420336748393794148 869 423259135984017509 870 426198435539462070 871 429154725265747351 872 432128083639413032 873 435118589408543913 874 438126321593395594 875 441151359487020875 876 444193782655896876 877 447253670940552877 878 450331104456198878 879 453426163593354879 880 456538929018480880 881 459669481674607601 882 462817902781967922 883 465984273838629043 884 469168676621125364 885 472371193185092085 886 475591905865899526 887 478830897279288167 888 482088250322004408 889 485364048172437049 890 488658374291254490 891 491971312422042651 892 495302946591943612 893 498653361112294973 894 502022640579269934 895 505410869874518095 896 508818134165806976 897 512244518907664257 898 515690109842020738 899 519154992998854019 900 522639254696832900 901 526142981543962501 902 529666260438230102 903 533209178568251703 904 536771823413919304 905 540354282747048905 906 543956644632029226 907 547578997426471147 908 551221429781857868 909 554884030644195789 910 558566889254666110 911 562270095150277151 912 565993738164517392 913 569737908428009233 914 573502696369163474 915 577288192714834515 916 581094488490976276 917 584921675023298837 918 588769843937925798 919 592639087162052359 920 596529496924604120 921 600441165756896601 922 604374186493295482 923 608328652271877563 924 612304656535092444 925 616302293030424925 926 620321655811058126 927 624362839236537327 928 628425937973434528 929 632511046996013729 930 636618261586896930 931 640747677337730851 932 644899390149854372 933 649073496234966693 934 653270092115796214 935 657489274626770135 936 661731140914684776 937 665995788439376617 938 670283314974394058 939 674593818607669899 940 678927397742194540 941 683284151096689901 942 687664177706284062 943 692067576923186623 944 696494448417364784 945 700944892177220145 946 705419008510266226 947 709916898043806707 948 714438661725614388 949 718984400824610869 950 723554216931546950 951 728148211959683751 952 732766488145474552 953 737409148049247353 954 742076294555888154 955 746768030875524955 956 751484460544212476 957 756225687424617597 958 760991815706705518 959 765782949908426639 960 770599194876404160 961 775440655786622401 962 780307438145115842 963 785199647788658883 964 790117390885456324 965 795060773935834565 966 800029903772933526 967 805024887563399287 968 810045832808077448 969 815092847342707209 970 820166039338616170 971 825265517303415851 972 830391390081697932 973 835543766855731213 974 840722757146159294 975 845928470812698975 976 851161018054839376 977 856420509412541777 978 861707055766940178 979 867020768341042579 980 872361758700432980 981 877730138753974101 982 883126020754510822 983 888549517299574343 984 894000741332087064 985 899479806141068185 986 904986825362340026 987 910521912979235067 988 916085183323303708 989 921676751075022749 990 927296731264504590 991 932945239272207151 992 938622390829644512 993 944328302020098273 994 950063089279329634 995 955826869396292195 996 961619759513845476 997 967441877129469157 998 973293340095978038 999 979174266622237719 1000 985084775273881000