1000 987
704054157 327411404 773241029 703430423 229246189 335303406 855291349 104990738 490618498 392692308 232824295 551569960 966414202 123016754 922592213 818272776 716537416 497363116 540415742 234382957 367095695 592759576 882271420 793259302 773478504 327624346 767235151 701476326 506838749 427859185 40950940 964051170 558200943 770940088 847941876 356350905 507255128 17747960 741906724 657519894 472758746 197872159 559714575 121879183 46139535 931776450 310380098 999948965 898185813 269888826 308751451 301768554 453561679 164988937 569677061 457684772 765463191 865843759 248131707 701505957 72677875 846331554 859739660 228481657 714186293 730456064 771381052 918526629 170819493 281416118 472443998 690653548 455957840 400657414 503372911 290226643 918292804 969623463 991687778 348633233 31645766 107849683 184333632 388589204 840557194 447678295 87571777 752210824 975512184 949914268 704412214 817056990 11392057 930941314 698001169 475060134 308619959 719316568 501451172 309049591 139707520 69587108 603512042 365473529 213405323 697915229 282825352 274622106 696057958 861405898 198810055 790772849 288789942 194042553 86885675 330836763 600391707 825302622 239892029 243937788 881548838 331602145 591367324 343066933 221756240 801042031 7287203 37030269 116741904 73786982 230530578 578451545 552512051 397111992 193048535 632885322 682703033 266461277 88777298 909582681 399731859 760941886 236587848 67746216 802861076 783905483 127952893 969582376 120600489 942435622 781520652 735483802 351786480 123593752 787240861 576076765 664693768 284232735 88210487 970212939 971049166 717485723 930467198 610765586 801847424 695088038 838373569 437979126 620519982 372736746 920056304 935799583 415787517 331927133 893424161 41436135 458274298 400840155 781781035 790340353 475599698 648468355 697216489 962170774 432638465 106201869 381197434 911546303 652029181 368849190 781776850 474002590 81454999 428482155 264090054 116452278 588644857 247796458 293887426 742271567 581017399 23007535 993394138 133887774 885102374 25210168 577671519 857388065 68300545 617324829 822861758 169928663 951632646 768772228 127784029 966800596 618990143 934560376 148248117 921547549 111320212 7810215 366949463 589013492 252957114 256632617 735985511 564647219 226198338 318030284 846312672 153666547 240554895 444493722 659417836 495096327 174757496 989765504 581856623 42387885 503802104 301155200 571380572 851893844 384938642 659695495 930305725 826683034 310507794 660290915 908126429 759536306 747099586 492921754 366389044 204877695 458597278 810003861 872797148 567820656 180470547 139505196 154268002 804894030 567378597 958585904 981676919 346163872 499874074 293512251 615205716 81775179 625814633 664491229 689974072 958961619 673802576 135992689 875281924 485159635 432996183 98238183 947003408 34109902 778230255 664501050 274224264 867687180 289341923 337570538 398577640 875765175 970847265 117053101 23410232 237960686 80294350 901606731 434936234 508509896 596683304 608192380 940140603 38018232 794431085 128389911 38173809 55790819 97138520 905000744 154363448 134794964 796600609 849672831 330764994 351034695 798933696 800597497 4703260 365043549 560704815 267684037 629439699 93660702 516482166 280706587 821486456 471479721 375876943 817508797 607936805 452514955 115077403 971435575 766500771 541633013 126733679 24945628 756821008 415367298 317166558 688899113 14645891 234291648 449031204 698629950 715591541 503697302 901185741 25737776 762539619 774352947 549331996 560373704 356870109 82493503 558305362 475214032 885022259 287292879 862379117 879681548 9687631 284927055 673524948 941687074 153131729 546132749 803762929 323613705 845012852 813545015 863507661 697400378 290593452 413962492 649510731 629618302 96495190 778584262 974428045 851557792 409421329 816412717 545016071 166077092 503863289 828389552 635967976 58629065 78158121 200170685 89928840 622926722 77749088 114692529 184065699 603347599 402707216 307965690 396766762 429466585 311375428 315151500 768236246 70173568 844481298 500758756 93298958 963599446 128744134 611783350 18285248 300031877 136038248 956149836 363702729 389237254 609991526 697517735 479584842 634112802 972397688 952910851 10327915 914602692 677775139 148004062 178085177 85685877 427875708 809642330 729790154 904943215 57718984 492973604 82503468 690761276 764355144 69788284 406574734 219804392 884703731 149376195 464110861 601160582 687239742 197539894 730648277 59846316 502406240 302207277 873880991 677212427 609035799 577863724 164044595 330724967 461568425 833478881 51692072 276269108 993969266 260547644 57207560 559947415 275661222 478215639 674166282 445972662 255895533 155785618 831088634 504646196 284832681 259018915 585730090 392179882 812430945 733570448 814291672 936862826 894237056 773862961 971054209 405633890 736125878 593033135 589414137 746497813 803799326 414221055 233644746 360248160 391970234 135243293 910427570 736260797 989551073 838508589 966681106 316584414 368658412 783507770 174897555 610213057 285921930 784083049 51561982 411337390 7813450 747576369 35551996 408509119 671503514 88757991 144856099 550578916 476770195 454328727 421017664 252879884 917091978 892113329 937742714 382853304 826331912 39126113 781915639 382135735 837589944 424509807 930104078 861637719 566213055 799183207 447610130 199966587 836478418 839029230 433798282 247927231 285544366 341934146 492226781 76818459 361331449 55356315 579350881 680860120 501076388 923341082 533562976 493016857 41508546 844093713 238167464 793751248 330908639 664678725 102182508 978228934 598496742 802187922 169072312 274844395 144974521 789014244 487429697 692661650 436965184 399520447 637076363 76797464 970031031 214359531 40490051 797237892 491881301 248485283 815045890 997857987 348056356 693988140 408208401 477222482 112441138 570436689 528084710 610872728 50903679 968944819 302147587 161741197 667448347 272395801 749862838 709591046 267839340 239857981 540191676 871297161 523606662 346534174 731185590 180839405 389584633 47620762 326893998 595595046 119543651 825282187 440877268 273793110 320442232 917539488 195946098 757734272 162976892 61300682 329836259 572632998 791516493 567440942 784640746 202372302 978630462 334544380 419684820 458278893 887166358 48077816 933676459 149776411 362349984 164004388 488447135 379235757 339502669 747357462 107424518 831303659 402120628 162849041 963374420 751906032 822314845 670709959 761834647 890687398 100926339 968791257 10792008 124460613 139967074 80673862 388888874 799730124 921085727 162170876 133360273 194574521 572483206 882035922 535800505 938964897 160854691 318471241 792675380 842168106 34863354 858856910 78734725 605390482 845811608 566088446 346081330 575838402 984079935 301289194 236371935 618867035 900478876 243580271 573816320 177632288 393385159 412950450 769357692 705780422 839849875 621427687 312607876 964882082 476890609 646455908 675676659 141314052 698087313 161218218 300341182 93067145 92704376 191173767 391105013 597950906 344705285 838286481 89617288 893867656 393188627 400043890 571156671 558583027 996337300 809199592 757008809 312070524 330591455 595669004 415783573 174082513 118157907 476540337 804685013 173072258 565809188 462426392 473192561 396819696 454704843 433264828 232557227 243712228 273839144 136043344 323569209 275665333 1782019 239580038 541468337 734296199 989912585 716975078 328217306 584482991 477678808 91333798 879823579 566261855 534533108 79237025 595224101 18173024 358156851 352596115 475402576 240544919 518700477 594647679 762410774 928642483 872970666 719852030 663642305 767360861 449867499 950893108 844798233 634091086 223001517 577730947 351327919 601867976 288331176 865805254 426942362 388099034 744473560 795336230 167673818 652256929 884878346 304571549 559391761 13688410 422215036 209919991 131248925 699988766 613744074 579690310 317621682 274594702 730720815 434302467 976230427 661148771 186341867 127086147 36842787 432279586 202642575 416624217 564664854 542601023 131020993 521913679 371044958 367726685 194778295 762733631 728415310 67229045 3241867 35538475 40150335 420259338 731674384 896694247 968590313 277569349 590527801 172309331 74133299 928208394 797416969 168223261 26838179 374840541 199990004 729015508 474124494 260924012 598516456 229849526 402340761 397667233 638337704 787364817 522327111 910983348 907293220 31292524 999426434 165108128 730193750 958601291 87168998 592791293 329888139 551410268 521694172 813543679 262258440 39783298 873724752 13836257 196474029 967494053 204466732 828570683 904967644 747381778 669343122 155700773 616694256 476603924 706753224 937293541 215388447 933599598 586365951 9247102 689365312 752491414 256325197 6237768 840272101 984301728 554416845 416967199 502379717 973518753 861470855 367746810 187342059 293187296 19240442 316291961 770538844 730679072 221392158 199672839 113432354 864057693 253333823 590572694 157421453 969911027 265060028 987084910 89010155 185181999 481267000 955782051 694147391 46538485 906372988 27863722 745422044 943864583 108718548 962396734 535150634 147247675 79322147 442415815 572778769 494092527 528350277 860281241 6517468 627917239 753813275 774566426 641425058 485096843 453755055 648413698 918966707 735409363 452604773 737881286 461103140 1737833 162696276 99908070 664905230 363660445 168512535 61197450 309637568 382989698 699191212 389566853 306057920 920233538 602821538 567071851 976711098 706351287 43118239 887198686 394207894 442129320 899734866 1962145 589868127 285336022 941775092 814158701 950465010 901841164 827428258 351509583 347919341 293991258 26721118 924505205 953805863 351073735 204080585 652245190 242581776 280309237 665904591 97918796 702182473 501236308 959018364 923231838 595266524 618640752 440329957 208826627 124381334 682429574 857410337 768361151 44264855 320760557 852229113 559209400 336313959 681953130 908029342 160353146 850622830 964100941