7500 300000000
802319178 161686551 304377450 651924735 644503897 696421418 254114777 74470577 565552277 678300236 517103031 78313886 689945627 307071605 243373066 497391569 848314776 534312016 561008851 654394119 963301148 778106786 1633058 436629542 309411335 74224469 979325542 165186142 845069599 486335265 832551363 147462619 904303044 252595158 247650204 71819812 163847739 505077320 582057776 601541651 95111462 316854486 135945312 601957233 202563092 966048153 899180942 472506926 720016181 799590182 74607522 543566649 794956326 187704321 678137894 820648706 417739755 933367454 838749073 462645642 243235834 612877332 593638817 800662132 705679201 893064673 711958218 871473007 862605652 452268618 219187997 551910766 235865883 179529222 993423610 805878514 723761513 512140880 653533366 791256873 253338179 726099830 291767543 888119749 731561832 711693312 779618351 530434539 160865205 930753083 544091406 910950926 529072769 320099358 161735725 253553566 516215172 926252537 351184900 982634445 680827298 698109105 104343309 542167437 803295053 470502455 89021210 813424498 824792378 482890677 60335060 737854973 266472845 37833812 617584769 817299523 832528512 256282357 671561830 73025091 822803246 427289162 90233223 839185719 752086760 771063007 55671562 336533083 574488439 195722804 557588641 452395480 86894462 88344936 77428703 40873497 222689693 897908524 848671522 52109249 296143203 767929553 815900707 342542541 261844799 543212288 169865146 701627228 222127358 928819494 902567793 890217815 164728079 196663688 299819300 130707228 839131802 359568698 6183371 464100299 93917345 223485449 559942892 781937513 226141347 126639297 490664395 410705662 260435770 207466055 360163038 304365818 511358752 906026960 388060919 77117695 106013320 921407017 908152344 321266539 589557411 730705564 940437498 122243019 591735596 985704712 379232382 489981515 180655050 556565405 299503989 845678726 741617445 701532095 82425482 203864785 564880107 634583649 459041138 306036372 775161505 959017002 247046115 167294195 643437042 618848648 186203460 161190953 641618283 814860766 794417907 80491728 392230873 876291890 362959543 74388249 886658784 285672111 393538108 691198476 866248617 584032430 417454228 227825528 488571369 938943445 2766493 691425803 30575908 158236051 626146617 839877585 454168738 466646574 473538450 573210185 137429634 597918057 303202685 817137702 753369576 786166734 400863740 473976479 471375441 191183005 388016094 618518643 944606216 404803153 918355073 946135165 409236914 810067915 242665144 87987695 563969795 527517726 693244871 404284974 501079187 958445814 952846987 689143882 869657803 378049957 104254647 121811480 281535481 464227020 454108728 569328516 907092130 603493562 823418875 418667577 888090084 473684033 461269955 704952665 28431871 462808623 510000953 925365249 733813983 281732306 561909721 723793842 325586664 475391668 215773006 810051119 74884321 175384809 590734140 226828358 861572979 347493491 482490785 232710271 412974362 816615286 473491171 373363116 642447736 610318483 772545466 492952463 234957910 845900118 186328507 733294489 139000773 591934082 174446747 275087641 340542844 811824579 43414477 900135817 374557262 168176585 708351081 746557761 12456422 463824932 85520494 741941362 439958044 874401396 878007291 982406274 496435716 492070709 733223338 595828836 657621346 661378182 452492803 894454122 734214708 795179946 585523417 438231684 827456264 499085175 24813433 444498270 153322097 173653271 304185260 98776829 985773495 735732758 716277400 400993845 224183069 424757370 245026417 725979708 415196391 312740717 249314085 411530416 820056035 298236768 885307046 524891920 130442332 440114867 170410394 381592056 506636090 452478183 852195272 17679846 242297448 369710434 435940124 759060848 318573470 89608620 131229253 199640156 629740947 729867537 510785237 748845564 120662834 486503162 816719032 153325982 97989243 859553182 127015471 730842761 816293825 406686338 362128891 229039900 878041255 315235800 7432673 470717031 80215635 64434368 248655685 612001901 216083024 485075140 224601842 809480775 220304866 779228797 965024441 661880790 929158703 391435246 4153139 948614982 486856261 527397576 612986552 447993458 215025155 316634968 156938707 730365167 593696068 514114665 442252690 524090661 498922006 160288823 960160280 236742479 622866493 326588669 329871518 991555720 939161644 359771235 546806909 161048616 504561144 569610902 830134256 513875762 191016715 36056159 387640086 642508050 172245661 504163302 600543977 539284251 159422017 784292980 106651942 329163460 987363229 952553419 549059772 299449683 51747335 671725815 288886789 127833815 927145688 562853539 871220531 8815006 90705595 959240768 760559214 218665807 908285036 829059984 673244951 287296943 784627057 578339193 741531388 212963290 939197412 598855439 588265549 336647616 990363502 732294613 872899898 555652907 273442727 28510247 522960768 337333910 848509726 223918864 549481533 812294548 24174197 518540232 26387681 571855839 517172649 131666637 17951557 98053889 967330672 764795036 120479958 175880856 158320827 149470220 610766057 335697226 307563099 567252552 554588723 383364166 228221631 723541607 735431504 708403570 642126811 245110442 140309633 412288566 944694053 431248209 737314021 915148729 698930458 335020602 872338115 411923101 984778583 669775965 43025079 818503966 117238698 788540682 338548366 26910041 136918368 709452650 423731433 938832086 298794600 365757967 918697925 904152398 43234287 983072394 199095717 199688077 257746073 626023450 412346718 241010290 858859613 722440063 101696127 853784084 503001597 492893676 440495194 783982335 393297441 57208602 879236019 198094748 915668495 464415865 292326149 133303214 376217097 759909249 359022955 228061689 68772164 964388647 876488242 443183613 869609856 34066028 118694648 738334176 936424008 872951311 226371200 90357865 316369352 825683811 358918678 38970664 271975750 986664507 822657433 44512436 156586815 709748225 578053674 329369357 377889055 748324326 15510896 419138591 176515227 826081332 697855877 842951272 11449519 382452415 747167616 740808624 324364847 292601465 531184287 543359479 104864780 1734181 165416465 870255726 27466534 620566564 46388062 334496411 767931848 114824555 673162612 955922335 120211141 39269782 279824975 492878740 582187052 331677205 162089283 583851280 431250346 656150148 909037033 384424135 15924349 734565401 25451428 108463437 792019217 222741047 460835791 255202552 281807929 850531359 359648901 352189411 18675723 397205446 721548812 807017487 137457240 442067393 636598494 333002661 771830470 437655645 986471510 383929687 620164236 672036811 278303220 532735716 102014410 40162680 875260237 725128122 99748483 927035515 509572242 326107573 249617208 328125224 74756538 433217542 186359745 874152527 561595439 515339275 503527500 223196114 216236842 479865801 96221568 488918732 535518889 564172120 932173017 363915379 625928313 138765203 369010123 274971381 1000000000 426379151 256424979 288929891 2440165 186567828 285952808 543742013 925977550 662565305 14039761 217173910 402123332 835632411 431264464 995041764 695002804 828626617 164956092 543987814 581359503 996567791 521097452 855814194 401495184 366173837 555051919 825234650 365853981 838019732 822040793 901956026 650750151 941364621 795498840 311153121 26807788 329137797 375875429 79773338 210937768 765325493 844032150 12421336 289535097 192814863 939492279 675295446 742541227 413538840 175643003 602599137 72359071 71898698 414407486 608818299 418292995 68944320 583154537 30627043 146684858 446000569 915515294 756031063 535256698 312209011 778808873 115238516 659826850 319337497 649101402 546742254 651105509 662295951 620980797 386451962 424340083 347742565 928765126 527796652 214031325 192464180 195969174 149073716 797643193 930392407 628255616 484607445 962719536 463097956 303702760 262034051 181698547 393341667 669432862 910453076 262227867 692725049 467638053 812191776 100944706 386310354 691504527 43717809 405073453 806057450 629118851 572369063 681558950 749834233 869835489 148787947 827059177 547049657 610505852 713427662 741932084 393314261 916942214 442894013 408350209 144295215 302110474 60917411 401877328 834977230 748831122 173729755 164991005 86380899 250283216 658204402 111586422 405670906 487561780 613457045 621294386 788046551 170023385 591891681 838192329 779390255 112057010 454645637 227308245 142239579 608863482 61985645 969452447 368442608 468701425 863512464 342303847 771820364 539085161 743899633 228603249 162374034 177280319 66157070 180478160 899937599 835375119 873451338 846685803 861967165 599250568 810293591 951960478 150221592 229796587 892521544 184601933 373913725 218130573 689541509 130973936 651331213 88501331 785312751 128863681 120340674 63830777 763115364 465987858 610082624 69301246 722356320 119889995 665786436 433581504 671192192 600671417 767314127 26751138 386765227 997747177 978006121 328954251 905069648 385998354 82502365 361265688 899811213 533858501 113779823 592382881 382706546 528266939 383016090 905184314 210696414 842008676 866597001 978155482 957706411 414910723 323165296 238997691 66668701 426039206 321022424 616869356 870349096 219951687 930371166 824385840 909252977 172485426 196221581 779491314 593837624 208898148 337028384 723450231 368085890 467486252 625452761 117892547 447806606 205338140 641142965 558983628 880419397 772196923 39700991 569796633 466544291 674056778 288035270 14292431 578261145 690422783 567441043 749739615 648192874 616017874 878104104 209684947 659916863 468762374 679754892 929341587 217934467 35935398 768592193 756857058 902241168 256412466 767450925 300060656 249476607 9897690 435909478 435406002 879389686 156528853 340262734 176863965 791514540 699665909 37536290 985507338 136946916 925326256 45141891 200312561 25946624 437055013 619508909 802524624 612801233 176122628 250434577 638161780 296975651 952417075 517986057 581334053 960388144 142287363 169671010 866861788 808221280 916566389 600854414 790663652 895241864 781399901 806626727 628559685 966389845 286815603 340062512 836305294 945900527 934799921 647377488 907998600 147618032 813721 275870673 989148816 852761649 638056716 550256001 981485476 318801818 282418665 979295843 65901145 649371871 891371054 48204198 768093545 697614619 376406009 389259287 321556254 438744779 911487979 951674377 824763858 799795427 299417427 278754593 211734263 581563563 679663104 837791421 614325296 724910387 465842488 838575873 98256539 156758465 952862848 934124082 911273477 716819740 98917191 47553910 625043921 109207035 304603181 274624077 534216933 228375806 254201077 993467803 634532457 287227646 207758678 340526393 486123309 88666278 656752529 731215815 496557061 804924275 484296571 918292571 287298201 921028977 820653412 173192250 414381043 695443547 74413197 114380250 67210896 670111031 758241360 781987623 43738236 769885007 692958865 198739975 654330897 980604105 357882195 597413768 199868126 985343716 631605095 420858793 80145059 236445649 553430591 787552706 437780088 840904747 264738528 718051216 465800725 99189238 891962593 803164939 757724655 37036289 918468056 657849497 604860084 252365485 241637342 113446652 923231219 657018944 613497637 110634838 636375085 988806362 397757327 371030583 575506373 827125223 956250193 642934212 858537997 427365474 930853165 574115889 860830634 798594453 141624027 144620661 664585209 239424682 83883422 75112982 187943739 355040243 766174150 89878659 289259502 443477204 376602191 232072208 365312311 989403726 52618151 964716686 250025082 929284648 309277325 665480070 566939323 294342933 450619922 234324315 429410248 315183193 983669790 603859806 219690216 470774437 802863090 891196362 669873616 64628259 743144448 105588346 483109653 779904701 180546843 883928952 697791347 408404302 421532608 600889510 39164668 882547494 588946943 825392722 99149904 657649436 729003105 606082541 165646710 487757438 407988702 908663319 698157753 876286564 167800948 364289990 678402922 532251154 142114383 148792602 438694754 664917798 673056334 834878978 871763455 405154313 402314379 847942911 879666875 317251969 710541705 183676929 689488234 219137890 690783737 270941037 723962384 860003113 203190080 221760604 944174353 880947209 154392261 458644949 603775196 573021090 298031424 450068535 169825144 96527369 960844187 83090215 799347769 545934762 365843833 921054829 619787144 415900110 177786347 495292226 127331331 385585854 498212346 665007434 974640586 779151079 62743774 156603237 24481125 14150112 687610904 429212885 127954797 554629341 184737479 700350262 797547401 584634104 682857779 104304781 915180460 675291253 144211482 724666164 259384502 415886779 682192169 657732191 601079609 852021232 899656838 245590104 445722928 974922122 712322305 24431820 520065641 899600012 156286155 897020928 372165845 245569496 892491572 747463445 157603775 787963830 758507936 95795687 257855944 366517507 189647974 650930308 390065412 549119986 484685769 582382745 510771583 675025155 353075237 398066143 916614867 372697745 41569268 422051286 310741907 316778455 354618922 458887027 936241934 331677366 639193616 421291670 195369499 128678398 999082369 364922177 137116304 11462665 922989408 547340988 24184910 699765404 492954716 79612137 552375591 912553353 225551333 940294837 971764073 979296629 824586444 784376076 214322868 982988963 249822579 521605712 739878370 366010665 902596196 585191549 772905270 36879924 948121553 589123577 423559913 473555639 358533330 529031650 189672113 817164944 122310349 276867737 313414006 693434895 812301189 250416654 483700683 563203731 863012335 693536189 962172381 665507607 21683099 539108536 919053564 772079868 893505278 132159653 518022682 562293071 129683689 598920004 300791794 174785125 10584385 830559439 270811402 162239926 369051078 41985949 380274973 530375375 509884747 976570864 12178191 640888430 105329204 372093644 793856753 572840731 468422053 172185614 912624089 365557160 628613480 133876101 947364602 857961155 52193321 916175172 882696351 42384978 212219253 107155378 25085962 298615393 641347745 757799065 187007289 216574128 656454715 896979630 226271913 617907791 293182114 40791485 114999611 724661458 603822514 823532084 690417458 527332759 893134542 294590303 474964544 557273795 580369939 613807437 711070918 841675709 174892348 594299274 374174936 234426902 205521700 799299225 806668467 561664515 795242390 24812450 934731891 828100604 613922001 612210961 946316280 623792138 752127015 205885209 480514009 794127574 553704242 980693314 563835503 840403436 713739719 468964194 323630825 944867129 385667553 288496981 227722193 900452754 624497812 276713119 130664135 307779784 53125353 230985253 575948317 646309142 789294090 3621261 423644890 391462897 986372175 127465156 277177911 469202790 309570596 316257016 68295553 614910128 850712580 91578444 968480425 163319417 480530737 818073073 943725839 615130849 717894880 428548421 244936633 696208267 371689476 801319734 843838762 31255569 324057487 911457555 816718485 997835040 28391318 223624915 260933003 722908931 142401505 804894026 472968227 86946387 767784401 269587403 504659793 935905983 969686704 653202480 125529461 914714063 422201443 12395015 215792743 830358988 777525481 243885491 203151976 40618686 934599147 614673266 962522230 332968349 645052462 732819412 36225170 189399186 653698882 685502058 29803625 986028167 933213856 123954921 861489927 123237573 959342341 976119691 467629712 518208113 392192993 870688767 398189949 60809452 884841097 258670267 225040692 416807409 52446360 585739094 599769516 927595574 41511162 717369674 273559029 857241241 805709004 76648483 398984944 575915104 351895396 857335073 63248717 21595740 871318006 552505757 839651156 715170050 44686157 58127902 760083867 518696842 173797914 716409397 547509013 253579942 563510686 603567354 940911928 889911506 403348911 245960783 301361639 598460328 338416107 816228877 557535022 451503261 152738227 494450673 776945734 743405670 834042652 55067103 217095539 399193820 758967284 189224600 18702348 314434909 259952423 870066413 372225543 766519540 795375258 397338672 997618211 578045739 76749187 267884268 501798714 96891826 193345057 284140492 644352917 116373694 937817629 595941459 338234015 953277392 32003971 209506050 511848060 228238859 423695981 799613009 211211159 496151982 603108315 898377939 889131056 273823514 176482941 36355824 47022716 718266821 435960895 809553497 494154179 540568464 318172242 966416011 564575946 537375351 616585694 29515964 400689561 622682998 605878266 368107385 207513806 312588612 244598660 871929427 114491749 667220313 74496817 850931750 862821069 471821570 609028661 339552630 146034856 739051412 227854219 4818164 201088544 756487650 773421089 346561249 987208228 556701194 575648182 203627540 703752355 520332337 59284164 950298338 624611724 523559773 681805177 943105534 330594215 348297602 805554463 684383672 153197304 449976431 324809248 30639843 617655301 628862717 535195614 77026300 366388938 600018720 866999017 39549490 875192750 980309787 772931969 433574308 293066738 421247552 244439455 661504039 720122874 48176382 661418785 230217794 354390815 48483629 198486028 173004830 285521613 473634926 943744925 105760060 181842074 568694916 984148349 78819678 784946679 742681936 615895725 979656533 717889930 953369086 253974317 934275029 617281960 858980755 530139113 785659946 836936726 816250159 793498303 172919708 29033747 139746362 532418757 554833192 650592807 613297424 394421591 854549189 73414980 342525714 41818559 90599105 516728791 117098879 236857674 430386048 856951101 436258313 652982974 751915561 903972940 509139433 762215638 737416828 37229267 773389046 619578086 360996703 181415520 641630562 775021261 963634299 248967326 454878809 233433539 952396889 553462703 218100623 675989840 629990876 767223163 908628536 224038095 461498292 363828824 119746131 304732978 306401194 129160609 21538676 209021036 91283618 971701825 422322224 213342768 797518630 215082730 583049808 76258567 283756753 28163780 887795934 100457474 287496209 732081379 174699510 109362197 114779503 58766556 223676871 365914860 58613782 539501354 737426290 445623174 98678519 18809122 4005944 285442266 259171336 205701922 189669763 197029603 392261887 85628981 553284406 250977733 517465205 840042068 244287693 436914799 619748621 887687975 951266971 399445487 977672578 829629930 802885327 176682554 992921012 500098872 647230509 115529528 296089547 67251721 483641918 874604663 579646353 569065506 765697549 193658648 220106823 901050336 674271619 800437837 240570129 442630021 645869906 270808451 782216788 646859249 969735058 974800132 14900717 298361838 257076183 616475267 933733501 239018774 309080920 719078756 751720399 70283182 639614586 744485552 668138679 957482592 184971151 655266496 617991997 977391370 896788863 170669945 246199336 916507679 890352420 277608483 121049732 6571721 459389155 763260993 857777978 777622176 76503246 443477115 950713445 663455985 26270127 354529328 72834664 718598581 934082133 843021787 536861747 790354585 249571111 726644751 804069314 106511851 744179529 861015616 706855596 968247703 538939623 525891887 222639770 427118671 770191005 930317595 317413666 797526382 370133155 698681959 883088038 663561038 712521147 297939785 627798324 502407590 887841109 178270474 294735492 629713678 819267768 198559669 378724846 157761166 754166293 361163607 638784224 210789639 694982667 450059904 798026403 142709713 639361752 486681889 871016176 220839470 510325300 49939854 947688902 104715952 420236413 622260230 429335280 311110804 121073164 663861912 604198056 452467385 793159076 101197235 214935126 279482427 15368708 415986549 107773104 502209180 8767134 597758615 586361342 371486044 788218495 853400024 176671143 794530632 719392108 977363046 314952850 432223349 180361001 125086522 656841084 287914255 92264201 553987273 478558866 632510124 303295640 162692153 215369103 515262078 924869512 740766651 598883715 878870362 248577107 199246911 607008671 122105783 913796373 206791237 145663648 57467861 979230164 136393210 184577421 5953923 977511632 778876119 514923019 593238196 117759143 7022090 772905766 407192289 489440739 110602429 94292678 930465294 526861837 5678187 927593907 478477406 596433874 505391555 711863243 49165506 801140432 137774501 755031006 903857868 413133312 700349513 215848746 26615202 72540353 313423999 41816174 726834189 37469821 90144016 73337517 758938033 416299258 755038788 423446401 735330135 395754815 646925181 162577510 271284512 61138177 158192592 799849841 467604328 726635989 306514795 977294314 794431139 401888196 587717615 794546419 665525381 414838655 282564125 748788565 904957946 105883870 800980875 364311177 594965451 511280453 23209568 580899060 675280874 323512865 428770476 695798065 589532506 396158866 21887330 302877318 277973693 379416355 339701490 840219255 741435772 134474119 645493113 624721293 290546041 140731098 657548991 866621412 395142427 56023985 799426353 688021368 453576956 637245688 483133819 813596400 523971992 189556546 919678186 160748860 356438896 269711592 814610334 391746422 950095280 700558040 109964214 407173366 292762943 423314820 952804980 179881269 726383617 630767668 161954356 105508815 415906497 509817019 547742075 384502829 338969276 866851175 394521631 976850990 874257999 136353117 269385583 804659287 678649797 600965403 671943326 669018183 195484459 447892266 764492645 467551645 800865946 527495654 872906090 733373061 210114274 391038068 678810513 535352662 724849147 836243989 709739535 35194998 472133123 889146065 487746444 207109419 328215346 113762315 240255725 821063031 793771227 565599029 487826222 124371504 356539474 329179703 407494231 167015356 213295430 441424490 444798118 262099336 886010383 63753282 218704730 358432769 422655109 889959976 385073851 448146047 28374118 463636750 186185909 737693159 221689404 459627883 719079604 412992631 7537679 309864664 966157259 680664769 252341070 977397441 278388252 116815267 227692793 53871432 309782631 664352433 240947971 351945061 157083931 320227622 899236004 658184368 447639016 423830616 8029922 569152400 713734946 944318133 308244316 952257069 572400624 101399787 472716146 452085806 739033251 117017526 431006974 621080260 68196273 155112529 345480267 915622939 37098812 302626228 241713133 478004029 136051456 475813083 66191664 805103693 885595010 63891696 64054544 22869134 867994121 883598391 54931518 352283111 101342085 532145448 501146613 423197561 865548587 837944771 633747869 311623987 156768322 855923467 379337170 384409285 278635898 897392407 25932375 804836255 67671166 686622077 737115297 255157446 826871878 135680835 672507098 862167219 735498476 224190793 187887874 979402954 640674463 425299286 782475824 38945397 166235056 645247421 663905271 613508061 250591178 160666027 577149924 185281605 911963711 665914147 99222530 274169213 207562816 411296283 494960543 936178341 861287289 767312928 536564859 816246934 172126667 617346218 689456633 29898589 323604340 755546178 212222027 377646444 171068179 823136244 212317391 881682896 995256557 552916167 876959678 903440757 727308519 172000215 499762534 201733986 723609303 258472509 61685972 659171817 422130306 58140778 51047175 860598877 202772012 235225535 75909941 383930472 506770883 789347143 374335894 954305790 400177531 20613266 160358767 583569681 4472575 215937446 237373727 326257999 8617924 586179052 312918468 256476695 919832699 175096250 401483518 542799640 185322400 400173694 760528075 28493960 979173680 760074115 698221970 857416703 328042359 173847395 571273275 185902318 889757447 595841546 711493822 61275077 316866914 653649197 782943881 235224861 758297761 157117660 474399343 813514581 544154667 612342365 307962518 502152703 333327769 402471362 19904905 861816214 803909737 327626637 512717806 926606396 692259395 108114063 304516841 809855503 669111900 772314396 40306840 193381382 392905623 504198572 252730897 925552243 37565871 43684845 603947572 342960264 592132796 609784181 787986262 579867433 528733495 485776020 894065037 915694926 850286609 219803751 606074719 867397290 929295489 139248903 618406019 553334974 940480376 279391748 815612502 217243016 41013788 518582171 515816374 225954001 774274403 346505175 198585396 323437523 270155400 201220299 803985192 173151950 890622803 687919012 162072421 23366909 211847102 469020879 295017149 568433188 125503187 732807731 930110637 266172504 988029363 173413124 28524085 529743976 657654450 250353990 77271755 526711527 683505312 944541407 996009431 423177763 38222934 225248948 783427316 300304192 814278001 429454072 603563993 570706383 820674899 966831887 799685979 782620161 585782908 718478900 654290084 673272459 469466793 825472204 475184585 298792137 64845417 351795948 600034448 148979063 992811895 650441790 325188952 734668501 770072192 372002356 642220297 897268499 963545210 861140821 222947069 472609513 272614302 982778809 52405644 315006052 997965828 860956304 657918258 940108737 902183386 313783004 335191647 726969970 894566209 587792191 270346716 921454653 130510789 205707502 122989188 488412534 70562757 434560903 317375903 819836327 540108149 396021639 575625317 375478083 699365336 355061420 287049674 80363207 36329573 353168282 435304098 36057055 351200959 172076780 98876804 692432545 958935549 304760522 658479712 291640722 245480531 297498292 218881814 939063209 481493932 744634610 798343038 938468504 862945444 365367586 790561596 17276385 180567451 201855004 102492158 722152025 329035839 729691431 795016985 998874993 54289069 256969217 616208162 319558753 201661012 124794660 79360156 709306865 766974711 331401163 147087588 815256016 254105209 846756775 841692929 287934162 685466110 976053228 806146751 311351304 858453058 846789710 457894169 108656842 924671162 248841964 703061650 143275288 603361543 741613416 94978940 936070973 67597511 304360252 159186608 575098462 798361219 613659116 399820098 697961783 622706042 972632293 477394129 443257307 423540397 36043156 916977712 15626734 322009693 256928623 323465212 430284610 831431763 576424770 455788162 623712373 612339420 26773415 831977550 625492408 198544741 339087507 737729873 429349039 628675085 222486190 793971810 433266683 693583137 141997196 463192580 629887253 505079466 647874325 132551418 610478880 850211964 36474054 731872097 519630500 262689495 566807656 791711845 737447295 477796827 252178440 828208442 141539456 932267728 346387626 66416947 559616633 318102623 193972434 718839902 158366824 69076401 712459258 624287285 383931250 382162155 852757626 656161191 12309284 319647048 910035618 42184641 624357586 437865706 667208441 955587879 273912253 117981505 745181463 88234156 330030977 606940097 496581285 396411088 179885828 723527073 627306213 393379611 654245200 657182773 860399060 145617182 496897517 807287858 810225924 107097432 531615382 915186523 911940681 180810269 459225556 727453901 226893935 831927211 818684311 583604432 123482445 353172129 76710209 95984085 165835018 562883707 705112870 13677586 152438584 12395338 837119142 721448969 893449355 77343706 12089037 14033542 124457250 29570035 147432908 335574184 944611171 520425159 555640555 416780152 95161633 530005454 910046841 842330730 500548859 511319579 239565241 376009730 844292433 891878601 29147498 252548756 837373588 473203954 348905763 489275145 570554499 21692966 739622507 760029066 654636472 168520699 702759449 714436752 892980798 360667513 639999346 460518476 474146267 718258697 988270604 507944626 659399820 221537225 19225723 494923300 875172625 759059316 727481189 883021088 635047029 733520422 138915614 420201681 371934268 482663742 697729763 938341058 280465193 809466975 560209840 847288749 573456553 630972305 411901630 571357554 726579423 828888966 149410205 616276003 308363597 643971062 533634025 987658812 581584412 857607723 432472236 304136688 212168200 920775577 571202896 702631146 567080101 683432511 977206114 126062819 716644742 114664729 461541922 112193353 175383697 650957212 48286035 305873134 585022949 238011101 705226405 969330864 785334263 853816016 283886965 147127138 131722253 66177328 890773148 675414005 519583778 693075074 838193490 987707158 197280998 366360967 244635837 539466996 6886745 51312587 25894426 541723135 883046235 152990348 628551105 626929044 955064682 365146549 441406741 649124994 846288093 778995350 785380054 511864456 742489713 390390219 181819777 743697290 320275825 748902624 393173411 364366992 36737532 379591712 268637176 282340225 482167696 596634389 964313389 422255082 886759742 905550793 699041165 396806868 394996632 688581794 306026378 303850757 734146655 655020394 581852657 468798650 759432377 651296888 688973927 106639422 152885548 246537740 142666671 105090217 756048486 12340299 93949589 859481036 943585333 404619016 344620756 501858606 706182453 483632479 954566575 728707760 527656465 331902632 686601982 744340562 706290127 273880816 1026816 256239163 585703432 684293991 309301298 577897545 48875432 955438569 101092619 371933739 373876230 443872758 505919599 537303023 385864621 345398092 386770237 353793832 816836920 571440669 288614149 723611323 79021655 820959986 653341143 57708782 126579740 479202615 245046830 465299548 450221266 637040172 200735044 320786649 378885612 764548727 375938836 663584315 793978081 379496905 591120204 529153155 538553005 331455527 866590998 840740397 38959271 663678333 776605453 493801073 503124050 794835176 839331354 216846362 125082053 293405237 98124620 718354418 434924411 840989512 917898946 334936583 211459036 46107996 285787643 905165731 533716661 929128082 766254399 668328733 702141918 672077995 727866035 139932389 193833021 21369993 589264059 542704328 926850130 173399869 921331351 895851719 729164172 141381343 292684346 475687368 521025923 29228177 503412497 294355559 651525445 923989689 496945462 454898442 979299201 41823931 645877774 28126701 205340449 634757663 91961821 743865260 175600059 576495308 48269271 568466071 43735103 405534510 166379519 140283735 948251066 400132346 117606729 436296177 42323368 883859487 584068352 13243137 981500481 394142092 982197515 246363597 527846016 932894877 940308085 486351763 698350208 204550389 364379219 474838261 893593549 450237175 905409941 512924527 395784443 793763624 335867911 281616638 874944322 828412319 288088844 20935822 462882474 144956773 237335090 155005232 296256747 950564901 490612406 779874687 808512114 51467683 124264662 800224179 524745442 527771572 30765634 601276181 810008520 805284061 78669730 627002032 626169676 83908727 842641452 127850338 173766540 69730311 913038364 59759033 451347053 256585693 600985013 66029985 107868567 217879324 256055178 536319594 576906934 68789459 29960136 688363824 534635445 981953480 652259376 332837262 309971116 542785526 71926635 160277727 477785179 995600408 375343743 595056356 837884736 647496065 895639951 361260825 768779623 116041582 240136970 517615969 499025148 641499826 376694015 575998188 357992668 909445845 174788803 296641279 112040707 738823942 422835644 779317347 619002052 401079509 83503393 894641606 294533185 158419122 711697384 164791410 172399895 184859658 334943320 687011780 285591925 417686578 764817599 731506645 830951912 201033244 923514513 907270864 575722560 224978942 830182293 946316812 262133698 873503243 860940623 820667528 836497416 614881123 771930471 693681199 400289671 568517848 315729985 551619944 787909305 162302926 41983290 968099307 475024188 440555136 221084659 590058405 2126543 879815310 838730855 549535153 370252333 941167939 725817786 739763402 805348950 206214814 992704436 406702818 416940839 979005720 872695716 889305104 722851577 752779678 682541015 827531285 842397798 375297834 262764071 292725385 229522987 643531261 513227691 563787175 13544233 392145531 795470732 213225394 563602054 811973538 979153143 599681794 126099441 774887208 382371374 240841390 673548081 823324631 60972735 70881706 619719867 137495439 111492667 966174533 659194207 495218520 974475793 482798705 251754126 740333742 609474485 361574153 274445234 127972228 435387209 417127778 713737552 901155067 783530952 40156878 836291403 802998870 433598128 330294817 721353508 711044771 429146082 40823317 639558966 347679129 984052433 768861497 771046348 937197615 486593547 628670099 461955594 87312843 925435388 514877049 460748981 108797868 122491313 156071037 594447736 767295027 761343443 83111660 10618655 800644618 375094815 260676320 899700163 241074517 950136390 222608880 705467151 388785393 91943288 726313193 106368963 192323666 388798513 814227229 257259034 509427451 328859177 448859577 92642309 858941618 289770834 642611031 892397187 362504467 161047981 327608276 971469839 214100656 256704713 77812543 292626346 395472978 348318937 604926444 533673600 558760542 133549425 673106857 490666554 234373715 208436189 166891016 842450911 572743280 321034014 727666651 28688743 517359475 915147650 16542654 570919902 706158715 337091038 398371278 646029874 151198991 455678571 645778552 409205401 777519415 237473083 540487788 334932129 811727304 730684502 822219183 542917589 61928126 914647925 268265936 336170249 475463514 217394482 946536515 45583050 240716490 63546248 16256326 463423711 338621737 179060064 604651196 559068410 208119472 418257110 585428991 244231944 206181965 221380969 95068036 609941261 840645399 68605674 895714788 336178788 237934955 770573712 229553032 128683432 660042537 468181233 24235423 583578475 467039138 218441220 647597834 463717225 610503594 433700900 425288241 337462817 932310994 205641553 983528986 418052658 651349087 435462885 789856426 770116228 515741140 131065136 961947389 116712039 488925707 335115309 236664339 67925454 84530526 769257080 896454502 460086352 55374832 195547063 449029296 472328898 555863473 440127680 107865224 265696805 797546928 523952518 459065428 234672294 117212272 902898086 313059781 942106755 513903560 499001921 363712306 254380122 103603997 514157728 941029550 491634619 960775897 907459222 706009578 591062146 512445403 663816760 110526512 661948697 483785249 862096532 948680403 864954324 878136775 881030840 705230610 428589942 506495515 670369798 102605479 828697804 173568138 916327984 739070867 236433609 61638506 39871220 786404091 47935234 922088205 42643167 362852842 431113376 577276426 991792581 118886332 106563033 771578518 899191977 650562906 716166534 121300710 797170562 610707438 921783391 599500875 347716716 947738326 448248626 742406631 572983158 820258980 727437503 293341308 16147210 549786175 453549363 21449056 103494389 774053414 363282239 38956685 625482771 569572821 140690133 707916952 948379968 662309759 936260402 761886973 33946748 738588251 769563707 885307269 892127613 299768759 883056307 295202410 776232954 210430533 698690108 426627241 596733293 517089275 570559785 677930343 370666122 730710129 25498110 505616095 784655736 707790014 770309801 717823610 927742940 490538661 565053384 283474727 187580854 468881393 520254415 731163058 273190632 604080664 616415697 918166361 64973781 942904783 17578154 341320085 244877241 657747122 591868043 335211986 524354618 549043293 624538964 650718274 740076651 165378315 465351702 306828737 429571110 853574869 364896767 486120202 693220160 202136776 724186069 265020177 425026006 131813333 501840288 11419393 552797632 252799068 593219173 589973965 134077219 189158991 599345676 889149301 657123875 717488134 10629987 569342423 391943093 25694623 725774907 204513071 326998418 933406480 139122608 762018861 958051143 393500295 519691698 813425257 756382476 361756592 667716134 279762919 748741570 126786168 205118584 182747416 284020613 707672755 320392755 917235870 736935235 770214970 443199293 660559641 189774168 90240928 310855580 184827107 693371793 317121578 130873600 232617361 877156562 32380070 657466047 420927541 1111848 460379877 587655690 693195046 412957258 675513908 617522562 574238713 214594975 440341403 35004546 363392197 339525491 784083511 308218059 642039390 861489855 531520500 144727517 426877177 337640954 56018552 678605776 296795548 542037442 266388679 749758694 847905583 483454145 747968887 742404404 283787895 53512650 438514839 899270689 106080290 830542038 572358180 340577012 378376084 918864793 661820821 347421176 855157184 351577536 136951953 289058860 376442570 771676353 724668438 381220224 993286335 752667061 16806162 710714925 144869235 358283160 408916432 589085923 903544830 793483307 343200641 418822976 568093692 674474329 441714020 165746593 146415101 418917963 860902337 788049772 661075789 211213610 278718548 407476048 169909714 913552211 426614278 556368830 270101387 920369476 391682015 601402305 760389846 161516382 553670298 205881748 880462761 207110637 817328606 474481986 256517667 71252109 971285115 254240417 438596414 271640358 794723863 553065043 515526464 985905352 733751767 675601893 956430885 816861679 206854671 333009412 749505776 853136969 857317126 8613284 870910243 879445212 685741199 214767943 430536097 560575322 353646150 683092523 837824927 823963718 952257674 273475170 599308862 124989960 706592137 703459550 581793421 513691619 259841212 118183151 314796254 855708797 829081738 922226227 849743883 303352037 837433372 419449474 453085716 300279517 246612801 654267402 875340076 188940678 451590869 695158540 395024364 305893546 603513663 50980653 379117739 329879206 683109652 700469882 321980389 898757362 467381721 558324731 10205143 56831311 697076453 150515698 479987501 140076428 656613989 8697265 443846867 79645684 919387769 464490261 881043176 147088983 395746428 624832930 606180561 108876211 21406306 527553340 709177471 812144768 610047574 393460629 547214802 871142589 46360951 557614522 213411449 423926163 741131641 13808587 310877407 309377062 518635657 537057669 596788505 100671486 789381668 701609200 473177793 291979134 369365770 990855273 666284347 454445566 975176785 269364555 978016786 251664789 13181753 41081216 453663788 431891533 788305664 353309753 475747411 583442510 305059512 755631351 834723467 750827470 909252061 703262389 860376587 795201197 44097025 532028813 495779479 184943760 406505661 889242630 921836895 975836466 742121518 767863817 361700673 954889267 363306572 789918582 629766853 725097362 72859324 826014055 237582102 479080626 782497851 118953599 487883221 64212163 125638870 765419886 679443318 140947463 744573086 145102676 540226672 301593984 636907423 748378399 617369636 413264590 691905873 352975597 850335112 525854315 634225085 139219207 178920235 526900863 230005982 203780906 814096477 174776709 463795412 339865381 150607868 389362070 95200679 357795611 984225066 84485262 502975352 829694007 42062214 899335538 78970237 747845632 823772646 129255349 386759020 191945841 212101394 569970326 757255516 348850256 539209941 365047115 5272832 311623437 110266393 121664929 637036556 693829645 858721345 428244625 540724720 477110339 670343616 864327788 83455937 647028584 846360003 643343268 150318649 943285462 100153102 746213940 198335445 658771974 616326117 941815213 344869149 636311328 483807710 986622208 986249804 475495522 296004640 250091869 257627620 629680995 90023838 842283158 71020136 524535288 522426751 877128808 947186644 37615685 581421549 691777145 974054617 545084670 119650825 425497306 98299207 810422878 293900363 723153414 963425413 842501377 361567683 477488128 104080797 920958869 825177979 864972552 293500528 990025501 204302841 626443257 803378187 280086497 103972577 736239682 215439378 354338550 601945782 36735359 477010265 252908133 542333633 278187187 323145618 106155003 248455434 377452324 39258656 658411693 507037827 832052947 511541258 174198437 427942725 158352535 956379915 432454637 267810545 392990677 51664838 875959735 263808313 292041182 194800918 673409606 40276087 555218661 504569988 431850877 383082619 535371419 413246418 705072642 161902946 235448937 32658868 395308815 207148705 282377545 318215582 115237589 956331553 685311810 148318392 526476173 441864069 590480367 438775068 735873927 611286025 910603045 258184033 250112384 243256872 759206280 125530911 426466566 444296960 717160367 800793298 565874882 640486480 516817652 223741424 19865858 455963821 714849329 843958494 970554821 540453514 948588233 302216230 326237396 965693031 600305097 875184844 93337941 432317279 905405688 161336209 336730930 83653996 875895397 190118686 419178800 256157794 108202188 500513016 411085624 286609206 970278830 79188609 937332379 863169435 178751296 156303178 591714079 734643061 909223065 428476289 487351840 841763411 376324769 952211703 448097744 135029388 353998888 140720331 475006110 746473973 271807763 168224184 790855349 633027644 321723057 542706425 248970651 601628900 823788331 2216917 493935098 93633245 583103002 3864522 252469628 166446015 78868019 62201178 195783375 540005027 197789725 915121516 774982088 277776995 910008161 803846563 604165339 932307077 253420469 932304745 10239060 44244265 259880269 373815402 261838125 997047151 789900643 893830061 229167458 586770954 968325848 749059801 344281482 891595104 916804281 349062319 893026718 554197840 497947812 498072572 314374145 127333222 712600159 310223301 208926410 615073384 68385348 162014690 30608746 696707674 289051586 916533944 823154084 336272833 848293521 135082382 825343671 871905855 776133505 744823926 977474935 795719359 447693125 32068001 656522754 57036564 407363912 708809459 734513310 590252252 248810712 228758629 746322458 653029996 203382357 734464173 674894382 968639114 382845288 225639564 673158593 129542228 340758195 911311555 701540 556376147 691738746 28659235 128498052 612572224 775294683 961796164 764801772 953373889 934976590 490505598 950215415 865217014 424178452 833459831 988520978 60272358 784195205 327940055 127242021 679214706 473561352 697538329 740608286 385053353 814279309 687517827 606026902 475721212 353224633 342791246 593195782 327711129 586099991 463388658 665957895 758432657 578793560 9939235 151652588 183657168 979829607 171489471 680972909 36614527 164716625 441441623 687646442 331313949 658031196 17250270 329765072 511777849 824423661 255103765 191701450 168877876 404919985 662264797 776203819 600071156 385587058 907420478 876641717 349307838 147993633 577681659 345069900 382947132 587742527 419386524 586526363 668518144 815987787 878263497 972722650 884444844 820431663 327624276 259723646 53040910 805378926 372798320 860323186 38928749 965021195 840840044 769149555 255702332 400415685 867592283 29544884 613169671 568224651 187188477 37762015 895716939 326439125 371154316 661122944 427253932 540384376 985744536 333549679 834816595 252503336 728041200 974775257 839784757 274370446 54659770 107703016 468589678 663276034 312603042 541168146 454567623 275994159 219283195 141018455 447248030 518327345 549228613 204121135 716469847 235318401 903959467 575279987 29205213 510188130 97680022 906179574 400739170 195967679 160662058 289014129 848812503 77712337 59084002 580399840 18029716 177661344 262889861 855746639 218927597 151017089 365932287 901241554 998339211 883658427 689690977 264299227 735038133 152800593 61265372 95347043 568588586 206334210 545006679 437630562 193725099 898265853 146986403 761072498 479408759 164647636 114826632 610947098 65047646 224648079 497433451 946375208 261265885 566620569 158502455 128323765 765441894 212727090 335408208 187060539 181938356 909221037 165929008 525335919 735344419 219225753 612176461 836275647 265911250 732779891 410236460 563902828 696867537 277213137 325436174 664129012 452111552 266673692 591728689 321767035 940919082 609741597 134790000 347358051 267664209 36770514 59255777 458110024 482784375 605059311 386394871 802327285 802815648 577658294 921169461 668664202 33265775 207096625 111312600 262493001 316194094 922220555 515262132 999217897 273369099 31898653 900057095 938547897 667116078 630827260 103604998 524706590 598273633 605881601 25930018 601547398 334984920 825388791 227848682 359939854 879444787 784399383 219933080 486356057 865738534 366648331 118494249 218005010 334087470 36975350 311855069 549805785 775920857 254141536 285343809 926071537 414655157 652423656 265541800 315079284 191947071 197848106 588585378 201573716 577904714 905790010 388645804 254249966 329583437 700250000 538560305 885507192 531491118 387781063 489299593 728512144 895686537 868272432 402887669 850834480 609296694 8230879 421912347 229926872 991851653 596095723 551238388 651816498 100599710 987991327 745669978 474312305 481924151 149697326 301656654 791467730 817039087 332045572 421745638 833717061 356376650 115767351 182246097 183590948 584346442 155494812 666532232 420303137 622246310 998458899 573947967 24987049 42263498 950343285 769521399 333698986 799119798 267245435 352166692 912691071 642080651 616495126 434645873 123483986 332044451 726857394 69967400 721988610 971010960 139470452 154227471 764730760 361877584 842204546 922631615 887182889 694639736 571063524 559765715 732691452 53710472 467952844 360603293 970102941 863590751 375053445 861887326 583532966 128814413 895116314 864009734 861984575 282215590 383165060 631070397 918195773 787167129 348446635 216938402 891705727 722053556 228149353 734989441 185679731 120464802 455445132 971591420 431689061 708495756 263442468 301521970 641858653 153910598 178152630 573573096 881385568 705250453 648354455 14738479 252695410 439187199 101165071 614984489 60956553 611976207 70462936 161022424 906431747 860796111 675062538 731939356 629049176 272882397 267073542 269212538 25153272 453342127 619419107 658681086 152812886 327484782 47952654 100938399 106523818 23450007 108849306 975055324 267032075 480478379 341984938 809681487 727942435 650385934 816141687 602552590 143171532 238529465 471929324 544849895 170645192 192865956 785766913 292333894 172155632 497313979 886932485 314102002 364420863 35722916 417736726 372134068 220328172 495322302 653979548 694573810 186802781 578110569 604401771 861114685 183112500 860164971 334539800 671335982 252843276 325170384 71243595 259421232 134184230 949899533 338719430 656468395 254273702 954548186 764118952 197059241 162877116 260419198 490442906 825431483 79398844 845008211 116222288 185233078 58141588 420154804 426459795 210544891 493442538 7997716 580719337 369222608 606340050 623352290 271549165 991186217 469838156 581870594 162954516 694862737 586277587 329737030 40307415 742639369 583911098 222870613 117132669 558486567 666266698 77486148 249592831 404837877 755042030 608504070 262731309 914577254 577617187 975056495 176895470 684437107 22759563 388647907 502155428 140015831 621685537 733447327 959394990 964124259 623307143 336555683 103549703 182679806 793001084 700658747 169170188 825136189 937195369 953338921 883344986 525467 467140634 124679281 231074517 922778709 137154442 402535873 831601862 892093925 619039191 755344250 902211868 581670424 664598868 148450911 949303763 821182926 855793341 354196953 572872306 758688590 82685573 337129956 264313006 637840196 470520140 86432154 960866604 372313944 603706221 460551770 625321060 722420147 745923477 930148769 456636528 128297259 74758453 214728677 737956884 288296617 332138089 163197677 269690867 966873233 235225473 701427212 837894339 214057219 282545822 811326590 200779082 173313144 170760878 803449908 911693447 957867351 514509854 376802156 61262920 325592091 963799743 774619352 86516771 466161094 409104858 243637716 584685334 520588782 379595323 181633566 959828720 950758662 173064939 893066194 295182052 390017528 47506322 716446102 451269255 566583514 322724777 32106916 35614066 281384293 241129668 641965454 163121022 312062624 27000463 228908912 964826957 368729231 392417961 643897895 57149835 356740376 519619012 709494202 409094714 365971779 575473390 912929399 682359490 623545064 504239850 495535019 861703613 340505597 864475704 135465540 564125543 885772624 629210041 504310482 97191573 741572893 897151224 939687246 143500502 550136143 260617133 498781419 360356434 318589167 738644301 256477494 350401173 25942510 611543379 880875514 755312501 787854061 68069300 78917884 294911662 150145399 761785715 895909481 21414191 788902692 546103634 896480326 676878013 218651919 852251847 643632414 118875095 852546360 405869269 118366263 985692601 577996334 624411728 602596908 604948356 197587894 923157979 481487005 665124272 20761879 919290504 730909695 764096083 889944659 456301865 123361663 952456817 699061272 616249579 780861752 709506293 468791041 517883865 246743824 649820786 16217296 196347429 824167266 712819766 486207894 768891306 827181095 514358563 367054574 755485701 256117149 860042974 160620960 630401183 199336533 768245317 127019741 875183080 156195020 657056055 639109812 351354196 655146456 728116287 595405038 669902149 176523230 860398137 464675890 458457664 235038318 575512882 604987968 530473477 553767787 795037127 536410932 795254908 172500604 745334244 253622950 861166610 382154041 999672596 229652241 265837537 950479525 981277312 697791007 693637636 225391013 59812373 723228963 470985666 997806151 223695256 77297873 177149121 755147462 603326461 166801620 601937255 947270343 24884502 313813143 192809181 802528303 317791846 109678769 85812021 462250399 266718996 255524586 861159848 488064653 149219067 337241326 676166392 249754880 843452126 777266061 670095860 688390375 334347705 660093613 383738906 721914647 467655117 299629654 518506464 310699823 21105462 733522921 325919562 81344129 65384896 557043557 529019633 346949310 353965886 240258004 262252410 474439468 72023431 378978809 242393009 325075160 416518690 522100142 622365505 443107783 852353677 946895212 423162127 416491332 318790442 841070570 233634611 264474968 755248839 467359196 497319059 808062296 18043080 792322012 855988766 556829592 384202739 941298278 830587810 553692221 557235672 487889918 485759051 455369009 688917211 157154156 104724665 502462767 250074336 347812391 194797053 987460753 450859216 698121391 718356410 20071758 194953173 214963310 777050957 527880114 41798710 33502197 751335933 535244478 522848356 283186207 661612453 974905669 650633174 257437930 151469108 39758677 972975334 949657447 226982841 742300291 446490459 530604168 488863942 701751366 328721166 160106115 746208348 622132254 284216917 630529667 188856393 409534744 451755682 523940429 925845158 751705095 51625947 738845514 326984038 43838753 561224904 492868100 577291293 127275538 469042554 572911947 661104837 819461466 234378698 142470899 959037106 383240038 548809080 35528938 556597418 884534646 519736157 139072656 165265333 586712878 308758776 149678354 943750859 87921320 948472260 643277764 808852623 513654613 459905068 257676055 592585178 183254270 979229725 808410822 385926518 800104109 338616190 63599089 998714934 578503262 442378125 364569557 212929567 252541250 620562477 982535876 44904623 270551720 507872548 869039279 466898216 585146101 115058171 299132674 277301987 494044961 385959935 634543675 357205755 747388748 485149221 855183573 563854261 65264088 173138536 46018147 672348060 889542476 123314811 992456066 886625079 827075552 602560866 262788984 589214477 503798392 822989164 204988709 201211529 319377889 751914940 199411670 415259063 733714577 635218216 212845683 554144880 824850232 723359572 239496108 429747517 654646094 842707389 68446075 653024671 12901343 149539576 670635023 613485257 10186207 997840654 101011825 662963912 211174459 484391201 760688468 910127980 721489280 637464425 580933767 932522449 275017113 384949961 774032259 572030601 853771189 584051725 532532772 817673831 504354375 336987843 439834229 100671978 399385383 105293234 54700196 498521925 201621462 426366203 613858325 857116935 544869855 17640907 114295186 819801452 229755736 506474427 630848159 910532671 46719880 59071940 372983275 390265194 570052834 770477795 681722396 744402864 44962372 935460961 595433621 344162187 398950188 407476354 855873681 237410409 474454422 457502799 716716399 494723632 155721788 722111133 223694096 302742620 62730049 991248156 857787865 702074352 145680806 482854439 874178571 959083515 433807009 117571260 462108981 781960027 674819199 367448123 799330155 123044206 703586341 242530777 513059556 54039952 685657781 60381333 786924464 841850051 532633702 571842203 665098302 511487022 343538106 188201964 162922513 496272460 104734803 378661891 256782354 58420586 646789579 660958933 499120238 127742183 625170044 570955734 32827908 214420548 770570048 302386811 767620249 58105703 49842027 161007077 384190045 110887297 828486133 826194615 378705496 209426151 455760508 575192320 210163788 351076908 32148725 654408375 316726524 85420479 878182701 852285368 69297074 93746904 535506337 185429127 810120085 103479258 32127218 231942895 711991937 930123282 388547183 754566499 432907056 321307998 235267018 528150858 709516361 482152496 210390572 779740072 11641019 549181259 964491362 840663659 773089343 799282458 543843892 690003028 382815743 539422893 743765206 384677760 10795861 967331409 615626872 180870291 657401516 37659082 666435320 230946944 44558467 498162735 107673016 147923190 417186448 398482787 189625993 436531050 58486017 470900011 896468934 770308285 486305245 912921073 565742462 610051209 871722953 976327951 1793383 305649898 181045307 236634521 279610963 940334711 638764607 57290467 649945083 444407771 934671499 984531887 986420998 743903529 953375308 318596197 695574962 788692874 470400762 661788170 625463245 5061235 552885185 439074584 786491759 537975671 133510264 415438818 677847195 626800182 773289632 763406669 560806242 668539379 130635041 884521663 124276576 558473920 515630941 390150504 793519258 617363543 824390984 918942881 607675120 645368739 685986070 131548107 328308657 935054716 529922315 956600479 857651728 451327476 80016539 979614549 254268119 2809670 504259967 258150215 209151290 704958022 561077755 447449415 778977606 880293485 912591172 929949665 949389075 762035216 626439606 788825966 396229274 607290400 570875526 143670409 994675110 43687780 383615136 834064555 561410183 577289265 588155095 626907509 31857310 341860296 178655031 61669532 533019895 301452108 906241910 465969265 228498704 785699422 321901193 511738636 686473656 438721879 878239252 759800339 827952929 521037433 551579438 262599866 184165042 545284946 601673472 26876159 243321382 763527161 272275681 169744974 371238265 672096388 194294047 31221679 490800862 26597198 892758508 564492647 459024496 710344421 355409744 45596751 129247552 149966300 191739345 751189839 341059730 472735693 388624225 474706086 27862075 703985828 743887738 393222219 902150511 958364603 16388621 336347660 724604385 346761752 984554299 625126335 441380621 607951083 98848428 497394320 421291043 706031667 324713616 584633210 983627915 520734593 542094033 857998384 582371579 566929359 43301284 299165283 290433599 284843081 769096187 740580171 21161909 654301385 45364157 66152747 138634077 908380639 638690312 370895051 759494476 559717045 111233206 107466184 314334721 364107765 709278720 599304853 40497622 645192023 986572860 111129618 348693906 154067402 244413895 699095751 778554907 851574846 717340413 166409661 592553801 274149477 492675321 41126869 399886230 555581040 318178064 43454532 508640126 580658160 126518665 559799670 685845188 553261221 816181270 670238064 4751521 501392586 54808380 90128340 692661258 595844119 947386503 118748629 416750058 182363252 373204564 919118652 650081025 538160071 41384504 710140293 160811353 596690158 867035665 976654118 745872736 567501257 278852775 881085038 181357309 145197452 131665462 786195328 787680058 209172776 356859289 788188719 213502764 877870891 50244580 507705989 377392677 206241262 742304712 705310852 671002564 747770821 39055295 485687170 226382590 191779134 22570821 824920038 117019732 951096990 152957931 572748760 120819245 298956186 968470410 452481159 131277663 832140464 322695573 299168278 411132364 58960264 524200996 349710121 621014667 178827901 346985206 67896282 744886566 351111645 541135683 618873849 119521179 650692403 805396637 828842614 924585340 969114396 608271479 520663640 811044196 987061595 649923543 26586658 850637228 299921929 248956313 421454161 934577351 604750313 223781213 928206337 277492539 291920858 350149902 75026237 390069605 871558774 800698117 133631000 791781928 284889320 327981753 390248631 857000215 880187334 231647389 827498456 552842482 615981105 103075502 797404583 374695878 552057103 256953728 392569282 989892713 7895981 954686419 706347234 117237408 591140898 758748166 912233987 974616196 293959512 244452414 818633981 329747152 400693922 757821205 461686357 97559135 658694044 688435317 567100376 242936885 482094607 878917313 698145853 949595687 26707235 121081372 995248990 299334139 555300535 453779347 287338467 872803045 364842038 30057739 45602495 266333010 671075398 322024289 811205267 488080727 595174053 512649691 381657402 934946456 607125587 169776152 505226670 406369969 695021491 948655073 954391931 744701067 559842251 524535426 780889223 216116924 971152998 734511080 270715339 613450007 566181210 592192005 135025446 597269846 847854960 570283171 184703748 970028771 67072359 263392065 358788660 812781891 537035538 960336004 795839704 77792031 412504220 60789596 990092405 836182000 290433460 5066026 817238599 850853923 693970645 980449278 498113207 288331586 61782360 303324754 933853024 586957801 459047622 915189784 610005818 700257486 399743830 760064311 733833948 130133537 83200340 876500223 257411310 177836594 872421798 672746797 558809333 141334054 726094338 75769744 931224906 539228688 479809744 742213775 124686761 181120712 709305505 92677347 261536624 985642384 540185698 681197685 162179645 459534761 455757446 78569793 285010468 797424897 880690386 45467223 334812045 989688841 216051909 211021051 272209573 197176481 726521837 908843663 65591357 987231002 620416195 835335159 352047345 209076634 427682705 864573929 200104239 911620587 310657027 361571529 1626642 27134433 760227710 441320004 825243093 449884329 956696828 938463688 27130408 472791867 127123736 996437079 102043719 369210453 745111177 571618422 97617668 68681407 653867580 793605484 462111657 386894606 587058831 540766512 621005412 128026388 29454591 431583461 695689026 480354404 397954322 833056157 589551563 11952440 573367958 654213543 757900143 714892716 889734893 883210325 432676930 933859022 571220835 828298728 118385090 481750920 336164370 200409516 440731949 841758310 747726307 564268464 286362048 766593070 106254065 189366591 45480708 541599940 1438187 804415550 3663180 468570348 224449453 558005185 197921250 372685357 525254779 899927995 731313107 976621776 950138586 378469325 567435604 758172680 985316874 468632383 945094096 803393579 369068067 936721420 609731870 170928586 267827479 973763588 723163537 365130620 783106995 547179997 937519874 817819325 17245266 564948164 786644908 143570185 655717520 731017675 511756398 223270161 966621257 465214009 671474941 399559238 301030824 564482898 30151871 369877537 863013005 520684676 760898786 571664840 363103734 998619672 156965257 122045529 281870713 118276501 259404320 752738261 650805997 905237938 923960528 13092905 468698101 913827086 103963617 110053092 619424748 12695374 480371161 629216444 403739655 719228374 886377414 374869330 727105709 506830250 71301266 640883017 42917042 580413707 517509904 489016264 2766386 653804686 929112978 162996271 578302495 224993434 540467738 688192238 79480588 828624724 837792851 209379692 907963292 129735757 211062577 682010655 142056096 711927691 831805400 606174086 191065770 181367064 38457676 888647007 883957789 557813382 206990847 127767691 797473937 89455416 785832602 50317572 473626140 556412739 686820742 546228213 473260703 626825682 988113140 627462218 421502319 417467376 53637103 157231267 639779802 798930973 387522368 930167442 934210876 546372436 533338941 217695823 480784718 944608895 546278557 776870577 434611394 353946690 521499017 916474311 842215581 412511223 240251991 623911192 729329448 404989170 555306730 142882604 321237647 943230703 684112505 226063008 113439226 743026132 294640595 438513277 853786779 979498740 224803155 590747054 750957340 124236118 87271715 827224856 11840345 868672481 579591429 995471713 655031865 619645223 102825220 803989230 701787479 708995019 373319776 665480633 139552586 149645717 5720687 233787353 890231669 219533332 572226341 3791905 198628183 630674478 748142585 905701644 542607052 535679444 3309058 541763723 894584039 818371611 788426278 651722197 720356067 963429072 733553894 644024540 870042677 754979460 695648719 963397135 906588958 813178152 585409803 969206659 797678997 242668098 161946131 585241791 770826818 776722634 21542786 990285604 584666023 808733859 815429637 375180023 593478490 45471673 980992623 871319917 917536435 516648681 305253138 904850926 89162069 183796550 909812853 57454217 439518326 265979509 23015411 974816844 251962776 528239888 105191871 156749699 861739561 419668241 27041355 318091202 382520405 472642211 26991542 636352513 938895750 60284950 465054162 246769377 689094777 301005008 348735245 661660414 756876818 252171403 374900556 976549485 497180498 204162302 185523458 906678786 19289126 171745198 961720104 270314519 179976543 102285613 651576471 689919630 933518839 547429212 755279242 599910594 492823009 302270890 140250225 178789521 247242567 660626442 962692588 440452687 863791718 743398324 254041492 435805049 912129331 658750450 863517883 739521070 798782590 127461081 745597888 991435851 652976033 700787305 181322748 779240305 290049593 903301626 725386476 938537443 682342745 579804199 254968944 789976286 300531759 327792366 832305711 626294267 218562216 250397699 112477490 714654684 69542793 587135052 332946640 682899238 473187555 7606380 201540976 202962716 225835429 897750508 193641837 726381529 63327308 185596680 782279698 609509418 971909301 507301140 582714564 843107589 475034386 707458441 187315263 632283306 869116411 356238768 166987093 4269980 511823594 315330978 530480653 266599834 643751020 368753855 911588527 626551464 992120475 261657361 272951761 716727783 753458730 170289666 103200807 891711168 988562713 215377153 31840707 244383503 400151525 480364971 34008217 159655842 166418408 724152242 558200327 24764382 100919910 279304479 802830883 643485719 906893774 545555858 834496748 123151901 836822033 648155809 221857503 897973479 308890962 998741453 246306739 950304211 846596899 113381819 487016303 92835159 603952137 923343744 283787617 640005594 529376892 387112351 190720177 725986405 982616747 759357522 726053346 722463990 911810257 764001911 303459447 826453124 576763551 375069463 212230322 61286032 840793561 864200083 694800485 223784445 14279789 924385360 357984748 768517405 15235760 754054538 301931566 575036366 169442813 298972284 57157478 289487417 420586471 260634818 447499343 612967867 504346745 141570998 343752473 505629550 181517053 298235693 725410595 850902859 539608878 696994364 949918168 832415445 245579511 242175433 501525116 987235834 855001336 145579764 268119127 523032322 884456308 145341974 564196813 926603866 176910756 572247927 989615925 178889758 669054388 677671309 238483599 532028403 114427392 720897456 843351377 381022426 232551549 614193925 136087245 183290621 635519824 694571174 140279836 980698865 636742265 291949677 16625686 44141707 688875180 626941538 781512573 759044444 390208320 409502398 145642809 207044810 913618752 951945372 650019518 857636300 15416736 477498171 311276170 845513281 179734665 611940850 262264522 525039598 236023765 331608241 525245468 323999506 604466839 72049263 93733544 627457489 570690742 142947335 494179385 985973321 385181831 242976413 767588699 565804405 968666346 56826531 86488777 709580691 86675159 812599461 499976480 673025237 346334778 739463371 218480436 902775226 884421351 274087035 387680269 705015928 467334170 25717275 687637121 438849429 575061161 340355316 722079855 243534741 425488690 205110165 668639694 228923912 899898383 273797207 837037454 834881008 896524909 12757791 404893788 162901264 96100719 440191002 365519358 328758712 978395285 869648195 269799688 398209292 300208555 255425333 721353647 411125854 616735696 997543495 330023118 325208219 349439370 938653210 608242938 490673717 657609024 438411617 794619469 836392861 696041732 573802952 867170921 112204639 23172642 446001164 876305968 82357754 971504565 393675194 698284309 321142974 525137072 254541302 120257467 208046013 110001866 389372733 539524897 841497983 120959347 987885086 932875460 614483883 32992931 223721620 793866827 689347304 226962228 23777804 113881538 577037552 312521717 59034623 317768780 193342429 443039139 980805413 176056242 918161756 909566208 827766087 939271927 340117584 757111588 314413490 486157832 222222527 895206767 570241813 293724745 147360756 695960461 751547387 573012005 206724204 413344949 630495670 180262863 59461646 56252919 931494470 845181617 436992202 667732354 240411108 31635053 484554861 690525952 969801040 524120009 309243456 583154060 986200901 999501880 551843021 255954257 662338830 362692097 757293505 634538176 603602483 618307342 931514861 399639883 258253908 419339111 763602567 610649589 107152857 254166477 740133618 412655975 769108137 373861123 820544777 523498443 823556080 873243607 818342654 140280010 712804005 548434000 560004445 971412898 865325467 870355885 647786848 769095224 261311063 472360389 603137168 327276771 305943059 240829664 350625433 722666195 291886815 895528754 645736502 803389215 379421923 518066677 110854987 926012523 213548991 95780386 593318417 567085075 527541451 459411819 788970678 718444314 64665368 608245848 893398145 196319857 561081308 233465474 719853206 3740662 605506771 246138867 838990393 342784972 515934075 137791463 323075416 935342202 482789525 856646451 887773460 360951557 666140145 362294320 468181555 701818815 95813654 154867513 964418160 985939355 191716929 984808516 267057591 242958202 588581578 838034996 658675952 785262583 352266321 947992514 879178301 700833309 432870791 597293177 565380304 199326009 684869014 814608859 73215078 343076811 472480558 616471201 392600163 608863126 963111469 727169056 273361547 625712343 996847082 681661895 177199450 322889362 282493983 967398085 457143810 106995207 180541040 618377159 13637119 394391876 732889244 694804703 397542488 587802943 776438144 661215860 543887509 488278849 25081510 554327189 918782943 520905491 892012534 328326017 980653491 127025789 53629469 659093539 603223585 569260061 682041171 43072772 808824268 617279337 419950607 844260379 638604269 353383083 952768113 659303287 855464923 679678422 635568709 806017018 115550717 792122381 949423231 567602837 259191196 544575082 854134753 755287369 446234008 679918349 373416798 456483926 122768949 27326122 193450829 220632804 887530404 338951776 183461609 47144052 548488614 553550832 668564569 340859765 895389618 751921564 407081966 696499447 914017727 489778731 872725240 636903287 202874122 836745797 743963352 206838104 18971276 670280563 906990895 335572050 116026497 467853893 381972371 221130694 871939966 42378823 540125364 941845697 865188142 689732827 54359326 26506829 786161101 381260130 715849446 46152068 886670866 765223279 456736001 971649285 345332697 819570541 108586165 501054472 340805469 56611086 738546819 491649100 46345638 162666810 587617966 507807666 385308483 369964161 692533990 295398155 487977582 769935293 55035331 222065162 139169163 391343926 158891385 828469069 82679862 610478714 945877850 916097260 39145384 850265259 510727745 444025542 309083450 506337902 612864159 757581432 301775612 115567907 953326381 778771166 545169494 773650438 147769674 984510770 207395989 272725472 505248893 764733023 621940618 63557644 395722407 764224118 440682145 307730971 511539374 659905642 882673651 798406287 714765443 601665690 120220479 209126017 366036553 331672594 6868122 56717450 695205732 681731049 965161740 682407104 100983808 561334786 760234617 497252829 501184393 92966789 805972966 146201904 382770180 771941479 442127159 297423413 842055334 918396305 335663891 21807487 132452271 140040931 378780964 753415763 927162520 56610042 138008085 825908361 749341525 884148569 16345149 907559120 302812005 142487093 596838171 366067659 379555802 579126367 114090841 84744127 554946651 566809585 983511117 571688046 819324233 271860041 701950333 305398103 95907308 743115644 42293506 330691360 733008476 479141359 398803867 57201867 554125683 862875484 327501121 746404364 736389646 167789661 966886084 773142437 214253499 120304156 609433376 768772113 776102864 908009832 195729713 870026390 708952822 391200740 880053145 447780364 203301722 447339045 317329503 204822321 779344908 227536014 201743956 712442054 71122294 615193418 99658010 400349655 285322617 643479380 195111893 377431064 772852005 118719155 727636594 259222635 730039748 714836879 781353343 185774949 824254214 472167570 224662012 678955289 484105814 338338110 159960635 393259506 880356218 791909101 208165241 476885023 978957546 146514514 641168772 70776947 717134579 193480859 573887579 976171195 179186585 151317632 915916668 686325338 882947928 854441644 768997102 198843913 670188993 187171142 259598447 67727634 677965618 201789274 177023863 999453324 726862090 218880756 559517951 440721788 691399956 360212810 292553212 375771343 521766797 229139321 365198435 223916136 248388175 501503807 994739629 31451721 197079172 471079140 96636721 834373694 105135678 878311766 874938264 835504226 123918509 630313751 271358010 620436686 389083089 714941247 676377500 426144815 310896704 519930583 381661163 891248511 448486149 641052714 167726414 173842718 333176625 908528754 772673348 740363660 458046497 937556009 755248577 915328100 861777869 264418520 232147241 161833991 313363896 856381033 254079296 286874703 405551099 281351195 197551813 433805524 707536719 31800141 324928158 327644477 330203559 225478728 448913721 436198991 142896982 638648824 358653546 565574004 204112979 408023658 928192133 993155015 391797727 20748768 22925597 218793860 70957216 28241947 975698302 914977556 982155298 173212081 343113046 649568174 430494573 272690143 422315639 519175083 890700832 189715242 968531374 467859183 838898932 477765146 432032750 90250225 514087706 403173369 210918273 144160763 789882304 749126441 768912472 312903710 238297011 288361250 188974979 923865782 792730399 231394824 852658620 11123093 485164401 347467749 669174557 82927823 119744861 476099464 818337778 517017122 724040953 245541033 666045183 984677900 947115927 129059046 573599545 27158481 402881971 776524361 960787519 525005437 559686869 640667452 996976445 715105240 627122489 812116794 93795530 423693339 561772685 140058803 973112300 510822695 751987843 554417451 984143281 798841234 524676061 282873994 769256045 162230643 700244612 854077573 910304499 71019640 422762332 19193647 353833360 61714120 449508454 963189334 684543576 197702636 443360351 502397305 898615430 22131047 87166327 902991776 584700027 468943223 319018887 227391274 187635779 580623966 949149625 849229744 938505832 392065200 128147262 846193471 348025405 310222070 486874778 835418175 416614760 297867227 158251756 527783575 581764423 723989478 187598564 410144189 128565721 145495276 839147021 195788086 860830978 984826876 550558610 617187454 814695804 586743731 423754571 378470912 917508275 139246606 944123951 256834625 925660224 329215318 326235391 800164959 23201704 541957418 494313816 425471528 303211833 791149029 342767747 552117463 408205307 401788621 371255665 70289478 545757631 605219327 644201889 681370044 276357209 778204698 432550451 496759807 865746207 249819583 722819764 249631427 701231629 484536492 813119240 945072820 749612741 238086658 225697855 710440376 258530507 404425200 918388910 21347012 351351602 372674681 884339133 760362536 859584877 596744952 188407045 93823345 13124074 103450449 712057138 86820260 773576395 454289338 801308931 328669975 591378862 458290976 874441326 564679403 474963112 426553399 615393761 544642089 298328657 84730145 385620900 991214200 726013689 22157754 40133466 508390009 823815929 788598398 280982951 124473791 797003299 214490136 446594539 386467950 90000475 407150472 407907371 869386351 805065023 670745839 910783249 289676877 30591746 4151546 407654922 498634159 160646230 297467625 510411661 121174386 325312391 468360507 482371964 76596578 686154405 240579320 270094242 256161174 640795866 408754074 331407453 373214565 339070682 287120725 855194632 109524087 783667090 344760938 899106510 98949460 66455571 472553644 273292534 615857842 335426860 885320806 704932278 397559791 267286691 297997035 641150595 977551338 467654603 34216084 928707871 287898090 477538479 448561626 797497474 746830467 160847087 155369683 670843248 528035268 702520484 709423890 402737429 382692557 309895065 8611129 356291238 616367606 334186111 378563127 883672859 49862548 253041388 868150224 248928513 995086125 390364436 503634182 177857928 326991778 30776981 358403162 600729340 486377960 991514813 423083567 755019604 769991569 83057992 243600743 144856516 309474803 279655321 514576238 296352247 696232987 605574384 704271672 430516864 796789408 891345827 162117817 832596341 911582824 377252108 15223884 407116141 574915357 561810536 292076615 343154184 185869610 451317062 175268482 597271983 190228732 338852335 844090776 108029779 843407867 208579249 388435500 761567484 829280158 901590711 33067882 823728662 969375574 252206988 378904132 98310020 964317261 173732934 40459373 634681170 505294711 457310760 770602308 561079188 971080079 957676710 29576627 432626106 754213123 123499005 237821735 937384700 414015103 904059901 713247277 500681199 112136724 351287462 241248058 693183237 614060657 967904679 238833506 337549358 137629926 737370863 358053312 56827666 262169706 27028997 857184405 782172031 223603291 406847726 121090612 663216096 28919508 262036616 157114717 541523019 191624326 262217386 183391029 712816474 330230025 612211023 639630491 813804524 224163486 380142764 149830458 921293597 466982076 454383185 426662520 88256434 339904182 341017785 508920298 107727513 186725818 884832729 216409787 990092522 409054814 948208885 779529791 419195187 541398154 527060797 175141101 476596720 270151316 420309243 561435930 672577942 686145131 960833684 843114710 124515550 612918476 862214585 178443598 351346866 212063091 870145969 689871261 49781293 499271446 172216878 417249764 300960347 965553862 418943486 256045690 799517309 351379310 439736170 433278016 361569529 734535031 648904239 227731086 597138710 23794009 62345758 871300989 425354546 850345405 922465337 368731190 48865974 559549944
