1806 358
210704203 877976501 753782417 180668249 61261628 373892453 551679969 189332890 956163827 125497411 315381089 752381821 754794854 565336257 143463852 83182045 364720961 896055957 526706703 873520082 366801011 33490506 643298772 400980630 546177413 550938727 211461411 718580729 647771454 240188161 104962334 724671390 748721533 554756953 946992872 408672563 146656014 715767920 17342810 964345351 808202816 441227520 828482219 966985073 761899342 409980764 560811119 692929415 605684167 604792536 240229885 652172695 694561055 202029383 253509610 87127620 280871932 770721456 77667218 555601503 622442301 801381203 761847307 539291699 70282508 165204996 506845355 8622026 476571542 880402767 151456984 467976278 525443579 127305415 827521903 636735726 341760423 38286305 513237881 401972676 597625012 187874018 63596656 197419841 67726179 231406525 48730704 979027060 204424762 442282067 466886664 987361611 999121698 347211424 311565925 477443676 280513287 103039101 46835016 330359492 180177041 952134940 330794951 316523017 716552188 892523972 652227810 410437682 122142300 90772599 370081923 414288821 447080476 426822764 314286395 986193915 577713167 872338338 965527017 124544438 555391633 336980814 307514864 690260615 990946369 595182480 525221605 539280886 543299351 535089567 623689940 367073386 385941970 469770413 76225317 316494666 775233988 125827335 128276178 531955638 512751919 838646857 393978814 960107280 542319843 986933859 568079644 863139207 889910900 820493122 835988733 299620664 831017788 269268722 334143224 650271348 525247380 475268648 978891438 73270581 701151312 561131725 653122198 242178080 241124309 924501992 893625169 300187504 690752541 57917691 169237358 526967681 331860607 988958842 749849071 394183271 749378717 972497207 571810027 274513373 908725280 452644554 869685109 201058386 482790244 16921771 428522553 669619926 455210775 486343407 55236537 641653506 95126208 758450125 841591348 69209558 111669443 416179870 240023905 59019442 919839069 232029366 914236834 20649661 150390835 9271682 539701415 674880723 179451335 261485613 110546653 954829859 157423079 768798008 101984349 227532717 614850300 51088849 117718287 393235282 332845876 345698296 803851390 831381450 329155320 529335959 180857740 763926032 336815967 168478738 476277453 643477342 622199837 357347417 314653578 216000491 251038457 359445202 18198739 956094538 850061176 648235347 26003045 79711706 596704636 513651003 395540498 746903367 952797711 484182459 261222075 404489140 144179223 780603361 68399555 773037588 384652315 199208101 277845854 429093013 695391218 869467189 850312597 457881124 677002045 607014641 58784315 478999736 613617975 393091058 681035460 604928728 708828168 795825235 274537347 684983563 584361558 639573333 764908873 664074808 72276749 191140828 43080841 257788751 696612585 259404878 478402679 266990242 354338436 934439356 685555634 302360136 752346246 275008194 811948678 45321387 597854663 642122356 398275292 112832866 44345272 925226546 656607501 800694158 15931697 459549674 340877510 306135200 744505376 595982002 190355366 571113234 776067051 627257796 330908972 220337214 787095436 958875604 775469683 710694037 261383269 118875089 201208650 471445666 62156186 907581752 666988281 426847580 23441096 705573729 652987686 754090022 845713322 828420518 974620264 196079643 91125616 61377226 647562718 751232576 194858238 422418839 756620550 801601694 436507241 378528197 395167739 514258865 736539006 890180175 111380664 271979018 218518036 75954106 467132587 825912292 272081376 34078620 585760311 643237096 346319441 656421767 781585777 469783250 983101527 69944624 452120824 991552701 154327577 31866791 248349972 338889121 246508525 23569870 210824767 118740909 449088843 452666199 710423316 428941589 796125015 166959123 558865231 16216359 234129356 926206928 444674361 959386992 27654950 511591011 311610893 651543496 587210645 312978936 376597965 522111091 671847938 355098796 590113485 52552175 947927808 635801134 431343958 316659797 673345216 687531309 701102982 353719418 885355637 507445536 577960419 493280642 706649829 307459619 585296285 157854319 417179919 42853203 220887276 521179139 354329763 374321920 350629330 214124937 432658144 832402759 847076324 577655252 351208101 921729696 941921101 326767828 24926372 450759659 279663966 817203142 856590274 334906181 216915971 442330603 277547177 704111181 662351459 948162521 426639647 694375540 158343597 882260281 360058446 86125966 581694889 202835415 233209137 833968171 701859190 518617854 305693628 850810725 67975239 510780975 483225825 532490246 854422166 945875559 584546583 563079131 2002038 716045924 179745689 928453688 977828092 779496858 717142538 876824620 65692835 244162759 298329855 921385337 753872433 367481163 46196122 64949524 928166404 939689768 1000000000 451300384 253131297 565662291 167564624 829883069 619363509 178864255 20721788 13126155 929870566 792135732 516883866 664202448 22402138 669615579 869669311 451039486 906404505 511146813 490256452 477184652 922249802 65355017 996839323 285519751 352033377 905188155 995285120 642966106 247483952 491379874 986822582 508806023 976800649 149543310 198276241 981512119 969476798 876532645 294118425 20485753 155487087 675239485 637482477 400966866 652457384 607983154 422964144 149421490 438983089 138124734 404851516 519390501 112427073 889159763 510276251 948614194 965139260 863527557 516356173 741765415 65209638 517322774 954748452 729674740 122188016 532805356 993110706 650799089 660260181 831400931 387588177 378492239 443552023 809818066 664226287 702450584 397086772 734994896 332727775 899017647 806532054 85450900 914888612 713554872 973629665 487846152 86764618 999404787 628144957 765239913 607023576 643248183 667164139 447932532 108538586 153195631 741843019 560482931 800890588 14161781 620604066 215797335 331432184 367013065 780363910 209105358 756029703 858623516 636580549 94335259 627073023 724371229 267289001 93204428 996011929 46778683 31193583 808246148 486370971 641784989 1610371 394119713 485418648 823512209 509888328 632380891 42324375 569796708 414208440 3738056 246578794 97366562 96940488 126749913 77511614 778913060 812958457 623413370 570661231 849570794 593876175 711862601 390613080 551974653 360899982 18970141 686116744 115954449 285623745 64262873 885123067 596084139 704632453 957551627 293913672 904021575 888614310 356378742 607320022 621537751 314864236 380797281 209769067 223927144 693672279 977533127 200450197 879126351 719674199 423955847 591053227 734713616 494134254 851731679 481623439 365582016 423230016 448773129 565420471 854127655 496661359 193950870 911239887 112438263 688112964 238891209 151208129 965191479 867504410 900682971 776866200 650442889 106138021 425076436 220491017 540789562 278744322 502778902 711362888 602416538 471795126 678792362 955590458 381712703 257708733 56745070 460803507 112546147 341898918 341507384 758174451 80407733 276451152 515353189 270066771 393960842 680297430 277225710 461991266 733178799 222295790 507566254 595084507 204226670 409110583 808470115 975939587 160068699 348408817 650675104 102223851 365467774 302661518 848899184 718311149 958464281 968347623 225850807 493202525 232376765 380014326 640049504 182540601 539235275 229404023 204720544 205173560 686671535 15751296 425933434 368020003 203919232 748005275 912001745 67284631 797582150 999776281 69859628 801681193 272881047 683064142 602521207 299326508 533133253 508499177 695327765 48198939 584763141 103269155 2571607 332657891 487228939 895242019 730302306 312065722 205300198 160995201 526447764 629534580 418503899 349510439 443591379 425525262 957336745 386962226 355944798 694550863 993759910 197165670 115124162 126440859 72718959 94201002 938901903 482242101 396119399 446557521 920347375 539429095 538058806 413032251 617396933 474715951 751010729 208596664 88048859 627271864 180816569 934546820 20092564 853008831 514889499 240636402 654007640 518401287 33585527 331654998 438479107 773154794 998315845 647727381 746747719 589167453 888921692 495784286 835973233 883117835 220771924 594388831 140625913 683406657 296077664 538023333 190913714 984415061 985673569 487615053 619180056 597027605 723394092 697241296 869834296 898490599 959453740 501068556 679733632 863369081 285583184 415501853 173529793 529169578 521707836 825860756 588192300 764307643 623472715 31879982 331544722 364031664 115271913 884114464 279983507 780768966 634715466 522335918 797253877 519028297 718406710 431838699 989815825 731057797 208890633 476881441 818014272 394269024 5678938 909510403 451526039 75655980 929291543 571621086 652779654 461719255 208020173 730128828 860201222 180235363 497730861 637045090 470485759 39349545 737649262 755845719 484297901 616289241 850142772 291652065 604203793 245550345 822679516 886498477 78054245 733602581 230375964 921650684 550525037 283551622 682940193 169677764 645231702 408599942 551110619 363734137 332460301 156203444 349425605 36676425 151662026 190806065 44921276 641658140 932098528 793624164 862032157 38737190 30413587 99656304 824900561 764418532 818164507 861567664 409607513 44585036 210588366 265255211 112229943 565872830 551282326 418113184 864814148 527366164 990448857 574693849 12702945 136343333 723985063 45940067 807300597 380243953 416914654 877553542 107115770 545914804 706545926 475209802 672743440 81362406 389108502 978995602 436843347 484487512 768253990 626807105 687839075 658146060 553474179 284395395 70186645 207776264 121425304 63387121 817503236 270772246 870596133 416131201 518010687 174843429 335869607 187252311 741970918 720459843 481742996 345066334 260607823 731979832 418340066 402435600 684378652 700592139 698330492 27827241 325932805 270906484 57310380 319171671 963499879 83940805 923000933 412162336 298225196 689313788 270422685 551209721 777789018 359430515 126338509 812607720 23166387 885654404 770363213 159332734 199809152 330582781 922255780 965527381 714289077 381126408 23193764 894073321 319990412 526162825 128667841 847136453 215146461 800768672 408162967 657351337 542692568 260923309 938870642 659311871 1106101 123917241 957284545 605481883 16670787 653102201 629143752 472808481 680585530 484888981 437025593 881633907 316592190 970695834 671614620 999050436 981706753 529804295 630837519 2254153 655894336 494968248 685035271 855113919 696474017 847130275 361207705 402212428 583218869 768853688 986378571 885484952 692604255 485186534 12271785 629302499 876966261 779582017 485232069 138369216 337491395 785339637 393741901 163730932 994857989 684217414 3972821 597386147 422423297 3521749 186123044 50554040 644527191 325581073 883059033 368784548 414944747 3135150 239696952 748322233 688620290 10044085 875951323 994618796 725223352 866838701 193869633 313832297 718862235 356916141 247414457 711125614 164644306 720355065 914883174 611459497 308496038 14608661 754476908 654737734 245248994 705062697 468909103 293207704 403264386 189252820 469849038 81908572 523965719 121555960 432460008 859358497 242073276 556397888 715563023 148979262 918392165 11989871 310215670 593365427 518892650 352107653 573662571 828830576 343660936 13496192 833332538 47063359 965893015 953227031 571598963 285089097 499457772 857917350 327248743 966410738 820979820 998128141 439488619 922937240 221665287 262560563 760711429 969985026 280393059 231930104 59941905 25010219 526506679 351535544 150185709 767754147 303361507 716115208 732712958 878898770 750726330 468172674 744987728 529162628 147360928 20343017 197966310 603271404 472229354 791177679 998239905 620806962 345757781 886419235 723858450 680958223 648055949 508038451 745963126 631360964 789753718 657627435 736264819 785687095 238876801 505713085 61974321 476738343 89147987 144753450 612597002 109247890 894467148 720961896 961724855 485309080 29890791 888954831 389815706 914980312 288139303 400879474 652532531 439923776 159851449 566820040 209680845 705615461 82290399 944246179 40793598 495141696 876339178 783854402 678776454 876034181 966910709 393787919 235850472 737746248 16233988 104786335 522530787 799300701 195060910 366399858 735371489 659586559 812251107 483953384 551133646 528506643 180749713 726320358 659805875 581515879 186442619 330414451 808185015 382009363 553690412 349842539 498752209 404188643 70484180 772252923 447121941 742867556 419207088 930566485 799613928 795267900 736483723 79977793 721322957 765651938 455104623 726941963 215441065 234122185 680218081 576529016 651149155 625661302 140096730 634509274 784167314 294310412 578882697 56201834 459931209 121166329 384154426 973974366 327897978 59484510 554261482 10521995 622731242 102419825 486541442 289535710 755829926 883714552 507142365 733436157 835566840 279214383 113341749 557202880 673998325 462541369 623687467 787504569 224006851 814478933 126410016 738716435 48547045 408870213 97587218 432637701 220617640 324184277 620411999 257910359 708064297 530773582 509277725 660466575 878516399 950940116 106111240 845774660 336041412 729317269 375922829 36288390 66323052 890584269 493278 815976404 127838540 811564980 218336026 50025147 375062165 980668856 516758888 537596015 501812058 652452951 734468543 350532421 82134801 711213106 20686404 735627519 846586459 818964259 557579097 206627686 269485413 309335949 514001400 920156291 429378544 870876583 555674781 662723969 947322710 872788919 260512990 449692890 132686166 905532390 340378305 993712830 54797650 318954370 592564248 400782185 495409181 725525933 193925707 445843228 532973183 982987568 720085300 839629600 909002658 838469090 246552312 116116474 594107589 306500466 290348452 490951038 996763470 953217874 892168188 614951604 388687414 45993400 810819497 519673926 162631955 98439507 792868940 310911663 835370719 212805750 627934128 197764622 615057912 852381262 360697291 633336136 725593890 444381176 594166398 946149607 381508369 908558992 267847013 383524131 448988610 744400701 92826807 934246840 850514028 942705134 24022345 842702934 342893509 968838035 92532897 304230746 355351781 773286127 318926196 523077451 212739952 30354852 199861413 680744069 869230936 651821196 542125449 212503022 683989874 144878061 269678769 218500380 131482544 668234761 512069223 174120023 313785006 873962759 78888348 972634683 344439071 443741506 735335439 633736019 358650148 132664651 783737676 69055042 497729652 321435164 268962653 640672838 860142565 332898414 61346135 113789298 674460467 869674184 722122145 270735892 187613085 440835416 192355434 293464546 699197970 780086674 286155987 462553691 412358268 565023515 830821731 771875439 169591966 163624972 601866574 248433217 189917316 106664356 217839396 148747747 725987946 594189190 505901243 286771485 145367368 38135116 620693090 776793957 903682999 195477837 190737420 551044399 608310892 972360965 112786126 243579752 421937550 498967394 204077763 279515523 490718996 987099796 302232804 302857681 343387109 801238707 726634305 289453061 980138869 527938296 124077305 978608404 467832701 310309981 767704151 757548905 459761201 846730564 907753005 848239185 558319738 940622707 921076532 224245264 499880613 230390301 358819649 661906762 623832558 232533236 637132175 201451748 23762748 853490227 808688024 292870547 702330717 899289599 549447929 617854828 366858201 34866681 929404033 616044972 479502621 238964349 871396120 426401746 53725145 1 831714980 440297418 513512643 973349251 961777153 726717234 519047736 377613946 251988206 699395023 157269195 804699591 806136185 542856864 90628498 549483060 439436822 893638739 822396387 972832855 345285352 741014497 560242586 419007852 191580792 223021869 754620494 829137416 97972031 52740249 971475808 463521617 947895055 666662719 162839237 238425821 353280004 119618238 262817274 4124396 648341306 532412120 364598289 939793768 899432662 553932981 724477571 134648311 726908454 482749352 514939731 720486953 465509663 13678653 284520965 663491208 362495632 729195489 897213693 905569445 725047336 709600913 957301945 949640156 762405960 425473702 183429323 614643794 165303228 779847131 731658620 569481016 668607227 952988586 343332631 994590486 373551749 102671340 702447068 384251673 110723305 159606965 224357951 649557725 640961560 747616663 16531811 79158126 388186760 599378879 277064689 744889275 487426563 993856292 69810616 664266826 880441034 258834860 939809260 165874200 996387446 474684316 417583573 804793101 634551461 967497117 493207790 227378712 852021397 192417912 833463676 170065906 893428288 304660317 75764542 304998263 40339071 311494048 604943430 26707648 114949663 966543487 903533036 489510367 991474052 137652003 850337688 363436164 977146918 472403505 876193255 905458428 960252127 668842769 626940193 769562639 195196947 750895445 101826848 859441025 35742208 671235929 580373196 742176332 778703398 492598543 880333012 631627444 975199189 154169313 918215279 333113253 19071840 52360543 307186508 74628084 40899126 563437948 220763498 284240749 802295940 89429375 632470011 622423348 499458199 524092044 353424119 864558873 377159812 547804369 42570017 316145159 5371050 697517447 389132899 123073923 49264488 890824676 441204253 571263141 622716979 750019957 646570480 157730882 541332038 450306291 868000126 272886606 822385184 648908566 900219144 934728249 350927215 272719193 487622405 573692947 919598774 897906374 103540585 729107637 149634190 357958124 790820753 476757653 436959850 935320438 271393697 161969519 345289541 527684800 973203620 901387933 891556321 824268997 792664249 626683499 367471260 880517909 305235865 355665263 311053379 270831542 366452592 255588186 612642670 277247739 803778322 204421773 866898830 635513626 971895127 389023987 368327122 59662396 780474501 536946090 406332999 125919628 104240562 96244087 360197374 333857043 402482279 132915487 216991299 995709769 218080544 947163243 338886950 129753024 962330745 302254627 904981603 648129248 364222009 521405383 933797396 434039853 187330384 679924879 124248378