0 1 1 1 2 4 3 10 4 24 5 49 6 94 7 169 8 289 9 468 10 734 11 1117 12 1656 13 2385 14 3370 15 4672 16 6375 17 8550 18 11322 19 14800 20 19138 21 24460 22 30982 23 38882 24 48417 25 59779 26 73316 27 89291 28 108108 29 130053 30 155646 31 185258 32 219489 33 258735 34 303748 35 355034 36 413442 37 479500 38 554256 39 638367 40 733005 41 838856 42 957332 43 1089264 44 1236222 45 1399069 46 1579666 47 1779048 48 1999265 49 2241373 50 2507780 51 2799736 52 3119876 53 3469477 54 3851588 55 4267696 56 4721127 57 5213390 58 5748298 59 6327599 60 6955424 61 7633527 62 8366614 63 9156698 64 10008857 65 10925111 66 11911188 67 12969380 68 14105854 69 15322898 70 16627422 71 18022014 72 19514081 73 21106179 74 22806570 75 24618130 76 26549686 77 28604077 78 30791082 79 33113866 80 35582861 81 38201173 82 40980304 83 43923712 84 47043624 85 50343403 86 53836482 87 57526589 88 61427973 89 65544250 90 69890996 91 74472192 92 79304338 93 84391271 94 89750960 95 95387629 96 101320263 97 107552889 98 114106128 99 120984400 100 128209452 101 135785481 102 143736016 103 152065636 104 160799129 105 169940805 106 179517404 107 189533633 108 200017604 109 210973687 110 222432142 111 234397732 112 246902225 113 259950005 114 273575162 115 287782453 116 302607632 117 318055016 118 334162882 119 350935924 120 368414221 121 386601939 122 405541910 123 425238662 124 445736988 125 467040834 126 489197948 127 512212602 128 536134693 129 560967829 130 586765096 131 613530422 132 641319204 133 670134599 134 700035456 135 731025224 136 763165251 137 796458140 138 830968928 139 866700458 140 903720482 141 942030897 142 981703412 143 1022740143 144 1065215705 145 1109131138 146 1154565314 147 1201519448 148 1250075536 149 1300233623 150 1352080232 151 1405615512 152 1460929361 153 1518020633 154 1576984058 155 1637818560 156 1700622462 157 1765393239 158 1832234386 159 1901143384 160 1972227573 161 2045482867 162 2121022086 163 2198841059 164 2279056734 165 2361663227 166 2446783308 167 2534410954 168 2624673317 169 2717562477 170 2813211790 171 2911613114 172 3012904472 173 3117075684 174 3224271322 175 3334480871 176 3447853891 177 3564377653 178 3684208652 179 3807333750 180 3933914716 181 4063935987 182 4197566692 183 4334790752 184 4475782893 185 4620524443 186 4769197874 187 4921783860 188 5078470830 189 5239236661 190 5404277956 191 5573571841 192 5747321201 193 5925500120 194 6108320128 195 6295754429 196 6488021194 197 6685090389 198 6887189260 199 7094286726 200 7306617077 201 7524145757 202 7747116606 203 7975493900 204 8209528884 205 8449182084 206 8694714812 207 8946086268 208 9203565573 209 9467107947 210 9736993054 211 10013174593 212 10295940482 213 10585240171 214 10881372642 215 11184285677 216 11494286915 217 11811319575 218 12135702930 219 12467378344 220 12806674192 221 13153527014 222 13508277342 223 13870859633 224 14241624013 225 14620499810 226 15007849878 227 15403601286 228 15808126928 229 16221348393 230 16643651924 231 17074956632 232 17515659293 233 17965673239 234 18425409168 235 18894777675 236 19374200528 237 19863582201 238 20363359008 239 20873432477 240 21394250485 241 21925708046 242 22468268260 243 23021822943 244 23586847296 245 24163226288 246 24751450966 247 25351402804 248 25963585541 249 26587873419 250 27224786702 251 27874195896 252 28536634496 253 29211965342 254 29900739186 255 30602814845 256 31318756891 257 32048416099 258 32792374978 259 33550479945 260 34323327970 261 35110757003 262 35913382686 263 36731038333 264 37564354637 265 38413155966 266 39278092476 267 40158983574 268 41056495108 269 41970437122 270 42901495662 271 43849475435 272 44815078877 273 45798100860 274 46799264812 275 47818359955 276 48856126746 277 49912344047 278 50987774160 279 52082189930 280 53196371385 281 54330080547 282 55484120084 283 56658245583 284 57853278190 285 59068962154 286 60306142114 287 61564555529 288 62845066213 289 64147399710 290 65472444244 291 66819918161 292 68190729612 293 69584584520 294 71002416300 295 72443923215 296 73910059419 297 75400510185 298 76916255850 299 78456973630 300 80023665352 301 81615994616 302 83234990414 303 84880307835 304 86552998173 305 88252702344 306 89980499724 307 91736022209 308 93520372350 309 95333167253 310 97175538534 311 99047093837 312 100948988765 313 102880815490 314 104843759730 315 106837403697 316 108862957966 317 110919988670 318 113009737482 319 115131760015 320 117287323737 321 119475967510 322 121698990952 323 123955921917 324 126248086688 325 128574995634 326 130938008306 327 133336623516 328 135772228417 329 138244303673 330 140754270756 331 143301598163 332 145887735970 333 148512133800 334 151176277168 335 153879602994 336 156623626331 337 159407764430 338 162233568976 339 165100443917 340 168009971476 341 170961535216 342 173956755112 343 176995000759 344 180077923741 345 183204872484 346 186377537516 347 189595252708 348 192859741196 349 196170314828 350 199528736950 351 202934304201 352 206388813605 353 209891539002 354 213444318818 355 217046410966 356 220699688688 357 224403386255 358 228159419578 359 231967006359 360 235828098393 361 239741888822 362 243710373454 363 247732728153 364 251810985748 365 255944296711 366 260134739148 367 264381445475 368 268686532033 369 273049104938 370 277471327152 371 281952286039 372 286494183932 373 291096080914 374 295760227360 375 300485663835 376 305274681295 377 310126292127 378 315042836672 379 320023306961 380 325070085202 381 330182134278 382 335361887204 383 340608285752 384 345923806013 385 351307359563 386 356761474802 387 362285041369 388 367880632024 389 373547105250 390 379287087536 391 385099414527 392 390986758437 393 396947922716 394 402985634810 395 409098674519 396 415289816294 397 421557806624 398 427905476778 399 434331548705 400 440838902041 401 447426224396 402 454096453726 403 460848252136 404 467684607390 405 474604146150 406 481609916084 407 488700517473 408 495879049153 409 503144074772 410 510498754742 411 517941625377 412 525475899696 413 533100076285 414 540817431322 415 548626435028 416 556530417711 417 564527810686 418 572622009092 419 580811414939 420 589099478932 421 597484562914 422 605970184180 423 614554674247 424 623241607497 425 632029274114 426 640921316738 427 649915994127 428 659017007614 429 668222573374 430 677536462756 431 686956859502 432 696487595173 433 706126809589 434 715878406176 435 725740491234 436 735717030002 437 745806083620 438 756011690948 439 766331878433 440 776770748441 441 787326280932 442 798002653742 443 808797811063 444 819715995836 445 830755104353 446 841919456964 447 853206913033 448 864621859705 449 876162107128 450 887832121702 451 899629675402 452 911559303202 453 923618726458 454 935812561338 455 948138489880 456 960601198511 457 973198317154 458 985934615466 459 998807682819 460 1011822360904 461 1024976185587 462 1038274083726 463 1051713549314 464 1065299583113 465 1079029624127 466 1092908760318 467 1106934387599 468 1121111669608 469 1135437945692 470 1149918468820 471 1164550533939 472 1179339471561 473 1194282518594 474 1209385096912 475 1224644397626 476 1240065922112 477 1255646801878 478 1271392631792 479 1287300496270 480 1303376071545 481 1319616380767 482 1336027195892 483 1352605491592 484 1369357123144 485 1386279002403 486 1403377082494 487 1420648225315 488 1438098469369 489 1455724612086 490 1473532792046 491 1491519755351 492 1509691727912 493 1528045389615 494 1546587068778 495 1565313392494 496 1584230778463 497 1603335785924 498 1622634937210 499 1642124737206 500 1661811799778 501 1681692560222 502 1701773739366 503 1722051716700 504 1742533306633 505 1763214817229 506 1784103172292 507 1805194622533 508 1826496187484 509 1848004044707 510 1869725325454 511 1891656148288 512 1913803742441 513 1936164151501 514 1958744718852 515 1981541427552 516 2004561721106 517 2027801505670 518 2051268341440 519 2074958072409 520 2098878361141 521 2123024972914 522 2147405689412 523 2172016212018 524 2196864427134 525 2221945955515 526 2247268805218 527 2272828531486 528 2298633249337 529 2324678431363 530 2350972316884 531 2377510311262 532 2404300763124 533 2431338993279 534 2458633477188 535 2486179466610 536 2513985548767 537 2542046888856 538 2570372203578 539 2598956587377 540 2627808871056 541 2656924060381 542 2686311118390 543 2715964978288 544 2745894719665 545 2776095185053 546 2806575588916 547 2837330699314 548 2868369849822 549 2899687715724 550 2931293768222 551 2963182606336 552 2995363822825 553 3027831921717 554 3060596636266 555 3093652392340 556 3127009047302 557 3160660929939 558 3194618040858 559 3228874628680 560 3263440820789 561 3298310766523 562 3333494739376 563 3368986806638 564 3404797371128 565 3440920398541 566 3477366440786 567 3514129379519 568 3551219898637 569 3588631776012 570 3626375847492 571 3664445804810 572 3702852618578 573 3741589874445 574 3780668697952 575 3820082586635 576 3859842803455 577 3899942737447 578 3940393809600 579 3981189318750 580 4022340826076 581 4063841519627 582 4105703121584 583 4147918727598 584 4190500202929 585 4233440530039 586 4276751738284 587 4320426715659 588 4364477637364 589 4408897275685 590 4453697973134 591 4498872405346 592 4544433063561 593 4590372505315 594 4636703392250 595 4683418182955 596 4730529690800 597 4778030253770 598 4825932858850 599 4874229742910 600 4922934047541 601 4972037886381 602 5021554577974 603 5071476132560 604 5121816026284 605 5172566143664 606 5223740141004 607 5275329797024 608 5327348928749 609 5379789186563 610 5432664570984 611 5485966624332 612 5539709510836 613 5593884641745 614 5648506368240 615 5703565991122 616 5759078028395 617 5815033647190 618 5871447555792 619 5928310808380 620 5985638283298 621 6043420898335 622 6101673725572 623 6160387567477 624 6219577669297 625 6279234694264 626 6339374084946 627 6399986386766 628 6461087218688 629 6522666984193 630 6584741503016 631 6647301058218 632 6710361649289 633 6773913414515 634 6837972557738 635 6902529094354 636 6967599411182 637 7033173375885 638 7099267583346 639 7165871775742 640 7233002734285 641 7300650050601 642 7368830717542 643 7437534198529 644 7506777676222 645 7576550460549 646 7646869949516 647 7717725322268 648 7789134169965 649 7861085515183 650 7933597168270 651 8006658018316 652 8080286072296 653 8154470059802 654 8229228210698 655 8304549118261 656 8380451212587 657 8456922924395 658 8533982910508 659 8611619462644 660 8689851441324 661 8768666972517 662 8848085147444 663 8928093950258 664 9008712679477 665 9089929150461 666 9171762896258 667 9254201587470 668 9337264968174 669 9420940537003 670 9505248276532 671 9590175537839 672 9675742518121 673 9761936393174 674 9848777602800 675 9936253172315 676 10024383759866 677 10113156212327 678 10202591434412 679 10292676119456 680 10383431394381 681 10474843770783 682 10566934626254 683 10659690315942 684 10753132443364 685 10847247178498 686 10942056379772 687 11037546057674 688 11133738300413 689 11230618930025 690 11328210293726 691 11426498050887 692 11525504782498 693 11625215956061 694 11725654415810 695 11826805463559 696 11928692181163 697 12031299675009 698 12134651294578 699 12238731977410 700 12343565314592 701 12449136044836 702 12555468031086 703 12662545839911 704 12770393579989 705 12878995615520 706 12988376331414 707 13098519916588 708 13209451005664 709 13321153581507 710 13433652559492 711 13546931743922 712 13661016304005 713 13775889834465 714 13891577789632 715 14008063582253 716 14125372924752 717 14243489016631 718 14362437859952 719 14482202468979 720 14602809107981 721 14724240574164 722 14846523426100 723 14969640272357 724 15093617937968 725 15218438810794 726 15344130014678 727 15470673745302 728 15598097397373 729 15726382942069 730 15855558077566 731 15985604579482 732 16116550421104 733 16248377149604 734 16381113046546 735 16514739460019 736 16649284951091 737 16784730635625 738 16921105387618 739 17058390120183 740 17196613991362 741 17335757678117 742 17475850656222 743 17616873396383 744 17758855662805 745 17901777685968 746 18045669552764 747 18190511283768 748 18336333258836 749 18483115254408 750 18630887977822 751 18779630991817 752 18929375301381 753 19080100221058 754 19231837088268 755 19384565000225 756 19538315596522 757 19693067721969 758 19848853353696 759 20005651115404 760 20163493291073 761 20322358247957 762 20482278612516 763 20643232526969 764 20805252929454 765 20968317701552 766 21132460128978 767 21297657864519 768 21463944510237 769 21631297453932 770 21799750650500 771 21969281255039 772 22139923543612 773 22311654402154 774 22484508464652 775 22658462380281 776 22833551109171 777 23009751027003 778 23187097457082 779 23365566534440 780 23545193913336 781 23725955450822 782 23907887169742 783 24090964682457 784 24275224347733 785 24460641495638 786 24647252858764 787 24835033518295 788 25024020547870 789 25214188741911 790 25405575553286 791 25598155523511 792 25791966451461 793 25986982587260 794 26183242114578 795 26380719026459 796 26579451857694 797 26779414305484 798 26980645294810 799 27183118261461 800 27386872486817 801 27591881106212 802 27798183796776 803 28005753428275 804 28214630039344 805 28424786194524 806 28636262333922 807 28849030752198 808 29063132256233 809 29278538830867 810 29495291690004 811 29713362544133 812 29932792979362 813 30153554391606 814 30375688779712 815 30599167260952 816 30824032211635 817 31050254429540 818 31277876709600 819 31506869566499 820 31737276178052 821 31969066734714 822 32202284838632 823 32436900392553 824 32672957387093 825 32910425395870 826 33149348839708 827 33389697000086 828 33631514691708 829 33874770861858 830 34119510761494 831 34365703041167 832 34613393351293 833 34862550003344 834 35113219089858 835 35365368620820 836 35619045093968 837 35874216175161 838 36130928810298 839 36389150359177 840 36648928178465 841 36910229278616 842 37173101470670 843 37437511454283 844 37703507456996 845 37971055824093 846 38240205243516 847 38510921744849 848 38783254438441 849 39057168994304 850 39332714989392 851 39609857773301 852 39888647351116 853 40169048707492 854 40451112320496 855 40734802849485 856 41020171206551 857 41307181680929 858 41595885663888 859 41886247114315 860 42178317863570 861 42472061495068 862 42767530325716 863 43064687603718 864 43363586091957 865 43664188657641 866 43966548555746 867 44270628313239 868 44576481637128 869 44884070668052 870 45193449611472 871 45504580262585 872 45817517285117 873 46132222082430 874 46448749823242 875 46767061560465 876 47087212927126 877 47409164578622 878 47732972659690 879 48058597470095 880 48386095625105 881 48715427021482 882 49046648792734 883 49379720474638 884 49714699677630 885 50051545528824 886 50390316163604 887 50730970342939 888 51073566685353 889 51418063537310 890 51764520049174 891 52112894195931 892 52463245617472 893 52815531868635 894 53169813127850 895 53526046572970 896 53884292878519 897 54244508796380 898 54606755546500 899 54970989498465 900 55337272374692 901 55705560112796 902 56075914987684 903 56448292549185 904 56822755581233 905 57199259195884 906 57577866736434 907 57958532921489 908 58341321610110 909 58726187077148 910 59113193748084 911 59502295498852 912 59893557277245 913 60286932509275 914 60682486716400 915 61080172920072 916 61480057170786 917 61882092034110 918 62286344141252 919 62692765647395 920 63101423719697 921 63512270051310 922 63925372397342 923 64340682034937 924 64758267261868 925 65178078886919 926 65600185803236 927 66024538397791 928 66451206113297 929 66880138862238 930 67311406689926 931 67744959081048 932 68180866637570 933 68619078363380 934 69059665470458 935 69502576529114 936 69947883314871 937 70395533910740 938 70845600709866 939 71298031355717 940 71752898812056 941 72210150228761 942 72669859194622 943 73131972413824 944 73596564053041 945 74063580316389 946 74533096003166 947 75005056865853 948 75479538288696 949 75956485517438 950 76435974576740 951 76917950254581 952 77402489167825 953 77889535591252 954 78379166789728 955 78871326573956 956 79366092808448 957 79863408784060 958 80363353021088 959 80865868340204 960 81371033868593 961 81878791900237 962 82389222226084 963 82902266663638 964 83418005618168 965 83936380373861 966 84457472007518 967 84981221320365 968 85507710011153 969 86036878340968 970 86568808688062 971 87103440824289 972 87640857757272 973 88180998711709 974 88723947382890 975 89269642499820 976 89818168394775 977 90369463242802 978 90923612071802 979 91480552554476 980 92040370363522 981 92603002610688 982 93168535672454 983 93736906151782 984 94308201077553 985 94882356484583 986 95459460113892 987 96039447484879 988 96622406998764 989 97208273599825 990 97797136409566 991 98388929850022 992 98983743710897 993 99581511831931 994 100182324731460 995 100786115720374 996 101392975992994 997 102002838270544 998 102615794484528 999 103231776820515 1000 103850877893981