1844 260
137106351 767951605 850291111 317986650 20244047 878010125 559884505 496334600 870124785 568570353 248403407 158224487 739118057 697906542 678339555 651657230 569567656 31727601 797623888 558064239 562872417 782140730 447664459 447900720 662268 823414765 635398649 459354185 990409765 642908886 844560319 413440692 901193711 911957609 691281772 353837294 37802675 449023124 25861809 916931513 242390280 159947491 620772692 139691991 949379146 779348069 410594338 943268168 329564470 684992616 179362849 456354838 779466166 937483678 476144232 981639440 102166175 206548891 321886104 807003822 162337911 233725631 952704450 418801860 806992885 639601940 442143931 243299700 222364033 303381995 759347006 113133420 709498170 322351271 331230880 512809576 931324772 346071250 978843810 608489361 198017396 655897567 580540658 596041126 152863223 29769416 582892892 592723048 505136110 579435450 469832498 391321071 137154723 929272867 96147882 142822654 691319209 847605104 943261778 435481743 514448275 706868277 798046626 180184581 378394280 921938199 660480135 755882207 796654979 765284318 979029015 999336435 142768451 391741526 807205960 816218058 55766035 589443215 770577794 593112913 421254964 272435172 39464742 948754718 37106832 606723664 730444691 511719723 392074672 457180356 920295294 921688801 199121060 203855552 412044219 808042046 280940324 55605901 514198591 343104633 113884106 330231026 788965224 834527112 481365002 916450961 323712771 95281994 37355090 855833642 998347349 887128807 93465863 999365542 2585203 902369383 412756812 279440685 788227208 614321502 496093376 116348647 528134223 503817671 158268412 388596357 613765009 840423603 331129647 757698656 389870083 915941532 20274705 236247575 758183616 773198012 26438861 953502409 984218161 723538063 790330762 54774846 622165324 846424472 518507939 909390101 765731119 890014357 900691254 567954172 519357692 334609611 720619726 911332350 368945779 310808617 947294980 862977493 149110362 460020447 392421728 788709724 850630190 490503566 326475540 611476898 946316596 427551869 589721937 181947749 740695953 627594683 380415749 617813203 110173312 33839876 368955246 895863761 102612156 888679846 995200500 557738205 154659423 599090405 775632238 208344504 162809750 289423758 325830749 441061804 848333707 235165608 311847089 300016040 261227255 308750325 905658046 909372383 300571430 1000000000 550045360 489406507 814732836 119694197 531304702 636277100 129178850 547485104 845161921 737826012 951414135 393492094 594078233 757435489 78123325 637033014 371281504 359855978 306717351 249847067 779508519 404709380 97132687 9447490 806615487 687197789 384290152 538995409 166327336 875237952 280643241 355308579 544322193 936174158 405934018 491611955 184759165 756220299 428968706 564634904 216776022 766521280 255049495 226138957 813545304 801084275 662350918 806921294 685049418 177573460 183397131 458082927 642981622 452946854 297605850 601141477 656521505 676626086 861315545 686659804 235723993 438920625 556085964 351455706 307729716 332938423 375449519 733016568 356751151 789856366 894370499 536823631 601140379 690179872 547733975 129954415 928984396 429472122 653044413 547944660 24121998 345826453 73402885 563675479 18518738 551525443 233951776 608552185 929757878 637635988 399086119 631717264 462251326 404641292 759839359 40374006 849109113 141848929 465747304 322229885 977453145 650636605 966391233 272017601 442503181 978725147 312564306 566623936 427332298 831808835 219456255 324230061 456950515 529714878 668191025 3423394 304354550 504951501 27530195 779859090 565863902 860845632 252318840 205464207 715861415 222460360 247885244 112084791 440150699 646930203 313279211 653479377 824117274 912270666 494822228 942467132 220722456 847162869 800435780 544544321 669312437 531073553 641903701 914764178 535284855 133596309 844926435 465614762 585903021 786243781 224946693 132803325 851839961 190575655 541405193 327909692 360095735 994173405 397271024 823263062 150270396 192416412 678318445 209718503 454864633 509720757 42773587 375666619 77062911 510650665 427242582 479076804 675773450 566593892 255145694 413046963 398946688 248947952 997513338 283663425 839673875 676772506 437281950 985758759 637045289 442989441 102281217 925858732 528501215 377689676 731805031 408514803 613864791 663762344 759422473 756823958 720253495 332199203 456566218 962019098 667376875 874641637 109228479 996941546 172775828 16127368 753048249 236211402 429324133 343466573 436176686 141126799 340573996 474184344 782652551 338554617 848238003 77441787 484798861 826793237 278659747 193691139 566338907 207666297 220850801 45804426 773954437 541023862 198490343 493657557 667664648 8758305 529075428 479150665 384774059 914626336 513528826 715967761 683614342 595077558 64641061 922333882 196893217 468842946 809637557 874730367 312120199 683455703 287314957 440755098 908243715 132910868 662631492 148328394 923595754 171928117 986841369 546537201 672422881 307377588 46393535 40412650 992397474 376971224 123365009 765192563 594575673 361317728 635114503 133523428 455261001 365212043 17910926 694652211 599173130 5037924 537247110 635877495 896873795 36097345 571628024 11754334 340390262 243281291 969885872 916492944 669482161 252013493 551511662 787137933 113684864 948216103 668017039 788012363 730596029 104735497 286056259 423218108 799044197 338510324 26133283 906545075 704773756 783778991 524124674 128580455 305614898 762863065 304844512 221063723 218834966 141249793 951776843 222946022 174311278 774070603 117941866 844218447 942574856 164420535 448863055 567208827 401418458 653100882 830765417 411252459 945957064 378367402 799555018 547185020 328898717 819410055 863782063 940875004 499124599 929048513 184040878 845111260 221624353 690630371 131338821 510692801 51476907 381299878 171623354 919847433 313666534 52194724 859899057 675738218 563677399 806853442 764558043 310321157 943252686 137669981 565179553 856346704 92215742 543414054 972224763 351084160 251640960 944991679 624126438 186779113 324187739 466649269 159393686 747967032 931379453 44279638 926637228 11753012 320682615 969799581 254582153 967111403 887822942 442100501 617291709 730607052 103352631 937324387 727487014 927301341 358493279 849245836 417116622 131158272 212355553 999972911 945753763 724504584 699876679 100930242 714822676 953063389 472250386 824046847 316882684 174297223 193577355 507492800 471807916 618200071 51152670 409134525 481986714 218435587 154947184 258225440 507062082 6694826 605052702 430663565 413805724 112518400 192274532 474591486 57145331 215560469 459827428 84558321 10845486 767752419 784284075 590755111 889107426 97360539 221857259 869385675 445117901 696549611 737605967 879040925 204594831 48200812 617595714 440889077 403581195 605056450 312701170 156096531 598556740 248329842 558351143 919125924 792891701 320945065 478861402 262155586 834410325 82008169 947044795 223129535 963280262 413676522 711375343 733908606 902127617 540637324 659216424 524625392 852577414 223699434 701920552 874885461 452879580 663555657 543371403 816606816 452408346 877033848 140871332 761993616 146258001 327739221 514214397 676853557 420936536 832442227 743798957 598899206 738806392 647231806 181797394 437190899 116675035 451656165 722746618 250725947 28958143 598109872 914100024 731421801 969515820 47066473 734147376 847881035 995366333 248566205 5869771 20868169 588447884 764317799 417388331 760972159 391827620 868189769 479080828 415450114 100222639 961608911 348943881 167963763 313767409 880719755 621775494 740117828 840719941 36501587 743857125 260599996 172238014 637516910 935104649 65614918 846650446 436474155 528447328 371628524 241604857 486368461 970117921 174861786 193849707 427081831 520409458 723538169 659111006 909533282 909109656 810599093 134973532 780916424 722556324 530022800 299832865 452003343 968624393 203535552 491017906 611269667 87024278 299822093 156462819 449606241 415451964 576847802 22049641 196327181 798929892 190525312 507066075 345353776 140123382 122592179 114864445 757191896 427544813 876222451 58946945 971114294 602935502 599631954 410244412 394967947 916210809 563876266 861197874 356908908 325618529 992205038 616175444 150705070 623351520 918157423 679483626 443830195 491819316 218743669 116558479 865354837 716907545 226859036 660474738 93765264 400860351 130399213 481655825 499896356 445425314 692232634 7455268 140104472 691308311 336753251 346483296 562330602 29809164 706452981 121981406 167431409 903037261 572709665 361670239 345537260 815554051 899639923 87229293 386900292 33880469 470815433 432601404 84077447 80327503 536016911 673418385 102152443 14376862 734826915 797896935 9765840 383550974 570563150 619022075 541075092 746791158 247539855 29554097 722672135 527388585 65286515 126749309 256195730 900990799 74724788 305545157 540883502 810797989 337790136 178106622 305055070 685163936 739980798 58456683 331759834 513028182 496902642 545411471 369690888 480812955 569261512 506755732 145821947 563219589 554605091 303268299 100565837 349044790 699202623 616345239 672064758 950883127 79406550 918931763 247168734 449060918 670528164 612219135 763855018 405841431 430163896 316047008 709261855 835347613 173452884 561601238 147978187 161314192 200317895 412399360 282713456 270672162 952407856 238381379 425081836 144519576 951510882 485458218 249598462 981218728 199035542 763770243 135559633 64433907 139126665 404768776 373445879 917930372 886434267 851253409 15827707 714837314 522386469 579115928 989835393 469539052 911023855 889062129 510593823 150481837 15125244 352009525 471673270 973229843 891328810 878308363 481833106 813442717 546717390 672183660 193241419 619614558 396326805 682976068 58404750 342666818 554772098 157161315 283896930 722531621 228964247 654293203 104070308 644715348 364311488 700811227 819508772 532632673 306636193 372781005 955994813 118164577 257976496 388155919 125091849 321595258 447093572 288170026 889324332 564556327 798600327 24928849 964541446 375038426 499470009 956297383 589796205 438537155 498040776 412560167 689799557 956686355 748590040 154363486 761835080 789852742 264164965 477945181 143198340 771341102 833885694 623724278 2332263 466350781 459082273 752493542 546862809 834082551 4110525 621977737 370284255 172099040 508747015 377220428 132176119 34050927 828738794 755763740 759651339 763893229 626406292 854660710 157849908 248174039 953487672 173606348 947309921 671540195 549349268 715922858 263949004 594993186 545529992 803977303 386694617 643745575 836612503 844153276 442884317 536356977 474232149 891115941 215434415 158292628 391143359 40864938 928916724 844445007 240032465 729880287 51253641 374856412 895481526 860971884 919155585 94087527 225195252 646121924 716010697 819040149 500894479 251108408 806658281 862345623 707982894 702593389 661424305 144500422 602623902 776919179 539439200 402149815 650494510 811658357 313815517 687699853 785396196 71232935 988998188 15246737 185015066 154454668 499926383 621175452 141564154 59199294 866151682 401364595 380531039 303994629 568390388 345718519 489768269 559486977 160901689 818415630 689789242 81825083 174440313 674734032 386874468 368048913 18374857 254638030 805623479 928019801 434733588 48969867 419230194 817222089 38635823 49288653 656535374 993461633 617119416 866940224 862927469 927540824 167925714 988948519 680298581 154906336 382291887 338721489 202263890 399138617 735111847 334865072 382078032 62157260 96308038 302234971 464854671 291206629 596615977 506024881 227104458 375644040 634311644 198997865 877205866 321950603 734205446 930720059 158977068 124508050 62255214 366732685 992867303 919449843 260372360 547035991 240049292 109517758 393496214 423529499 695981698 662501679 659725403 172239645 565705729 987799652 60353934 33341736 740796241 963060815 799181433 136083189 831346306 868669954 923652007 757646279 620189624 443408999 702580209 597427123 525376416 54457819 215025174 837838104 282597110 478946479 885048321 733407051 734412215 440809627 407307231 710172054 590767215 976512475 437223150 696107763 11106169 389649414 954783639 177384353 806173992 312601638 911334069 673745157 773794735 26313313 561126321 912004584 838059070 664677681 536389753 788920841 13183345 982651249 576234439 733372820 962970883 980848113 625966444 573413570 213521062 668439391 88680665 889953183 722827652 48403491 70761118 670134428 135275631 863697741 849879124 540991104 837474353 24563650 689093039 544943006 23803102 537674320 254359784 471928986 172032213 968822307 609871596 140236456 330803178 120590791 764573560 312805348 914067088 809023013 143893606 781485036 656731018 588236344 412349350 778173922 121770794 581808911 179758929 942419439 45193852 796729386 459352209 312137610 875170821 990459685 497398048 149238355 117557364 824032253 866672410 878683549 720452677 438422765 395920513 660825993 497854857 242680439 278499140 981713834 109451291 380558537 771469404 46684106 146781796 312860101 795507994 900278334 640376484 296282929 485115478 151465979 209879709 953814135 448463743 184399227 669154225 916830949 77048295 156050146 202895652 231483518 636088123 502766746 981581166 935704921 89850781 949504170 436161695 663205110 298152100 112220869 47342694 83170794 832285433 875670120 704815624 257092769 709923931 618708477 774305386 197558391 432250023 245065841 381559747 407524573 274388559 481429 156733195 193049936 730983579 85630804 882325808 384939460 935391621 374800342 2562121 788333192 240277863 996092439 137377229 505787330 826838612 815491980 615290646 722982510 899195153 928304078 825645115 227744264 248505638 267371627 54302477 731255457 566150929 19437627 482431471 590941590 799910626 345616517 645908365 336556266 76510521 621972323 616867388 323897243 1743183 455275838 403869513 302554222 315584851 710118817 395320494 297537261 247883048 365684768 353224041 712568453 481399545 945673150 520768150 46173649 876298943 508196076 249069567 772695543 835380584 102741987 40157026 372982080 84632437 528917076 616599693 100264822 50359606 335445048 60236736 887050420 619924433 894348052 230066297 348908018 897015556 759025739 509972411 358137577 449099760 205904018 619612864 830448431 353846431 30735091 281807122 68830812 840686749 694115144 456411950 553130122 776983585 237394236 69901528 638047562 46011634 261340839 654445024 920746371 948546338 200990766 687534321 268621716 157738863 992850780 714411858 11910349 393771194 652377740 814923324 890955867 501044511 358096885 722879849 473834884 233911973 57681413 450681336 126822332 111538640 942718259 674959305 223873925 831787627 29868650 263863825 762588282 19634025 748632288 947650657 972739764 992202717 291126108 457381383 211847167 616257033 593885333 763045101 789214666 859860709 894020665 420135211 94076563 366111577 733253107 513452047 143304210 341656144 278135984 52800943 639152692 148186826 833947597 974930533 18542455 779155654 461494798 139576672 614675317 774757238 480308148 777329549 987509646 10036027 901557246 255335390 865292347 39852398 734890890 707726939 960584004 426514710 560903605 839691209 931535480 993241059 853683068 434435692 320642665 542465758 376986387 3905883 487945913 348949268 775829939 332463919 147452690 689324891 198761303 762597797 702427103 166560228 140014808 137234973 513541616 42394260 637213867 165737872 215780513 827318035 330795902 226480028 95279150 300474973 545832350 848110662 710369922 425079206 200284477 170000540 834807952 889250843 714401626 70906612 413057170 232310828 212818368 748226405 974374358 675152680 790302105 521035920 505443473 581348481 99890565 685833086 947008442 911066950 324080873 365150755 243994496 441920194 665099258 476779106 754922811 699117888 693748474 144829495 348724382 978032446 711113348 562569043 644869741 601343432 125027138 615658030 324963017 971229394 758783002 141705316 865857444 581520160 627584301 512103957 274743308 760714874 764377642 416503511 117412973 694071462 686588577 215081671 277693553 177102849 861488896 752857613 458463213 579615658 509378218 791202543 770922067 553303595 577380201 374072609 11327049 870979525 542609170 146758389 451100826 640941246 986523926 354442985 274583293 260934794 870862246 299003600 398677193 89660651 514888037 226315975 396097192 699898070 580941541 882021797 626268013 385825944 819481710 171077401 48054010 362879404 104998334 434731009 424007198 292682896 241117554 368135361 575757610 146591790 362850967 918778622 148148848 341078337 209836570 33808806 902333523 892447738 257500835 274445033 607041478 447145909 741385286 803400406 323943003 826252913 504328037 879875096 27874045 82669034 786914198 550965389 591718088 597156863 824544516 759593231 50442444 358949678 897713925 221400605 146735259 996959352 964287667 806496173 179698483 224665323 390912114 813927932 807863653 289480079 232481936 976188143 110093329 418457906 182183125 96297384 754770847 481400430 804516969 590911840 514188305 569172113 545990567 75204311 189854304 323793247 95976569 319742863 45803217 621416282 677963082 652347301 619514023 444347964 183370532 852763306 244744561 170928414 925267595 595282877 102886730 281826022 622412339 716996134 313870297 389147768 535189925 818285755 257796979 637925464 459084563 615468174 317896946 22724745 663454708 328285855 242138435 365167229 467936826 1910517 445028963 848800175 678628008 17487437 989403990 662636668 601785717 411932012 572766025 704577950 326829838 556606557 796628267 979129803 659287585 717591844 546889611 903019350 493899385 127021090 102016958 142467623 820689289 687863104 213726578 430596709 235320348 461682855 230739342 318840629 678745166 971167775 786176834 158859809 506972168 983129488 145699436 922451385 891242624 665713385 828616001 153153947 87273461 873349565 588641179 352405618 536642292 812916299 370457192 206137494 384509450 780622811 880625543 949866994 1 784474684 933174980 536657783 175089417 979873240 703766400 380601929 615345297 765077040 409690479 5161251 624378869 554795850 382419164 945014965 244759586 177625621 525099374 804896194 636843462 835116306 606552127 991002735 138903412 867061351 792451539 409618544 342252990 123987027 123889392 884611039 454689904 321064479 594636113 778583800 694076732 594085478 719192588 339256373 110289372 312093727 732117959 21978281 144591770 545167306