0 1 1 9 2 41 3 131 4 336 5 742 6 1470 7 2682 8 4587 9 7447 10 11583 11 17381 12 25298 13 35868 14 49708 15 67524 16 90117 17 118389 18 153349 19 196119 20 247940 21 310178 22 384330 23 472030 24 575055 25 695331 26 834939 27 996121 28 1181286 29 1393016 30 1634072 31 1907400 32 2216137 33 2563617 34 2953377 35 3389163 36 3874936 37 4414878 38 5013398 39 5675138 40 6404979 41 7208047 42 8089719 43 9055629 44 10111674 45 11264020 46 12519108 47 13883660 48 15364685 49 16969485 50 18705661 51 20581119 52 22604076 53 24783066 54 27126946 55 29644902 56 32346455 57 35241467 58 38340147 59 41653057 60 45191118 61 48965616 62 52988208 63 57270928 64 61826193 65 66666809 66 71805977 67 77257299 68 83034784 69 89152854 70 95626350 71 102470538 72 109701115 73 117334215 74 125386415 75 133874741 76 142816674 77 152230156 78 162133596 79 172545876 80 183486357 81 194974885 82 207031797 83 219677927 84 232934612 85 246823698 86 261367546 87 276589038 88 292511583 89 309159123 90 326556139 91 344727657 92 363699254 93 383497064 94 404147784 95 425678680 96 448117593 97 471492945 98 495833745 99 521169595 100 547530696 101 574947854 102 603452486 103 633076626 104 663852931 105 695814687 106 728995815 107 763430877 108 799155082 109 836204292 110 874615028 111 914424476 112 955670493 113 998391613 114 1042627053 115 1088416719 116 1135801212 117 1184821834 118 1235520594 119 1287940214 120 1342124135 121 1398116523 122 1455962275 123 1515707025 124 1577397150 125 1641079776 126 1706802784 127 1774614816 128 1844565281 129 1916704361 130 1991083017 131 2067752995 132 2146766832 133 2228177862 134 2312040222 135 2398408858 136 2487339531 137 2578888823 138 2673114143 139 2770073733 140 2869826674 141 2972432892 142 3077953164 143 3186449124 144 3297983269 145 3412618965 146 3530420453 147 3651452855 148 3775782180 149 3903475330 150 4034600106 151 4169225214 152 4307420271 153 4449255811 154 4594803291 155 4744135097 156 4897324550 157 5054445912 158 5215574392 159 5380786152 160 5550158313 161 5723768961 162 5901697153 163 6084022923 164 6270827288 165 6462192254 166 6658200822 167 6858936994 168 7064485779 169 7274933199 170 7490366295 171 7710873133 172 7936542810 173 8167465460 174 8403732260 175 8645435436 176 8892668269 177 9145525101 178 9404101341 179 9668493471 180 9938799052 181 10215116730 182 10497546242 183 10786188422 184 11081145207 185 11382519643 186 11690415891 187 12004939233 188 12326196078 189 12654293968 190 12989341584 191 13331448752 192 13680726449 193 14037286809 194 14401243129 195 14772709875 196 15151802688 197 15538638390 198 15933334990 199 16336011690 200 16746788891 201 17165788199 202 17593132431 203 18028945621 204 18473353026 205 18926481132 206 19388457660 207 19859411572 208 20339473077 209 20828773637 210 21327445973 211 21835624071 212 22353443188 213 22881039858 214 23418551898 215 23966118414 216 24523879807 217 25091977779 218 25670555339 219 26259756809 220 26859727830 221 27470615368 222 28092567720 223 28725734520 224 29370266745 225 30026316721 226 30694038129 227 31373586011 228 32065116776 229 32768788206 230 33484759462 231 34213191090 232 34954245027 233 35708084607 234 36474874567 235 37254781053 236 38047971626 237 38854615268 238 39674882388 239 40508944828 240 41356975869 241 42219150237 242 43095644109 243 43986635119 244 44892302364 245 45812826410 246 46748389298 247 47699174550 248 48665367175 249 49647153675 250 50644722051 251 51658261809 252 52687963966 253 53734021056 254 54796627136 255 55875977792 256 56972270145 257 58085702857 258 59216476137 259 60364791747 260 61530853008 261 62714864806 262 63917033598 263 65137567418 264 66376675883 265 67634570199 266 68911463167 267 70207569189 268 71523104274 269 72858286044 270 74213333740 271 75588468228 272 76983912005 273 78399889205 274 79836625605 275 81294348631 276 82773287364 277 84273672546 278 85795736586 279 87339713566 280 88905839247 281 90494351075 282 92105488187 283 93739491417 284 95396603302 285 97077068088 286 98781131736 287 100509041928 288 102261048073 289 104037401313 290 105838354529 291 107664162347 292 109515081144 293 111391369054 294 113293285974 295 115221093570 296 117175055283 297 119155436335 298 121162503735 299 123196526285 300 125257774586 301 127346521044 302 129463039876 303 131607607116 304 133780500621 305 135982000077 306 138212387005 307 140471944767 308 142760958572 309 145079715482 310 147428504418 311 149807616166 312 152217343383 313 154657980603 314 157129824243 315 159633172609 316 162168325902 317 164735586224 318 167335257584 319 169967645904 320 172633059025 321 175331806713 322 178064200665 323 180830554515 324 183631183840 325 186466406166 326 189336540974 327 192241909706 328 195182835771 329 198159644551 330 201172663407 331 204222221685 332 207308650722 333 210432283852 334 213593456412 335 216792505748 336 220029771221 337 223305594213 338 226620318133 339 229974288423 340 233367852564 341 236801360082 342 240275162554 343 243789613614 344 247345068959 345 250941886355 346 254580425643 347 258261048745 348 261984119670 349 265750004520 350 269559071496 351 273411690904 352 277308235161 353 281249078801 354 285234598481 355 289265172987 356 293341183240 357 297463012302 358 301631045382 359 305845669842 360 310107275203 361 314416253151 362 318772997543 363 323177904413 364 327631371978 365 332133800644 366 336685593012 367 341287153884 368 345938890269 369 350641211389 370 355394528685 371 360199255823 372 365055808700 373 369964605450 374 374926066450 375 379940614326 376 385008673959 377 390130672491 378 395307039331 379 400538206161 380 405824606942 381 411166677920 382 416564857632 383 422019586912 384 427531308897 385 433100469033 386 438727515081 387 444412897123 388 450157067568 389 455960481158 390 461823594974 391 467746868442 392 473730763339 393 479775743799 394 485882276319 395 492050829765 396 498281875378 397 504575886780 398 510933339980 399 517354713380 400 523840487781 401 530391146389 402 537007174821 403 543689061111 404 550437295716 405 557252371522 406 564134783850 407 571085030462 408 578103611567 409 585191029827 410 592347790363 411 599574400761 412 606871371078 413 614239213848 414 621678444088 415 629189579304 416 636773139497 417 644429647169 418 652159627329 419 659963607499 420 667842117720 421 675795690558 422 683824861110 423 691930167010 424 700112148435 425 708371348111 426 716708311319 427 725123585901 428 733617722266 429 742191273396 430 750844794852 431 759578844780 432 768393983917 433 777290775597 434 786269785757 435 795331582943 436 804476738316 437 813705825658 438 823019421378 439 832418104518 440 841902456759 441 851473062427 442 861130508499 443 870875384609 444 880708283054 445 890629798800 446 900640529488 447 910741075440 448 920932039665 449 931214027865 450 941587648441 451 952053512499 452 962612233856 453 973264429046 454 984010717326 455 994851720682 456 1005788063835 457 1016820374247 458 1027949282127 459 1039175420437 460 1050499424898 461 1061921933996 462 1073443588988 463 1085065033908 464 1096786915573 465 1108609883589 466 1120534590357 467 1132561691079 468 1144691843764 469 1156925709234 470 1169263951130 471 1181707235918 472 1194256232895 473 1206911614195 474 1219674054795 475 1232544232521 476 1245522828054 477 1258610524936 478 1271808009576 479 1285115971256 480 1298535102137 481 1312066097265 482 1325709654577 483 1339466474907 484 1353337261992 485 1367322722478 486 1381423565926 487 1395640504818 488 1409974254563 489 1424425533503 490 1438995062919 491 1453683567037 492 1468491773034 493 1483420411044 494 1498470214164 495 1513641918460 496 1528936262973 497 1544353989725 498 1559895843725 499 1575562572975 500 1591354928476 501 1607273664234 502 1623319537266 503 1639493307606 504 1655795738311 505 1672227595467 506 1688789648195 507 1705482668657 508 1722307432062 509 1739264716672 510 1756355303808 511 1773579977856 512 1790939526273 513 1808434739593 514 1826066411433 515 1843835338499 516 1861742320592 517 1879788160614 518 1897973664574 519 1916299641594 520 1934766903915 521 1953376266903 522 1972128549055 523 1991024572005 524 2010065160530 525 2029251142556 526 2048583349164 527 2068062614596 528 2087689776261 529 2107465674741 530 2127391153797 531 2147467060375 532 2167694244612 533 2188073559842 534 2208605862602 535 2229292012638 536 2250132872911 537 2271129309603 538 2292282192123 539 2313592393113 540 2335060788454 541 2356688257272 542 2378475681944 543 2400423948104 544 2422533944649 545 2444806563745 546 2467242700833 547 2489843254635 548 2512609127160 549 2535541223710 550 2558640452886 551 2581907726594 552 2605343960051 553 2628950071791 554 2652726983671 555 2676675620877 556 2700796911930 557 2725091788692 558 2749561186372 559 2774206043532 560 2799027302093 561 2824025907341 562 2849202807933 563 2874558955903 564 2900095306668 565 2925812819034 566 2951712455202 567 2977795180774 568 3004061964759 569 3030513779579 570 3057151601075 571 3083976408513 572 3110989184590 573 3138190915440 574 3165582590640 575 3193165203216 576 3220939749649 577 3248907229881 578 3277068647321 579 3305425008851 580 3333977324832 581 3362726609110 582 3391673879022 583 3420820155402 584 3450166462587 585 3479713828423 586 3509463284271 587 3539415865013 588 3569572609058 589 3599934558348 590 3630502758364 591 3661278258132 592 3692262110229 593 3723455370789 594 3754859099509 595 3786474359655 596 3818302218068 597 3850343745170 598 3882600014970 599 3915072105070 600 3947761096671 601 3980668074579 602 4013794127211 603 4047140346601 604 4080707828406 605 4114497671912 606 4148510980040 607 4182748859352 608 4217212420057 609 4251902776017 610 4286821044753 611 4321968347451 612 4357345808968 613 4392954557838 614 4428795726278 615 4464870450194 616 4501179869187 617 4537725126559 618 4574507369319 619 4611527748189 620 4648787417610 621 4686287535748 622 4724029264500 623 4762013769500 624 4800242220125 625 4838715789501 626 4877435654509 627 4916402995791 628 4955618997756 629 4995084848586 630 5034801740242 631 5074770868470 632 5114993432807 633 5155470636587 634 5196203686947 635 5237193794833 636 5278442175006 637 5319950046048 638 5361718630368 639 5403749154208 640 5446042847649 641 5488600944617 642 5531424682889 643 5574515304099 644 5617874053744 645 5661502181190 646 5705400939678 647 5749571586330 648 5794015382155 649 5838733592055 650 5883727484831 651 5928998333189 652 5974547413746 653 6020376007036 654 6066485397516 655 6112876873572 656 6159551727525 657 6206511255637 658 6253756758117 659 6301289539127 660 6349110906788 661 6397222173186 662 6445624654378 663 6494319670398 664 6543308545263 665 6592592606979 666 6642173187547 667 6692051622969 668 6742229253254 669 6792707422424 670 6843487478520 671 6894570773608 672 6945958663785 673 6997652509185 674 7049653673985 675 7101963526411 676 7154583438744 677 7207514787326 678 7260758952566 679 7314317318946 680 7368191275027 681 7422382213455 682 7476891530967 683 7531720628397 684 7586870910682 685 7642343786868 686 7698140670116 687 7754262977708 688 7810712131053 689 7867489555693 690 7924596681309 691 7982034941727 692 8039805774924 693 8097910623034 694 8156350932354 695 8215128153350 696 8274243740663 697 8333699153115 698 8393495853715 699 8453635309665 700 8514118992366 701 8574948377424 702 8636124944656 703 8697650178096 704 8759525566001 705 8821752600857 706 8884332779385 707 8947267602547 708 9010558575552 709 9074207207862 710 9138215013198 711 9202583509546 712 9267314219163 713 9332408668583 714 9397868388623 715 9463694914389 716 9529889785282 717 9596454545004 718 9663390741564 719 9730699927284 720 9798383658805 721 9866443497093 722 9934881007445 723 10003697759495 724 10072895327220 725 10142475288946 726 10212439227354 727 10282788729486 728 10353525386751 729 10424650794931 730 10496166554187 731 10568074269065 732 10640375548502 733 10713072005832 734 10786165258792 735 10859656929528 736 10933548644601 737 11007842034993 738 11082538736113 739 11157640387803 740 11233148634344 741 11309065124462 742 11385391511334 743 11462129452594 744 11539280610339 745 11616846651135 746 11694829246023 747 11773230070525 748 11852050804650 749 11931293132900 750 12010958744276 751 12091049332284 752 12171566594941 753 12252512234781 754 12333887958861 755 12415695478767 756 12497936510620 757 12580612775082 758 12663725997362 759 12747277907222 760 12831270238983 761 12915704731531 762 13000583128323 763 13085907177393 764 13171678631358 765 13257899247424 766 13344570787392 767 13431695017664 768 13519273709249 769 13607308637769 770 13695801583465 771 13784754331203 772 13874168670480 773 13964046395430 774 14054389304830 775 14145199202106 776 14236477895339 777 14328227197271 778 14420448925311 779 14513144901541 780 14606316952722 781 14699966910300 782 14794096610412 783 14888707893892 784 14983802606277 785 15079382597813 786 15175449723461 787 15272005842903 788 15369052820548 789 15466592525538 790 15564626831754 791 15663157617822 792 15762186767119 793 15861716167779 794 15961747712699 795 16062283299545 796 16163324830758 797 16264874213560 798 16366933359960 799 16469504186760 800 16572588615561 801 16676188572769 802 16780305989601 803 16884942802091 804 16990100951096 805 17095782382302 806 17201989046230 807 17308722898242 808 17415985898547 809 17523780012207 810 17632107209143 811 17740969464141 812 17850368756858 813 17960307071828 814 18070786398468 815 18181808731084 816 18293376068877 817 18405490415949 818 18518153781309 819 18631368178879 820 18745135627500 821 18859458150938 822 18974337777890 823 19089776541990 824 19205776481815 825 19322339640891 826 19439468067699 827 19557163815681 828 19675428943246 829 19794265513776 830 19913675595632 831 20033661262160 832 20154224591697 833 20275367667577 834 20397092578137 835 20519401416723 836 20642296281696 837 20765779276438 838 20889852509358 839 21014518093898 840 21139778148539 841 21265634796807 842 21392090167279 843 21519146393589 844 21646805614434 845 21775069973580 846 21903941619868 847 22033422707220 848 22163515394645 849 22294221846245 850 22425544231221 851 22557484723879 852 22690045503636 853 22823228755026 854 22957036667706 855 23091471436462 856 23226535261215 857 23362230347027 858 23498558904107 859 23635523147817 860 23773125298678 861 23911367582376 862 24050252229768 863 24189781476888 864 24329957564953 865 24470782740369 866 24612259254737 867 24754389364859 868 24897175332744 869 25040619425614 870 25184723915910 871 25329491081298 872 25474923204675 873 25621022574175 874 25767791483175 875 25915232230301 876 26063347119434 877 26212138459716 878 26361608565556 879 26511759756636 880 26662594357917 881 26814114699645 882 26966323117357 883 27119221951887 884 27272813549372 885 27427100261258 886 27582084444306 887 27737768460598 888 27894154677543 889 28051245467883 890 28209043209699 891 28367550286417 892 28526769086814 893 28686702005024 894 28847351440544 895 29008719798240 896 29170809488353 897 29333622926505 898 29497162533705 899 29661430736355 900 29826429966256 901 29992162660614 902 30158631262046 903 30325838218586 904 30493785983691 905 30662477016247 906 30831913780575 907 31002098746437 908 31173034389042 909 31344723189052 910 31517167632588 911 31690370211236 912 31864333422053 913 32039059767573 914 32214551755813 915 32390811900279 916 32567842719972 917 32745646739394 918 32924226488554 919 33103584502974 920 33283723323695 921 33464645497283 922 33646353575835 923 33828850116985 924 34012137683910 925 34196218845336 926 34381096175544 927 34566772254376 928 34753249667241 929 34940531005121 930 35128618864577 931 35317515847755 932 35507224562392 933 35697747621822 934 35889087644982 935 36081247256418 936 36274229086291 937 36468035770383 938 36662669950103 939 36858134272493 940 37054431390234 941 37251563961652 942 37449534650724 943 37648346127084 944 37848001066029 945 38048502148525 946 38249852061213 947 38452053496415 948 38655109152140 949 38859021732090 950 39063793945666 951 39269428507974 952 39475928139831 953 39683295567771 954 39891533524051 955 40100644746657 956 40310631979310 957 40521497971472 958 40733245478352 959 40945877260912 960 41159396085873 961 41373804725721 962 41589105958713 963 41805302568883 964 42022397346048 965 42240393085814 966 42459292589582 967 42679098664554 968 42899814123739 969 43121441785959 970 43343984475855 971 43567445023893 972 43791826266370 973 44017131045420 974 44243362209020 975 44470522610996 976 44698615111029 977 44927642574661 978 45157607873301 979 45388513884231 980 45620363490612 981 45853159581490 982 46086905051802 983 46321602802382 984 46557255739967 985 46793866777203 986 47031438832651 987 47269974830793 988 47509477702038 989 47749950382728 990 47991395815144 991 48233816947512 992 48477216734009 993 48721598134769 994 48966964115889 995 49213317649435 996 49460661713448 997 49708999291950 998 49958333374950 999 50208666958450 1000 50460003044451