0 1 1 0 2 5 3 26 4 83 5 203 6 456 7 853 8 1497 9 2477 10 3860 11 5690 12 8305 13 11470 14 15684 15 20947 16 27328 17 35057 18 44569 19 55569 20 68849 21 84153 22 101912 23 122125 24 146014 25 172246 26 202378 27 236593 28 274399 29 316494 30 364473 31 416055 32 473938 33 537432 34 607225 35 683593 36 767218 37 857111 38 955830 39 1062872 40 1178661 41 1302138 42 1438057 43 1580998 44 1737004 45 1903728 46 2080268 47 2270538 48 2474818 49 2689856 50 2919877 51 3164631 52 3424738 53 3698025 54 3992164 55 4299388 56 4625304 57 4969529 58 5332319 59 5714580 60 6119988 61 6539885 62 6987167 63 7456191 64 7946170 65 8460646 66 9001899 67 9564170 68 10155366 69 10774900 70 11422101 71 12093490 72 12801378 73 13530636 74 14297615 75 15098346 76 15927355 77 16790063 78 17690305 79 18622925 80 19597621 81 20603902 82 21651289 83 22735797 84 23869392 85 25032027 86 26241606 87 27500091 88 28797174 89 30139134 90 31537467 91 32968220 92 34456104 93 35993645 94 37581869 95 39219411 96 40916338 97 42658623 98 44461631 99 46323097 100 48238678 101 50208922 102 52251748 103 54342911 104 56505802 105 58729220 106 61010609 107 63366711 108 65796187 109 68276442 110 70843384 111 73472477 112 76180752 113 78947340 114 81813031 115 84740617 116 87745131 117 90838541 118 94002509 119 97256273 120 100599192 121 104003946 122 107512473 123 111108480 124 114793860 125 118568073 126 122442814 127 126388136 128 130445974 129 134603584 130 138856410 131 143197232 132 147666021 133 152207258 134 156869850 135 161647363 136 166513008 137 171487000 138 176591409 139 181794657 140 187123990 141 192553646 142 198114549 143 203785371 144 209589981 145 215492428 146 221537318 147 227719869 148 234010279 149 240430102 150 247006542 151 253676382 152 260515542 153 267479604 154 274581881 155 281817576 156 289215611 157 296732379 158 304402421 159 312241112 160 320218964 161 328330092 162 336620842 163 345034113 164 353640405 165 362398544 166 371299977 167 380377458 168 389639184 169 399024626 170 408614938 171 418362585 172 428280659 173 438368884 174 448673697 175 459125657 176 469748217 177 480574235 178 491583735 179 502775981 180 514193328 181 525730627 182 537517040 183 549482597 184 561661784 185 574022145 186 586606271 187 599379439 188 612360517 189 625567492 190 638964451 191 652574486 192 666448561 193 680467000 194 694760115 195 709286898 196 723996914 197 738942108 198 754157176 199 769554079 200 785220061 201 801106480 202 817247240 203 833610707 204 850251197 205 867100649 206 884223789 207 901612499 208 919228333 209 937101106 210 955273305 211 973627429 212 992313360 213 1011252714 214 1030464016 215 1049939756 216 1069718149 217 1089714541 218 1110016943 219 1130633597 220 1151528292 221 1172644234 222 1194134335 223 1215864656 224 1237938032 225 1260282525 226 1282895413 227 1305855659 228 1329131001 229 1352672843 230 1376563965 231 1400761461 232 1425256906 233 1450061950 234 1475266183 235 1500704471 236 1526518679 237 1552673700 238 1579144623 239 1605932419 240 1633137590 241 1660560743 242 1688413141 243 1716610372 244 1745150991 245 1774047300 246 1803310171 247 1832905950 248 1862857614 249 1893205274 250 1923934213 251 1954996180 252 1986513029 253 2018267778 254 2050492419 255 2083132864 256 2116087242 257 2149441475 258 2183257159 259 2217405994 260 2251988306 261 2286944262 262 2322321361 263 2358074431 264 2394328117 265 2430887946 266 2467916099 267 2505371064 268 2543250482 269 2581555781 270 2620335496 271 2659428122 272 2699073756 273 2739118445 274 2779591098 275 2820534939 276 2861937517 277 2903733694 278 2946045670 279 2988853313 280 3032073577 281 3075675074 282 3119909829 283 3164514554 284 3209633913 285 3255263467 286 3301316198 287 3347868437 288 3394947984 289 3442436918 290 3490520432 291 3539062915 292 3588131767 293 3637643410 294 3687797581 295 3738330507 296 3789449841 297 3841109488 298 3893199918 299 3945904500 300 3999186715 301 4052849975 302 4107150542 303 4162010123 304 4217425326 305 4273319253 306 4329850201 307 4386852520 308 4444481636 309 4502648378 310 4561425451 311 4620692638 312 4680662348 313 4741047812 314 4802137012 315 4863838528 316 4925993579 317 4988833402 318 5052336582 319 5116331748 320 5180992553 321 5246230713 322 5312133604 323 5378565679 324 5445752084 325 5513407882 326 5581736298 327 5650802059 328 5720447911 329 5790705406 330 5861700575 331 5933170937 332 6005433345 333 6078310566 334 6151853360 335 6226090546 336 6301021278 337 6376475094 338 6452700976 339 6529666566 340 6607283802 341 6685510609 342 6764576608 343 6844174058 344 6924585012 345 7005702680 346 7087468319 347 7169941285 348 7253256755 349 7337151788 350 7421899876 351 7507280695 352 7593399675 353 7680206545 354 7767930109 355 7856293767 356 7945423006 357 8035356285 358 8125916857 359 8217355917 360 8309660252 361 8402418330 362 8496205746 363 8590757659 364 8686071880 365 8782076969 366 8879022347 367 8976691883 368 9075169693 369 9174483956 370 9274604015 371 9375467234 372 9477304189 373 9579792698 374 9683252623 375 9787508818 376 9892551035 377 9998467583 378 10105309717 379 10212812855 380 10321342793 381 10430667531 382 10540897777 383 10651924755 384 10764003503 385 10876772700 386 10990438324 387 11105143945 388 11220610740 389 11336982433 390 11454419829 391 11572478698 392 11691624896 393 11811634754 394 11932651795 395 12054581773 396 12177468069 397 12301081876 398 12425813872 399 12551563493 400 12678125307 401 12805557887 402 12934203221 403 13063583260 404 13194086308 405 13325587606 406 13457910557 407 13591273236 408 13725730530 409 13860991491 410 13997364407 411 14134762689 412 14273199874 413 14412512087 414 14553037368 415 14694400241 416 14836895047 417 14980373474 418 15124927270 419 15270452721 420 15417252740 421 15564680161 422 15713517359 423 15863372592 424 16014207315 425 16166150067 426 16319227955 427 16473321159 428 16628459261 429 16784839613 430 16942216766 431 17100617847 432 17260402632 433 17420931301 434 17582857304 435 17745848515 436 17909877677 437 18075095715 438 18241515411 439 18409014023 440 18577791747 441 18747556181 442 18918488564 443 19090562735 444 19264075880 445 19438476767 446 19614125404 447 19791108344 448 19969197278 449 20148342949 450 20328992887 451 20510446535 452 20693356617 453 20877520264 454 21062931259 455 21249527058 456 21437356119 457 21626271434 458 21816614048 459 22008265850 460 22201062939 461 22395036186 462 22590564672 463 22786953980 464 22984944953 465 23184198457 466 23384571524 467 23586401122 468 23789591760 469 23993813436 470 24199575670 471 24406635688 472 24615042836 473 24824532506 474 25035713915 475 25248032102 476 25461740942 477 25676805308 478 25893193180 479 26110987804 480 26330326840 481 26550602747 482 26772567726 483 26995967964 484 27220640481 485 27446666753 486 27674306792 487 27903084064 488 28133422160 489 28365268239 490 28598508291 491 28832949514 492 29069240919 493 29306609654 494 29545598428 495 29786087909 496 30027808894 497 30271138763 498 30516071725 499 30762361701 500 31010246019 501 31259418734 502 31510273572 503 31762547274 504 32016583034 505 32271629745 506 32528529297 507 32787004357 508 33046834593 509 33308280657 510 33571542350 511 33835894796 512 34102041246 513 34369742905 514 34638964083 515 34909805955 516 35182389562 517 35456326302 518 35731887860 519 36009161255 520 36288092258 521 36568359441 522 36850644161 523 37134113041 524 37419600529 525 37706714581 526 37995156348 527 38285413863 528 38577506923 529 38870865798 530 39166277302 531 39463286332 532 39761963255 533 40062098644 534 40364314452 535 40668030418 536 40973388070 537 41280643854 538 41589539897 539 41900234065 540 42212699695 541 42526404548 542 42842392009 543 43160041737 544 43479515024 545 43800509945 546 44123598454 547 44448082248 548 44774630724 549 45103057444 550 45433123262 551 45764862540 552 46098811417 553 46434054990 554 46771425254 555 47110817523 556 47451748229 557 47794574286 558 48139532548 559 48486009927 560 48834597035 561 49184752852 562 49536966553 563 49890978865 564 50247207612 565 50605015258 566 50964828870 567 51326732312 568 51690202956 569 52055782172 570 52423585176 571 52792728219 572 53164277770 573 53537595287 574 53913018399 575 54290284004 576 54669705235 577 55050728320 578 55433903370 579 55819290837 580 56206637331 581 56595679808 582 56987190561 583 57380393848 584 57775856312 585 58173315646 586 58572531713 587 58974041625 588 59377807894 589 59783115953 590 60190889936 591 60600720210 592 61012599599 593 61426401892 594 61842795425 595 62260706048 596 62680891098 597 63103468984 598 63528044658 599 63954540759 600 64383667571 601 64814239180 602 65247575386 603 65682894993 604 66120380305 605 66560007882 606 67001926586 607 67445940910 608 67892190942 609 68340736227 610 68791351161 611 69244103596 612 69699529879 613 70156440669 614 70616269483 615 71078391502 616 71542458877 617 72008596605 618 72477479739 619 72948418801 620 73421796599 621 73897307076 622 74375110652 623 74855255796 624 75337995126 625 75822570280 626 76309720431 627 76799417525 628 77291179155 629 77785435648 630 78282344835 631 78780694716 632 79282259728 633 79785972374 634 80292167190 635 80800713580 636 81311863928 637 81825070997 638 82340698735 639 82859077831 640 83379798648 641 83902591524 642 84428559489 643 84956468394 644 85487035160 645 86020055632 646 86555458785 647 87093438534 648 87634122004 649 88176808974 650 88722476984 651 89270495717 652 89821039278 653 90373963871 654 90930042244 655 91488075577 656 92048883541 657 92612350042 658 93178249832 659 93746745355 660 94318308436 661 94891531396 662 95467928710 663 96047059989 664 96628675450 665 97212925800 666 97799833438 667 98389189494 668 98981429432 669 99576445099 670 100174111895 671 100774196225 672 101377440201 673 101982560832 674 102591157514 675 103202484376 676 103815938088 677 104432334510 678 105051926122 679 105673874427 680 106298715756 681 106926154792 682 107556600588 683 108189333119 684 108825671786 685 109464024875 686 110105605485 687 110750054823 688 111397149729 689 112046941957 690 112700037451 691 113355325759 692 114014101493 693 114675601382 694 115339569418 695 116006820864 696 116677074408 697 117349682971 698 118025437309 699 118704434611 700 119386275218 701 120070450041 702 120758424609 703 121448488280 704 122142010424 705 122838484450 706 123537725592 707 124240144321 708 124945715599 709 125653863466 710 126365412466 711 127079764312 712 127797227677 713 128517415193 714 129241309306 715 129967509772 716 130696888464 717 131429791970 718 132165449332 719 132904389676 720 133646800631 721 134391038930 722 135139215158 723 135890560664 724 136645108655 725 137402415780 726 138163298601 727 138926924058 728 139694010442 729 140464045869 730 141237391742 731 142013788813 732 142793720689 733 143576336174 734 144362680673 735 145152327989 736 145944582830 737 146740327772 738 147539644587 739 148341680695 740 149147503713 741 149956366587 742 150768545490 743 151583546249 744 152402837532 745 153224656918 746 154050009608 747 154879096139 748 155710997329 749 156546264226 750 157385416395 751 158227080860 752 159072826649 753 159921633646 754 160774052404 755 161629746051 756 162489185422 757 163351039379 758 164217113105 759 165086842029 760 165959554852 761 166835340230 762 167715651305 763 168598665241 764 169485542067 765 170375975116 766 171269357715 767 172166582031 768 173067646311 769 173971612174 770 174879593255 771 175790669198 772 176705794951 773 177624133870 774 178546550858 775 179471985405 776 180401147151 777 181334236626 778 182270506106 779 183210654151 780 184154867840 781 185101417463 782 186052644655 783 187007424812 784 187965758061 785 188927520986 786 189893580695 787 190862799787 788 191835718548 789 192812794359 790 193793559374 791 194777623543 792 195766083840 793 196757129498 794 197752869673 795 198752488435 796 199755433837 797 200762251928 798 201773289766 799 202787396554 800 203805884426 801 204827905590 802 205853868100 803 206883661970 804 207917861781 805 208955251657 806 209996467944 807 211042078036 808 212091283430 809 213144150030 810 214201848955 811 215262165934 812 216327465842 813 217396123295 814 218469188772 815 219545889774 816 220626939472 817 221711254751 818 222800058901 819 223893260854 820 224989652734 821 226090167593 822 227195604451 823 228304109418 824 229417279706 825 230534498510 826 231655157788 827 232780150237 828 233909892263 829 235042795031 830 236180473425 831 237322115826 832 238468084795 833 239617423418 834 240771810493 835 241929947337 836 243092434545 837 244258963732 838 245429475605 839 246604472901 840 247784261495 841 248966537444 842 250154206436 843 251346346506 844 252542573348 845 253743010541 846 254947894301 847 256156573708 848 257369621378 849 258587392100 850 259809490759 851 261035031187 852 262266057937 853 263500383516 854 264739991976 855 265983792194 856 267231295892 857 268483626392 858 269740710714 859 271001376603 860 272267239152 861 273537207044 862 274811576501 863 276090276375 864 277374232115 865 278661166916 866 279953571662 867 281250820803 868 282552054301 869 283857485781 870 285168314797 871 286482581741 872 287802050291 873 289126088963 874 290454666506 875 291787617601 876 293125327607 877 294467329889 878 295814050833 879 297165861767 880 298522213860 881 299882332395 882 301248392173 883 302617598759 884 303992611105 885 305372063224 886 306755685378 887 308144516773 888 309538487494 889 310936317320 890 312339448320 891 313747184417 892 315159438322 893 316576104405 894 317998695400 895 319425368138 896 320856929963 897 322293168929 898 323734155949 899 325180331813 900 326631682915 901 328086293094 902 329547150062 903 331012611540 904 332482757860 905 333957762892 906 335438309751 907 336923046897 908 338412992767 909 339908187030 910 341408024232 911 342912137587 912 344422657400 913 345936621396 914 347456236442 915 348981423486 916 350510976573 917 352045648172 918 353585782740 919 355130018833 920 356680358963 921 358234991450 922 359795229648 923 361360091454 924 362930971833 925 364505400220 926 366085881954 927 367671938088 928 369262354636 929 370858118280 930 372459795625 931 374065385441 932 375676679228 933 377293499879 934 378915617502 935 380542663416 936 382175166153 937 383811910180 938 385454825925 939 387103142219 940 388756778262 941 390414677159 942 392079281633 943 393748094374 944 395422904472 945 397103109368 946 398787472214 947 400478066407 948 402174670561 949 403875596532 950 405582563213 951 407294702582 952 409012475626 953 410734722263 954 412464012958 955 414197506884 956 415936634198 957 417681890778 958 419431986694 959 421187811996 960 422949668250 961 424715391431 962 426488186663 963 428265849992 964 430049344878 965 431838425873 966 433633546784 967 435433142922 968 437238929952 969 439050382910 970 440867278352 971 442689714113 972 444518833497 973 446351936126 974 448191629718 975 450037529745 976 451888059508 977 453744253973 978 455607179165 979 457475159436 980 459349372726 981 461228536701 982 463113928281 983 465004987567 984 466902671867 985 468804862466 986 470713381418 987 472628176628 988 474548021835 989 476473854538 990 478406571005 991 480342941820 992 482287134188 993 484236709614 994 486192495373 995 488153393644 996 490121141260 997 492094076636 998 494073095166 999 496058885683 1000 498050018596