0 0 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 3 9 3 10 5 11 5 12 7 13 7 14 10 15 11 16 14 17 15 18 19 19 22 20 26 21 30 22 35 23 42 24 47 25 56 26 62 27 76 28 83 29 100 30 108 31 132 32 142 33 171 34 184 35 222 36 239 37 284 38 306 39 363 40 394 41 460 42 500 43 581 44 636 45 730 46 802 47 914 48 1010 49 1139 50 1262 51 1415 52 1577 53 1753 54 1956 55 2163 56 2423 57 2663 58 2986 59 3268 60 3672 61 4002 62 4495 63 4885 64 5493 65 5953 66 6685 67 7232 68 8119 69 8772 70 9830 71 10610 72 11875 73 12812 74 14305 75 15431 76 17200 77 18558 78 20628 79 22262 80 24691 81 26665 82 29493 83 31867 84 35162 85 38026 86 41841 87 45278 88 49703 89 53834 90 58939 91 63879 92 69776 93 75688 94 82479 95 89514 96 97340 97 105714 98 114713 99 124629 100 134990 101 146727 102 158637 103 172461 104 186165 105 202436 106 218199 107 237262 108 255403 109 277719 110 298596 111 324610 112 348655 113 378948 114 406644 115 441791 116 473707 117 514440 118 551235 119 598284 120 640710 121 694998 122 743933 123 806390 124 862836 125 934616 126 999737 127 1082023 128 1157131 129 1251367 130 1338007 131 1445693 132 1545580 133 1668529 134 1783677 135 1923787 136 2056439 137 2215980 138 2368749 139 2550136 140 2725916 141 2931996 142 3134169 143 3368000 144 3600286 145 3865456 146 4132181 147 4432570 148 4738501 149 5078625 150 5429270 151 5814064 152 6215477 153 6650633 154 7109803 155 7601588 156 8126174 157 8681788 158 9280585 159 9907981 160 10590648 161 11298923 162 12076494 163 12875761 164 13760335 165 14662087 166 15667464 167 16684525 168 17825820 169 18972732 170 20267112 171 21560119 172 23026419 173 24483881 174 26143408 175 27785892 176 29662016 177 31512671 178 33631782 179 35716575 180 38107617 181 40455723 182 43151277 183 45795397 184 48831249 185 51808048 186 55224372 187 58574976 188 62415901 189 66186278 190 70501281 191 74742977 192 79586426 193 84356978 194 89789692 195 95153526 196 101242424 197 107271330 198 114091130 199 120865453 200 128498399 201 136107467 202 144645301 203 153188984 204 162732737 205 172321941 206 182984140 207 193742642 208 205647328 209 217712399 210 230997558 211 244522248 212 259340035 213 274493780 214 291013336 215 307984805 216 326392710 217 345390570 218 365894005 219 387150217 220 409977867 221 433748696 222 459154267 223 485724262 224 513987829 225 543670935 226 575103034 227 608247407 228 643190888 229 680180341 230 719015018 231 760274558 232 803419863 233 849417616 234 897337841 235 948591632 236 1001799440 237 1058879053 238 1117941602 239 1181476611 240 1247020043 241 1317702758 242 1390419234 243 1469013680 244 1549667248 245 1637013020 246 1726447667 247 1823470503 248 1922617523 249 2030333966 250 2140221442 251 2259751312 252 2381513211 253 2514085574 254 2648972755 255 2795940251 256 2945331856 257 3108178337 258 3273594533 259 3453951867 260 3637067798 261 3836725169 262 4039386012 263 4260309659 264 4484547503 265 4728892433 266 4976943918 267 5247076646 268 5521403568 269 5819916817 270 6123226734 271 6452966084 272 6788237121 273 7152318868 274 7522824139 275 7924666564 276 8334003806 277 8777349316 278 9229469635 279 9718420942 280 10217664436 281 10756711900 282 11307841406 283 11901905448 284 12510148974 285 13164613145 286 13835703901 287 14556464645 288 15296691279 289 16090198396 290 16906452262 291 17779766722 292 18679601634 293 19640444909 294 20632132783 295 21688954696 296 22781556204 297 23943594216 298 25147024750 299 26424383598 300 27749496463 301 29153219947 302 30611884291 303 32154048088 304 33759247161 305 35453045443 306 37218968441 307 39078822855 308 41020980532 309 43062643680 310 45197977093 311 47438660478 312 49785676574 313 52244174761 314 54823074806 315 57519914857 316 60352753868 317 63310343899 318 66421181943 319 69663986574 320 73079075762 321 76633792588 322 80381755897 323 84277521372 324 88389571417 325 92658171072 326 97168321060 327 101844430175 328 106789750342 329 111911183688 330 117332049642 331 122940043845 332 128880436673 333 135019945396 334 141527744597 335 148247769579 336 155375103616 337 162729044088 338 170532635411 339 178578675044 340 187120250201 341 195921769844 342 205268465080 343 214894496140 344 225119336630 345 235645046711 346 246827424004 347 258334647667 348 270560878865 349 283138689560 350 296502578653 351 310247908635 352 324851399677 353 339869712271 354 355823548235 355 372229562988 356 389654048175 357 407572528812 358 426598302705 359 446164904587 360 466933830660 361 488296024711 362 510962098448 363 534280159720 364 559010545581 365 584458634958 366 611434730206 367 639202048623 368 668620692384 369 698912744405 370 730987464474 371 764027404710 372 798989825798 373 835019935219 374 873121238823 375 912404493047 376 953917058483 377 996738850350 378 1041957961779 379 1088627928939 380 1137873686645 381 1188727718124 382 1242347034613 383 1297749398750 384 1356118222623 385 1416463904399 386 1479989552496 387 1545706728181 388 1614830473765 389 1686383230619 390 1761583024747 391 1839474239470 392 1921267721564 393 2006042220687 394 2094989893556 395 2187237798962 396 2283946527617 397 2384306928753 398 2489433641638 399 2598598479961 400 2712854235250 401 2831572567253 402 2955726862625 403 3084809370131 404 3219694866022 405 3360018799998 406 3506536336398 407 3659050750206 408 3818174828340 409 3983906310094 410 4156690927665 411 4336749667207 412 4524334679388 413 4719921110002 414 4923539009504 415 5135950840756 416 5356934135022 417 5587574041596 418 5827363127463 419 6077746896348 420 6337898608913 421 6609664038815 422 6891860790466 423 7186777123071 424 7492836807416 425 7812815021277 426 8144701609400 427 8491805335699 428 8851640343333 429 9228097764576 430 9618172532157 431 10026389008661 432 10449177968235 433 10891749788654 434 11349924685017 435 11829653662387 436 12326098896811 437 12846008250259 438 13383837334964 439 13947188558445 440 14529761851943 441 15140073046527 442 15771016782677 443 16432082141191 444 17115308913918 445 17831219876708 446 18570950631396 447 19346118379628 448 20146906063799 449 20986085921001 450 21852840878705 451 22761158269898 452 23699175532029 453 24682154114300 454 25697142707600 455 26760734313616 456 27858848728998 457 29009465787332 458 30197339785167 459 31441889841305 460 32726672721678 461 34072595784618 462 35461991349923 463 36917299677574 464 38419608014091 465 39992929113637 466 41617091475722 467 43317713933485 468 45073360842880 469 46911283819189 470 48808786739666 471 50794772734723 472 52845299419852 473 54990931217853 474 57206505163534 475 59524246562789 476 61917810661818 477 64421071958899 478 67006556868790 479 69709764721075 480 72502162028260 481 75420834733583 482 78436275529576 483 81587103354961 484 84842942293839 485 88243873977230 486 91758779529363 487 95429114607530 488 99223165583234 489 103183653743067 490 107278442911303 491 111551390058606 492 115970134924164 493 120579517252407 494 125347178957125 495 130318764743308 496 135462175147032 497 140823655659586 498 146371653702297 499 152152783000115 500 158136360416551 501 164369105514256 502 170821563152326 503 177540264407645 504 184497379223215 505 191738922526952 506 199239126693340 507 207043127389517 508 215127699601016 509 223536699844058 510 232249970435602 511 241309650008943 512 250699220008295 513 260458622425434 514 270575598362469 515 281087372404692 516 291986617018105 517 303307275663486 518 315047676577361 519 327237873603477 520 339882630148823 521 353007456524081 522 366624387024635 523 380753687532765 524 395415557304592 525 410624269666865 526 426409142322963 527 442777659467334 528 459769271841100 529 477383829758191 530 495671993365345 531 514625085410235 532 534306114845666 533 554696935134953 534 575874106655377 535 597809023673267 536 620593064497387 537 644186127762613 538 668695739704742 539 694069220923197 540 720431639023006 541 747716610815137 542 776068201014852 543 805405154967231 544 835892051659725 545 867431559072737 546 900210347016834 547 934113764483052 548 969352206139774 549 1005792429607060 550 1043670242884540 551 1082832512797617 552 1123542200494081 553 1165624961998414 554 1209372698511172 555 1254588519799448 556 1301595096671364 557 1350171649847759 558 1400673486319118 559 1452854594428715 560 1507104814941176 561 1563151569941660 562 1621421155426058 563 1681613111414507 564 1744192126705122 565 1808828573645656 566 1876027478630064 567 1945428801606511 568 2017579848919542 569 2092088978712060 570 2169547706396409 571 2249531667226599 572 2332678489759147 573 2418530050583780 574 2507771957592376 575 2599911393741392 576 2695683760445969 577 2794560732659804 578 2897329252411382 579 3003424811098266 580 3113687554788289 581 3227516277348982 582 3345805891171540 583 3467918161383080 584 3594804208628972 585 3725788646783250 586 3861880106381681 587 4002366160516820 588 4148314088988898 589 4298974796890056 590 4455475167855184 591 4617030101622095 592 4784826830657675 593 4958045234660031 594 5137933405177467 595 5323637540853253 596 5516466840153866 597 5715535549713526 598 5922213932583154 599 6135586436967960 600 6357084027466722 601 6585763972054277 602 6823117222810039 603 7068176988277424 604 7322493109649665 605 7585078403146892 606 7857540083669623 607 8138874830044922 608 8430745262532770 609 8732136812580988 610 9044765049651894 611 9367609727777773 612 9702436383396151 613 10048225393748875 614 10406788717227152 615 10777114433596015 616 11161056775188257 617 11557619436123137 618 11968694133561233 619 12393308971273206 620 12833387679326740 621 13287992506488764 622 13759073002155527 623 14245736288856183 624 14749950777518181 625 15270880245522903 626 15810504204389585 627 16368055975019916 628 16945517562885707 629 17542205889157490 630 18160095962851274 631 18798603586742777 632 19459686357556716 633 20142875526912067 634 20850099901927163 635 21581024093016329 636 22337535739326018 637 23119452123965880 638 23928606305876970 639 24764989014801678 640 25630364247345103 641 26524918473763676 642 27450331048258709 643 28407008049645591 644 29396527480755909 645 30419540528408913 646 31477505984778891 647 32571347326352996 648 33702385101028830 649 34871843991931318 650 36080886081850031 651 37331067958606655 652 38623371816987880 653 39959718675703498 654 41340888214554327 655 42769200276429600 656 44245208191686041 657 45771666926776353 658 47348878432173595 659 48980071033307208 660 50665269085141441 661 52408214472307875 662 54208626581229139 663 56070803039357151 664 57994129762200677 665 59983504303001082 666 62037949521901981 667 64163009085007965 668 66357312179098482 669 68627096774736201 670 70970566804114407 671 73394704726364468 672 75897256747279999 673 78486001973209501 674 81158195618201735 675 83922467537235197 676 86775547994493093 677 89726973598075602 678 92772915139317128 679 95923873832354803 680 99175426040799935 681 102539097221414860 682 106009834086584645 683 109600247674867156 684 113304619725004909 685 117136709805867661 686 121090099464357605 687 125179761246452996 688 129398541604580841 689 133762691881354447 690 138264289095586327 691 142920930434205593 692 147723889964591957 693 152692178832219910 694 157816235754515452 695 163116554834308572 696 168582708469374548 697 174236743401976694 698 180067336522515701 699 186098157354983714 700 192316960243354490 701 198749107850920386 702 205381407498595804 703 212240985294207414 704 219313680050523312 705 226628451280629742 706 234170151275541301 707 241969642254007939 708 250010775940178041 709 258326385555898018 710 266899312733187668 711 275764428624292113 712 284903560334105103 713 294353682106048696 714 304095607801253457 715 314168477727457374 716 324552100152563931 717 335287841781411970 718 346354520016438984 719 357795785174502555 720 369589486329704690 721 381781610997113330 722 394349071065506150 723 407340240670206200 724 420731135083691672 725 434572559748996011 726 448839684204554095 727 463585784560159662 728 478785246727528060 729 494493850883605300 730 510685273627456368 731 527417825992863536 732 544664562793837601 733 562486345411011441 734 580855708693137611 735 599836075849468438 736 619399578979726562 737 639612205849687627 738 660445819600173460 739 681968965765814494 740 704153390095229017 741 727070178790357719 742 750691130827918956 743 775089844851602890 744 800238364041205799 745 826212759287660413 746 852985530679001345 747 880635168338428889 748 909134865095654542 749 938565463586903123 750 968901109816811162 751 1000224917627799264 752 1032512272723992645 753 1065848463347500292 754 1100210429081229535 755 1135685519357406048 756 1172252571051348788 757 1210000864245981238 758 1248911507405496352 759 1289075562485862639 760 1330476816379783769 761 1373207944975133128 762 1417255854700641865 763 1462714647376701366 764 1509574826074096902 765 1557931709584492307 766 1607779912514852735 767 1659215739845636740 768 1712238472190237727 769 1766945147256464434 770 1823340307550126771 771 1881521446568223006 772 1941499007840394845 773 2003370639453997320 774 2067153370211294948 775 2132944676625321582 776 2200768903988795230 777 2270723005432711658 778 2342839422810469409 779 2417214207842841918 780 2493888729717287301 781 2572957733963569024 782 2654472400449192506 783 2738525736570697752 784 2825179670617630593 785 2914525012405646467 786 3006635432611038870 787 3101599056322021037 788 3199502348553891662 789 3300430234715409294 790 3404483085851924506 791 3511742085009249364 792 3622322682363902529 793 3736301748370504188 794 3853811048485902281 795 3974922543200836538 796 4099785613988338542 797 4228466687399730687 798 4361134127729712800 799 4497848177804345034 800 4638797618976785264 801 4784035835717092895 802 4933773529386904930 803 5088056527881483481 804 5247119025370539173 805 5410998572833291122 806 5579954500926282630 807 5754015343049970305 808 5933467281764171664 809 6118329073955039289 810 6308915541961807804 811 6505234891380667545 812 6707632445189082695 813 6916105069800126564 814 7131030523026285787 815 7352393534245521259 816 7580606303766244098 817 7815640619615902182 818 8057945205648390040 819 8307478101748868549 820 8564726709419540697 821 8829634515508847061 822 9102729825750139227 823 9383940775883773097 824 9673838874071222985 825 9972336119062054664 826 10280049590116277132 827 10596874381279731635 828 10923475580587423318 829 11259730634317015593 830 11606355144179876639 831 11963208197430499159 832 12331058479441543877 833 12709746046717727568 834 13100095300866144099 835 13501926643915945053 836 13916122885980272684 837 14342484207981157326 838 14781954577224705145 839 15234313453908958805 840 15700568763923660027 841 16180478824749091289 842 16675118370808257257 843 17184224244004247791 844 17708940881197396847 845 18248983417256186961 846 18805568924259850352 847 19378390713236601913 848 19968741457577188562 849 20576292656391689096 850 21202415577711341976 851 21846760064516067973 852 22510778993451767658 853 23194100867058751589 854 23898263198084061298 855 24622873641400648743 856 25369557379185061211 857 26137901906646588857 858 26929623106319735953 859 27744289216359267324 860 28583709839390821384 861 29447435094144898088 862 30337371302486994188 863 31253051858094690145 864 32196482770685695469 865 33167182382829943352 866 34167259319611604690 867 35196218850226866466 868 36256275090419513770 869 37346922542929844863 870 38470483625493028043 871 39626444737348448830 872 40817239333303061087 873 42042348756184764451 874 43304320143799285694 875 44602633243412520026 876 45939951419174865581 877 47315756728329647915 878 48732831188114502077 879 50190663548501660339 880 51692156775448611558 881 53236811205498867164 882 54827652902783741431 883 56464199230880387457 884 58149601339874402963 885 59883399644388504732 886 61668872190565164444 887 63505589090261487668 888 65396956901749288440 889 67342582742549181014 890 69346003088315532123 891 71406870074698738971 892 73528851272136607476 893 75711652594168144105 894 77959073638189286005 895 80270883647692250202 896 82651014916491590281 897 85099310408882862319 898 87619835504142333168 899 90212518165249807504 900 92881556947911119334 901 95626977028407825443 902 98453109914050370990 903 101360091197236863636 904 104352384778788124936 905 107430250911126641257 906 110598284979873380725 907 113856887237098274353 908 117210783277023107062 909 120660529842714097895 910 124210981076792639057 911 127862867914080700389 912 131621170985630842006 913 135486814387196801939 914 139464902763393817674 915 143556573669102564427 916 147767052858669747324 917 152097713035147102967 918 156553897716707437479 919 161137237897790686564 920 165853191060747204289 921 170703671153224434912 922 175694245358013958520 923 180827136822182096588 924 186108017692662337242 925 191539448213289003148 926 197127200279552757581 927 202874200848483068561 928 208786315864894645771 929 214866870403230536174 930 221121818272626659675 931 227554915926659722194 932 234172198368806232396 933 240977888621264175105 934 247978095730483976448 935 255177546475567854091 936 262582416320315418861 937 270197975059144534506 938 278030456483876831306 939 286085714804606997163 940 294370033602942261542 941 302889895118802677081 942 311651623755359286768 943 320662375682309431148 944 329928506750121957606 945 339457895315731118651 946 349256918925452705246 947 359334228809956312168 948 369696214117509186964 949 380352352138909450448 950 391309033228565848056 951 402576616493982738451 952 414161482845353680615 953 426074931602862050746 954 438323323381701645540 955 450918958818317298262 956 463868167243696021713 957 477184314488428575300 958 490873687541482036256 959 504950784145004925518 960 519421837898374232188 961 534302548075462689767 962 549599083936546840707 963 565328418871395425607 964 581496647047835837302 965 598122091578450561861 966 615210761089758515940 967 632782407103043397501 968 650842942679114186884 969 669413629565983099649 970 688500275790367960700 971 708125738327256794163 972 728295711401581174081 973 749034735444233419692 974 770348382969083755127 975 792262969363310218280 976 814783938551281463768 977 837939475686861252228 978 861734890444377022390 979 886200335899059255818 980 911340983235988817323 981 937189054980181163832 982 963749581229382475724 983 991056958885075476625 984 1019116076238649648863 985 1047963612912124118114 986 1077604316806680956498 987 1108077262039897917966 988 1139387059950255765783 989 1171575294364437324027 990 1204646446593342562173 991 1238644728826234982546 992 1273574501907528542834 993 1309482728477312637841 994 1346373661841044917062 995 1384297140600744888132 996 1423257327181568990845 997 1463307065062429615994 998 1504450446566884232231 999 1546743452343266497567 1000 1590190129927671651048