1000 100 100 231647 981967 490114 472979 118720 179554 86409 941758 231590 301668 231563 330886 919437 446610 119928 97910 410519 313809 376395 850888 259836 843215 643393 649235 56150 820054 857139 557149 431594 758836 303832 919772 627411 556270 772364 612534 12375 609368 856236 752876 472845 166424 287815 724836 860887 382912 485022 720121 625265 255933 666283 172137 639065 812692 249858 99797 957705 253544 181822 757371 561262 366393 216707 358978 467179 278138 200646 10865 762338 398939 639720 262510 446339 166011 253484 300180 516263 553367 900489 956643 909025 834142 236025 138637 95301 35468 971668 145089 473038 16186 983054 4248 623018 566132 702824 192887 815118 863068 168005 974949 578798 70360 595760 110368 331127 230241 369708 604979 953980 285134 923724 693554 731890 172705 772811 581430 358546 318142 724329 642993 763766 894118 117310 960761 473198 40340 498005 686242 84389 778287 178286 235477 453367 318964 884154 87838 305637 762209 414487 284623 896324 545495 288197 897556 204552 310708 559437 893459 360259 110723 749869 344236 131506 266814 297074 219113 500320 717651 544295 121877 202042 13029 183491 990103 853178 307490 347860 938289 596900 754819 149851 754374 245023 993513 459524 5121 942325 165179 246310 638419 311273 678229 7025 28227 431602 797751 734849 435852 581365 948382 69386 499093 220625 122091 603985 159004 897665 99534 923795 620354 244958 888481 58880 316682 650823 702041 672665 687561 376889 601730 33624 11891 81666 670989 933353 372833 451701 81362 156678 251061 829773 964995 913113 896174 929339 816325 438929 296823 627073 108712 352774 216714 423752 168715 159140 481089 530873 990186 445559 93492 919003 293957 855569 861435 675455 943518 264763 102140 65121 900747 360322 417733 852236 1341 211103 588388 966969 577747 590272 663801 636997 57791 859930 484118 81471 318525 939892 39750 155449 289711 524129 749737 223754 683577 496 149228 679613 715702 797110 799579 363289 433791 641233 598257 508340 193438 319931 837441 915279 624647 967488 796639 687074 858973 283573 37701 677886 135266 636510 966432 949867 369892 241572 662017 21018 880465 10529 632188 198928 414420 782915 313345 694172 920374 624781 220531 176520 780662 976844 419422 863926 113967 766291 754476 726500 918389 297477 931294 566380 785062 393706 936898 103874 994096 54443 342447 359016 131638 263976 944258 612027 424558 249413 161686 339181 163762 217339 138611 964659 146707 822993 16464 197333 147150 549721 871812 374029 870845 68213 248902 284500 655855 784084 411366 183441 10133 653262 750560 719261 839627 711407 477637 856886 590407 660395 137236 484040 566981 406045 27692 191399 863844 534121 125391 384113 694618 914526 619172 763356 955051 630063 349615 374064 818317 440872 44107 910980 138317 546700 981648 451550 789587 221267 978228 216969 198419 859356 910021 497385 676516 919550 762723 762860 16780 74543 819902 912377 422725 868073 948763 443390 500651 751102 261109 953490 446215 179791 995191 790246 786830 979999 437435 641217 881633 446516 759073 729400 351606 195048 444277 78420 175779 589464 163176 639377 960169 41672 352336 16083 690059 701307 75522 712029 52036 838619 696639 673269 655064 984940 532620 346408 823605 148724 562062 430036 763792 506031 339112 759006 602021 350682 1934 93116 203826 439529 467231 144744 254240 640175 179853 536435 242083 778642 624199 767973 112208 635448 349691 132389 331343 897997 294077 124089 99344 314930 122937 414800 91731 189174 524535 951774 126510 737909 277166 270076 497033 500344 290223 175229 572157 333644 273591 548514 804480 806961 462644 116956 569492 771631 745190 224961 790906 968641 39184 800169 776467 524557 371271 470395 132005 658008 114995 236589 377486 200812 302270 154402 202202 35415 256983 80123 905900 492287 755685 948643 441773 371562 774879 410990 97612 330091 591520 69158 691810 979193 464455 96674 260568 731604 997590 795820 33014 422035 605784 306035 462315 377104 209506 431625 311383 405146 878657 714017 805389 899300 77977 832187 18642 177774 90991 733330 15344 699581 610559 589691 71714 765502 720766 456066 559955 815950 103090 22502 684151 616718 20929 8732 940169 981476 233781 45898 494154 218500 958011 323454 545261 862943 151908 754944 489116 854915 417947 340286 432298 531009 940332 238524 246779 495723 641875 927419 750642 274189 300283 135632 143357 812870 886536 781291 430264 34932 119008 735499 459369 673303 86256 71053 407021 724188 350602 422645 500415 140573 434128 424685 28253 866942 874918 213779 775237 704830 499545 383947 367028 947352 437460 354117 324251 773843 394798 174136 917873 515982 652406 259379 49817 97269 649617 928908 986281 149472 836375 536150 209246 562753 480997 3468 648136 531908 270348 590283 173801 879853 353453 612668 294370 756880 307682 732087 803438 34538 355828 347813 887158 586086 940191 993984 311408 727072 64971 672309 68824 647746 434329 367882 742448 932831 75448 557256 363080 218636 778421 208357 975661 101163 371524 219414 422407 600751 369537 331435 720762 348023 933845 405061 658849 433265 751632 928922 83259 373680 473601 214984 79148 658725 382197 527407 832552 873360 757770 760400 584174 587416 592250 660485 172950 562169 243153 845329 784706 983473 253831 460865 284712 404853 853537 523259 981155 364068 173351 126316 566229 800069 214274 793355 804094 53549 705965 453629 83974 727517 828823 221362 109329 664243 249811 9045 96108 963179 62263 923050 949330 3202 525752 192786 943884 617261 36847 41672 271688 466621 809919 577371 225426 961691 995502 892982 553476 864431 874154 363480 34268 376524 841812 640267 379824 691317 701551 307005 378262 900248 45853 411219 948530 677623 632985 528974 946087 702273 541679 382649 873660 417735 129099 334560 921070 841580 296289 665293 131773 213647 582907 592095 955329 528751 906816 264422 915650 201650 750193 873649 263231 517310 81750 493966 26812 192955 411449 263878 244551 277987 173268 607929 283769 345855 740140 331917 637885 684979 420521 519075 333680 674811 819332 498558 729817 624821 138850 626639 834296 243834 534907 231408 145616 798912 341637 528307 916108 57717 487249 19744 112756 5533 816992 277153 649963 101911 590291 70721 943251 40741 402479 200346 945470 592934 482515 302331 106285 91189 56403 150659 673680 477445 327009 685787 574133 903665 508120 482480 627241 204038 645860 101902 591916 918369 36412 366604 490248 26444 500498 36383 539810 72810 602206 704031 318115 640333 859189 826104 628050 664273 213403 160629 182101 223952 171898 193933 384608 80188 514258 568744 526420 743464 157000 779342 191140 61239 735634 791689 691185 289714 620760 588679 730912 313705 512468 565992 344957 48814 851774 256540 916654 218129 905200 442321 230606 651296 933706 745675 58514 361146 731715 450611 300941 519981 542788 867180 520487 243291 200399 826433 876223 301854 511055 213132 876906 541469 303618 937286 154855 35485 358552 188635 670516 955839 467830 187708 916368 167466 116992 894 946 822 824 79 108 828 875 450 529 506 534 629 651 746 844 32 122 367 453 77 117 167 193 956 988 36 53 884 971 866 959 352 402 944 959 282 291 581 609 462 467 489 563 292 327 552 620 876 947 851 872 646 663 18 34 622 677 281 367 470 554 539 624 80 103 614 651 319 386 681 744 858 947 578 597 59 113 334 384 363 371 386 434 946 975 879 941 818 913 73 125 936 952 717 789 177 265 501 507 945 994 359 380 623 633 58 136 328 348 999 1000 926 982 179 219 328 409 818 867 33 54 772 840 282 305 27 36 284 327 369 423 514 601 55 152 87 172 213 307 293 298 555 565 392 450 959 994 717 757 537 594 673 738 264 319 755 799 550 590 302 323 357 434 387 405 384 415 408 484 798 879 409 452 345 404 40 67 910 950 481 552 836 852 661 701 899 948 927 960 839 882 8 65 252 262 609 657 576 653