1385 456
384241222 687368472 112280805 17038562 655885790 762274499 82396334 681465103 457805961 52836800 137490556 467659867 772109194 794670130 199054120 491211522 325844269 423009046 906992886 185115317 184093520 668721932 653839752 357105914 590951288 565015500 931008720 725322905 231208158 555493691 2575273 1 75676283 573218121 564826162 168784252 706355073 528481111 85021408 905356196 967265494 632157706 652332318 141166072 50903403 346973429 708372411 876288555 928520896 623881583 813076623 613295626 265371248 916593430 273837325 955661830 343454597 225909203 265955382 146684687 15361185 163045174 353698118 73886783 96134573 220083820 669561609 466962533 247038046 235963609 411815530 1165079 640400145 723284451 276025481 606369130 837597975 227537050 933634528 970172236 194919270 322352512 89113596 99882467 488372358 39559949 211184806 112775591 508912256 407555800 868033604 558439165 126071326 688250623 476016659 420174206 166246550 99831486 109390977 463775058 752088180 32101609 188101754 577346058 456107494 419616329 707198853 405106818 541560993 331266565 239892448 648677476 936512736 754855970 77608162 667585654 485609720 30046211 845419195 15927400 116146573 628111700 394741214 953487478 973639242 92093371 788279595 478222210 261492624 813314145 279705260 141278390 365473482 31451981 263243689 828706123 346847122 982519615 703589204 991587875 284111670 928295150 422213545 710150658 431760543 192289356 281345831 522808842 571655396 558285368 424530028 145945931 269469556 255818697 685717305 753418080 580563895 144489939 81982835 527536559 325911466 79430164 793779592 237513316 603354194 264577846 651155172 585336792 301691617 483057619 806741246 634904019 566976133 552687605 153684077 996244506 816133816 742262464 25958632 151827290 440034795 883789243 780119852 34598218 150265156 625024735 20920306 733035299 431081406 119134731 23006136 804509403 557213480 217926716 28086311 823625595 293586195 693977658 520645008 26754688 938098617 671179584 707304143 806030244 185409800 106692488 995006301 182463238 788596911 927161192 49308493 140343931 802387948 395873137 830156894 269671275 778896793 222727351 354766528 219926804 23494454 681735970 49600094 320002658 757800346 88056115 845850596 176417910 260016775 53205243 901566048 820203427 755813450 350514895 621619628 22391773 789888759 940201435 827989268 16882072 322653734 719946973 491683536 442173950 36139727 368741704 280953787 967886455 990550777 345653263 730664377 204521075 645927645 118400198 60777840 362825946 656957120 603397464 526965557 518635904 570844558 137833817 763655464 562159514 999270180 710265678 852854018 871614480 998038287 323790451 916953535 397239915 9025673 996856614 673810982 887265034 670496185 606699838 201020408 890236747 173430640 293853606 606095603 378445845 450857566 856343561 287969746 87205161 713270719 777295609 937716501 49842556 819800485 702819382 68805286 494250119 666050072 343019226 919003895 759940711 511887385 370849504 314568801 511012712 552697708 715129204 133428689 315381038 175621255 158688206 592598809 389398830 728113371 490782980 27802341 763572065 373826235 359870761 618624876 931993051 751912951 60110934 966880194 327058925 879397017 403049144 771416670 294142944 421756787 807828380 548388856 722078066 918363021 503623197 887415869 966113373 817799061 301694464 613661548 782267115 325572737 618099451 604222107 407885161 953299809 792184881 875909289 492928018 886870549 572819629 479570649 820026996 752363079 736626473 429714977 655758172 645688088 599741636 474615740 649001173 288561415 827101813 33385303 456980698 886721370 882030245 574935430 709121426 722608260 710786510 290150864 24909901 39330913 405701561 664009259 803517493 765475353 616191023 402985240 910602323 638318779 830861966 132488139 253645692 368952518 814707530 780002011 83267546 877520124 83518537 143932220 547861754 933914078 900085491 398912124 996341154 102555404 720174557 995690327 373169420 100896954 303333276 933391646 98524433 931270267 206454395 588266090 25404912 470811790 107334143 108042207 284378978 767144254 151643487 707442523 798242873 441025284 173975186 344670042 197069215 624415028 551755379 237690894 513610274 542996089 777397196 962694281 813518312 972044767 457016939 276173822 443945285 290260165 999110957 848337079 963454041 524074196 57148614 75218583 974375859 107888649 651059229 775103719 784377057 578311453 49326346 669779951 345663565 315376106 470006450 192643675 315888860 447865534 750171027 428097160 271440960 449377697 483601564 686018871 541858695 435665013 413594357 83983940 174825944 829273704 192119027 921843981 53197234 892678576 472703921 353174909 263397855 31574629 816476099 942541417 485929328 773698048 92389852 402235374 730497630 681185660 110031145 151322090 873345133 394321054 28925808 692430766 665138919 53734483 977057306 758371241 371777851 16432528 468918853 5425607 198151448 200029385 374748225 102279257 112972063 441193399 786607564 177799742 393553763 61137918 906680377 455752273 953338899 731263 935603873 764659279 666712012 390280808 925294381 670937454 608025160 822369029 182885416 341340974 398705969 406170929 697827990 807939621 445108499 993444097 186449386 436781556 422728827 695841551 688904211 157421402 525175621 334500825 468217602 999209629 17545340 409171672 120650149 227636131 434913057 958730687 296950678 326493293 165814049 776755717 501146202 2065631 527573172 744860423 640629651 274061067 220445564 678536360 604731401 883915861 216085214 931402361 109143678 164768200 820575660 391462254 399918787 409399032 904545049 537098012 659596083 872591236 131290535 990292320 356960929 799701301 944446681 589414370 268845921 423762814 2946242 419380987 252399859 531454820 178555633 156303000 747333032 763484666 379995828 120671251 721985125 305481710 756880529 826211157 99032303 145467002 20094699 769988156 380882120 365311754 438868865 894852843 650918991 481161503 615698983 839642989 144928889 429539296 543831308 767013375 6826054 619761264 664179349 794577535 890431709 319721810 786581079 428167485 576459786 409066553 152014469 924744951 377447530 293286613 295420084 67119573 909391908 329870796 720412779 634936794 455413143 808548039 172634103 983761358 75048937 750981720 636392896 725764289 612280740 428529792 771023799 233860530 865582251 451848492 426704032 758636772 492073909 772398933 842099324 40591482 241298738 174003991 970669059 119193243 504641116 797695266 270721366 989445526 335323133 182391519 536611290 83062687 258289227 178024252 850023230 932087042 902674047 762868643 401162387 232451701 255165562 68648956 400409072 848437902 675828477 901339539 788753388 645721181 594408849 128231819 346301774 770184468 631601312 778895396 14211083 778128608 641185113 600531218 733746205 838493798 583376710 754608727 925612551 548821571 631190504 694254368 320968307 564762699 384743315 217311052 199341639 790930392 304249974 314329126 830563895 380506475 961862594 489730543 922164627 258583162 388672802 880673354 54284693 423967363 364792762 272737060 571618984 780852388 926603180 983210242 20348708 281267134 97756769 221960734 1172869 756537484 117572900 596325558 3340722 72712001 325047755 408617355 356314104 345670897 56157901 241154739 820366756 548187114 444248471 845328993 443998076 178611039 600116950 528267279 759361871 24588271 943437777 73644761 762198275 790845040 203552339 159135510 753001995 431899300 349718373 935697473 737068146 18054927 245281969 803692827 960867376 741813935 810186238 517871105 51214741 719674834 34369868 735585174 155598442 989256245 66676589 297367045 625841221 960454652 45248901 157198309 104827855 786645946 819024599 657964215 30220644 480443681 535342631 524383658 330284779 520108975 429718403 283130740 512490180 726717590 25212928 318046005 11748798 181077690 576763822 364566333 811636508 486633094 817051408 418548384 517748150 562565666 414468793 634252306 575661384 56151284 887975632 639401215 275166637 435536331 953129261 790697475 728598010 444081323 377968734 251858766 30370138 693278598 6946325 472414314 292069392 970277754 136679968 388234205 219961544 973339326 484508840 644544710 527790591 948542852 964667996 574645858 659861193 308263642 784090614 935127574 696309608 77901461 130222950 474000682 178927253 247083509 357985107 446927736 463099723 85366471 133681320 436522139 724477374 978508626 875449715 594341463 839788647 734343567 37054625 839471215 826055349 835133822 545030243 77328695 56167147 472473907 15773055 799869829 229997472 473379948 614403469 148645063 670049090 899657575 890553613 56922653 178996933 175008072 450859207 150958230 832318654 26907648 576049645 292149452 435181282 898001412 986246393 719979402 228904361 959499813 871254008 793661576 732915941 156579765 131152110 18469416 248318606 497396449 702111881 418880839 76748303 480038547 672005800 945480982 434467731 360830715 293641369 337803738 437460160 290894220 529910534 201446657 865530131 800911438 909577339 766777848 484696178 868781078 921653003 233321087 292441038 896908916 549483122 155222975 418082952 182974789 807979106 131430003 946296360 193982323 354290659 936142530 615616882 501465516 534160574 18878696 512204791 840888295 590775909 167464377 52085357 853128780 210278749 618039251 248150148 278973522 413044417 975502677 527248699 52059647 822133320 995408283 895919633 996678601 298319853 246078057 737441448 235444484 905140595 780774843 163265007 739786718 41928215 278239005 842246769 392622115 403744468 394923569 28976363 572429293 668824038 770566400 325338265 838172280 467174096 687752151 493904534 259493878 613080130 975784934 694260532 806220594 233942435 273502934 404779029 489608443 235184260 952877908 224596845 97435279 345910032 502232794 249598599 413541626 896897644 565534578 775314293 296397289 278927184 365677151 435314195 677502308 240181799 681026280 244983107 50040687 529476776 679545681 361096270 918998255 42556788 676804123 138558325 1401594 320958626 990126658 80599084 606497146 922333541 434457992 876054451 240804591 568827985 303974542 688666811 341571858 515064587 921684544 226082256 855378912 278217067 967009148 10830430 475930842 635065024 80948380 154201438 204683074 345666036 265768240 347857461 250518550 398721715 838760691 725114033 987676988 308419740 178148417 454567204 810634053 534586095 907159105 789232850 597323673 429490926 635079173 641628330 822500535 587293562 156803838 603461627 965304158 794577967 731129515 980377238 645904087 395452984 392884870 643249269 555377369 786927188 842431884 98482717 766785735 242939114 769353313 866776815 607042593 254330299 13075833 328217739 313480334 771095274 503149922 13322541 942571232 539737874 923932722 157951441 4931916 832632637 797630821 184734489 864971460 69026444 600442797 667819611 918091322 379029051 499305490 647736962 700598488 110794548 138727499 92838450 19654009 134140171 437617537 708002015 231738867 830431266 222309560 717801620 427702947 811832946 472423200 229854344 695650913 139033221 468913368 867045626 791721085 100833512 70052477 436390499 823668867 595671294 621586554 152113365 804228964 281661461 748468029 91315133 938527077 916798913 165935303 1000000000 967127601 2601871 426515351 902520904 707222818 631654112 872606848 650099640 314418091 8371645 131279513 519381494 574525152 912197886 14239542 407772227 62955212 445243657 927076832 45159416 587180318 451279278 506174674 557373424 166753208 325873624 829221456 879417997 108799038 370473872 812858220 908636512 592548866 509087516 659348008 620284537 101247631 487730979 330400880 321193420 915486556 679853856 690743286 509805132 630894888 663339920 782016759 167685249 854761552 456417848 901276711 836166559 573969066 897962694 160327024 209359742 198918777 310161904 706539109 686057841 981862864 146090612 167229141 651589406 479213312 416242246 368976977 944402818 311134590 834640127 15491564 814102855 531871429 483347702 438228103 276494866 533837521 345319311 920520113 58833669 827482864 363928656 414760613 536295860 73851614 66945231 973370206 574823527 257665088 44746242 736087764 545000714 477833252 791634826 104525603 871144919 194845159 521464248 896733685 875329223 395161143 278828983 69758569 882170111 163461397 309210316 907085305 466330711 638071800 643302840 493364710 577347117 988914793 42912264 489969134 326637776 591530762 764848321 217743260 446008991 779065453 29754490 966122224 574698935 246342129 332886615 491811753 349935025 920171422 348438642 983248259 565266234 206341181 704216848 318073211 43633743 568033914 229382470 204009262 49953015 910939973 727472209 417163775 548149928 147299441 60192030 394277357 851257912 418587737 917731696 300959725 85864425 794507257 431048632 989683160 254676484 729822233 461479018 334038394 931095424 167369021 895380635 933432906 399458002 484839875 233502482 824041003 295488177 859563144 530152279 787229199 362975880 276495920 474400374 888746491 691517750 855680658 752081954 688432102 109902764 472688312 888457141 899359663 90531550 348821449 504298380 556638524 174693857 452274853 235096587 473913604 664895198 96056666 369858241 78640026 464921971 236923400 513763071 302673417 788538547 987261911 504555016 691236062 904406532 597525365 86996889 218972115 321092607 353292418 580937251 178415503 341348893 647935951 172840615 373475159 13125952 69521590 539258474 383899125 697076008 509820724 227404171 698529046 816714630 370454032 830940489 257692580 650321325 504999827 407132695 145190395 921970392 577726024 369313633 495291952 184038727 716096235 189289098 928295 134696599 186884888 270568989 723016941 99792914 55592400 375738024 247708786 260154155 442051343 659380222 672748979 476153658 25378100 36145653 576969430 712588115 616762982