1 1 2 2 3 3 4 4 5 6 6 9 7 11 8 15 9 19 10 25 11 31 12 41 13 49 14 61 15 75 16 91 17 109 18 134 19 156 20 188 21 221 22 262 23 305 24 361 25 416 26 485 27 560 28 648 29 740 30 858 31 972 32 1115 33 1266 34 1441 35 1627 36 1851 37 2078 38 2348 39 2634 40 2965 41 3309 42 3721 43 4138 44 4625 45 5143 46 5728 47 6344 48 7059 49 7792 50 8637 51 9525 52 10529 53 11577 54 12778 55 14020 56 15422 57 16904 58 18555 59 20284 60 22242 61 24265 62 26537 63 28923 64 31568 65 34340 66 37434 67 40653 68 44221 69 47972 70 52104 71 56423 72 61216 73 66196 74 71684 75 77447 76 83747 77 90347 78 97597 79 105150 80 113419 81 122083 82 131522 83 141389 84 152170 85 163407 86 175629 87 188441 88 202312 89 216822 90 232584 91 249007 92 266801 93 285417 94 305502 95 326500 96 349188 97 372847 98 398347 99 425022 100 453688 101 483631 102 515866 103 549454 104 585533 105 623242 106 663615 107 705783 108 750983 109 798089 110 848508 111 901156 112 957369 113 1016023 114 1078702 115 1143999 116 1213657 117 1286365 118 1363754 119 1444473 120 1530468 121 1620009 122 1715282 123 1814634 124 1920130 125 2030094 126 2146913 127 2268521 128 2397556 129 2532043 130 2674513 131 2822908 132 2980191 133 3143824 134 3317059 135 3497494 136 3688214 137 3886767 138 4096713 139 4315050 140 4545708 141 4785773 142 5039055 143 5302550 144 5580606 145 5869640 146 6174360 147 6491334 148 6825128 149 7172184 150 7537738 151 7917505 152 8317197 153 8732669 154 9169471 155 9623368 156 10100591 157 10596157 158 11116825 159 11657728 160 12225535 161 12815178 162 13434175 163 14076599 164 14750540 165 15450267 166 16183693 167 16944936 168 17742849 169 18570550 170 19437643 171 20337329 172 21279134 173 22256065 174 23278657 175 24338904 176 25448083 177 26598356 178 27800915 179 29047655 180 30351019 181 31701627 182 33112891 183 34575568 184 36102946 185 37685612 186 39338110 187 41049721 188 42836072 189 44686515 190 46616704 191 48615635 192 50700511 193 52858829 194 55108971 195 57438642 196 59866105 197 62378811 198 64996730 199 67705574 200 70526815 201 73446183 202 76485211 203 79629297 204 82901827 205 86286429 206 89807994 207 93450316 208 97238343 209 101155428 210 105228778 211 109439562 212 113816873 213 118341991 214 123044048 215 127904004 216 132953311 217 138170695 218 143589676 219 149189012 220 155002511 221 161008330 222 167243076 223 173682378 224 180365096 225 187267068 226 194427306 227 201821162 228 209490721 229 217408479 230 225619251 231 234095491 232 242882470 233 251952023 234 261352768 235 271053623 236 281106022 237 291478997 238 302224527 239 313310861 240 324793918 241 336638502 242 348903902 243 361554952 244 374651551 245 388157886 246 402137976 247 416552448 248 431469060 249 446848313 250 462758994 251 479160616 252 496126737 253 513612960 254 531696917 255 550334267 256 569603631 257 589459783 258 609986610 259 631134485 260 652992136 261 675509654 262 698777192 263 722743870 264 747505506 265 773006720 266 799348468 267 826475186 268 854489558 269 883334789 270 913120133 271 943783594 272 975440388 273 1008028279 274 1041664323 275 1076285296 276 1112015205 277 1148785355 278 1186726470 279 1225769305 280 1266047130 281 1307489297 282 1350236963 283 1394213598 284 1439567600 285 1486222180 286 1534328354 287 1583808014 288 1634820977 289 1687282466 290 1741360800 291 1796970491 292 1854283128 293 1913211892 294 1973937790 295 2036367239 296 2100690299 297 2166812775 298 2234928641 299 2304941924 300 2377057492 301 2451171635 302 2527499509 303 2605936810 304 2686702854 305 2769691944 306 2855134968 307 2942918112 308 3033283809 309 3126117168 310 3221665998 311 3319813418 312 3420820258 313 3524561046 314 3631308980 315 3740937964 316 3853726878 317 3969547733 318 4088693899 319 4211027738 320 4336856929 321 4466042572 322 4598899170 323 4735285942 324 4875532884 325 5019489525 326 5167501128 327 5319416082 328 5475587630 329 5635861692 330 5800609208 331 5969665168 332 6143417697 333 6321700646 334 6504910769 335 6692879996 336 6886023919 337 7084163093 338 7287732272 339 7496550231 340 7711062265 341 7931084534 342 8157083332 343 8388862862 344 8626910068 345 8871027908 346 9121714658 347 9378770850 348 9642717979 349 9913343328 350 10191191927 351 10476049042 352 10768472855 353 11068246328 354 11375952567 355 11691361180 356 12015080601 357 12346878542 358 12687378486 359 13036345249 360 13394430399 361 13761383933 362 14137885645 363 14523683710 364 14919474282 365 15325003356 366 15740997233 367 16167186450 368 16604328652 369 17052151846 370 17511432838 371 17981896841 372 18464353982 373 18958513368 374 19465218982 375 19984178072 376 20516255466 377 21061155834 378 21619780828 379 22191817451 380 22778205375 381 23378629062 382 23994051762 383 24624155733 384 25269943867 385 25931080608 386 26608609974 387 27302193982 388 28012903399 389 28740397405 390 29485791018 391 30248724056 392 31030356833 393 31830327134 394 32649824376 395 33488484459 396 34347544583 397 35226620456 398 36126999416 399 37048294354 400 37991825984 401 38957204873 402 39945804112 403 40957213635 404 41992860600 405 43052333078 406 44137094761 407 45246731677 408 46382765321 409 47544759289 410 48734295243 411 49950934382 412 51196299121 413 52469949491 414 53773570057 415 55106698499 416 56471084566 417 57866263703 418 59294031592 419 60753921920 420 62247799253 421 63775173398 422 65337980282 423 66935728335 424 68570403383 425 70241513639 426 71951119369 427 73698704069 428 75486406745 429 77313708713 430 79182805418 431 81093177886 432 83047102766 433 85044036279 434 87086339970 435 89173469371 436 91307847727 437 93488931010 438 95719231758 439 97998179233 440 100328379887 441 102709262046 442 105143500402 443 107630525365 444 110173107690 445 112770651580 446 115426029506 447 118138645327 448 120911447673 449 123743842317 450 126638883780 451 129595950249 452 132618207235 453 135705034145 454 138859679183 455 142081526115 456 145373937630 457 148736269383 458 152172005895 459 155680503713 460 159265339771 461 162925875595 462 166665812755 463 170484485108 464 174385725630 465 178368871454 466 182437856427 467 186592024248 468 190835445247 469 195167433935 470 199592205020 471 204109076839 472 208722375047 473 213431427235 474 218240706148 475 223149511424 476 228162472067 477 233278893047 478 238503526186 479 243835686522 480 249280287088 481 254836614353 482 260509751260 483 266298992316 484 272209553929 485 278240744367 486 284397954401 487 290680464025 488 297093849627 489 303637400024 490 310316839340 491 317131472172 492 324087211927 493 331183336529 494 338425959648 495 345814371715 496 353354847558 497 361046696380 498 368896399486 499 376903239009 500 385073915026 501 393407724270 502 401911543169 503 410584691782 504 419434269152 505 428459570839 506 437667932612 507 447058667584 508 456639305586 509 466409185695 510 476376080491 511 486539305579 512 496906890157 513 507478172083 514 518261391236 515 529255917281 516 540470252599 517 551903745160 518 563565176797 519 575453920421 520 587578989359 521 599939792841 522 612545628388 523 625395887256 524 638500168325 525 651857893784 526 665478914559 527 679362694547 528 693519393812 529 707948459832 530 722660380550 531 737654639096 532 752941997974 533 768521989715 534 784405709991 535 800592679929 536 817094349614 537 833910281406 538 851052226032 539 868519800835 540 886325118632 541 904467789096 542 922960308269 543 941802335144 544 961006691539 545 980573100850 546 1000514776065 547 1020831437500 548 1041536714206 549 1062630381748 550 1084126425290 551 1106024693083 552 1128339593024 553 1151070977546 554 1174233702721 555 1197827686205 556 1221868170786 557 1246355156233 558 1271304343925 559 1296715742859 560 1322605540451 561 1348973819748 562 1375837188191 563 1403195823356 564 1431066826552 565 1459450393891 566 1488364151120 567 1517808378532 568 1547801159782 569 1578342880072 570 1609452158294 571 1641129406358 572 1673393809212 573 1706245876160 574 1739705287548 575 1773772672649 576 1808468289097 577 1843792802515 578 1879767083243 579 1916391905577 580 1953688679168 581 1991658312419 582 2030322837905 583 2069683213210 584 2109762130323 585 2150560671634 586 2192102113257 587 2234387687739 588 2277441345015 589 2321264377841 590 2365881449287 591 2411293992170 592 2457527302453 593 2504582982696 594 2552487053962 595 2601241195068 596 2650872195315 597 2701381890994 598 2752797758606 599 2805121822356 600 2858382342493 601 2912581434784 602 2967748187418 603 3023884894686 604 3081021387041 605 3139160170326 606 3198331919076 607 3258539248368 608 3319813726514 609 3382158166985 610 3445604943134 611 3510157103288 612 3575847930275 613 3642680603110 614 3710689365633 615 3779877620822 616 3850280482402 617 3921901614370 618 3994777111842 619 4068910790010 620 4144339780650 621 4221068148335 622 4299133965070 623 4378541586905 624 4459330141000 625 4541504161028 626 4625103889207 627 4710134137176 628 4796636164693 629 4884615104856 630 4974113355291 631 5065136253237 632 5157727396022 633 5251892432020 634 5347676055731 635 5445084273476 636 5544163003530 637 5644918486358 638 5747397932379 639 5851607926131 640 5957596864356 641 6065371726643 642 6174982226268 643 6286435611857 644 6399782984328 645 6515031976280 646 6632234967788 647 6751400027720 648 6872580953849 649 6995786119020 650 7121070814647 651 7248443838281 652 7377961860858 653 7509634163004 654 7643518938066 655 7779625813051 656 7918014585445 657 8058695352264 658 8201729399922 659 8347127355947 660 8494952145226 661 8645214785145 662 8797979923808 663 8953259099920 664 9111118564068 665 9271570441266 666 9434682741618 667 9600468028631 668 9768996164787 669 9940280287161 670 10114391986543 671 10291345043775 672 10471212939671 673 10654009948622 674 10839811538125 675 11028632617464 676 11220550513766 677 11415580843684 678 11613802965746 679 11815233046541 680 12019952579199 681 12227978428447 682 12439394088865 683 12654217203417 684 12872533445308 685 13094361073660 686 13319788050679 687 13548833403763 688 13781587250040 689 14018069468198 690 14258372515979 691 14502516956648 692 14750597703342 693 15002636165550 694 15258729571479 695 15518900265986 696 15783247987039 697 16051795840278 698 16324646198351 699 16601823093809 700 16883431390516 701 17169496143417 702 17460124908533 703 17755343586156 704 18055262554306 705 18359908732862 706 18669395175085 707 18983749919397 708 19303088907523 709 19627441111163 710 19956925499054 711 20291572158585 712 20631502932393 713 20976749131953 714 21327435693775 715 21683594963570 716 22045355119019 717 22412749727778 718 22785910055089 719 23164871002781 720 23549767154536 721 23940634551313 722 24337611248649 723 24740734625898 724 25150146050093 725 25565884359380 726 25988094473959 727 26416816487332 728 26852199038872 729 27294283682286 730 27743222613161 731 28199058973600 732 28661948765193 733 29131936512740 734 29609182196328 735 30093731938552 736 30585749531702 737 31085282829389 738 31592499700805 739 32107449515835 740 32630304404464 741 33161115477727 742 33700058953660 743 34247187829521 744 34802682684532 745 35366598183025 746 35939119460279 747 36520303079465 748 37110338559439 749 37709284512514 750 38317335127921 751 38934550842445 752 39561130718882 753 40197137264335 754 40842774235563 755 41498106371024 756 42163342421417 757 42838549122898 758 43523940439155 759 44219585356926 760 44925702871362 761 45642364390781 762 46369794252118 763 47108066049813 764 47857409690226 765 48617901219694 766 49389775929422 767 50173112495552 768 50968151922815 769 51774975271834 770 52593829503237 771 53424798339978 772 54268134507427 773 55123924583816 774 55992427398610 775 56873732135913 776 57768103985609 777 58675635024392 778 59596596612907 779 60531083920382 780 61479374834781 781 62441567362902 782 63417946187219 783 64408612456347 784 65413857450285 785 66433785673242 786 67468695375694 787 68518694152940 788 69584087513120 789 70664986455854 790 71761703549126 791 72874353423383 792 74003256092550 793 75148529552617 794 76310501561776 795 77489293811050 796 78685241602807 797 79898470558754 798 81129323934354 799 82377931006229 800 83644643300012 801 84929594091819 802 86233142971034 803 87555427467943 804 88896815658070 805 90257449046826 806 91637704530670 807 93037727946065 808 94457904807425 809 95898385546221 810 97359564738764 811 98841597127387 812 100344886699176 813 101869592885045 814 103416128872789 815 104984659063540 816 106575606310168 817 108189139690154 818 109825692095439 819 111485437669067 820 113168819132847 821 114876015993388 822 116607481283342 823 118363399579816 824 120144234614908 825 121950176445749 826 123781699293811 827 125638999006419 828 127522560803604 829 129432586019143 830 131369571283981 831 133333723846800 832 135325551533778 833 137345267842709 834 139393392321343 835 141470144410754 836 143576055815300 837 145711352362301 838 147876577703070 839 150071964397987 840 152298068598387 841 154555129287807 842 156843715571000 843 159164073324630 844 161516784390959 845 163902101909018 846 166320621037305 847 168772601857757 848 171258653329990 849 173779042963805 850 176334393307039 851 178924979687871 852 181551438842133 853 184214053599865 854 186913475389103 855 189649995051933 856 192424278497074 857 195236624985312 858 198087715540693 859 200977857515864 860 203907747584252 861 206877701724659 862 209888432043979 863 212940263584080 864 216033924542094 865 219169748695653 866 222348480895328 867 225570464207431 868 228836459929528 869 232146820870631 870 235502325465168 871 238903335935388 872 242350648439504 873 245844635199473 874 249386109886248 875 252975455203746 876 256613503058031 877 260300646296612 878 264037735686920 879 267825174826277 880 271663833138395 881 275554125480261 882 279496940680924 883 283492704524717 884 287542325897715 885 291646242149153 886 295805382021823 887 300020194960921 888 304291630358176 889 308620149413285 890 313006722855913 891 317451824308620 892 321956445636419 893 326521073453748 894 331146721581752 895 335833889287345 896 340583613074080 897 345396405553677 898 350273325723699 899 355214900132662 900 360222211133897 901 365295798874208 902 370436769819575 903 375645678449029 904 380923655151002 905 386271269364274 906 391689676302540 907 397179460018579 908 402741801357166 909 408377299744970 910 414087161477857 911 419872002019487 912 425733054053557 913 431670948745292 914 437686946005379 915 443781693499464 916 449956478194805 917 456211964948543 918 462549468774369 919 468969671378758 920 475473916707743 921 482062904155089 922 488738006429976 923 495499941351931 924 502350111420024 925 509289252543209 926 516318797943779 927 523439502489086 928 530652829975723 929 537959554998791 930 545361173006623 931 552858477990963 932 560452998024943 933 568145547417195 934 575937686719366 935 583830251371143 936 591824835531697 937 599922295436498 938 608124259885971 939 616431606865815 940 624845999687304 941 633368338946220 942 642000323637096 943 650742876646338 944 659597733729273 945 668565841065820 946 677648971057703 947 686848094075265 948 696165020404166 949 705600744283043 950 715157115017523 951 724835151767004 952 734636742749138 953 744562932999962 954 754615650934525 955 764795967154254 956 775105851467839 957 785546401134974 958 796119627277943 959 806826654811979 960 817669537521105 961 828649427676126 962 839768422970527 963 851027704186713 964 862429412856759 965 873974759328293 966 885665930385028 967 897504165640450 968 909491698452575 969 921629798902011 970 933920746873528 971 946365844026925 972 958967418242430 973 971726802482681 974 984646374003267 975 997727498331330 976 1010972602074995 977 1024383084486614 978 1037961423075552 979 1051709050546621 980 1065628496763221 981 1079721229207236 982 1093989830087194 983 1108435802895935 984 1123061783797773 985 1137869312041683 986 1152861079276647 987 1168038661884958 988 1183404807029361 989 1198961129514155 990 1214710433704337 991 1230654372591169 992 1246795809337017 993 1263136436575265 994 1279679176313164 995 1296425762185646 996 1313379176814825 997 1330541194609933 998 1347914860495616 999 1365501991169808 1000 1383305693940735