0 1 1 1 2 1 3 2 4 3 5 3 6 4 7 6 8 7 9 8 10 10 11 12 12 14 13 16 14 20 15 23 16 26 17 30 18 36 19 41 20 47 21 55 22 64 23 73 24 83 25 96 26 111 27 125 28 144 29 165 30 187 31 211 32 241 33 272 34 306 35 346 36 391 37 439 38 493 39 553 40 622 41 695 42 779 43 871 44 974 45 1086 46 1211 47 1348 48 1502 49 1671 50 1857 51 2061 52 2288 53 2533 54 2808 55 3107 56 3439 57 3800 58 4199 59 4634 60 5113 61 5634 62 6208 63 6838 64 7525 65 8270 66 9094 67 9988 68 10965 69 12026 70 13196 71 14461 72 15839 73 17342 74 18983 75 20758 76 22694 77 24804 78 27096 79 29574 80 32281 81 35209 82 38390 83 41832 84 45579 85 49632 86 54023 87 58774 88 63927 89 69494 90 75522 91 82039 92 89095 93 96704 94 104941 95 113823 96 123426 97 133778 98 144968 99 157027 100 170036 101 184053 102 199173 103 215449 104 232993 105 251880 106 272224 107 294095 108 317660 109 342977 110 370218 111 399495 112 430987 113 464797 114 501132 115 540154 116 582062 117 627017 118 675295 119 727080 120 782644 121 842196 122 906093 123 974546 124 1047922 125 1126521 126 1210754 127 1300926 128 1397492 129 1500852 130 1611502 131 1729846 132 1856488 133 1991925 134 2136786 135 2291598 136 2457139 137 2634008 138 2823011 139 3024880 140 3240544 141 3470786 142 3716632 143 3979029 144 4259107 145 4557885 146 4876700 147 5216713 148 5579364 149 5965963 150 6378184 151 6817475 152 7285661 153 7784466 154 8315905 155 8881869 156 9484654 157 10126422 158 10809680 159 11536836 160 12310811 161 13134265 162 14010378 163 14942210 164 15933365 165 16987204 166 18107698 167 19298754 168 20564787 169 21910068 170 23339579 171 24858183 172 26471351 173 28184468 174 30003787 175 31935327 176 33985903 177 36162318 178 38472294 179 40923308 180 43523861 181 46282510 182 49208718 183 52311871 184 55602555 185 59091369 186 62789992 187 66710149 188 70865009 189 75267629 190 79932488 191 84874230 192 90109032 193 95653083 194 101524286 195 107740850 196 114322624 197 121289699 198 128664226 199 136468611 200 144727311 201 153465198 202 162709558 203 172487979 204 182830552 205 193768079 206 205333966 207 217562197 208 230489801 209 244154715 210 258597836 211 273861028 212 289989784 213 307030615 214 325033621 215 344050307 216 364136388 217 385348821 218 407748960 219 431400109 220 456370226 221 482729038 222 510551668 223 539915615 224 570903692 225 603601297 226 638100229 227 674495013 228 712886640 229 753379539 230 796085547 231 841119889 232 888605631 233 938670296 234 991449764 235 1047084420 236 1105724147 237 1167524156 238 1232649472 239 1301271003 240 1373570971 241 1449737868 242 1529972032 243 1614481320 244 1703486671 245 1797216906 246 1895914974 247 1999833245 248 2109239211 249 2224410280 250 2345640935 251 2473236830 252 2607521538 253 2748831179 254 2897522010 255 3053963709 256 3218547390 257 3391679799 258 3573791153 259 3765328145 260 3966763121 261 4178587522 262 4401320156 263 4635500266 264 4881697759 265 5140505337 266 5412548050 267 5698476320 268 5998976768 269 6314763163 270 6646588054 271 6995235047 272 7361529959 273 7746331766 274 8150545596 275 8575114113 276 9021029501 277 9489324378 278 9981086382 279 10497447776 280 11039599517 281 11608781907 282 12206300024 283 12833512385 284 13491847255 285 14182792755 286 14907912844 287 15668835928 288 16467273405 289 17305008262 290 18183912839 291 19105937178 292 20073129807 293 21087624421 294 22151660342 295 23267570777 296 24437804771 297 25664912983 298 26951571400 299 28300568661 300 29714829293 301 31197399625 302 32751474547 303 34380383069 304 36087614197 305 37876802906 306 39751759846 307 41716454692 308 43775046151 309 45931867748 310 48191459461 311 50558550347 312 53038093145 313 55635248984 314 58355421108 315 61204238376 316 64187593894 317 67311627712 318 70582764914 319 74007699291 320 77593436191 321 81347273059 322 85276843384 323 89390100458 324 93695363262 325 98201297075 326 102916963421 327 107851803053 328 113015685784 329 118418892155 330 124072169738 331 129986713917 332 136174224379 333 142646887758 334 149417439724 335 156499144435 336 163905859118 337 171652017590 338 179752697475 339 188223600413 340 197081125859 341 206342353797 342 216025118878 343 226147993103 344 236730368251 345 247792437497 346 259355279501 347 271440843214 348 284072039334 349 297272721309 350 311067781984 351 325483140200 352 340545840627 353 356284037894 354 372727106004 355 389905625936 356 407851496316 357 426597922333 358 446179538426 359 466632395894 360 487994089339 361 510303749890 362 533602181311 363 557931850135 364 583337029975 365 609863799448 366 637560191998 367 666476192379 368 696663900549 369 728177532904 370 761073590005 371 795410861744 372 831250611105 373 868656579564 374 907695177840 375 948435500309 376 990949529563 377 1035312148891 378 1081601360389 379 1129898308445 380 1180287506857 381 1232856863919 382 1287697929827 383 1344905928903 384 1404580015226 385 1466823313588 386 1531743197218 387 1599451330923 388 1670063962691 389 1743701980943 390 1820491225423 391 1900562546285 392 1984052136573 393 2071101607503 394 2161858335694 395 2256475545655 396 2355112686788 397 2457935527241 398 2565116546643 399 2676835046235 400 2793277573475 401 2914638038460 402 3041118162599 403 3172927618286 404 3310284505414 405 3453415499605 406 3602556362874 407 3757952116533 408 3919857576757 409 4088537543815 410 4264267381449 411 4447333225735 412 4638032592830 413 4836674616157 414 5043580699761 415 5259084771741 416 5483533977540 417 5717288969584 418 5960724643825 419 6214230449561 420 6478211179435 421 6753087317877 422 7039295872456 423 7337290754842 424 7647543676568 425 7970544564590 426 8306802505840 427 8656846210044 428 9021225022403 429 9400509418970 430 9795292085084 431 10206188468176 432 10633837922564 433 11078904304396 434 11542077198850 435 12024072576457 436 12525634089189 437 13047533784737 438 13590573500671 439 14155585637291 440 14743434633246 441 15355017817160 442 15991266985984 443 16653149317984 444 17341669056096 445 18057868513252 446 18802829860010 447 19577676206640 448 20383573519955 449 21221731803131 450 22093407125286 451 22999902902691 452 23942572076200 453 24922818492439 454 25942099215338 455 27001926035242 456 28103867938257 457 29249552724869 458 30440669646296 459 31678971170149 460 32966275782248 461 34304469887266 462 35695510809846 463 37141428853983 464 38644330487117 465 40206400569295 466 41829905764134 467 43517196935617 468 45270712775944 469 47092982409450 470 48986629264231 471 50954373865012 472 52999037968665 473 55123547591683 474 57330937407766 475 59624354005050 476 62007060592559 477 64482440512756 478 67054002243738 479 69725383191482 480 72500355040595 481 75382827824527 482 78376855623969 483 81486640969717 484 84716540919749 485 88071071779683 486 91554915594424 487 95172925243199 488 98930131346463 489 102831747740502 490 106883178864567 491 111090025646182 492 115458093361258 493 119993397973282 494 124702174530707 495 129590883963143 496 134666222031196 497 139935126651296 498 145404787437190 499 151082653548961 500 156976443882695 501 163094155514596 502 169444074547905 503 176034785175642 504 182875181270298 505 189974476107541 506 197342214705835 507 204988284276606 508 212922927398193 509 221156753205862 510 229700751436622 511 238566304458524 512 247765202238038 513 257309655221205 514 267212310311809 515 277486264695593 516 288145082853022 517 299202811378421 518 310673997144800 519 322573703175849 520 334917527993521 521 347721622646237 522 361002711347804 523 374778109695234 524 389065746671740 525 403884184188564 526 419252640528339 527 435191011251469 528 451719894212107 529 468860611953229 530 486635238344047 531 505066622558764 532 524178417497720 533 543995105436275 534 564542028298681 535 585845415132124 536 607932414382008 537 630831123258225 538 654570622138391 539 679181006012466 540 704693421127579 541 731140098601500 542 758554393503430 543 786970820806116 544 816425097000066 545 846954178543039 546 878596306231316 547 911391046282953 548 945379337596712 549 980603535697145 550 1017107463091005 551 1054936456199575 552 1094137419017464 553 1134758873293921 554 1176851015670510 555 1220465771277676 556 1265656854637175 557 1312479826915523 558 1360992160763357 559 1411253301483667 560 1463324736122134 561 1517270058760711 562 1573155044091190 563 1631047717171140 564 1691018431776565 565 1753139944841923 566 1817487499918445 567 1884138906667671 568 1953174629701164 569 2024677873412878 570 2098734676619018 571 2175434003083386 572 2254867842247839 573 2337131305851731 574 2422322735203704 575 2510543804230204 576 2601899633668191 577 2696498901037272 578 2794453962191669 579 2895880968584605 580 3000899996683252 581 3109635173058218 582 3222214812093044 583 3338771549368525 584 3459442488276278 585 3584369342223911 586 3713698590633835 587 3847581630579671 588 3986174942822657 589 4129640253411429 590 4278144710359952 591 4431861055935166 592 4590967814632792 593 4755649476753395 594 4926096698436456 595 5102506497304674 596 5285082465234147 597 5474034976806686 598 5669581415713404 599 5871946396806100 600 6081362006899007 601 6298068041349035 602 6522312260209334 603 6754350640167161 604 6994447646997444 605 7242876503925303 606 7499919481361217 607 7765868182644498 608 8041023852208678 609 8325697679849208 610 8620211128370486 611 8924896257534927 612 9240096072507852 613 9566164868680264 614 9903468602114745 615 10252385256637582 616 10613305237695910 617 10986631763004640 618 11372781281267486 619 11772183887960231 620 12185283770396342 621 12612539650133558 622 13054425256106356 623 13511429795350777 624 13984058455823153 625 14472832907218062 626 14978291835412890 627 15500991475181379 628 16041506178126985 629 16600428979378986 630 17178372201103402 631 17775968055163984 632 18393869284418333 633 19032749803678780 634 19693305381034832 635 20376254319402602 636 21082338180433157 637 21812322509179015 638 22566997603069017 639 23347179282376306 640 24153709707127164 641 24987458196095501 642 25849322094494764 643 26740227644609754 644 27661130907371431 645 28613018687656666 646 29596909513080175 647 30613854617416778 648 31664938979979028 649 32751282370656690 650 33874040453690526 651 35034405898083410 652 36233609549543735 653 37472921610314601 654 38753652883517759 655 40077156026512589 656 41444826871960483 657 42858105759328757 658 44318478937293482 659 45827479977987370 660 47386691265728379 661 48997745499133124 662 50662327271235373 663 52382174664738856 664 54159080929177772 665 55994896174908362 666 57891529153001535 667 59850949054023645 668 61875187396927162 669 63966339938791828 670 66126568679210896 671 68358103887836854 672 70663246231127650 673 73044368924633842 674 75503919989534008 675 78044424537243055 676 80668487163328235 677 83378794372347115 678 86178117117505768 679 89069313374066164 680 92055330833282237 681 95139209633375583 682 98324085217021679 683 101613191229132797 684 105009862547596129 685 108517538357989527 686 112139765367774699 687 115880201068334998 688 119742617143648421 689 123730902930857726 690 127849069034745587 691 132101250998646545 692 136491713137071962 693 141024852429332537 694 145705202583066896 695 150537438163922566 696 155526378903668765 697 160676994079709677 698 165994407082211457 699 171483900058390921 700 177150918753783180 701 183001077436791161 702 189040164030386826 703 195274145333482008 704 201709172459899485 705 208351586374084181 706 215207923655547532 707 222284922367246940 708 229589528164437018 709 237128900515444773 710 244910419175105593 711 252941690778365428 712 261230555699669653 713 269785095041411913 714 278613637901629165 715 287724768780269451 716 297127335279205074 717 306830455950729057 718 316843528454824056 719 327176237875774545 720 337838565363458188 721 348840796945156672 722 360193532678877965 723 371907695989399435 724 383994543363319982 725 396465674239561648 726 409333041277638917 727 422608960834987606 728 436306123841415756 729 450437606897173349 730 465016883788876941 731 480057837244220380 732 495574771126159089 733 511582422882381944 734 528095976457028991 735 545131075474807585 736 562703836911514234 737 580830865055421669 738 599529265980195809 739 618816662328091783 740 638711208631535400 741 659231606965574784 742 680397123166587588 743 702227603403884259 744 724743491347241140 745 747965845710337002 746 771916358421194656 747 796617373193356075 748 822091904756744254 749 848363658515146272 750 875457050898052780 751 903397230166861214 752 932210097951540132 753 961922331270924442 754 992561405321964756 755 1024155616783523140 756 1056734107929210561 757 1090326891287820167 758 1124964875155327623 759 1160679889689032810 760 1197504713897950320 761 1235473103252425237 762 1274619818236906546 763 1314980653560777028 764 1356592468362078644 765 1399493217110666685 766 1443721981556178395 767 1489319003419150969 768 1536325718182125124 769 1584784789670012614 770 1634740145788090382 771 1686237015098435864 772 1739321964614975509 773 1794042938488461655 774 1850449297974252683 775 1908591862345056601 776 1968522951153811080 777 2030296427499299847 778 2093967742713278054 779 2159593982111635942 780 2227233912241667334 781 2296948029258255765 782 2368798608875244556 783 2442849757514021722 784 2519167465110154669 785 2597819659189931294 786 2678876260692389580 787 2762409241137511790 788 2848492681632041618 789 2937202833302643219 790 3028618179663341392 791 3122819500495675643 792 3219889937765467722 793 3319915063142660688 794 3422982947664887177 795 3529184233099727880 796 3638612205564044113 797 3751362870942603411 798 3867535032682723310 799 3987230371495101620 800 4110553527555993345 801 4237612184727796046 802 4368517157413150791 803 4503382479546566610 804 4642325496358189063 805 4785466958400548727 806 4932931118494053587 807 5084845831067964097 808 5241342654573785116 809 5402556956434300065 810 5568628021227347615 811 5739699161552692212 812 5915917832304189047 813 6097435747781386996 814 6284409002385971467 815 6476998194321952728 816 6675368553070013069 817 6879690070039624757 818 7090137633193952310 819 7306891165035891687 820 7530135764776771370 821 7760061854059571487 822 7996865327084980861 823 8240747704496470293 824 8491916291900457557 825 8750584342360568450 826 9016971223771238108 827 9291302590433076805 828 9573810559764494508 829 9864733893454548437 830 10164318184022906273 831 10472816046074133714 832 10790487313243410034 833 11117599240103340863 834 11454426710062248828 835 11801252448504676737 836 12158367242238385303 837 12526070164480577883 838 12904668806482621476 839 13294479515006356663 840 13695827636788146601 841 14109047769184759487 842 14534484018174174312 843 14972490262885630276 844 15423430427871631633 845 15887678762275903650 846 16365620127149616796 847 16857650290050101756 848 17364176228216270669 849 17885616439433522449 850 18422401261925426558 851 18974973202364581196 852 19543787273384149812 853 20129311339660504202 854 20732026473995149384 855 21352427322444916268 856 21991022479975536820 857 22648334875665560713 858 23324902168985794735 859 24021277156158500704 860 24738028188171903584 861 25475739599432351206 862 26235012148682710279 863 27016463471145507589 864 27820728543574243384 865 28648460161148884938 866 29500329427954992723 867 30377026259958439754 868 31279259902274492457 869 32207759459619556318 870 33163274441804126798 871 34146575323131417041 872 35158454117623648482 873 36199724968915661353 874 37271224756802232021 875 38373813719255080090 876 39508376091963287547 877 40675820764187526843 878 41877081953051715285 879 43113119895038350252 880 44384921556882588437 881 45693501364605750934 882 47039901952958890164 883 48425194933991935139 884 49850481687095419340 885 51316894169205370421 886 52825595747599200636 887 54377782053947029729 888 55974681862128741040 889 57617557988456756821 890 59307708216900672010 891 61046466247927254438 892 62835202673641513036 893 64675325977817488409 894 66568283563595889540 895 68515562807411435857 896 70518692142023543454 897 72579242167187721215 898 74698826790939404414 899 76879104400002838439 900 79121779062400076522 901 81428601760746751497 902 83801371659415629067 903 86241937404030856179 904 88752198456583946783 905 91334106464608738074 906 93989666667821351364 907 96720939340638765539 908 99530041274099452613 909 102419147295575558590 910 105390491829924033781 911 108446370500442341041 912 111589141773402533052 913 114821228644507156819 914 118145120371173351607 915 121563374248965224874 916 125078617436217599719 917 128693548825150660495 918 132410940963660178330 919 136233642026060883443 920 140164577837115803224 921 144206753947609553860 922 148363257765950040982 923 152637260744037228437 924 157032020622043121935 925 161550883730322915314 926 166197287353264834400 927 170974762153282532589 928 175886934659928688715 929 180937529822316566961 930 186130373630005157352 931 191469395800521505112 932 196958632538858799986 933 202602229367109844683 934 208404444029766253363 935 214369649472831946409 936 220502336902477836374 937 226807118921376814965 938 233288732748652463229 939 239952043521572083799 940 246802047685129790311 941 253843876467645664648 942 261082799448748364447 943 268524228217862426986 944 276173720129797549551 945 284036982155561366418 946 292119874835230683829 947 300428416331003247235 948 308968786587514091455 949 317747331597543131685 950 326770567780453771472 951 336045186471496925951 952 345578058529588738809 953 355376239061705780187 954 365446972271782781541 955 375797696432272070048 956 386436048986538076957 957 397369871780262364473 958 408607216430332494348 959 420156349829413037064 960 432025759794982036232 961 444224160861056360168 962 456760500221713982686 963 469643963824667019740 964 482883982624327970070 965 496490238992658809097 966 510472673297595694223 967 524841490647378038566 968 539607167810936767396 969 554780460312717950005 970 570372409712473617713 971 586394351068446053568 972 602857920594870021296 973 619775063512278480693 974 637158042101942130164 975 655019443962992319938 976 673372190483982961382 977 692229545527512255106 978 711605124340098596701 979 731512902686011628119 980 751967226217711701206 981 772982820081684207862 982 794574798772797785688 983 816758676236069992074 984 839550376229464139743 985 862966242946703907497 986 887023051914245204366 987 911738021161507078925 988 937128822679035038978 989 963213594163822183988 990 990010951067020408407 991 1017539998943401343536 992 1045820346118376980390 993 1074872116672087067911 994 1104715963756967047589 995 1135373083248459758528 996 1166865227745911667439 997 1199214720923489527582 998 1232444472248809845089 999 1266577992069299777923 1000 1301639407084662136004