0 0 1 1 2 0 3 1 4 1 5 1 6 2 7 2 8 3 9 3 10 5 11 5 12 7 13 8 14 10 15 12 16 15 17 17 18 21 19 25 20 29 21 35 22 41 23 48 24 56 25 66 26 76 27 89 28 103 29 119 30 137 31 159 32 181 33 209 34 239 35 273 36 312 37 356 38 404 39 460 40 522 41 591 42 669 43 757 44 853 45 963 46 1085 47 1219 48 1371 49 1539 50 1725 51 1933 52 2164 53 2418 54 2702 55 3016 56 3362 57 3746 58 4171 59 4637 60 5155 61 5725 62 6351 63 7043 64 7805 65 8639 66 9561 67 10571 68 11679 69 12897 70 14233 71 15694 72 17298 73 19054 74 20972 75 23074 76 25372 77 27878 78 30621 79 33613 80 36875 81 40437 82 44319 83 48545 84 53153 85 58169 86 63623 87 69561 88 76017 89 83029 90 90653 91 98933 92 107915 93 117670 94 128250 95 139718 96 152156 97 165632 98 180224 99 196032 100 213142 101 231651 102 251679 103 273337 104 296741 105 322043 106 349375 107 378885 108 410755 109 445151 110 482255 111 522289 112 565455 113 611983 114 662135 115 716169 116 774359 117 837029 118 904492 119 977086 120 1055204 121 1139228 122 1229572 123 1326712 124 1431114 125 1543286 126 1663800 127 1793227 128 1932183 129 2081361 130 2241455 131 2413215 132 2597473 133 2795077 134 3006931 135 3234043 136 3477437 137 3738207 138 4017569 139 4316757 140 4637099 141 4980051 142 5347105 143 5739863 144 6160071 145 6609531 146 7090168 147 7604076 148 8153426 149 8740526 150 9367892 151 10038124 152 10753996 153 11518516 154 12334802 155 13206180 156 14136241 157 15128719 158 16187595 159 17317151 160 18521857 161 19806463 162 21176077 163 22636033 164 24191999 165 25850057 166 27616567 167 29498277 168 31502427 169 33636581 170 35908777 171 38327607 172 40902069 173 43641713 174 46556733 175 49657817 176 52956297 177 56464252 178 60194364 179 64160058 180 68375644 181 72856136 182 77617432 183 82676456 184 88050968 185 93759776 186 99822866 187 106261230 188 113097085 189 120354013 190 128056803 191 136231659 192 144906389 193 154110219 194 163874037 195 174230593 196 185214311 197 196861557 198 209210865 199 222302737 200 236179951 201 250887795 202 266473875 203 282988461 204 300484723 205 319018573 206 338649011 207 359438413 208 381452373 209 404760073 210 429434627 211 455552902 212 483195950 213 512449386 214 543403204 215 576152284 216 610796772 217 647441948 218 686198762 219 727184264 220 770521504 221 816340102 222 864776750 223 915975133 224 970086551 225 1027270505 226 1087694615 227 1151535345 228 1218978641 229 1290219887 230 1365464721 231 1444929733 232 1528842479 233 1617442391 234 1710981545 235 1809724759 236 1913950567 237 2023952121 238 2140037337 239 2262529987 240 2391770719 241 2528117273 242 2671945703 243 2823651545 244 2983650087 245 3152377787 246 3330293535 247 3517879069 248 3715640550 249 3924109972 250 4143845740 251 4375434388 252 4619492214 253 4876665994 254 5147634896 255 5433112368 256 5733846970 257 6050624578 258 6384270486 259 6735650442 260 7105673140 261 7495292565 262 7905509291 263 8337373269 264 8791986475 265 9270504499 266 9774139647 267 10304163973 268 10861911163 269 11448780029 270 12066237955 271 12715823115 272 13399148425 273 14117905457 274 14873867029 275 15668891709 276 16504928195 277 17384018405 278 18308302555 279 19280024087 280 20301533353 281 21375293271 282 22503884969 283 23690012063 284 24936507031 285 26246337641 286 27622611881 287 29068585203 288 30587667784 289 32183430240 290 33859611848 291 35620128706 292 37469080414 293 39410759330 294 41449659806 295 43590485944 296 45838161996 297 48197842872 298 50674923066 299 53275048390 300 56004127908 301 58868344156 302 61874166451 303 65028364365 304 68338019483 305 71810540447 306 75453678171 307 79275539365 308 83284603525 309 87489740117 310 91900224125 311 96525755179 312 101376477033 313 106462995357 314 111796399299 315 117388283571 316 123250768715 317 129396525493 318 135838799859 319 142591436045 320 149668904179 321 157086328395 322 164859513269 323 173004974923 324 181539972799 325 190482539809 326 199851517363 327 209666591327 328 219948326305 329 230718205145 330 241998669587 331 253813159172 332 266186155868 333 279143229924 334 292711084066 335 306917603852 336 321791909364 337 337364405424 338 353666838346 339 370732354230 340 388595555970 341 407292567140 342 426861097800 343 447340509090 344 468771885180 345 491198107524 346 514663927937 347 539216049695 348 564903211223 349 591776268747 350 619888287707 351 649294636941 352 680053082249 353 712223889271 354 745869929545 355 781056786323 356 817852870255 357 856329538893 358 896561216179 359 938625522573 360 982603409643 361 1028579294835 362 1076641207937 363 1126880942473 364 1179394207737 365 1234280793541 366 1291644740405 367 1351594511083 368 1414243175701 369 1479708603121 370 1548113654287 371 1619586390193 372 1694260287055 373 1772274454063 374 1853773866985 375 1938909610007 376 2027839120787 377 2120726452872 378 2217742547334 379 2319065508474 380 2424880898502 381 2535382042466 382 2650770338398 383 2771255588038 384 2897056339054 385 3028400233810 386 3165524380284 387 3308675736196 388 3458111500868 389 3614099531196 390 3776918772658 391 3946859699278 392 4124224780166 393 4309328962781 394 4502500166833 395 4704079807317 396 4914423336107 397 5133900796337 398 5362897408399 399 5601814176881 400 5851068512463 401 6111094888243 402 6382345519757 403 6665291062241 404 6960421345567 405 7268246135871 406 7589295916923 407 7924122712961 408 8273300941321 409 8637428287807 410 9017126627623 411 9413042979481 412 9825850486035 413 10256249444173 414 10704968372403 415 11172765108557 416 11660427961931 417 12168776907217 418 12698664812861 419 13250978729195 420 13826641223445 421 14426611753707 422 15051888108821 423 15703507900531 424 16382550099853 425 17090136646101 426 17827434113996 427 18595655431258 428 19396061675878 429 20229963938268 430 21098725240732 431 22003762544274 432 22946548828186 433 23928615234148 434 24951553306524 435 26017017313956 436 27126726643504 437 28282468301008 438 29486099501872 439 30739550343674 440 32044826595846 441 33404012589946 442 34819274202254 443 36292861965203 444 37827114290877 445 39424460798441 446 41087425783287 447 42818631811277 448 44620803429521 449 46496771033333 450 48449474872651 451 50481969188877 452 52597426524193 453 54799142185951 454 57090538857121 455 59475171397215 456 61956731815329 457 64539054407103 458 67226121101545 459 70022066999237 460 72931186094139 461 75957937226501 462 79106950248975 463 82383032397617 464 85791174917933 465 89336559928019 466 93024567510175 467 96860783084349 468 100851005044675 469 105001252651069 470 109317774231965 471 113807055678919 472 118475829226041 473 123331082572545 474 128380068329357 475 133630313783339 476 139089631039893 477 144766127525537 478 150668216844066 479 156804630050302 480 163184427323436 481 169817010033620 482 176712133269848 483 183879918810792 484 191330868533154 485 199075878329376 486 207126252516120 487 215493718729644 488 224190443383158 489 233229047668106 490 242622624096892 491 252384753665412 492 262529523618760 493 273071545818178 494 284025975791992 495 295408532455048 496 307235518495261 497 319523841515527 498 332291035915649 499 345555285514677 500 359335447007115 501 373651074237909 502 388522443299435 503 403970578548203 504 420017279527947 505 436685148804411 506 453997620814533 507 471978991719067 508 490654450265445 509 510050109769883 510 530193041209701 511 551111307434669 512 572833998613491 513 595391268907859 514 618814374385973 515 643135712298709 516 668388861712683 517 694608625516057 518 721831073927085 519 750093589502397 520 779434913665049 521 809895194889263 522 841516038543057 523 874340558412079 524 908413430050195 525 943780945962091 526 980491072644795 527 1018593509643885 528 1058139750632851 529 1099183146547821 530 1141778970943649 531 1185984487583465 532 1231859020300771 533 1279464025309580 534 1328863165980340 535 1380122390127284 536 1433310009993206 537 1488496784956394 538 1545756007011400 539 1605163589222264 540 1666798157179784 541 1730741143521464 542 1797076885727060 543 1865892727227738 544 1937279121896496 545 2011329742147280 546 2088141590688280 547 2167815116007652 548 2250454331833628 549 2336166940624028 550 2425064461174326 551 2517262360602058 552 2612880190773903 553 2712041729275499 554 2814875125199957 555 2921513049833337 556 3032092852349159 557 3146756720808473 558 3265651848555699 559 3388930606136717 560 3516750719057469 561 3649275451486205 562 3786673796043095 563 3929120670017193 564 4076797118129881 565 4229890522006529 566 4388594816719871 567 4553110714543105 568 4723645936092503 569 4900415449250247 570 5083641716025233 571 5273554947551673 572 5470393367646779 573 5674403485105287 574 5885840374954617 575 6104967969123719 576 6332059356725945 577 6567397094206895 578 6811273525843185 579 7063991114819133 580 7325862785160835 581 7597212275049827 582 7878374501773225 583 8169695938620055 584 8471535004286481 585 8784262465079023 586 9108261850258705 587 9443929881133815 588 9791676914224405 589 10151927398879243 590 10525120350001141 591 10911709836240922 592 11312165484083706 593 11726972998533830 594 12156634700801338 595 12601670083459906 596 13062616383837064 597 13540029176088124 598 14034482982472132 599 14546571904652100 600 15076910275522812 601 15626133332137918 602 16194897910626492 603 16783883163657366 604 17393791301083498 605 18025348354729110 606 18679304967938474 607 19356437210586290 608 20057547420589134 609 20783465072605548 610 21535047674697364 611 22313181694075541 612 23118783512694603 613 23952800413545845 614 24816211598865821 615 25710029241106613 616 26635299567603487 617 27593103980258789 618 28584560211177179 619 29610823515283237 620 30673087901350299 621 31772587402473061 622 32910597387120443 623 34088435912315575 624 35307465120083785 625 36569092678419639 626 37874773268448017 627 39226010119040381 628 40624356590260399 629 42071417807455275 630 43568852347384605 631 45118373977895289 632 46721753453114503 633 48380820365693017 634 50097465057756673 635 51873640592706057 636 53711364789550197 637 55612722321597323 638 57579866881822535 639 59615023416769191 640 61720490430985579 641 63898642364512911 642 66151932045469809 643 68482893219927439 644 70894143161807473 645 73388385365052047 646 75968412320470897 647 78637108380234223 648 81397452712481189 649 84252522348682147 650 87205495326978589 651 90259653934212525 652 93418388049538800 653 96685198593120298 654 100063701082883950 655 103557629302508658 656 107170839084445318 657 110907312211239290 658 114771160438627014 659 118766629644535866 660 122898104107575684 661 127170110918821516 662 131587324531376500 663 136154571451647778 664 140876835076495292 665 145759260681132426 666 150807160562087158 667 156026019339778826 668 161421499426010638 669 166999446661099668 670 172765896125628690 671 178727078132578222 672 184889424405013318 673 191259574444774259 674 197844382098431225 675 204650922326169295 676 211686498179559985 677 218958647995027087 678 226475152809206295 679 234244044002710871 680 242273611179704489 681 250572410290062679 682 259149272001242761 683 268013310327905837 684 277173931526709725 685 286640843264052681 686 296424064065510711 687 306533933055083721 688 316981119992746519 689 327776635619810815 690 338931842320970241 691 350458465112305009 692 362368602965583951 693 374674740478557873 694 387389759901373461 695 400526953530348285 696 414100036479695899 697 428123159842260965 698 442610924251483277 699 457578393856157331 700 473041110720059245 701 489015109659722799 702 505516933532998831 703 522563648991567089 704 540172862711841551 705 558362738118063409 706 577152012611945089 707 596560015324569083 708 616606685405594117 709 637312590865435897 710 658698947987495687 711 680787641326859403 712 703601244312555177 713 727163040471927127 714 751497045295042921 715 776628028757765665 716 802581538523661834 717 829383923844290934 718 857062360178181944 719 885644874550425288 720 915160371674194658 721 945638660856325214 722 977110483710787822 723 1009607542703293714 724 1043162530551140078 725 1077809160504209848 726 1113582197532448118 727 1150517490446085002 728 1188652004976766816 729 1228023857847191684 730 1268672351857864458 731 1310638012021574894 732 1353962622775669534 733 1398689266303276796 734 1444862361996744984 735 1492527707096050800 736 1541732518536102800 737 1592525476039086324 738 1644956766487523111 739 1699078129614978383 740 1754942905053693743 741 1812606080777986871 742 1872124342983622325 743 1933556127445826571 744 1996961672398234613 745 2062403072976522787 746 2129944337273086339 747 2199651444048795521 748 2271592402149435701 749 2345837311677195147 750 2422458426967299483 751 2501530221421580901 752 2583129454253694659 753 2667335239200491899 754 2754229115255882661 755 2843895119486617389 756 2936419861989285009 757 3031892603049798511 758 3130405332569908899 759 3232052851825248605 760 3336932857621531393 761 3445146028918996479 762 3556796115995248129 763 3671990032218926389 764 3790837948510317665 765 3913453390565186015 766 4039953338920563745 767 4170458331945143907 768 4305092571837202077 769 4443984033715628933 770 4587264577893800045 771 4735070065426420681 772 4887540477022355011 773 5044820035420841557 774 5207057331329060421 775 5374405453022115067 776 5547022119711152901 777 5725069818786084499 778 5908715947042692461 779 6098132956008882835 780 6293498501485747093 781 6494995597422691447 782 6702812774251176841 783 6917144241802717118 784 7138190056940661348 785 7366156296040911268 786 7601255232458042492 787 7843705519117491396 788 8093732376380449660 789 8351567785329671458 790 8617450686628922730 791 8891627185115167382 792 9174350760284419990 793 9465882482837068524 794 9766491237455260044 795 10076453951987066484 796 10396055833217402786 797 10725590609412917602 798 11065360779830509214 799 11415677871384796898 800 11776862702677610102 801 12149245655595330954 802 12533166954686063612 803 12928976954536846162 804 13337036435374278448 805 13757716907118565584 806 14191400922129770067 807 14638482396888648133 808 15099366942861588755 809 15574472206808571629 810 16064228220797097625 811 16569077762192748985 812 17089476723907089735 813 17625894495188137555 814 18178814353246962605 815 18748733866024714667 816 19336165306409433565 817 19941636078220995943 818 20565689154294030375 819 21208883526994282013 820 21871794671513620995 821 22555015022301162647 822 23259154462994267593 823 23984840830223664887 824 24732720431680083135 825 25503458578836771583 826 26297740134733597159 827 27116270077242480601 828 27959774078241681447 829 28828999099138652121 830 29724714003196255163 831 30647710185125703557 832 31598802218422777223 833 32578828520940003961 834 33588652039196962261 835 34629160951945107819 836 35701269393520805563 837 36805918197530705417 838 37944075661428966225 839 39116738332564358661 840 40324931816286795451 841 41569711606719417919 842 42852163940822241441 843 44173406676386018007 844 45534590194612881643 845 46936898327961653013 846 48381549313949575403 847 49869796775621599125 848 51402930729421174111 849 52982278621211769191 850 54609206391219218073 851 56285119568689490279 852 58011464397073225881 853 59789728990570899318 854 61621444522898774218 855 63508186449154143854 856 65451575761682660212 857 67453280280878790028 858 69515015981870482036 859 71638548358065376130 860 73825693822566193834 861 76078321148484858072 862 78398352949213230684 863 80787767199740884388 864 83248598800134267132 865 85782941182322203396 866 88392947961367599676 867 91080834632431368096 868 93848880314667578142 869 96699429543326362178 870 99634894111369622020 871 102657754961940183036 872 105770564133065354756 873 108975946756006934134 874 112276603108708110730 875 115675310725831043382 876 119174926566912724032 877 122778389244208219657 878 126488721311836903943 879 130309031617884150201 880 134242517721155708517 881 138292468374331971709 882 142462266075309460495 883 146755389688565124223 884 151175417138432781251 885 155726028176224662635 886 160411007223183084757 887 165234246291305042087 888 170199747984129931673 889 175311628579636795977 890 180574121197459563959 891 185991579052680286025 892 191568478798520969399 893 197309423960321357713 894 203219148463245957377 895 209302520256228988671 896 215564545034737683403 897 222010370064995111989 898 228645288112374218941 899 235474741476751895403 900 242504326137677850259 901 249739796012289060911 902 257187067328983558489 903 264852223119938803221 904 272741517835641894989 905 280861382084688091507 906 289218427502181622733 907 297819451750161219159 908 306671443653568710217 909 315781588475363079095 910 325157273334477709679 911 334806092770421728159 912 344735854458417408813 913 354954585079068397715 914 365470536346664476013 915 376292191200327225349 916 387428270162311757169 917 398887737867899037387 918 410679809771420128757 919 422813959033073128587 920 435299923591321969525 921 448147713425781841035 922 461367618015624772009 923 474970213998676991241 924 488966373036504784877 925 503367269890924376083 926 518184390717519859486 927 533429541581888586714 928 549114857204482978854 929 565252809940077494424 930 581856218998035887176 931 598938259909715075768 932 616512474249513802312 933 634592779616232546646 934 653193479881584869088 935 672329275712885209436 936 692015275377109275514 937 712267005833710340970 938 733100424123773592214 939 754531929063275601258 940 776578373248417679294 941 799257075381215713058 942 822585832923728933138 943 846582935089527316206 944 871267176181227356626 945 896657869283141833262 946 922774860318323215890 947 949638542479527807470 948 977269871043860864530 949 1005690378581115024302 950 1034922190566080529048 951 1064988041405357475385 952 1095911290889471851815 953 1127715941081383383805 954 1160426653652744992003 955 1194068767679566103573 956 1228668317909239930477 957 1264252053511188207507 958 1300847457323691775413 959 1338482765609806540789 960 1377186988335580942765 961 1416989929984130118609 962 1457922210919478132015 963 1500015289314421198289 964 1543301483657029924475 965 1587813995850791634565 966 1633586934923762307451 967 1680655341362490729513 968 1729055212086889390777 969 1778823526082624070351 970 1829998270708017209073 971 1882618468692903140647 972 1936724205847301837209 973 1992356659498233295719 974 2049558127673471061163 975 2108372059051495478121 976 2168843083697397487055 977 2231017044604996054535 978 2294941030065930444537 979 2360663406887016155861 980 2428233854477704184309 981 2497703399830020140043 982 2569124453413927576309 983 2642550846011652128075 984 2718037866515081642835 985 2795642300710968503469 986 2875422471079297090387 987 2957438277630802779313 988 3041751239810286282061 989 3128424539493051736755 990 3217523065102468616165 991 3309113456877364804237 992 3403264153318694208883 993 3500045438845645748521 994 3599529492692121455729 995 3701790439075302668705 996 3806904398668802457183 997 3914949541413720962497 998 4026006140701770837677 999 4140156628965479061587 1000 4257485654711351820239