0 0 1 1 2 346 3 6219 4 36628 5 124405 6 316206 7 672511 8 1267624 9 2189673 10 3540610 11 5436211 12 8006076 13 11393629 14 15756118 15 21264615 16 28104016 17 36473041 18 46584234 19 58663963 20 72952420 21 89703621 22 109185406 23 131679439 24 157481208 25 186900025 26 220259026 27 257895171 28 300159244 29 347415853 30 400043430 31 458434231 32 522994336 33 594143649 34 672315898 35 757958635 36 851533236 37 953514901 38 1064392654 39 1184669343 40 1314861640 41 1455500041 42 1607128866 43 1770306259 44 1945604188 45 2133608445 46 2334918646 47 2550148231 48 2779924464 49 3024888433 50 3285695050 51 3563013051 52 3857524996 53 4169927269 54 4500930078 55 4851257455 56 5221647256 57 5612851161 58 6025634674 59 6460777123 60 6919071660 61 7401325261 62 7908358726 63 8441006679 64 9000117568 65 9586553665 66 10201191066 67 10844919691 68 11518643284 69 12223279413 70 12959759470 71 13729028671 72 14532046056 73 15369784489 74 16243230658 75 17153385075 76 18101262076 77 19087889821 78 20114310294 79 21181579303 80 22290766480 81 23442955281 82 24639242986 83 25880740699 84 27168573348 85 28503879685 86 29887812286 87 31321537551 88 32806235704 89 34343100793 90 35933340690 91 37578177091 92 39278845516 93 41036595309 94 42852689638 95 44728405495 96 46665033696 97 48663878881 98 50726259514 99 52853507883 100 55046970100 101 57308006101 102 59637989646 103 62038308319 104 64510363528 105 67055570505 106 69675358306 107 72371169811 108 75144461724 109 77996704573 110 80929382710 111 83943994311 112 87042051376 113 90225079729 114 93494619018 115 96852222715 116 100299458116 117 103837906341 118 107469162334 119 111194834863 120 115016546520 121 118935933721 122 122954646706 123 127074349539 124 131296720108 125 135623450125 126 140056245126 127 144596824471 128 149246921344 129 154008282753 130 158882669530 131 163871856331 132 168977631636 133 174201797749 134 179546170798 135 185012580735 136 190602871336 137 196318900201 138 202162538754 139 208135672243 140 214240199740 141 220478034141 142 226851102166 143 233361344359 144 240010715088 145 246801182545 146 253734728746 147 260813349531 148 268039054564 149 275413867333 150 282939825150 151 290618979151 152 298453394296 153 306445149369 154 314596336978 155 322909063555 156 331385449356 157 340027628461 158 348837748774 159 357817972023 160 366970473760 161 376297443361 162 385801084026 163 395483612779 164 405347260468 165 415394271765 166 425626905166 167 436047432991 168 446658141384 169 457461330313 170 468459313570 171 479654418771 172 491048987356 173 502645374589 174 514445949558 175 526453095175 176 538669208176 177 551096699121 178 563737992394 179 576595526203 180 589671752580 181 602969137381 182 616490160286 183 630237314799 184 644213108248 185 658420061785 186 672860710386 187 687537602851 188 702453301804 189 717610383693 190 733011438790 191 748659071191 192 764555898816 193 780704553409 194 797107680538 195 813767939595 196 830688003796 197 847870560181 198 865318309614 199 883033966783 200 901020260200 201 919279932201 202 937815738946 203 956630450419 204 975726850428 205 995107736605 206 1014775920406 207 1034734227111 208 1054985495824 209 1075532579473 210 1096378344810 211 1117525672411 212 1138977456676 213 1160736605829 214 1182806041918 215 1205188700815 216 1227887532216 217 1250905499641 218 1274245580434 219 1297910765763 220 1321904060620 221 1346228483821 222 1370887068006 223 1395882859639 224 1421218919008 225 1446898320225 226 1472924151226 227 1499299513771 228 1526027523444 229 1553111309653 230 1580554015630 231 1608358798431 232 1636528828936 233 1665067291849 234 1693977385698 235 1723262322835 236 1752925329436 237 1782969645501 238 1813398524854 239 1844215235143 240 1875423057840 241 1907025288241 242 1939025235466 243 1971426222459 244 2004231585988 245 2037444676645 246 2071068858846 247 2105107510831 248 2139564024664 249 2174441806233 250 2209744275250 251 2245474865251 252 2281637023596 253 2318234211469 254 2355269903878 255 2392747589655 256 2430670771456 257 2469042965761 258 2507867702874 259 2547148526923 260 2586888995860 261 2627092681461 262 2667763169326 263 2708904058879 264 2750518963368 265 2792611509865 266 2835185339266 267 2878244106291 268 2921791479484 269 2965831141213 270 3010366787670 271 3055402128871 272 3100940888656 273 3146986804689 274 3193543628458 275 3240615125275 276 3288205074276 277 3336317268421 278 3384955514494 279 3434123633103 280 3483825458680 281 3534064839481 282 3584845637586 283 3636171728899 284 3688047003148 285 3740475363885 286 3793460728486 287 3847007028151 288 3901118207904 289 3955798226593 290 4011051056890 291 4066880685291 292 4123291112116 293 4180286351509 294 4237870431438 295 4296047393695 296 4354821293896 297 4414196201481 298 4474176199714 299 4534765385683 300 4595967870300 301 4657787778301 302 4720229248246 303 4783296432519 304 4846993497328 305 4911324622705 306 4976294002506 307 5041905844411 308 5108164369924 309 5175073814373 310 5242638426910 311 5310862470511 312 5379750221976 313 5449305971929 314 5519534024818 315 5590438698915 316 5662024326316 317 5734295252941 318 5807255838534 319 5880910456663 320 5955263494720 321 6030319353921 322 6106082449306 323 6182557209739 324 6259748077908 325 6337659510325 326 6416295977326 327 6495661963071 328 6575761965544 329 6656600496553 330 6738182081730 331 6820511260531 332 6903592586236 333 6987430625949 334 7072029960598 335 7157395184935 336 7243530907536 337 7330441750801 338 7418132350954 339 7506607358043 340 7595871435940 341 7685929262341 342 7776785528766 343 7868444940559 344 7960912216888 345 8054192090745 346 8148289308946 347 8243208632131 348 8338954834764 349 8435532705133 350 8532947045350 351 8631202671351 352 8730304412896 353 8830257113569 354 8931065630778 355 9032734835755 356 9135269613556 357 9238674863061 358 9342955496974 359 9448116441823 360 9554162637960 361 9661099039561 362 9768930614626 363 9877662344979 364 9987299226268 365 10097846267965 366 10209308493366 367 10321690939591 368 10434998657584 369 10549236712113 370 10664410181770 371 10780524158971 372 10897583749956 373 11015594074789 374 11134560267358 375 11254487475375 376 11375380860376 377 11497245597721 378 11620086876594 379 11743909900003 380 11868719884780 381 11994522061581 382 12121321674886 383 12249123982999 384 12377934258048 385 12507757785985 386 12638599866586 387 12770465813451 388 12903360954004 389 13037290629493 390 13172260194990 391 13308275019391 392 13445340485416 393 13583461989609 394 13722644942338 395 13862894767795 396 14004216903996 397 14146616802781 398 14290099929814 399 14434671764583 400 14580337800400 401 14727103544401 402 14874974517546 403 15023956254619 404 15174054304228 405 15325274228805 406 15477621604606 407 15631102021711 408 15785721084024 409 15941484409273 410 16098397629010 411 16256466388611 412 16415696347276 413 16576093178029 414 16737662567718 415 16900410217015 416 17064341840416 417 17229463166241 418 17395779936634 419 17563297907563 420 17732022848820 421 17901960544021 422 18073116790606 423 18245497399839 424 18419108196808 425 18593955020425 426 18770043723426 427 18947380172371 428 19125970247644 429 19305819843453 430 19486934867830 431 19669321242631 432 19852984903536 433 20037931800049 434 20224167895498 435 20411699167035 436 20600531605636 437 20790671216101 438 20982124017054 439 21174896040943 440 21368993334040 441 21564421956441 442 21761187982066 443 21959297498659 444 22158756607788 445 22359571424845 446 22561748079046 447 22765292713431 448 22970211484864 449 23176510564033 450 23384196135450 451 23593274397451 452 23803751562196 453 24015633855669 454 24228927517678 455 24443638801855 456 24659773975656 457 24877339320361 458 25096341131074 459 25316785716723 460 25538679400060 461 25762028517661 462 25986839419926 463 26213118471079 464 26440872049168 465 26670106546065 466 26900828367466 467 27133043932891 468 27366759675684 469 27601982043013 470 27838717495870 471 28076972509071 472 28316753571256 473 28558067184889 474 28800919866258 475 29045318145475 476 29291268566476 477 29538777687021 478 29787852078694 479 30038498326903 480 30290723030880 481 30544532803681 482 30799934272186 483 31056934077099 484 31315538872948 485 31575755328085 486 31837590124686 487 32101049958751 488 32366141540104 489 32632871592393 490 32901246853090 491 33171274073491 492 33442960018716 493 33716311467709 494 33991335213238 495 34268038061895 496 34546426834096 497 34826508364081 498 35108289499914 499 35391777103483 500 35676978050500 501 35963899230501 502 36252547546846 503 36542929916719 504 36835053271128 505 37128924554905 506 37424550726706 507 37721938759011 508 38021095638124 509 38322028364173 510 38624743951110 511 38929249426711 512 39235551832576 513 39543658224129 514 39853575670618 515 40165311255115 516 40478872074516 517 40794265239541 518 41111497874734 519 41430577118463 520 41751510122920 521 42074304054121 522 42398966091906 523 42725503429939 524 43053923275708 525 43384232850525 526 43716439389526 527 44050550141671 528 44386572369744 529 44724513350353 530 45064380373930 531 45406180744731 532 45749921780836 533 46095610814149 534 46443255190398 535 46792862269135 536 47144439423736 537 47497994041401 538 47853533523154 539 48211065283843 540 48570596752140 541 48932135370541 542 49295688595366 543 49661263896759 544 50028868758688 545 50398510678945 546 50770197169146 547 51143935754731 548 51519733974964 549 51897599382933 550 52277539545550 551 52659562043551 552 53043674471496 553 53429884437769 554 53818199564578 555 54208627487955 556 54601175857756 557 54995852337661 558 55392664605174 559 55791620351623 560 56192727282160 561 56595993115761 562 57001425585226 563 57409032437179 564 57818821432068 565 58230800344165 566 58644976961566 567 59061359086191 568 59479954533784 569 59900771133913 570 60323816729970 571 60749099179171 572 61176626352556 573 61606406134989 574 62038446425158 575 62472755135575 576 62909340192576 577 63348209536321 578 63789371120794 579 64232832913803 580 64678602896980 581 65126689065781 582 65577099429486 583 66029842011199 584 66484924847848 585 66942355990185 586 67402143502786 587 67864295464051 588 68328819966204 589 68795725115293 590 69265019031190 591 69736709847591 592 70210805712016 593 70687314785809 594 71166245244138 595 71647605275995 596 72131403084196 597 72617646885381 598 73106344910014 599 73597505402383 600 74091136620600 601 74587246836601 602 75085844336146 603 75586937418819 604 76090534398028 605 76596643601005 606 77105273368806 607 77616432056311 608 78130128032224 609 78646369679073 610 79165165393210 611 79686523584811 612 80210452677876 613 80736961110229 614 81266057333518 615 81797749813215 616 82332047028616 617 82868957472841 618 83408489652834 619 83950652089363 620 84495453317020 621 85042901884221 622 85593006353206 623 86145775300039 624 86701217314608 625 87259341000625 626 87820154975626 627 88383667870971 628 88949888331844 629 89518825017253 630 90090486600030 631 90664881766831 632 91242019218136 633 91821907668249 634 92404555845298 635 92989972491235 636 93578166361836 637 94169146226701 638 94762920869254 639 95359499086743 640 95958889690240 641 96561101504641 642 97166143368666 643 97774024134859 644 98384752669588 645 98998337853045 646 99614788579246 647 100234113756031 648 100856322305064 649 101481423161833 650 102109425275650 651 102740337609651 652 103374169140796 653 104010928859869 654 104650625771478 655 105293268894055 656 105938867259856 657 106587429914961 658 107238965919274 659 107893484346523 660 108550994284260 661 109211504833861 662 109875025110526 663 110541564243279 664 111211131374968 665 111883735662265 666 112559386275666 667 113238092399491 668 113919863231884 669 114604707984813 670 115292635884070 671 115983656169271 672 116677778093856 673 117375010925089 674 118075363944058 675 118778846445675 676 119485467738676 677 120195237145621 678 120908164002894 679 121624257660703 680 122343527483080 681 123065982847881 682 123791633146786 683 124520487785299 684 125252556182748 685 125987847772285 686 126726372000886 687 127468138329351 688 128213156232304 689 128961435198193 690 129712984729290 691 130467814341691 692 131225933565316 693 131987351943909 694 132752079035038 695 133520124410095 696 134291497654296 697 135066208366681 698 135844266160114 699 136625680661283 700 137410461510700 701 138198618362701 702 138990160885446 703 139785098760919 704 140583441684928 705 141385199367105 706 142190381530906 707 142998997913611 708 143811058266324 709 144626572353973 710 145445549955310 711 146268000862911 712 147093934883176 713 147923361836329 714 148756291556418 715 149592733891315 716 150432698702716 717 151276195866141 718 152123235270934 719 152973826820263 720 153827980431120 721 154685706034321 722 155547013574506 723 156411913010139 724 157280414313508 725 158152527470725 726 159028262481726 727 159907629360271 728 160790638133944 729 161677298844153 730 162567621546130 731 163461616308931 732 164359293215436 733 165260662362349 734 166165733860198 735 167074517833335 736 167987024419936 737 168903263772001 738 169823246055354 739 170746981449643 740 171674480148340 741 172605752358741 742 173540808301966 743 174479658212959 744 175422312340488 745 176368780947145 746 177319074309346 747 178273202717331 748 179231176475164 749 180193005900733 750 181158701325750 751 182128273095751 752 183101731570096 753 184079087121969 754 185060350138378 755 186045531020155 756 187034640181956 757 188027688052261 758 189024685073374 759 190025641701423 760 191030568406360 761 192039475671961 762 193052373995826 763 194069273889379 764 195090185877868 765 196115120500365 766 197144088309766 767 198177099872791 768 199214165769984 769 200255296595713 770 201300502958170 771 202349795479371 772 203403184795156 773 204460681555189 774 205522296422958 775 206588040075775 776 207657923204776 777 208731956514921 778 209810150724994 779 210892516567603 780 211979064789180 781 213069806149981 782 214164751424086 783 215263911399399 784 216367296877648 785 217474918674385 786 218586787618986 787 219702914554651 788 220823310338404 789 221947985841093 790 223076951947390 791 224210219555791 792 225347799578616 793 226489702942009 794 227635940585938 795 228786523464195 796 229941462544396 797 231100768807981 798 232264453250214 799 233432526880183 800 234605000720800 801 235781885808801 802 236963193194746 803 238148933943019 804 239339119131828 805 240533759853205 806 241732867213006 807 242936452330911 808 244144526340424 809 245357100388873 810 246574185637410 811 247795793261011 812 249021934448476 813 250252620402429 814 251487862339318 815 252727671489415 816 253972059096816 817 255221036419441 818 256474614729034 819 257732805311163 820 258995619465220 821 260263068504421 822 261535163755806 823 262811916560239 824 264093338272408 825 265379440260825 826 266670233907826 827 267965730609571 828 269265941776044 829 270570878831053 830 271880553212230 831 273194976371031 832 274514159772736 833 275838114896449 834 277166853235098 835 278500386295435 836 279838725598036 837 281181882677301 838 282529869081454 839 283882696372543 840 285240376126440 841 286602919932841 842 287970339395266 843 289342646131059 844 290719851771388 845 292101967961245 846 293489006359446 847 294880978638631 848 296277896485264 849 297679771599633 850 299086615695850 851 300498440501851 852 301915257759396 853 303337079224069 854 304763916665278 855 306195781866255 856 307632686624056 857 309074642749561 858 310521662067474 859 311973756416323 860 313430937648460 861 314893217630061 862 316360608241126 863 317833121375479 864 319310768940768 865 320793562858465 866 322281515063866 867 323774637506091 868 325272942148084 869 326776440966613 870 328285145952270 871 329799069109471 872 331318222456456 873 332842618025289 874 334372267861858 875 335907184025875 876 337447378590876 877 338992863644221 878 340543651287094 879 342099753634503 880 343661182815280 881 345227950972081 882 346800070261386 883 348377552853499 884 349960410932548 885 351548656696485 886 353142302357086 887 354741360139951 888 356345842284504 889 357955761043993 890 359571128685490 891 361191957489891 892 362818259751916 893 364450047780109 894 366087333896838 895 367730130438295 896 369378449754496 897 371032304209281 898 372691706180314 899 374356668059083 900 376027202250900 901 377703321174901 902 379385037264046 903 381072362965119 904 382765310738728 905 384463893059305 906 386168122415106 907 387878011308211 908 389593572254524 909 391314817783773 910 393041760439510 911 394774412779111 912 396512787373776 913 398256896808529 914 400006753682218 915 401762370607515 916 403523760210916 917 405290935132741 918 407063908027134 919 408842691562063 920 410627298419320 921 412417741294521 922 414214032897106 923 416016185950339 924 417824213191308 925 419638127370925 926 421457941253926 927 423283667618871 928 425115319258144 929 426952908977953 930 428796449598330 931 430645953953131 932 432501434890036 933 434362905270549 934 436230377969998 935 438103865877535 936 439983381896136 937 441868938942601 938 443760549947554 939 445658227855443 940 447561985624540 941 449471836226941 942 451387792648566 943 453309867889159 944 455238074962288 945 457172426895345 946 459112936729546 947 461059617519931 948 463012482335364 949 464971544258533 950 466936816385950 951 468908311827951 952 470886043708696 953 472870025166169 954 474860269352178 955 476856789432355 956 478859598586156 957 480868710006861 958 482884136901574 959 484905892491223 960 486933990010560 961 488968442708161 962 491009263846426 963 493056466701579 964 495110064563668 965 497170070736565 966 499236498537966 967 501309361299391 968 503388672366184 969 505474445097513 970 507566692866370 971 509665429059571 972 511770667077756 973 513882420335389 974 516000702260758 975 518125526295975 976 520256905896976 977 522394854533521 978 524539385689194 979 526690512861403 980 528848249561380 981 531012609314181 982 533183605658686 983 535361252147599 984 537545562347448 985 539736549838585 986 541934228215186 987 544138611085251 988 546349712070604 989 548567544806893 990 550792122943590 991 553023460143991 992 555261570085216 993 557506466458209 994 559758162967738 995 562016673332395 996 564282011284596 997 566554190570581 998 568833224950414 999 571119128197983 1000 573411914101000