0 1 1 8 2 35 3 112 4 294 5 673 6 1393 7 2668 8 4803 9 8218 10 13476 11 21315 12 32684 13 48782 14 71101 15 101473 16 142121 17 195714 18 265426 19 354999 20 468809 21 611936 22 790238 23 1010430 24 1280166 25 1608124 26 2004094 27 2479071 28 3045353 29 3716642 30 4508148 31 5436696 32 6520838 33 7780968 34 9239441 35 10920695 36 12851378 37 15060479 38 17579463 39 20442410 40 23686158 41 27350450 42 31478083 43 36115061 44 41310752 45 47118051 46 53593545 47 60797681 48 68794937 49 77653999 50 87447942 51 98254413 52 110155817 53 123239507 54 137597980 55 153329076 56 170536182 57 189328439 58 209820954 59 232135014 60 256398304 61 282745129 62 311316641 63 342261069 64 375733950 65 411898364 66 450925174 67 492993272 68 538289826 69 587010531 70 639359864 71 695551346 72 755807807 73 820361654 74 889455142 75 963340649 76 1042280955 77 1126549523 78 1216430785 79 1312220432 80 1414225709 81 1522765711 82 1638171684 83 1760787331 84 1890969123 85 2029086611 86 2175522740 87 2330674168 88 2494951591 89 2668780073 90 2852599377 91 3046864300 92 3252045012 93 3468627401 94 3697113420 95 3938021438 96 4191886595 97 4459261161 98 4740714897 99 5036835419 100 5348228568 101 5675518784 102 6019349483 103 6380383435 104 6759303148 105 7156811258 106 7573630924 107 8010506224 108 8468202554 109 8947507032 110 9449228907 111 9974199971 112 10523274973 113 11097332038 114 11697273090 115 12324024279 116 12978536410 117 13661785377 118 14374772601 119 15118525471 120 15894097787 121 16702570208 122 17545050707 123 18422675030 124 19336607157 125 20288039765 126 21278194697 127 22308323436 128 23379707582 129 24493659330 130 25651521952 131 26854670284 132 28104511217 133 29402484191 134 30750061693 135 32148749760 136 33600088485 137 35105652526 138 36667051619 139 38285931097 140 39963972413 141 41702893665 142 43504450123 143 45370434761 144 47302678795 145 49303052224 146 51373464373 147 53515864440 148 55732242049 149 58024627807 150 60395093863 151 62845754470 152 65378766551 153 67996330269 154 70700689600 155 73494132910 156 76378993537 157 79357650378 158 82432528479 159 85606099628 160 88880882953 161 92259445525 162 95744402964 163 99338420046 164 103044211314 165 106864541694 166 110802227116 167 114860135137 168 119041185567 169 123348351099 170 127784657944 171 132353186470 172 137057071844 173 141899504679 174 146883731685 175 152013056324 176 157290839467 177 162720500056 178 168305515770 179 174049423695 180 179955820996 181 186028365593 182 192270776842 183 198686836220 184 205280388013 185 212055340006 186 219015664178 187 226165397401 188 233508642144 189 241049567179 190 248792408292 191 256741468998 192 264901121261 193 273275806217 194 281870034900 195 290688388972 196 299735521456 197 309016157473 198 318535094982 199 328297205526 200 338307434981 201 348570804309 202 359092410313 203 369877426397 204 380931103330 205 392258770014 206 403865834255 207 415757783537 208 427940185801 209 440418690228 210 453199028027 211 466287013225 212 479688543462 213 493409600789 214 507456252471 215 521834651793 216 536551038870 217 551611741460 218 567023175780 219 582791847326 220 598924351696 221 615427375418 222 632307696781 223 649572186671 224 667227809410 225 685281623601 226 703740782977 227 722612537254 228 741904232986 229 761623314423 230 781777324373 231 802373905068 232 823420799035 233 844925849969 234 866897003610 235 889342308623 236 912269917484 237 935688087369 238 959605181047 239 984029667776 240 1008970124203 241 1034435235268 242 1060433795112 243 1086974707990 244 1114066989187 245 1141719765938 246 1169942278350 247 1198743880329 248 1228134040511 249 1258122343198 250 1288718489296 251 1319932297256 252 1351773704019 253 1384252765966 254 1417379659872 255 1451164683862 256 1485618258371 257 1520750927108 258 1556573358026 259 1593096344295 260 1630330805279 261 1668287787516 262 1706978465702 263 1746414143678 264 1786606255421 265 1827566366040 266 1869306172776 267 1911837506005 268 1955172330243 269 1999322745156 270 2044300986575 271 2090119427515 272 2136790579195 273 2184327092061 274 2232741756814 275 2282047505444 276 2332257412268 277 2383384694971 278 2435442715651 279 2488444981868 280 2542405147697 281 2597337014784 282 2653254533406 283 2710171803535 284 2768103075905 285 2827062753081 286 2887065390532 287 2948125697710 288 3010258539133 289 3073478935470 290 3137802064629 291 3203243262851 292 3269818025810 293 3337542009716 294 3406431032420 295 3476501074522 296 3547768280484 297 3620248959747 298 3693959587851 299 3768916807558 300 3845137429980 301 3922638435711 302 4001436975962 303 4081550373700 304 4162996124792 305 4245791899153 306 4329955541895 307 4415505074479 308 4502458695872 309 4590834783711 310 4680651895470 311 4771928769629 312 4864684326846 313 4958937671135 314 5054708091049 315 5152015060865 316 5250878241772 317 5351317483063 318 5453352823332 319 5557004491673 320 5662292908883 321 5769238688669 322 5877862638860 323 5988185762621 324 6100229259670 325 6214014527500 326 6329563162607 327 6446896961722 328 6566037923044 329 6687008247477 330 6809830339872 331 6934526810275 332 7061120475176 333 7189634358761 334 7320091694168 335 7452515924749 336 7586930705335 337 7723359903503 338 7861827600847 339 8002358094253 340 8144975897178 341 8289705740931 342 8436572575960 343 8585601573144 344 8736818125090 345 8890247847431 346 9045916580128 347 9203850388777 348 9364075565921 349 9526618632364 350 9691506338486 351 9858765665563 352 10028423827092 353 10200508270121 354 10375046676580 355 10552066964617 356 10731597289938 357 10913666047152 358 11098301871118 359 11285533638296 360 11475390468103 361 11667901724273 362 11863097016220 363 12061006200403 364 12261659381697 365 12465086914768 366 12671319405452 367 12880387712135 368 13092322947139 369 13307156478113 370 13524919929428 371 13745645183573 372 13969364382554 373 14196109929298 374 14425914489061 375 14658810990840 376 14894832628787 377 15134012863629 378 15376385424092 379 15621984308330 380 15870843785356 381 16122998396478 382 16378482956739 383 16637332556360 384 16899582562185 385 17165268619130 386 17434426651638 387 17707092865137 388 17983303747501 389 18263096070513 390 18546506891334 391 18833573553976 392 19124333690779 393 19418825223890 394 19717086366747 395 20019155625568 396 20325071800844 397 20634873988835 398 20948601583069 399 21266294275846 400 21587992059745 401 21913735229135 402 22243564381689 403 22577520419903 404 22915644552618 405 23257978296545 406 23604563477793 407 23955442233402 408 24310657012881 409 24670250579749 410 25034266013079 411 25402746709046 412 25775736382481 413 26153279068429 414 26535419123710 415 26922201228482 416 27313670387808 417 27709871933227 418 28110851524329 419 28516655150334 420 28927329131675 421 29342920121585 422 29763475107687 423 30189041413588 424 30619666700477 425 31055398968727 426 31496286559500 427 31942378156355 428 32393722786860 429 32850369824209 430 33312368988844 431 33779770350080 432 34252624327733 433 34730981693752 434 35214893573856 435 35704411449175 436 36199587157894 437 36700472896900 438 37207121223432 439 37719585056735 440 38237917679718 441 38762172740616 442 39292404254655 443 39828666605721 444 40371014548033 445 40919503207821 446 41474188085009 447 42035125054902 448 42602370369876 449 43175980661070 450 43756012940082 451 44342524600669 452 44935573420452 453 45535217562624 454 46141515577661 455 46754526405036 456 47374309374938 457 48000924209996 458 48634431027006 459 49274890338661 460 49922363055284 461 50576910486566 462 51238594343308 463 51907476739168 464 52583620192411 465 53267087627663 466 53957942377668 467 54656248185049 468 55362069204073 469 56075470002420 470 56796515562956 471 57525271285508 472 58261802988643 473 59006176911451 474 59758459715334 475 60518718485797 476 61287020734242 477 62063434399765 478 62848027850959 479 63640869887722 480 64442029743068 481 65251577084941 482 66069582018032 483 66896115085601 484 67731247271302 485 68575050001013 486 69427595144669 487 70288955018100 488 71159202384871 489 72038410458126 490 72926652902436 491 73824003835652 492 74730537830761 493 75646329917743 494 76571455585432 495 77505990783382 496 78450011923740 497 79403595883121 498 80366820004487 499 81339762099029 500 82322500448055 501 83315113804881 502 84317681396725 503 85330282926604 504 86352998575235 505 87385909002940 506 88429095351553 507 89482639246332 508 90546622797875 509 91621128604041 510 92706239751872 511 93802039819520 512 94908612878179 513 96026043494023 514 97154416730146 515 98293818148504 516 99444333811861 517 100606050285740 518 101779054640379 519 102963434452688 520 104159277808210 521 105366673303086 522 106585710046026 523 107816477660282 524 109059066285625 525 110313566580326 526 111580069723141 527 112858667415298 528 114149451882487 529 115452515876856 530 116767952679012 531 118095856100026 532 119436320483439 533 120789440707273 534 122155312186047 535 123534030872798 536 124925693261103 537 126330396387104 538 127748237831538 539 129179315721772 540 130623728733841 541 132081576094488 542 133552957583209 543 135037973534302 544 136536724838920 545 138049312947126 546 139575839869953 547 141116408181469 548 142671121020846 549 144240082094431 550 145823395677821 551 147421166617944 552 149033500335144 553 150660502825268 554 152302280661755 555 153958940997731 556 155630591568109 557 157317340691692 558 159019297273277 559 160736570805763 560 162469271372264 561 164217509648226 562 165981396903547 563 167761045004701 564 169556566416868 565 171368074206068 566 173195682041298 567 175039504196672 568 176899655553566 569 178776251602767 570 180669408446624 571 182579242801201 572 184505871998435 573 186449413988300 574 188409987340974 575 190387711249008 576 192382705529499 577 194395090626269 578 196424987612048 579 198472518190659 580 200537804699206 581 202620970110267 582 204722138034092 583 206841432720804 584 208978979062603 585 211134902595974 586 213309329503900 587 215502386618078 588 217714201421138 589 219944902048867 590 222194617292438 591 224463476600642 592 226751610082121 593 229059148507605 594 231386223312154 595 233732966597405 596 236099511133821 597 238485990362943 598 240892538399647 599 243319290034407 600 245766380735562 601 248233946651585 602 250722124613356 603 253231052136439 604 255760867423363 605 258311709365905 606 260883717547378 607 263477032244923 608 266091794431805 609 268728145779711 610 271386228661052 611 274066186151270 612 276768162031149 613 279492300789129 614 282238747623622 615 285007648445334 616 287799149879592 617 290613399268676 618 293450544674152 619 296310734879209 620 299194119391000 621 302100848442988 622 305031072997295 623 307984944747054 624 310962616118765 625 313964240274654 626 316989971115036 627 320039963280681 628 323114372155186 629 326213353867350 630 329337065293553 631 332485664060137 632 335659308545793 633 338858157883953 634 342082371965186 635 345332111439596 636 348607537719222 637 351908812980443 638 355236100166387 639 358589562989345 640 361969365933187 641 365375674255783 642 368808653991427 643 372268471953266 644 375755295735732 645 379269293716978 646 382810635061317 647 386379489721664 648 389976028441982 649 393600422759732 650 397252845008329 651 400933468319601 652 404642466626252 653 408380014664327 654 412146287975683 655 415941462910464 656 419765716629580 657 423619227107188 658 427502173133176 659 431414734315651 660 435357091083431 661 439329424688542 662 443331917208717 663 447364751549899 664 451428111448747 665 455522181475148 666 459647147034733 667 463803194371398 668 467990510569828 669 472209283558024 670 476459702109833 671 480741955847482 672 485056235244117 673 489402731626345 674 493781637176780 675 498193144936591 676 502637448808055 677 507114743557114 678 511625224815937 679 516169089085484 680 520746533738073 681 525357757019951 682 530002958053870 683 534682336841668 684 539396094266853 685 544144432097191 686 548927552987297 687 553745660481231 688 558598959015097 689 563487653919646 690 568411951422882 691 573372058652672 692 578368183639359 693 583400535318379 694 588469323532883 695 593574759036363 696 598717053495281 697 603896419491700 698 609113070525920 699 614367221019119 700 619659086315999 701 624988882687434 702 630356827333121 703 635763138384235 704 641208034906089 705 646691736900798 706 652214465309946 707 657776442017257 708 663377889851270 709 669019032588018 710 674700094953710 711 680421302627417 712 686182882243762 713 691985061395613 714 697828068636778 715 703712133484704 716 709637486423182 717 715604358905057 718 721612983354941 719 727663593171929 720 733756422732320 721 739891707392343 722 746069683490886 723 752290588352227 724 758554660288768 725 764862138603774 726 771213263594116 727 777608276553017 728 784047419772801 729 790530936547647 730 797059071176347 731 803632068965067 732 810250176230112 733 816913640300696 734 823622709521717 735 830377633256534 736 837178661889747 737 844026046829981 738 850920040512676 739 857860896402880 740 864848868998044 741 871884213830820 742 878967187471865 743 886098047532650 744 893277052668271 745 900504462580263 746 907780538019418 747 915105540788608 748 922479733745610 749 929903380805935 750 937376746945661 751 944900098204272 752 952473701687500 753 960097825570170 754 967772739099049 755 975498712595700 756 983276017459340 757 991104926169699 758 998985712289883 759 1006918650469242 760 1014904016446244 761 1022942087051350 762 1031033140209892 763 1039177454944955 764 1047375311380265 765 1055626990743080 766 1063932775367083 767 1072292948695279 768 1080707795282897 769 1089177600800297 770 1097702652035879 771 1106283236898997 772 1114919644422877 773 1123612164767540 774 1132361089222726 775 1141166710210822 776 1150029321289795 777 1158949217156130 778 1167926693647770 779 1176962047747057 780 1186055577583678 781 1195207582437616 782 1204418362742106 783 1213688220086592 784 1223017457219689 785 1232406378052150 786 1241855287659839 787 1251364492286706 788 1260934299347765 789 1270565017432076 790 1280256956305731 791 1290010426914843 792 1299825741388537 793 1309703213041947 794 1319643156379217 795 1329645887096506 796 1339711722084994 797 1349840979433894 798 1360033978433469 799 1370291039578053 800 1380612484569073 801 1390998636318074 802 1401449818949750 803 1411966357804980 804 1422548579443868 805 1433196811648784 806 1443911383427410 807 1454692625015790 808 1465540867881385 809 1476456444726130 810 1487439689489496 811 1498490937351556 812 1509610524736054 813 1520798789313476 814 1532056070004125 815 1543382706981202 816 1554779041673890 817 1566245416770441 818 1577782176221265 819 1589389665242026 820 1601068230316743 821 1612818219200895 822 1624639980924527 823 1636533865795360 824 1648500225401906 825 1660539412616587 826 1672651781598857 827 1684837687798327 828 1697097487957895 829 1709431540116879 830 1721840203614154 831 1734323839091292 832 1746882808495707 833 1759517475083803 834 1772228203424125 835 1785015359400513 836 1797879310215262 837 1810820424392288 838 1823839071780297 839 1836935623555956 840 1850110452227067 841 1863363931635747 842 1876696436961612 843 1890108344724964 844 1903600032789980 845 1917171880367905 846 1930824268020249 847 1944557577661988 848 1958372192564769 849 1972268497360119 850 1986246878042658 851 2000307721973315 852 2014451417882548 853 2028678355873569 854 2042988927425574 855 2057383525396976 856 2071862544028640 857 2086426378947121 858 2101075427167907 859 2115810087098667 860 2130630758542502 861 2145537842701199 862 2160531742178489 863 2175612860983310 864 2190781604533074 865 2206038379656937 866 2221383594599072 867 2236817659021945 868 2252340984009595 869 2267953982070918 870 2283657067142956 871 2299450654594190 872 2315335161227837 873 2331311005285150 874 2347378606448722 875 2363538385845795 876 2379790766051573 877 2396136171092538 878 2412575026449768 879 2429107759062259 880 2445734797330251 881 2462456571118559 882 2479273511759907 883 2496186052058265 884 2513194626292189 885 2530299670218166 886 2547501621073964 887 2564800917581986 888 2582197999952628 889 2599693309887640 890 2617287290583491 891 2634980386734737 892 2652773044537394 893 2670665711692314 894 2688658837408565 895 2706752872406814 896 2724948268922714 897 2743245480710295 898 2761644963045359 899 2780147172728879 900 2798752568090400 901 2817461608991444 902 2836274756828919 903 2855192474538534 904 2874215226598217 905 2893343479031537 906 2912577699411129 907 2931918356862124 908 2951365922065583 909 2970920867261934 910 2990583666254412 911 3010354794412502 912 3030234728675387 913 3050223947555399 914 3070322931141475 915 3090532161102616 916 3110852120691351 917 3131283294747203 918 3151826169700159 919 3172481233574144 920 3193248975990500 921 3214129888171469 922 3235124462943678 923 3256233194741628 924 3277456579611187 925 3298795115213089 926 3320249300826435 927 3341819637352198 928 3363506627316731 929 3385310774875281 930 3407232585815506 931 3429272567560995 932 3451431229174791 933 3473709081362918 934 3496106636477912 935 3518624408522354 936 3541262913152408 937 3564022667681363 938 3586904191083181 939 3609908003996047 940 3633034628725924 941 3656284589250112 942 3679658411220812 943 3703156621968692 944 3726779750506455 945 3750528327532411 946 3774402885434054 947 3798403958291644 948 3822532081881790 949 3846787793681037 950 3871171632869457 951 3895684140334246 952 3920325858673323 953 3945097332198933 954 3969999106941254 955 3995031730652009 956 4020195752808081 957 4045491724615131 958 4070920199011221 959 4096481730670441 960 4122176876006540 961 4148006193176558 962 4173970242084463 963 4200069584384793 964 4226304783486303 965 4252676404555613 966 4279185014520859 967 4305831182075349 968 4332615477681224 969 4359538473573122 970 4386600743761844 971 4413802864038025 972 4441145411975810 973 4468628966936535 974 4496254110072410 975 4524021424330206 976 4551931494454946 977 4579984906993600 978 4608182250298782 979 4636524114532451 980 4665011091669618 981 4693643775502057 982 4722422761642018 983 4751348647525942 984 4780422032418182 985 4809643517414729 986 4839013705446941 987 4868533201285273 988 4898202611543011 989 4928022544680012 990 4957993611006449 991 4988116422686559 992 5018391593742394 993 5048819740057577 994 5079401479381062 995 5110137431330897 996 5141028217397990 997 5172074460949880 998 5203276787234512 999 5234635823384014 1000 5266152198418476