1000 655
938026496 312194315 569959542 69171072 179646339 257160306 455355354 483771773 168808992 318106355 911091374 415671859 168376114 93124619 610556538 14273542 577963099 877612649 623150178 78111746 58614381 292824581 289322328 664045377 353670911 844504430 923161038 321262736 608593034 652068499 807821697 472131295 496023688 51013031 397305531 408363001 483599092 29848051 787163836 964190299 91006960 762183799 953678241 339292329 603556763 234740434 186222249 400327175 43763269 316164457 128087436 370794416 107103804 918714427 402644674 404525146 691990567 741399490 250182533 156813022 385049295 533681077 564195864 493733963 813463003 591231948 607675210 679887493 185208306 861019442 244183451 229967247 371409534 381534111 487052205 57182787 884205919 624181281 246664741 934759913 927681943 396197105 773458861 971751083 319513325 597875244 966800632 211246710 368785596 529529022 679433181 640045541 936553767 666272830 789213395 638041809 886506780 189613974 161669228 208310582 643521098 241463056 79907702 732993916 979953932 499354525 698278699 671255580 104226414 799363405 792999884 564069524 462307869 471141041 79517846 402515092 804368695 536262875 35254656 149578481 795331091 786445506 574221013 912759241 2706045 812365040 445335198 821895567 610583839 829401419 205120331 175649118 236123924 995812733 64723555 657185791 669733948 420927067 194514229 888023854 861089210 582351274 758521858 993624511 92960772 752073696 557672620 367510711 412509020 742562223 778725676 730109972 662190876 312990779 78154697 884175241 981655988 140764918 256928169 365273514 255559551 636274191 304790441 479139114 976055804 678155892 803781715 997353683 86051547 77996638 417983157 758968856 855285626 817424511 349223106 282201442 291414025 255156050 639401023 441357621 367673473 393856758 161617973 507819065 483270990 211584202 811696075 493800473 844523974 812752425 615654569 882883388 999120333 666762258 984670829 288130464 238694876 873245115 770920934 421227912 183895430 231807194 411416573 134597314 9963514 961668860 201437838 87979159 223618101 529760462 987762849 202177276 41645276 868280395 945851705 194526692 838191920 736479763 22479375 165115975 136732655 938112246 629030273 663324998 350798531 415120864 341359561 962482507 696471249 524050862 994755575 384073732 332712236 162475501 923043875 721089312 728441728 596332944 846989294 222892846 508838098 249961834 533289891 220382127 546464858 495841868 565139121 47289313 144441111 289247488 207045405 736623945 153724677 621229909 190971248 818596147 664967496 744824958 206500137 21277335 878394509 569569135 119472306 438416727 988740221 361300050 1432157 992381581 843874544 656963372 1990627 251070070 785468391 532866058 727654808 95231930 694540799 745273278 350883321 347651736 627087902 168883373 599405471 162421463 739537562 15228863 710010371 777880253 248231908 728699877 709590346 485025895 312468185 305964757 385500651 391611651 287773639 884088492 739201376 121299767 834672147 29564743 248649818 215724447 514087624 520685636 705621355 7682920 824535295 104264736 727255944 697863987 99183267 448062853 684089190 948638954 905400125 910766567 441980926 276457893 742607738 377715927 961925342 918171730 693965300 579257597 289726739 369721908 452074835 800406704 468706795 924504104 849045003 673493065 968271309 230903576 593200021 819260519 76922227 420526157 949550230 698046575 994022635 486353615 395577237 940864900 825845652 68375243 433878609 155796703 695462771 194568266 41871880 221000506 890687132 235427624 44792313 152850207 220071096 692917549 567749484 218155749 882645152 235453485 272492940 197388263 89320382 398687214 809579257 958593107 359297663 366780217 743612054 297624179 192384440 68599590 232863828 352527536 354065958 232196046 784656747 762927335 938356359 111628299 787210129 143681047 7766096 278510302 808456857 288026826 636428412 846304931 798536110 791283658 572316955 578635633 28646721 288588678 803117093 318878356 76360905 592218278 348249810 739866558 540593163 384098054 285874886 509562030 759718967 888033137 974131994 649790855 462579134 535550132 952763829 71222458 917032929 176015212 818270059 200991585 726854536 623148300 20026536 108112746 901612847 28994873 572589309 360350560 131566380 718859175 691398595 693249357 271889444 792670352 691741615 696248260 80428483 613285576 975053644 486162102 66527315 208498315 867711269 568548055 315892380 636624750 293095621 123743328 394981065 565147335 772559462 97748719 199762124 547076803 447082502 158918890 488801688 119013546 907523211 113100058 554849902 911025314 638653579 598087313 894081535 250158726 333354254 71448880 72247728 536181419 788511545 144802967 758735419 778402939 324305127 496109653 947954787 726448885 833685762 395726600 2806948 702322751 105669024 684614358 464541485 561416207 910296176 845739640 176255346 582473571 668951799 578110412 868014467 307983102 929868144 931506263 656063193 517139575 352842488 391714656 363822749 541642291 762248109 145242133 870837259 265125231 961869375 306681857 759240846 515158771 558793369 695510833 913065391 287202456 942788039 135765994 467599022 559218177 948381492 854649828 603239442 418232085 409023222 475772907 882825486 289208516 419686042 808834125 360352555 120664940 818716582 171088715 975069350 999956615 662917674 682215752 323744199 548052402 835658349 795107945 913897272 996882455 149063887 190874279 309422154 791393039 617084655 342162088 332597085 731232681 618062822 707659729 827219464 998330047 138495878 111872054 624188684 2125396 663377331 747784461 873801313 568776915 712907491 690874125 788994852 753525040 165519993 493506557 132467114 356534523 904506362 770375892 165507654 380129932 370359905 622192268 790167382 893406027 60438904 158391470 520023817 8906160 545903272 256756614 4068762 797471946 393145646 566825637 907169642 946160864 426243724 547874101 913479730 265781385 315747302 765885306 505332590 657550385 843035898 820683356 981450293 667998478 759191354 451949009 343644807 277082674 313933630 55600469 57073989 307936255 202921549 46258478 759730542 430027070 414833720 225799916 156540466 703647613 297584807 220178528 588801245 81431835 956583495 838797274 959427822 60032862 114037670 750958458 236269205 929425327 598914219 107129117 912056469 559667924 981493129 451726712 727121336 798710057 411638117 623480002 872797281 278273438 419332220 1469009 666846982 482867726 489628319 894108879 779470267 905363170 735585434 125296984 390694529 860676969 100813396 34431286 951767085 92349269 918609715 966220816 181877541 386967410 203301345 70783897 787715006 470455352 786764553 46137015 965490500 16370153 997600111 561750230 498360472 211206218 960366515 621912589 815977122 334699265 756371473 132477033 365952675 984401857 850385619 249941410 919111147 61977145 734002813 278836620 646487114 251700054 640399404 299646309 155680408 355674230 219910878 805165184 228943032 59784440 162675509 354532670 477999587 103745550 66919721 982196645 287425255 143971730 807429829 479034942 924841989 480043430 865417816 781178211 317168728 272145871 529303179 737773858 933683122 26338558 566679521 927150437 255229443 98955650 684598071 480829506 633055858 173429714 81673228 368616773 770164756 642020517 90186431 142472177 628557776 289108516 690506744 679182333 593205193 844544549 373275321 592897761 605748141 522984664 552591038 109609015 595202108 146540456 809750761 958191367 825971037 2624858 756744799 484418684 482296570 756342484 355091732 209963025 878282069 459563715 876762348 493061192 813641753 260397158 884356805 878751250 395259692 925156182 534453909 749336850 569890785 8636590 717925671 628925563 782154975 232111865 562191987 267184654 902730964 183803955 224645930 572411428 408678242 446718656 57292118 193564105 981908923 932640927 801324956 239223156 123529743 778738902 333937151 24690902 534316754 183480114 296594578 818866071 117902684 536426557 598720337 646107537 223635898 428898388 632912774 435632126 690864361 125404010 814110937 170992644 446583269 918997073 698305868 457632105 35152068 472455092 630946811 666330771 434552062 14126953 809071270 532694149 987889576 885335556 292430829 417304496 894443717 412603689 105990408 453310255 452383317 855102049 695282389 610001083 863112506 747350907 221212843 718150155 492633442 50859746 975908186 976699625 737274587 706208172 394006958 580125247 497547925 45176580 919651427 918081188 486788903 469556821 58086287 911192386 204697266 418406938 3752188 577305002 480225744 893717925 973405438 460830932 802471739 179531406 41289153 425064912 930865424 381626632 111316374 730863069 22997258 840733632 211596417 11332262 500161232 494815138 77760212 267267038 781355548 164432696 17481481 665705667 218153182 835545644 598401515 544405751 410574589 193794160 460415524 751285327 669986682 521332670 359634201 804638127 240655811 964722825 918223765 419350996 345188096 319002099 478020938 282079508 819958885 690986463 632801659 971877406 620425451 285818954 638817702 462278217 810372279 576330926 525859520 953923596 75854452 247145165 665513034 961632981 164995364 524026089 828706838 728386967 156542625 781340891 956448291 164609226 710351746 974744604 263386083 976120579 207459321 866170049 878256732 843354821 230598129 326264422 411861255 852066461 460318310 888327959 124367899 266526448 735461916 170656225 107671437 756978744 854348820 577735297 531763398 107863199 616685048 399505599 828857707 331999947 336254990 660690814 965144304 420405152 611801837 648676305 124242852 799388071 287770988 707072550 496260952 617535342 684745467 906467733 202161212 247781756 426964135 507556505 107679669 756111659 180543858 224034392 758117229 211693642 609362282 684273046 452242993 780639161 7135001 886364789 66129064 448313685 763567208 716296098 93838210 170949552 771041704 314759249 724168296 632120813 513733934 147883555 358881843 955682387 900231610 127857482 176582987 776764162