1 0 2 1 3 3 4 14 5 100 6 979 7 196 8 500 9 3834 10 1333 11 2178 12 1022 13 16731 14 12647 15 42420 16 23912 17 23409 18 26265 19 15162 20 79730 21 84441 22 21723 23 28566 24 160732 25 280625 26 329405 27 137295 28 569702 29 74849 30 71999 31 463202 32 715984 33 247665 34 31873 35 1302420 36 574170 37 807710 38 225091 39 1377129 40 968260 41 2153361 42 1204357 43 3152545 44 831182 45 2252475 46 91239 47 2957851 48 106040 49 3791179 50 3486665 51 6638772 52 7237698 53 7008455 54 3644091 55 1879130 56 8204972 57 2308044 58 7541709 59 6874975 60 6343990 61 12796519 62 4706511 63 3887541 64 12607904 65 5150275 66 12240833 67 19109673 68 1606058 69 9638058 70 5889331 71 5812273 72 17185044 73 3218716 74 11315893 75 18351750 76 1632670 77 32301192 78 3298087 79 21556414 80 34285320 81 2948076 82 18952617 83 15390026 84 14407442 85 42222900 86 54442427 87 7511232 88 8059260 89 54250929 90 14363997 91 43160572 92 67452422 93 68079441 94 54914751 95 7555730 96 45080176 97 10481626 98 2717281 99 10284516 100 49270650 101 5406530 102 91145891 103 98377257 104 2843620 105 85934100 106 125931973 107 115062450 108 49039470 109 133982037 110 16844663 111 62089959 112 93878232 113 4303153 114 98219113 115 117308395 116 53599714 117 14446458 118 167912523 119 191343432 120 37218380 121 48739889 122 113299629 123 58267191 124 181293270 125 174984375 126 564879 127 73983723 128 210297664 129 16364037 130 210695329 131 282933407 132 81423946 133 2175747 134 2764083 135 138720195 136 104306356 137 290788117 138 151761797 139 146008797 140 229326910 141 204383730 142 370064423 143 369249452 144 371921064 145 20583475 146 233013881 147 360167493 148 433100466 149 74706365 150 367109995 151 169593838 152 294018844 153 195636816 154 246875629 155 512001580 156 31125926 157 140277459 158 166327151 159 31079253 160 156954640 161 583766841 162 544490289 163 239599242 164 559526426 165 613306650 166 90879603 167 285722805 168 532599172 169 277213066 170 425702661 171 836682480 172 140662030 173 782942640 174 871935431 175 117728625 176 61567352 177 716724507 178 267445977 179 647516569 180 883139970 181 252816637 182 581997467 183 588413442 184 664219116 185 245359025 186 855176509 187 976369449 188 242931062 189 402985611 190 449147327 191 708935273 192 265651424 193 146165076 194 780381585 195 903421155 196 965123306 197 975503024 198 104999235 199 541266468 200 366601300 201 1088861421 202 1349060533 203 655758817 204 389856478 205 1600269975 206 741624615 207 660831561 208 1325800008 209 1736843922 210 315377993 211 662338917 212 385050194 213 989604390 214 681845835 215 1440380245 216 305394876 217 1275499743 218 1382640909 219 1674766803 220 1963497030 221 502085480 222 156599503 223 1277438552 224 655892912 225 817965000 226 2432550433 227 1375463597 228 292601786 229 1238551538 230 2340188659 231 1083307071 232 542326564 233 2621127209 234 2149320693 235 2595199470 236 260063150 237 599174157 238 594356567 239 32444728 240 1217825560 241 1654785771 242 1763547753 243 1278076239 244 3428598818 245 3397655100 246 2389223627 247 1924040833 248 2174296972 249 1957640988 250 1531683325 251 2819294750 252 669668118 253 3817694606 254 57568463 255 3357535530 256 1025656448 257 1664632947 258 685998049 259 216738711 260 552465290 261 3054772710 262 3658290147 263 3146705317 264 1469350388 265 2675151150 266 3908176101 267 1438850451 268 2460019838 269 3452415671 270 1452005991 271 785524936 272 5429543912 273 1812804357 274 3725471001 275 303195750 276 3935043826 277 5107772801 278 4477157611 279 634897143 280 4278614620 281 5781524420 282 4152775757 283 5732610442 284 4343917030 285 4743729525 286 6649056271 287 4180968071 288 689140560 289 3228420734 290 6933880657 291 1582378266 292 2858788186 293 834452280 294 295151059 295 6269472455 296 4040645828 297 6540726753 298 3959227253 299 1857752780 300 2911791950 301 6095725881 302 305471639 303 7687107273 304 5640602808 305 7681911475 306 1698039321 307 257488268 308 8833354178 309 6305407032 310 3632311323 311 5206007825 312 300501292 313 6876738017 314 6150143885 315 356284845 316 6230881206 317 8249744944 318 9806172095 319 23201508 320 3001755680 321 8810556015 322 9190325809 323 1890656275 324 1246497066 325 1486566250 326 6593194659 327 1270246215 328 2693582740 329 2327830946 330 3578651989 331 1819917771 332 10615599902 333 6133972887 334 7174375943 335 1344814620 336 10327920008 337 9989302102 338 2057475433 339 8916529872 340 10035544210 341 1973172289 342 11356546107 343 11894078602 344 7307087868 345 197859225 346 11168768413 347 13149385254 348 9790294150 349 6877737067 350 6768956655 351 10102532544 352 14932305136 353 12387131472 354 2444577857 355 5632208480 356 8851664634 357 9689498364 358 11774942019 359 6044003376 360 2815715940 361 15335002391 362 13627743941 363 11717877765 364 9319591918 365 14770522525 366 7236529735 367 13785823217 368 10098646616 369 9926863092 370 6491699321 371 13517034405 372 12029074274 373 12269229994 374 8042505163 375 15909262500 376 17255222988 377 14978691052 378 6582169629 379 663765061 380 2971389270 381 3486816750 382 8254130511 383 17834741998 384 9893063104 385 6532127525 386 12341254337 387 12775944699 388 14522176714 389 17607257597 390 182753987 391 17898695956 392 13091786036 393 22325346714 394 1638515781 395 2860281505 396 10623528894 397 20767665103 398 22159031879 399 20485113663 400 13444642600 401 16511207481 402 15924012409 403 2096375372 404 6085889330 405 17429679225 406 12965876539 407 12350955089 408 24282662300 409 14535213371 410 24773484653 411 22746959400 412 16864179494 413 26099615535 414 9283202799 415 5612847195 416 599029392 417 12456771618 418 27672951185 419 22343648470 420 12109714330 421 25027138164 422 22282506243 423 29584896219 424 11318974468 425 3377506875 426 4548624869 427 33016135320 428 3208895118 429 5266394562 430 739055319 431 6837305127 432 24119908344 433 20725409038 434 26547359609 435 4916355645 436 28664322306 437 34931667542 438 32705678635 439 9247331743 440 6307402860 441 13920070185 442 11361164685 443 20104532556 444 20004269558 445 38486950850 446 10781557391 447 29034913161 448 39139232608 449 19841772021 450 20650679985 451 4691037263 452 21204167274 453 33685742739 454 4137005763 455 6232736055 456 3646814932 457 25494615128 458 1067871653 459 18090826335 460 9385226590 461 33683515895 462 16638178823 463 34589081257 464 9721708744 465 25552893900 466 11226525993 467 44547295318 468 31767898578 469 47322849462 470 4778082651 471 8600407248 472 36140518204 473 5692804744 474 39857554237 475 9157938250 476 4405513926 477 31340147832 478 16462774815 479 33775550728 480 39908943920 481 31754065889 482 41585314209 483 9131275839 484 33984994362 485 18681334275 486 3258184419 487 42865925060 488 47215076772 489 50507218794 490 36469197317 491 6502436732 492 46870575406 493 44473835167 494 30226854919 495 26451804555 496 14863774104 497 51872384018 498 14435694905 499 23413813031 500 45524953250 501 45344921826 502 25647607451 503 11831459867 504 8366307852 505 47104137600 506 48192561549 507 37951848012 508 42817634710 509 22569582234 510 31517387983 511 9043403593 512 55197469952 513 57647257173 514 64731174673 515 24494907920 516 62622674954 517 69468411100 518 54236841571 519 58357151994 520 44831012980 521 48859380000 522 70274159781 523 12629928046 524 74554339838 525 74009302500 526 36330887063 527 34466446629 528 76083702376 529 72842332459 530 34167368649 531 17785347984 532 14928185202 533 28447536104 534 39945239435 535 19810548170 536 73734594780 537 38731514862 538 11144375981 539 17099485018 540 7546161510 541 2139205429 542 60229663007 543 64554929670 544 47322102224 545 15661831225 546 38637455857 547 30935218510 548 1653874138 549 23578700697 550 35873603315 551 48782001478 552 80027935556 553 84797165992 554 10683237109 555 53004798255 556 47612714446 557 34215810965 558 51161816487 559 43575475450 560 33027517240 561 26972953491 562 36761158185 563 34701132182 564 23893402690 565 86348447150 566 15064526667 567 91398189834 568 3196157868 569 45244952228 570 105549065981 571 74322676155 572 9723705654 573 61936750380 574 95857187503 575 20967326125 576 56280739488 577 39184744513 578 73160693009 579 59219765652 580 111847238570 581 99985568200 582 68739290851 583 86529312408 584 55415105044 585 62396971650 586 101161384805 587 56558933936 588 57193953950 589 20129397183 590 11564550647 591 113046310974 592 4063425544 593 83814835852 594 84017234169 595 7951139105 596 684619538 597 109157148615 598 67714013627 599 73575733060 600 23712523900 601 88303892073 602 110783468605 603 105764161860 604 95654268678 605 23619227225 606 50174484575 607 7057272146 608 122865052528 609 9178368717 610 10753161313 611 23137315617 612 107451540858 613 122814836884 614 31653200307 615 88799110770 616 101682508004 617 144507260266 618 78377046085 619 55107364503 620 140689771630 621 131812607988 622 118427739799 623 67056659201 624 45243155672 625 141581640625 626 11467534681 627 103271188053 628 139386611170 629 91268839726 630 39162311979 631 26206558859 632 29990552908 633 107149583019 634 130922535229 635 59446735945 636 80606948566 637 38537099237 638 91306114735 639 116624780127 640 154049540160 641 165525054374 642 124085643905 643 30097846853 644 763975498 645 89908133475 646 3721828547 647 10346340044 648 63290684340 649 102068374727 650 105728226645 651 67887612597 652 79951292990 653 158899608214 654 89908850887 655 165372491330 656 41003310504 657 125178353883 658 43837571113 659 175907256174 660 64565907890 661 65016903247 662 14260567995 663 66120149316 664 47660792860 665 193725063525 666 70113509085 667 154634518620 668 41888534182 669 31778324877 670 182437069311 671 147547577628 672 72936848656 673 15120128807 674 199646748817 675 136631701125 676 130066922778 677 188310886256 678 20694173075 679 59784108552 680 67424153220 681 141031268013 682 192379140661 683 187016373078 684 74554110222 685 129773089025 686 19481795879 687 54700422546 688 81324719736 689 117822429153 690 72941003977 691 172235991358 692 203597329794 693 17814628755 694 216381440731 695 179939950780 696 187870874348 697 66242972004 698 63147131309 699 86974563171 700 162767154550 701 126734774905 702 51396943455 703 143405613948 704 104671941088 705 107773575600 706 85315136465 707 134164470090 708 116419881706 709 97524638129 710 204411224643 711 216834807600 712 143159378260 713 58414139945 714 13735905701 715 54578483245 716 45485574366 717 215363365572 718 226228048503 719 247153367529 720 206479550280 721 43111973653 722 55609695881 723 146308364409 724 273903276370 725 252141786875 726 24885563131 727 114292282134 728 208029172156 729 174305384973 730 189368375309 731 247083182790 732 248542112582 733 170682745786 734 248311036975 735 62103550845 736 222855835312 737 158944828625 738 112983622305 739 174393365051 740 141608698810 741 226035994548 742 5226393123 743 244797296266 744 111198972964 745 147513989475 746 305078649669 747 266248600263 748 138007994542 749 114536208164 750 108973799975 751 60882779948 752 107826108440 753 209009914824 754 129183755337 755 211608214655 756 285523247394 757 68150998423 758 92999562347 759 98655215439 760 309318758540 761 19724282139 762 319059082861 763 203296907814 764 20075250966 765 69526095525 766 9465002015 767 196069075943 768 48145159040 769 5170269223 770 306260012641 771 183797791014 772 190820170378 773 341362939939 774 170135425443 775 94498853875 776 50923962100 777 89617216521 778 274481678101 779 25933956976 780 355566847870 781 304055189163 782 261381254487 783 337860064305 784 58681200872 785 110654907025 786 241179593993 787 301446892300 788 78462069746 789 282802784880 790 250305917307 791 377366355849 792 24587085660 793 277253235610 794 86977978477 795 48271246455 796 282211721446 797 307870557284 798 30339311359 799 316468782121 800 95648645200 801 118742594139 802 98990277345 803 251803776400 804 244502713946 805 382175335850 806 380175857571 807 417259361298 808 385126476228 809 422514608132 810 30512537973 811 31529171577 812 82953245518 813 125196343959 814 424889141655 815 17718334720 816 248331309496 817 401958538355 818 278076974425 819 400907513097 820 150847188930 821 208524693965 822 220349781131 823 133674264795 824 136586581548 825 448298647500 826 3818367133 827 252727495867 828 280990508214 829 193173136485 830 170630348639 831 129032246091 832 423688058144 833 117852189427 834 320711580145 835 462701657870 836 488255783466 837 169878408057 838 297511040083 839 343869632026 840 465279757460 841 435904353110 842 195162381861 843 52159744065 844 32125403678 845 326633592350 846 47077560951 847 314336340395 848 448669899400 849 5933155845 850 275650823305 851 20681007957 852 350442292882 853 20314843280 854 232141384731 855 210991749480 856 307117952252 857 71279009899 858 504238750301 859 91414601328 860 69321389190 861 340927209021 862 336525861551 863 391043942526 864 128530313712 865 254840945650 866 233528879809 867 218205839523 868 563589846778 869 226996865634 870 1522385971 871 473953378340 872 566950750052 873 169896337110 874 314910842549 875 324911496875 876 325911011054 877 233217602767 878 2940618231 879 80092998885 880 242328562520 881 290066888920 882 90063548841 883 482908958729 884 148274142562 885 123849280650 886 490544854059 887 524506634771 888 66584038348 889 521483827998 890 63608240637 891 291098168064 892 620234940246 893 586922464 894 474717857759 895 571677284255 896 377902118592 897 59958121665 898 485056174065 899 551071879719 900 371816795850 901 268253146042 902 437515449443 903 287661190719 904 279092005428 905 619472834850 906 474751794469 907 309144913008 908 150201950654 909 445363255584 910 206687511303 911 245706411260 912 446913037352 913 349287993142 914 55721572649 915 606526423320 916 377639527474 917 618008006994 918 389247160923 919 301031944596 920 636639527580 921 438055688658 922 412614086781 923 343886252424 924 259193654566 925 448624722500 926 602605537455 927 18053070075 928 416081085328 929 136750572532 930 741165731969 931 35388118108 932 715651785370 933 502638921831 934 365739541459 935 471096423270 936 159823566084 937 260758548938 938 740717348069 939 757579388529 940 448352276110 941 314493630327 942 719732503063 943 493891562347 944 592013354232 945 168062372100 946 781202221833 947 752307959448 948 61452936962 949 131755224497 950 152312296635 951 396246418851 952 547376206188 953 165160531277 954 579664438269 955 234373278930 956 167748687606 957 774967917009 958 380751259551 959 615091849610 960 421024159840 961 445342143662 962 217913530449 963 856295748963 964 127039099754 965 380795595775 966 846539922179 967 847727375086 968 327217870804 969 368308704198 970 400114459301 971 340916220144 972 283509559134 973 761736259942 974 834087260487 975 494130702000 976 685062573512 977 691209766473 978 428660587465 979 453044517849 980 58660457170 981 263910502539 982 225056248219 983 298836468718 984 477213968444 985 352404154275 986 588125738781 987 471795381435 988 227409013702 989 623331082154 990 906821783967 991 400024179163 992 229588612400 993 114997310238 994 541117624929 995 628093838555 996 173567530810 997 912212993399 998 753059298627 999 274794918012 1000 693731406500