0 0 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 3 9 4 10 5 11 6 12 8 13 9 14 11 15 14 16 16 17 19 18 23 19 27 20 32 21 38 22 44 23 52 24 61 25 71 26 82 27 96 28 111 29 128 30 148 31 170 32 195 33 224 34 256 35 293 36 334 37 380 38 432 39 491 40 557 41 630 42 713 43 805 44 908 45 1024 46 1152 47 1295 48 1455 49 1632 50 1829 51 2048 52 2291 53 2560 54 2859 55 3189 56 3554 57 3958 58 4404 59 4896 60 5440 61 6038 62 6697 63 7424 64 8222 65 9100 66 10066 67 11125 68 12288 69 13565 70 14964 71 16496 72 18176 73 20013 74 22023 75 24223 76 26625 77 29250 78 32117 79 35244 80 38656 81 42378 82 46432 83 50849 84 55661 85 60896 86 66592 87 72789 88 79523 89 86841 90 94793 91 103424 92 112792 93 122960 94 133984 95 145937 96 158894 97 172928 98 188128 99 204587 100 222396 101 241665 102 262508 103 285039 104 309392 105 335709 106 364130 107 394820 108 427953 109 463703 110 502272 111 543872 112 588719 113 637059 114 689152 115 745264 116 805694 117 870761 118 940789 119 1016145 120 1097216 121 1184400 122 1278142 123 1378913 124 1487200 125 1603543 126 1728514 127 1862705 128 2006772 129 2161408 130 2327335 131 2505344 132 2696275 133 2901004 134 3120487 135 3355740 136 3607822 137 3877888 138 4167163 139 4476928 140 4808575 141 5163578 142 5543484 143 5949967 144 6384801 145 6849849 146 7347122 147 7878751 148 8446976 149 9054209 150 9703008 151 10396060 152 11136256 153 11926659 154 12770491 155 13671210 156 14632480 157 15658157 158 16752373 159 17919504 160 19164160 161 20491270 162 21906055 163 23414016 164 25021028 165 26733312 166 28557422 167 30500352 168 32569504 169 34772679 170 37118192 171 39614838 172 42271891 173 45099223 174 48107275 175 51307057 176 54710275 177 58329308 178 62177211 179 66267851 180 70615890 181 75236784 182 80146944 183 85363712 184 90905372 185 96791321 186 103042048 187 109679158 188 116725549 189 124205408 190 132144231 191 140569024 192 149508304 193 158992128 194 169052315 195 179722452 196 191037934 197 203036211 198 215756801 199 229241344 200 243533873 201 258680835 202 274731168 203 291736592 204 309751648 205 328833792 206 349043712 207 370445393 208 393106223 209 417097350 210 442493764 211 469374426 212 497822668 213 527926295 214 559777744 215 593474528 216 629119360 217 666820355 218 706691513 219 748852884 220 793430803 221 840558426 222 890375941 223 943030842 224 998678528 225 1057482560 226 1119614980 227 1185256993 228 1254599264 229 1327842304 230 1405197227 231 1486886106 232 1573142435 233 1664211968 234 1760353152 235 1861837663 236 1968951344 237 2081994729 238 2201283662 239 2327150353 240 2459943996 241 2600031488 242 2747798624 243 2903650816 244 3068013937 245 3241335661 246 3424086302 247 3616759810 248 3819875261 249 4033977856 250 4259640064 251 4497463301 252 4748079104 253 5012150445 254 5290373632 255 5583479669 256 5892235774 257 6217447532 258 6559960464 259 6920661791 260 7300482853 261 7700400928 262 8121441280 263 8564679872 264 9031245487 265 9522322073 266 10039151810 267 10583037568 268 11155345596 269 11757508992 270 12391030535 271 13057485770 272 13758526941 273 14495886243 274 15271379369 275 16086909952 276 16944473300 277 17846160480 278 18794163321 279 19790778720 280 20838413312 281 21939589120 282 23096948516 283 24313259547 284 25591422336 285 26934474761 286 28345598542 287 29828126493 288 31385549012 289 33021521044 290 34739870277 291 36544604560 292 38439919872 293 40430209568 294 42520072875 295 44714323970 296 47018002434 297 49436382969 298 51974985728 299 54639588149 300 57436236032 301 60371255303 302 63451265408 303 66683191924 304 70074279965 305 73632109309 306 77364608768 307 81280071445 308 85387171821 309 89694982121 310 94212989652 311 98951116106 312 103919736195 313 109129697328 314 114592341435 315 120319526143 316 126323647104 317 132617662676 318 139215117952 319 146130170112 320 153377616287 321 160972920832 322 168932244096 323 177272473861 324 186011256304 325 195167028586 326 204759054345 327 214807458816 328 225333265725 329 236358437366 330 247905914380 331 259999657520 332 272664692896 333 285927156995 334 299814343959 335 314354756608 336 329578157394 337 345515621885 338 362199596288 339 379663955100 340 397944061555 341 417076832470 342 437100803445 343 458056197135 344 479984996352 345 502931017731 346 526939988816 347 552059630459 348 578339739985 349 605832278227 350 634591462324 351 664673859595 352 696138485760 353 729046909408 354 763463357934 355 799454828289 356 837091204574 357 876445377536 358 917593369376 359 960614466108 360 1005591352239 361 1052610251386 362 1101761075205 363 1153137575105 364 1206837500639 365 1262962766973 366 1321619625744 367 1382918843392 368 1446975889411 369 1513911128704 370 1583850022240 371 1656923338624 372 1733267370559 373 1813024160524 374 1896341738496 375 1983374365397 376 2074282786829 377 2169234500103 378 2268404027904 379 2371973203488 380 2480131470484 381 2593076190432 382 2711012963218 383 2834155963546 384 2962728286432 385 3096962307047 386 3237100058240 387 3383393618532 388 3536105516032 389 3695509151927 390 3861889235968 391 4035542239722 392 4216776871473 393 4405914564807 394 4603289987075 395 4809251571712 396 5024162066222 397 5248399102368 398 5482355792640 399 5726441344672 400 5981081700353 401 6246720204000 402 6523818290999 403 6812856203904 404 7114333740719 405 7428771026397 406 7756709314942 407 8098711827141 408 8455364614564 409 8827277457715 410 9215084803552 411 9619446732758 412 10041049965104 413 10480608908288 414 10938866740480 415 11416596535244 416 11914602434574 417 12433720860039 418 12974821771028 419 13538809976320 420 14126626488576 421 14739249931264 422 15377698004676 423 16043029000192 424 16736343372977 425 17458785380049 426 18211544772627 427 18995858553568 428 19813012807073 429 20664344589500 430 21551243892503 431 22475155686230 432 23437582031167 433 24440084270336 434 25484285310240 435 26571871978730 436 27704597472256 437 28884283901440 438 30112824922773 439 31392188469760 440 32724419592896 441 34111643396100 442 35556068083729 443 37059988128040 444 38625787544659 445 40255943290864 446 41953028797282 447 43719717620399 448 45558787231427 449 47473122952992 450 49465722030764 451 51539697856535 452 53698284355072 453 55944840521536 454 58282855127168 455 60715951606272 456 63247893111216 457 65882587754324 458 68624094050391 459 71476626546688 460 74444561660320 461 77532443737738 462 80744991323296 463 84087103657775 464 87563867422976 465 91180563719097 466 94942675297262 467 98855894064512 468 102926128847872 469 107159513441517 470 111562414955442 471 116141442452480 472 120903455899293 473 125855575450951 474 131005191056348 475 136359972411616 476 141927879282715 477 147717172184801 478 153736423447184 479 159994528686869 480 166500718678528 481 173264571651734 482 180296026040320 483 187605393671973 484 195203373431265 485 203101065422748 486 211309985622882 487 219842081056401 488 228709745525632 489 237925835882499 490 247503688881152 491 257457138642086 492 267800534718469 493 278548760805085 494 289717254123520 495 301322025475154 496 313379680005394 497 325907438715588 498 338923160715163 499 352445366260896 500 366493260622512 501 381086758768672 502 396246510923819 503 411993929038075 504 428351214166179 505 445341384809472 506 462988306266800 507 481316720992256 508 500352280017664 509 520121575489792 510 540652174322185 511 561972653024080 512 584112633760675 513 607102821646916 514 630975043342341 515 655762287005696 516 681498743614370 517 708219849721571 518 735962331714741 519 764764251583723 520 794665054277156 521 825705616716160 522 857928298477568 523 891376994231137 524 926097188006143 525 962136009303443 526 999542291144340 527 1038366630138368 528 1078661448590336 529 1120481058745735 530 1163881729263557 531 1208921753942118 532 1255661522805176 533 1304163595644960 534 1354492778053812 535 1406716200060245 536 1460903397474800 537 1517126395983897 538 1575459798116832 539 1635980873201024 540 1698769650350624 541 1763909014624262 542 1831484806477399 543 1901585924562117 544 1974304432021888 545 2049735666417780 546 2127978353347966 547 2209134723920640 548 2293310636228828 549 2380615700899177 550 2471163410888192 551 2565071275687981 552 2662460960024701 553 2763458427237728 554 2868194087516647 555 2976802951091248 556 3089424786578816 557 3206204284682086 558 3327291227346208 559 3452840662597093 560 3583013085271837 561 3717974623764650 562 3857897233030144 563 4002958894073537 564 4153343820068205 565 4309242669363200 566 4470852765631488 567 4638378325317804 568 4812030692671375 569 4992028582637740 570 5178598331788453 571 5371974157599226 572 5572398426376033 573 5780121930029952 574 5995404172039168 575 6218513662924832 576 6449728225466420 577 6689335310025040 578 6937632320331159 579 7194926949989984 580 7461537530105331 581 7737793388411526 582 8024035220196640 583 8320615471453268 584 8627898734682752 585 8946262157668864 586 9276095865696260 587 9617803397679110 588 9971802156551824 589 10338523874440192 590 10718415093121031 591 11111937660162314 592 11519569241308768 593 11941803849667584 594 12379152392130622 595 12832143233648485 596 13301322779962594 597 13787256079280128 598 14290527443562116 599 14811741090087456 600 15351521803830365 601 15910515621382205 602 16489390537141929 603 17088837232370432 604 17709569827906304 605 18352326661333792 606 19017871089262382 607 19706992315587712 608 20420506246597341 609 21159256373651456 610 21924114684386452 611 22715982603385072 612 23535791963120224 613 24384506006205833 614 25263120419986217 615 26172664404355050 616 27114201773931138 617 28088832095717984 618 29097691863230208 619 30141955708316768 620 31222837651911680 621 32341592394796752 622 33499516649718009 623 34697950516199680 624 35938278899251712 625 37221932973433828 626 38550391693744199 627 39925183354650390 628 41347887198857837 629 42820135077419940 630 44343613162639947 631 45920063715504896 632 47551286909403760 633 49239142711724845 634 50985552825231365 635 52792502691128127 636 54662043555573760 637 56596294601709929 638 58597445149295863 639 60667756923877385 640 62809566397749245 641 65025287204991360 642 67317412632698624 643 69688518190867456 644 72141264263429760 645 74678398842761472 646 77302760350352560 647 80017280546357706 648 82824987530581668 649 85729008837830368 650 88732574630595557 651 91839020991875663 652 95051793321329549 653 98374449838002124 654 101810665192696304 655 105364234193476988 656 109039075647842304 657 112839236324933152 658 116768895041581440 659 120832366876055775 660 125034107513198600 661 129378717725099008 662 133870947991512139 663 138515703264071535 664 143318047878813859 665 148283210621609792 666 153416589950932992 667 158723759382894732 668 164210473043555153 669 169882671393364179 670 175746487129103456 671 181808251268795770 672 188074499424893789 673 194551978271602742 674 201247652212300260 675 208168710252864640 676 215322573087293536 677 222716900402116691 678 230359598405958583 679 238258827591207680 680 246423010734883584 681 254860841145652720 682 263581291164574299 683 272593620927307781 684 281907387395381203 685 291532453664781696 686 301478998560297216 687 311757526523915120 688 322378877806278667 689 333354238970390528 690 344695153716637625 691 356413534038944480 692 368521671722070912 693 381032250189965667 694 393958356715860873 695 407313495005022092 696 421111598160978432 697 435367042046872121 698 450094659053820304 699 465309752288108288 700 481028110189891022 701 497266021596360815 702 514040291262282960 703 531368255851704320 704 549267800414952480 705 567757375365004249 706 586856013968257086 707 606583350365081600 708 626959638135515007 709 648005769426465792 710 669743294657177545 711 692194442819707290 712 715382142392241152 713 739330042883485024 714 764062537026404293 715 789604783640713749 716 815982731183976384 717 843223142011236439 718 871353617364303616 719 900402623112309973 720 930399516265259936 721 961374572283556518 722 993359013207040768 723 1026385036627216896 724 1060485845527674963 725 1095695679018328983 726 1132049843989266560 727 1169584747711425909 728 1208337931411979250 729 1248348104852528071 730 1289655181939719676 731 1332300317398622214 732 1376325944539473165 733 1421775814150010890 734 1468695034546397892 735 1517130112816076800 736 1567128997287594562 737 1618741121263304717 738 1672017448051250747 739 1727010517334336063 740 1783774492915840307 741 1842365211880804598 742 1902840235214724448 743 1965258899922030592 744 2029682372687378700 745 2096173705124804563 746 2164797890660940930 747 2235621923099115611 748 2308714856913315424 749 2384147869322247315 750 2461994324194440192 751 2542329837837637780 752 2625232346727093279 753 2710782177228187280 754 2799062117371250025 755 2890157490737951199 756 2984156232519541760 757 3081148967809853705 758 3181229092197578752 759 3284492854723389999 760 3391039443270263936 761 3500971072457122304 762 3614393074107087259 763 3731413990364622027 764 3852145669537751840 765 3976703364742874880 766 4105205835432853826 767 4237775451891172992 768 4374538302776415505 769 4515624305804714489 770 4661167321660110363 771 4811305271224387846 772 4966180256221598284 773 5125938683374950989 774 5290731392175587744 775 5460713786366633984 776 5636045969248618700 777 5816892882914388480 778 6003424451525787648 779 6195815728747314964 780 6394247049454219270 781 6598904185836934144 782 6809978508026946980 783 7027667149371689233 784 7252173176490786308 785 7483705764249476880 786 7722480375787766944 787 7968718947748970528 788 8222650080855060559 789 8484509235979297094 790 8754538935872045056 791 9032988972699793686 792 9320116621560744257 793 9616186860146164284 794 9921472594721163264 795 10236254892602234635 796 10560823221315160194 797 10895475694621713408 798 11240519325607653056 799 11596270287031203500 800 11963054179136470528 801 12341206305140697283 802 12731071954611454887 803 13133006694955562305 804 13547376671246422016 805 13974558914624167826 806 14414941659509209100 807 14868924669875118444 808 15336919574835080192 809 15819350213802834627 810 16316652991494923305 811 16829277243049919360 812 17357685609547613645 813 17902354424217550080 814 18463774109635838636 815 19042449586217074116 816 19638900692315214754 817 20253662616257513159 818 20887286340644156194 819 21540339099253951504 820 22213404846907391821 821 22907084742647715120 822 23621997646608966240 823 24358780630951874011 824 25118089505258427359 825 25900599356785184371 826 26707005105988038880 827 27538022077742081024 828 28394386588690166784 829 29276856551167453642 830 30186212094160979360 831 31123256201774240390 832 32088815369681390592 833 33083740280068483111 834 34108906495571035040 835 35165215172732956691 836 36253593795525755490 837 37374996929479835821 838 38530406996996662443 839 39720835074425577056 840 40947321711503106685 841 42210937773770829680 842 43512785308604129724 843 44853998435499449825 844 46235744261287267328 845 47659223820955614208 846 49125673044785587264 847 50636363752521386618 848 52192604675316471651 849 53795742506215493632 850 55447162979954354176 851 57148291982881358080 852 58900596693822062599 853 60705586756734836768 854 62564815486026459036 855 64479881105418402033 856 66452428021280725120 857 68484148131374636032 858 70576782169967929083 859 72732121090315784982 860 74952007485525525953 861 77238337048849044378 862 79593060074477057536 863 82018182999937575760 864 84515769991228235264 865 87087944571844901536 866 89736891296899483886 867 92464857473549473119 868 95274154928996970160 869 98167161827347992099 870 101146324536654902528 871 104214159547502768896 872 107373255444536144445 873 110626274932357522432 874 113975956917269577056 875 117425118646371883707 876 120976657905560471844 877 124633555278022561800 878 128398876464860527072 879 132275774669519929359 880 136267493047743840113 881 140377367224820716102 882 144608827881937292359 883 148965403413498952737 884 153450722657328721943 885 158068517699703873696 886 162822626757244063422 887 167716997137717486880 888 172755688281883363825 889 177942874888548179968 890 183282850125069924992 891 188780028925600627712 892 194438951379421163556 893 200264286211783657545 894 206260834359737473024 895 212433532645483336037 896 218787457549866397696 897 225327829088684665465 898 232060014794563057172 899 238989533807214872831 900 246122061074983455585 901 253463431670636309700 902 261019645224461180855 903 268796870477790349105 904 276801449960164993248 905 285039904793434857120 906 293518939626171420946 907 302245447701864964688 908 311226516064465894656 909 320469430904920394387 910 329981683052449718919 911 339770973614419568486 912 349845219768742903264 913 360212560712866436864 914 370881363773495850681 915 381860230681319491259 916 393158004015105397278 917 404783773819659583072 918 416746884402246628672 919 429056941312197549056 920 441723818508551905280 921 454757665720703306522 922 468168916007150881625 923 481968293517590888059 924 496166821463714580480 925 510775830304222117785 926 525806966149704223100 927 541272199393185782784 928 557183833572280236639 929 573554514469056690800 930 590397239453875481472 931 607725367079614439040 932 625552626932873174479 933 643893129748908707867 934 662761377797235039262 935 682172275544997242475 936 702141140605409808242 937 722683714978741966592 938 743816176593524596736 939 765555151155846640276 940 787917724314816696176 941 810921454152472323098 942 834584384006628124672 943 858925055635377336416 944 883962522732184594944 945 909716364800732524576 946 936206701398925511680 947 963454206761694336000 948 991480124812487944416 949 1020306284573597776675 950 1049955115985719002217 951 1080449666147414663600 952 1111813615985427617810 953 1144071297367064187904 954 1177247710666155547788 955 1211368542794403017025 956 1246460185710214068992 957 1282549755417439991460 958 1319665111466749158101 959 1357834876972693741777 960 1397088459159855530687 961 1437456070451804125312 962 1478968750116949665152 963 1521658386485725561382 964 1565557739753910779520 965 1610700465387276971008 966 1657121138143126518482 967 1704855276724690060145 968 1753939369084756730564 969 1804410898395320639712 970 1856308369700460174860 971 1909671337270102488928 972 1964540432672767566464 973 2020957393585852178441 974 2078965093362483269642 975 2138607571374446482588 976 2199930064151196770795 977 2262979037335463249536 978 2327802218476473300199 979 2394448630682360170085 980 2462968627153862162176 981 2533413926621973858176 982 2605837649712789852192 983 2680294356263366885455 984 2756840083613025073152 985 2835532385895132796928 986 2916430374355049934850 987 2999594758720544530687 988 3085087889651669009408 989 3172973802297760176460 990 3263318260989916710201 991 3356188805098029506560 992 3451654796082169978702 993 3549787465768883602125 994 3650659965883712062217 995 3754347418872052562944 996 3860926970041261709840 997 3970477841057745900087 998 4083081384833624949632 999 4198821141838415440913 1000 4317782897872077580753