5000
409894089 800959381 763637953 625043107 54804727 788127312 261747332 207791577 881224536 65359280 341570224 82685886 765826713 59645868 51076715 412924604 645044081 295408763 319660882 307622569 651787759 706073133 942357623 268036000 243506876 357156725 516774919 564519570 605708662 38749584 651662091 202613777 651491331 853234035 191351573 720592017 274396143 242406400 525050858 700591975 998031031 594643161 66942712 959963137 773642507 79013514 475017884 768151627 102119033 14129083 147940837 162045481 296944797 613778358 334162657 924864564 284279719 442464718 546238482 497764091 93600573 919968343 117446261 648854576 260975534 194019564 366446992 663595556 374173599 276369887 834281722 115740960 669989127 746378377 916540379 204754424 254793489 419254232 626430338 659697500 740659061 974399109 236118833 782702670 21510851 481568888 641826933 773513461 784817189 747653760 394133090 623998699 102943724 406766475 666439608 482359873 534013160 587450898 939230924 993503719 774284029 553803189 988015881 64235219 105029839 581996456 709954972 725367540 671968339 671290140 714705725 807835951 928714539 220375476 164217947 383569599 179347724 557900418 625409024 224885590 210774382 955369716 367775734 260200110 112610100 544219371 767362976 449108878 494806918 41119036 798783975 653743237 891274004 564647387 927212706 329354417 271779501 704033296 628611061 677891373 614524337 126936854 348127720 125621456 175110916 549400980 173822527 314394462 56274323 733657634 160298667 463175537 665877726 923378748 664530646 601666461 626521671 995553249 385726113 982480093 52506902 249289161 697376957 828740429 8932997 239078682 151443940 482675508 424295443 588632207 816157261 234424470 46964653 69787413 771766469 753978588 511281425 793880676 31456898 506182779 445399290 602542039 460395572 508192242 214752627 178172469 346234693 52555503 514283766 950800301 944830409 984750801 834486154 861144179 781947898 163292751 374466464 804633450 771421040 813433395 396817135 779407103 781484217 668881265 276200827 615224861 610774583 820711056 901296254 494364592 155434897 381969105 61866683 508187027 536379086 384585197 254935169 35562028 391243167 836762629 835724504 699229042 327549362 157725221 149370010 623929221 296350436 185323073 64684371 903080727 68730404 170076756 4066093 681269381 783335364 645729448 310473441 733392289 217821809 881001737 167505907 94733873 483441720 283654517 260791730 304923681 183132860 442771526 212950717 195868769 475924968 300954062 314821825 385635282 356936970 917637 424210456 351573169 717181190 857032996 644152287 608769315 46019275 843504776 879807674 948124476 956101573 965156550 937509581 927983371 749075955 616756992 142417554 439617478 677667125 669480 995817156 828925465 410961097 965732587 257868417 205609534 178620979 447161223 104578190 904793192 352031473 514979918 531456956 630714317 326965832 550325656 648819491 655492094 456461107 823794694 978284905 174661660 339799885 906789130 193886897 757322529 32146354 917396542 861349101 858683348 356780344 118527675 708032045 907817384 723325774 241097696 803094852 185980985 281196484 304788118 109035026 819871477 202601479 573587172 746639610 867153976 764255028 676694289 184956911 621641243 317126995 531074374 90307994 966261217 453199624 320633499 774972822 222391327 687737146 971067667 447294821 733932458 526604807 35386364 449529976 679456507 3800659 236914927 782809706 161251250 116957404 665896950 627942982 800243526 509777986 285774062 891267671 452754395 675545748 888186554 923533002 147283326 574509571 961354884 160615843 718828945 604352637 132016954 361233926 601523041 680252947 414409275 488103337 325385582 733809388 537044894 450307170 311680148 75714790 858258730 706427965 192654926 244550507 65797213 987707870 281750759 43812494 224765749 728534695 318860380 670787891 292572937 473610160 916623272 203174271 12443946 725230306 135131641 445523876 856558122 245310349 285308930 231626378 714078666 8484791 744239609 132641640 578202496 606213696 514468174 519229129 217590044 446234920 766449453 547487861 269487931 656242644 476251820 944373768 311274591 667743483 826877035 970650869 585336894 980619389 584766888 359632317 518883565 413341605 631380645 7401466 842328808 694688042 108951356 49451455 870087296 939464869 455630432 707593244 608613430 786795626 15079158 56217187 549821127 85377363 393760509 663886595 920013422 781637307 123710390 750044994 489210975 828681056 957298306 956619537 670253930 338083075 18337675 444177518 573208733 725753820 439298750 668747429 6134531 993493339 920159341 176519830 335552121 440792653 311905576 598286066 391159251 370273337 716032249 311908293 317222271 838340667 131932047 615360051 757894821 800042874 285512328 593514225 479917685 299163712 204939462 265140664 196792419 569657604 660261341 93537188 49685712 785613658 58376106 489778195 955923515 170009852 54104798 674691948 329064639 209172597 470107239 810486685 281880020 126902469 289544596 886605387 143133742 313660128 262655348 283784632 168351919 356901695 363564196 544685956 103248720 374174862 418468116 964467915 890831723 971430365 751283911 740367508 616187684 121059093 616089954 587677597 450295450 148013280 716794206 341139629 85772410 837035267 51993964 684047152 398898837 989254787 459948994 734767866 690427826 882181096 71471879 288131154 879774303 771776727 59515367 617116323 520152738 573876186 906282674 538364919 750520194 342049771 819643601 559780500 608785283 347425529 905440375 728130208 912780385 847990829 96534924 747300831 898054467 955315917 656113001 935701277 214712716 751055237 243950870 42896020 954930917 630387236 46862742 530657470 95771454 365444107 532228348 120010746 203351180 16490707 917687945 961364754 13051809 268076973 916553125 328461416 997498324 387464849 569955597 285662598 402998403 859436405 299975400 770146750 228682626 716661007 768527030 16110410 960871266 749869687 637553447 74564271 678838333 710013549 885293051 341653697 19332621 878598502 490746112 383656043 995849402 809564905 983624576 111185539 788546179 31192006 446511207 523108310 624376244 853477974 842057301 701883027 609978125 643203970 795353257 562613965 985896312 468025055 431933608 314333369 626129823 137681035 221159377 43199289 344062799 384102259 602708242 628178884 864672482 729519907 853652308 558749527 284306045 468975709 581465399 659466021 588803169 510985087 379962811 18327357 35956169 650997490 312894189 736135253 712872999 176297737 869044295 711169012 715299093 312160815 89730980 417969626 92762679 811968727 827848797 565694928 894580754 464208955 848509955 954966532 565463331 363804796 727363866 507284506 75739705 623355447 218495202 834581857 703481675 285996126 286301896 494003930 265605594 724410115 53267715 361308634 411094261 969701618 359574723 538022276 976067440 545365141 217871475 257512923 43343338 986358471 820930534 410754573 209272019 876515706 53866801 43561951 579758160 286491410 189475389 846039835 438812175 267193864 502117754 36061011 387311441 762499120 288378821 202172107 596103086 130369473 485051162 798259902 821841692 224820345 750228675 821573737 906549795 559608813 556170647 666116488 221493511 568130053 122381902 947851346 187756026 76666700 36002801 898900135 994324066 406684586 608142996 266629521 469188557 797496407 398098433 758170529 757232213 556093177 492055902 862734821 936570287 733514877 22624172 383666672 883487532 404429042 128150375 240778401 784547648 695454130 500626778 953110754 15739504 93260125 263955225 218042738 48920197 385205355 773257205 622057520 578408686 558481708 430535013 666133825 210311701 990114487 807739263 43561444 205598666 118597035 756190912 343191831 97155118 896872100 875317639 286208263 142663840 222757793 116181182 353744879 638586958 867864549 583573385 370589379 955563777 781457729 729232036 797650966 475969326 388445745 244223904 582502202 837266768 366557923 3654115 453184662 623868631 501450993 24637811 42462491 112795653 220774014 726091423 42257363 391053724 795011742 610564568 831511721 447958974 194070707 509489462 152995786 205203602 390714130 681474819 567625690 50649298 88646656 143101392 915653114 150256526 564673862 640833263 530919311 388850473 416239828 386513271 61608704 569778131 347583594 905999976 733787310 140690272 100186914 156166843 58388739 324365400 233963911 476853782 789168518 404771614 37019064 875174299 384705958 92883340 985609171 467573771 674749856 702102842 134800358 189332883 597913003 113016235 255854931 424175144 103242978 35531476 322233514 484120699 504904570 726301905 714901740 532090125 428894753 696403757 432272056 150756927 559891400 889183044 369335688 773498997 370130162 779597835 89475137 249011674 731163488 204846077 762993147 753432113 706906912 497888684 892934396 289307176 337691457 851863710 838096901 689041755 665567836 467890122 83222150 979408672 9638771 63064160 212785288 921806117 211693009 336206931 832826193 542668785 187846933 520910386 185586163 556152942 12286601 580731027 427707272 306797232 157512930 59581327 664307436 839992897 970406228 741039896 612286604 620722951 705376977 414136242 467364668 298937499 422531350 364394086 956760671 808309696 533560031 858065358 375761597 645553938 258327584 289408415 64834694 161058813 200676587 796763116 808733221 927841199 833599594 679232594 819889872 129615073 328615747 47727508 249262891 937404856 272949320 830823479 159222149 104355782 562806662 668155511 862700230 950548210 77701419 302110127 629349448 109880850 605917810 156737588 13538319 891223400 705094793 244810496 839677329 878187950 642218312 577158440 95620390 298048015 574276616 452513043 619736958 76010073 910572742 642164015 386843922 756069878 934026524 445629100 804355172 82577005 848211323 674721626 250453194 50598179 623717750 280863945 170064231 789424668 237446506 784303603 951791238 335215614 318982007 920269677 452668969 251006131 951789082 667853316 583133722 972920597 114647094 810261784 673888233 658151649 918158727 304489826 65853736 244256884 326274982 384103328 485170177 900701921 393983602 141757265 455980840 71083530 920164460 513747487 532411569 21282016 557992736 311800192 765209051 447952582 877232073 720541814 40906305 152735826 822878871 366744698 409250391 663198275 698339408 211279168 113957122 417757649 831821058 308323827 505321486 648879452 365818090 343079261 764126789 810598593 347681598 275744492 811064158 725299688 658474311 472239201 701340532 585959885 34979437 478530810 988462937 609065112 316471590 417286053 255623009 681918780 703221162 171680127 805614649 908511834 76906167 159588022 153473453 692266313 120328741 262771414 978560122 626812221 48517165 583496331 436152107 285025341 680865498 410680162 167324258 189781092 336354110 460027709 688130135 829565184 106830008 739137478 936392893 293149561 633687294 378197437 883526362 52152378 395334096 723810763 148100333 203203842 862063539 498037439 866418880 223749444 76767868 46619794 296824497 310323249 207773194 219980856 606949905 410040198 942334537 209913429 324147218 67876380 204041826 349200568 889401767 281935633 617664449 828204946 722047080 590818013 302365054 611403912 934324142 717368446 782132496 921264242 992745892 678329226 909850420 742740677 71311099 528079989 926470575 525637951 177631456 551684079 424481031 365805456 452857154 752006940 370410833 618025027 47206797 552023365 257379104 947145360 520028612 578807516 423218507 925223759 596925401 808723584 896694493 874394491 183777592 603112402 833331280 696141166 564338883 411547916 55428183 971268273 966684586 195365306 68421164 440196435 847719212 486260636 359898366 574382190 777741246 418222787 535281375 836671674 334715657 917594068 976694221 276097527 631056862 799395049 378659944 717304542 448510032 534421261 849250785 175057193 519381139 406584924 358562481 778238848 594286305 8443081 8890777 571806087 771465931 863013521 293628452 390029627 817229698 109356630 164161631 915699358 220187989 730542650 364140308 479156604 670799053 219219309 314768282 50936431 841785575 416063139 414237818 808324 882807757 356597641 498777313 96839259 224810949 579077738 68760481 573181726 237460043 907307464 430704104 85224484 226709339 68835335 400234426 159877521 888078633 226096204 320354312 444868060 649628351 783665372 239720271 965677040 550350466 715659551 800562827 792376647 362794202 626800442 168466735 855858952 799712576 187633021 488608895 663726567 445809087 547731615 758443139 400953391 938023783 135676033 76811067 779473532 913048105 883470750 6024322 413483846 711454243 240268057 278564368 652261530 648943470 482699464 831601318 249182193 685829786 243657186 982923790 683149458 912094773 794144351 289769228 537834388 429875689 947016671 934207297 384852344 124682963 661157707 265511510 761270332 548969697 407738175 141081666 140799903 287382870 777003479 527476780 752227137 676434464 910826302 779895315 821166718 570403342 635950536 125768052 215727047 357356080 900960219 741683271 441660260 240500871 740388013 120015267 181245831 660773171 994803892 687839220 630675925 396312137 111573511 533326546 124782496 856854146 613859622 142265206 545496255 520841914 827358064 596624274 708740883 808576889 863962831 296238699 293399725 350053588 877360721 523380850 953689438 352043495 111243059 703858503 108292703 6282443 329108446 493823185 876656065 101532521 736296054 893355151 589998331 209936524 737821087 912051615 802345828 180373976 954357522 294396982 105750156 328095242 748587924 951606981 703959093 833750400 193012674 115202869 611176923 715115145 598525634 519932306 453294273 138879585 827639011 379539181 191662876 309872428 60447152 132238210 770208214 971429932 27992655 665587493 258897702 996856824 983865904 257092078 690098893 720339365 401517381 923568758 557625504 579773359 430602644 6348967 584547093 205335862 915544549 503113688 800474333 920538954 487670223 997400239 503482826 499581301 907044139 301766254 919970691 15401434 541743269 280359756 292456690 938272160 621049305 986220640 98574427 739102604 139837050 37507614 226328537 554802914 672597651 497244224 351975070 633671240 438089332 934493837 847409388 39447015 494530973 909696156 462091901 214558482 222583407 392204795 625836356 560418622 267074242 305022379 571777953 529564826 456065132 506430636 304471452 159709542 654822906 74257619 936693454 609627734 232003473 480124138 81113131 140493504 433242264 709247732 412456429 223938854 784639305 233974604 416654356 294043752 424501136 347758763 230678897 178691611 438306454 47026185 556725252 59129050 707248616 172078719 418879846 575171778 208057856 542607184 510741275 600205902 169303836 443112216 80967181 192891061 414823607 862018445 749246731 197502003 390238081 398636350 494358383 156226632 542564424 502921016 300989612 865375063 444231114 118835496 483237770 73088719 170772679 941191376 167720036 150748156 545889777 636165218 955045917 540848241 717260476 701488057 476215680 173937064 405279345 888966783 437632979 816571929 78056827 93103710 958879228 353769816 310855107 228826337 970121884 644207445 686449552 469276657 629291106 154335648 643405538 344782780 705421924 467750291 336598328 235873604 339158809 849738497 67604703 696035642 97044376 711226932 543444708 154454761 94641608 412613036 371747548 68373167 892046803 587626950 13271568 381413502 167537925 822400429 290818367 12327466 791613658 73244683 918749360 310516917 95546192 291971192 302056858 319718952 900869129 453678182 706088968 211853240 465838104 103282456 205856913 580871815 409631525 68213092 117502507 772230079 305983322 12884044 386066304 122217455 897342429 138725683 345290755 83149573 647843814 622118345 810462594 606553124 607880472 710616775 339029511 941418936 649100172 839128623 296849039 742902341 649019388 891532811 959452331 82179594 800762061 468262158 133953977 365422259 15360329 765334924 101635818 831931119 666344582 933326820 761120063 364667457 638341442 586023740 358060282 59034386 504945115 37897001 89845646 399325111 902185605 137403507 453635790 527161349 8573556 763569609 101738880 180662548 191524480 775148589 926815423 229102223 983655365 751213209 279401362 971269319 782755380 375889228 828069871 797511428 341257150 282941862 497381332 639223570 739965333 132543756 504378109 570482835 241273171 846072432 877892480 536917076 976017877 101313666 660411381 904839467 273824951 987256654 203597354 313242730 526880290 337136412 911899663 676093098 288261399 888447449 434947168 219989792 411787485 270840832 221220935 349737925 31138148 63056123 818164940 570095850 81196369 874487497 300736931 663911346 736709945 401720234 245530568 902591308 704019287 962535558 97143943 741933010 476682782 326652118 379191106 489006920 377083488 407744362 24314028 361592369 680673473 401482800 769184397 291062983 594092055 152597873 692598969 97207229 706425736 590321453 898503962 29149851 917758272 768106730 309548279 227680074 472704266 638227717 84521309 860468066 112583357 302404196 361585459 879086039 902595621 929560936 852650966 501100581 780373989 589885963 936117696 804412325 955737991 705426959 729769947 686535046 692581424 681303001 228880340 85362203 620178009 980916043 953072525 603064167 111248810 219331698 430086404 593537218 894999749 264662676 429962141 146920822 442811098 571943080 585440820 558000465 5756971 104534655 199654076 579679923 444231804 138509699 559887320 77861131 348957383 693921150 293560779 261117668 413765742 806368997 701530618 955291328 324663356 38590100 527942897 517368770 722002201 170846436 254414911 726854872 526856069 927019178 305343665 600481396 158273461 105942069 771827254 653321014 693037985 753511003 762593653 287873738 688971766 854624180 146370900 807380126 77852380 969240160 768698985 721353606 975714376 646239890 475837691 709994910 508744921 863303065 394674928 646961632 283442483 267687624 698970291 745106763 424052919 276975592 173662503 297395643 118410701 200211677 95256012 274231262 654735546 352678938 623735303 920326556 196841596 277830469 566002262 434528533 843421550 44224090 459468097 784326105 134557234 26849154 494541458 500385084 41975955 417248569 256341711 813398020 981128920 474138179 19397323 831783928 48577393 30651710 229809883 604000881 683197419 632628966 285215729 221880120 823267841 947999379 771995006 121937138 559063834 953598219 139544202 818519543 8013665 176277177 297846641 156315629 745219221 610675778 448844951 511304880 227156016 243483471 121561787 579175055 784054670 907544352 437929461 118813936 613184548 264263033 354025953 791772767 821799060 389991150 543593686 765740726 160111794 785669568 292327486 982548288 495567212 672373500 537042559 306823243 49760151 763132905 14880879 235319941 3702026 80118851 415615726 512225661 922258393 290105644 563193355 687172562 586426151 883921848 508173342 941567789 194167099 679800472 606528038 389324751 83491720 447214316 522396904 148064013 953276584 99818054 274351363 116557587 585649322 36025377 926258735 78098287 303328622 858611869 127773533 956417168 952836768 524706464 571756060 937099558 148069909 297101245 391988496 892655248 293289356 479627720 507638187 177468485 320528020 250633749 94274983 506690818 374988474 761649325 435458363 396148911 346088245 411638890 481680294 425825461 543592966 305083866 383274680 563647093 188362225 950947316 83299958 373629860 305162716 431088514 34095594 471871367 855486333 952755851 952101844 291366992 123079695 259177111 723785071 118437504 556931957 335730089 280168359 805216091 875925778 415770434 178309633 781123562 26533071 893056985 485638061 930442552 967524355 946990967 838234176 462797091 102145770 261859367 640998081 353827058 451021394 958899045 569558378 728920306 855172876 948268382 158686305 820202865 58092958 399344729 639633739 648281319 14142586 900776420 979782285 605155954 806400575 920874272 34476403 602710523 691299359 195680585 698531205 411433342 398345830 782960646 624319600 219789316 233776503 68691216 832512251 919054449 106220867 830518292 568349168 50803962 852773490 161667240 987235091 221361919 773332617 978508017 910880387 589946154 356455232 918479290 15887178 228817605 697991882 599302354 192355502 200676525 223921462 187717582 259423907 426499015 916681474 512956210 966852283 854635759 681920174 934509159 293976337 64420627 495344276 44053856 440957646 959158527 78497758 210534361 31686240 339424798 386151243 170625984 924755422 638292471 519056802 91576951 228692217 997715784 115173958 270248900 284702292 514056158 918836067 188790249 946754605 72022348 68064589 922078 781112638 845870219 20590026 371330006 603291450 326420345 782730500 610738583 618849721 709599387 359596231 41332028 53880970 100373892 611542483 350058479 634538132 523277406 457305579 101678266 20377265 86913669 580112185 857976447 818366143 539481504 595234956 881614406 511442333 805428791 257192062 228473678 807260078 555543394 66953758 350772635 985759986 444225273 965470127 577294797 693318918 146032040 450325298 90257040 850148104 476437606 580756667 17631140 302035181 661726169 205633958 903110677 97421457 158237120 976738430 252838091 824221218 673722198 350939566 445228649 921285100 318086331 87831993 469234249 329417903 172090041 598573521 382457126 190491082 181533525 544371593 781527723 780570742 882301737 403592965 338066342 648849831 639873369 32955673 35420154 319034236 822404346 769431362 884165986 398147134 431299205 701088446 597020821 817171806 937164077 648748750 955925759 214575034 182000559 56700080 247179473 190388777 895790170 725111662 923522387 223991257 830813337 775764148 3752043 526828837 562366653 906030041 328328069 276588167 679420121 277334816 13237892 488910209 192961034 483117423 313764081 631905586 247740245 258759027 458730583 432118906 403942367 941251008 128160459 381006852 677042182 109599302 695498178 598784325 908689622 117221647 622478683 580750294 178207294 402580304 906457631 901680296 225568275 414333349 599729462 656884631 2924689 292501673 261962990 875132295 303153977 676934960 244094306 967087097 957728448 452511447 214386618 429637906 231586969 697055946 213139371 790811812 253118189 676839103 183155210 434053167 597778889 447227998 184914603 737749562 3572859 713228591 679219687 512113306 466122236 250803025 842699702 875252786 910739565 674182194 659968755 627132454 54075065 29916848 182820696 893230558 626803070 80862536 965556872 74695506 497017904 62872550 39802375 531855526 25617610 330509003 742726333 417552005 602745773 97508403 474746470 716829666 860411118 327206247 125594144 465288239 563086120 536994470 368983866 124757793 708036724 836636607 149812324 851634534 163239028 439370250 581454783 387621542 116208416 498939079 77296243 685234885 387412658 728067008 267593005 876037963 422106582 266777664 512437200 315988147 582964855 623995746 481510810 933830784 465463910 429186405 916157922 488741929 685522659 104731747 875944304 904834192 527048767 720831643 249579467 867235272 335960472 687457887 765713661 413912010 439787898 584531185 864405990 688871915 538091502 222799493 547644253 210528988 903315622 557755814 537700789 518352858 352843286 662624908 900201796 922182368 230250804 550427629 934008736 700882723 839298380 885948890 856469858 611761851 960343124 801571491 619451100 228097597 936435674 725402415 248226775 84063651 719430680 105113316 158180132 544731284 491298711 796546194 706574764 310786590 752889398 417111680 70101667 898272666 685624720 725068138 440106519 334407653 668410176 447777500 163412285 233536214 951139195 335354213 515641413 544101964 297783348 537968770 600101506 645846714 490901372 533901072 433352471 161170746 339274483 614923469 19718279 638469076 259629402 619333501 902568328 161349021 23915518 447730767 281340303 584324495 698030041 275261795 31391477 200214550 227309781 92456319 629439804 786208245 262760516 152504961 806938586 267631484 449664300 376372340 161825269 419577241 805596437 466543198 515616212 553636841 422112625 227846457 362105430 619280616 885944680 526514795 837126653 94656208 38813324 860755777 271904772 6910872 215587725 59642902 64512075 549614704 234515582 700973284 102994503 432702954 51884518 76819410 409021575 707920664 925972189 163572222 585990200 320934840 433557787 50560146 114649776 181939096 660672953 656644643 92437320 151868352 421970197 77401517 630145768 261892791 91250650 842999241 757510063 73985745 341798472 534528159 477046250 132789803 231292197 802645427 698906324 622265664 725393485 794626994 637502090 837739785 976203390 384578398 934673067 912776798 566137376 169472341 736059061 813444603 1850625 106045655 853753089 322423899 155977974 309377602 805675693 998254206 558789285 338864609 211063452 918307664 450666188 582690667 472595168 669056532 905559105 749553408 134078494 580790248 725322551 213220022 850437722 986771902 541119490 447214985 137974798 619229133 684322008 383896411 761446874 81990480 523659396 644206459 531002110 91425470 250745316 975468374 47243988 781235638 536279115 518441231 996435266 856933546 506567675 660187431 883937029 401279491 227326393 221630865 634513779 814303465 732908028 3962315 691433050 846808953 649815770 154750011 384920970 122630845 12679914 202236950 406939285 676880633 598955590 311581542 702664102 105030603 713083794 294703402 8400992 149469809 818989684 6756900 598017376 59736618 305626978 402041109 394269214 215773820 123498140 603326551 672500647 902042220 348135461 429461048 698276849 283354381 809949824 280350582 593337421 239757653 460993124 461158389 445746128 892735705 482076827 981187640 889014704 161386219 561616450 493538763 874661577 656361201 277851509 937152687 592820336 398456794 85897639 460136025 241453321 463728841 590034499 663908118 491079093 331268070 488072907 872259599 891817326 926550674 515705017 930172416 271384047 176163119 672341780 411752848 793436394 633965933 310892358 905493923 735831721 934879793 225019302 514722516 957366763 88094278 340697764 194048100 212265206 87713608 193218228 943898113 392681794 676151570 717155761 666210380 339336944 562489693 471378091 612105712 398111944 259102162 839807193 121566579 359778216 522155245 559325824 999329666 202993733 812708514 519130525 23566594 857701594 446652566 386874677 554062229 218811009 160018048 984945173 19887625 286324115 298754043 128513438 897577613 782760 232474612 870930218 807856782 687944181 855391326 190638586 308068840 83426594 202547828 509052213 321383468 835627309 188896641 421575084 197523455 729887417 874260849 169307685 397064113 288736353 531149480 200291979 123922476 681579927 581838537 255198579 211330374 948366788 468683697 135365954 174719673 730347672 956198400 869939235 168785605 910877543 918883503 340385257 983182469 457388512 53271517 731173647 333111023 412500588 870331519 338916266 588157236 948539806 74361886 328692787 301149736 657661852 301977642 76876043 152873533 981634148 505159985 408747594 173076496 247519346 992949856 178794936 869323129 822166248 659063314 89033032 156674596 432883822 313001884 87090982 792642685 608059050 211377868 21526942 51862346 613088731 407546800 472955354 142681951 642938826 724525440 250323712 614362813 730810756 148274539 597042969 463457442 602432603 50001165 543162966 709097733 111212092 833743108 159125352 734121745 475239104 123483675 304214003 7587282 78519547 122231654 987801028 173903889 583674626 352005085 343119951 715455406 663560643 116953877 718849008 764321973 723031835 422746019 195400143 798636355 872840420 366471472 580894726 645843602 243492493 28656755 926317139 269845613 699837057 461323776 738402292 699336124 873946647 725455102 316449719 637259871 911134369 827588078 655928608 167997487 521552868 223175064 463566947 631444064 487939327 887639013 665344169 770344178 542538723 630613902 799275391 630711131 543601951 359353021 426344357 858518718 229727000 550045737 914744757 991873790 291012122 107791510 273708787 327317840 155341547 158384099 193560628 850983425 628486252 164013213 30285960 814239624 919390163 181047655 942754980 949609764 680290779 652148215 596950138 176502202 82808076 203642993 13150539 545643148 491847373 42278963 244733443 831004707 483904042 320446315 485451312 982312275 638441725 358011032 293179442 884873041 694470473 282440092 285902950 863109003 479105365 480805552 657867902 47068681 381607383 223073347 273565849 111769210 684075336 465642107 113338545 142039479 749669889 5200356 120117165 184145422 814076693 511973881 931946594 355617155 37117904 30709106 911016364 911609898 861287292 408036464 696328965 383186429 781353994 474682479 591788976 714755584 96382843 184748162 262956502 897371235 157658159 140687113 495839924 385183740 759230262 469712799 527165065 880882536 584796719 957794465 575265978 699280998 290848184 950859208 478791767 73499596 710935445 776744913 673511024 131651997 387856209 375033975 267331837 548559363 164461148 883823352 386829799 175424043 336651020 358239573 98878844 76156715 851560130 105129633 70087399 44904714 92546899 247858932 161448667 931881174 403647627 20494635 551999388 382088376 976346894 134169195 383205981 667211525 148828108 696032853 406611890 761986446 872928841 343705399 239292338 857227527 690423306 564574078 280424122 543265499 453911832 617142068 710493481 908421081 186647895 318251264 947641464 754818712 645000394 47455373 604338643 129214924 200662700 139536941 643768363 774892752 750475395 790472312 882351975 199431211 378113692 687278584 8034808 747825030 427077144 182727306 116004125 553126116 138272861 422573368 61333036 514563733 942571776 839807541 207664529 248603232 258011763 962274752 513343755 460131951 169850812 351911902 739031555 771950877 379031446 243939173 170399521 784828938 599942382 989485930 83820820 56700353 887963875 862850111 489372767 245891502 994412362 651742509 1369272 258226314 273877261 68182346 409297855 490519970 845915562 536125136 769595305 999728528 81018652 320329339 29400054 468793456 152248900 590991975 109433231 114958941 317109371 628994249 917098027 613531864 783561672 349781973 59356801 684679691 227708861 567606450 683118978 742539275 651780999 844096602 730089341 68584139 15507866 240903811 790518579 73935923 866303359 171136414 881939533 789331316 710457178 109225486 678748091 979586406 463395718 404491500 691922899 598134411 193227273 85630421 436119951 898164499 919507432 441017386 515187762 388838954 587637954 605791925 562234914 305402649 903094360 422891794 141651022 482917879 631780259 238696109 953039676 256245717 572058939 137981781 236784616 96728556 428896820 300366950 908230894 855071399 640788040 366070228 445087485 130390636 947757460 311861258 412524219 834038550 473085475 986985046 553968231 959269087 935980354 918773610 541762705 245776742 725054603 155999488 413708465 507543001 26524389 587004422 416817861 549354288 705731628 141180380 214374877 574310334 585281504 226080819 476167740 679496073 3250248 20937421 201690197 345935007 596723694 212677373 970048123 58392725 899421879 474766817 142418519 24040729 636971776 383674673 213564910 195054285 211884976 230397770 372883378 663684828 374746871 495579640 784583981 758852315 741385131 353648834 285436281 948820385 198008910 299847262 35061410 969760362 659937686 564462482 425778989 566240915 452020241 402869288 811769324 399310896 569256279 265960007 887232040 47718983 785899950 149569020 347863303 204675965 100095479 54646283 330940391 515991485 338526939 849981943 646630941 129367238 944016124 782237198 202135542 623649701 180315809 518730772 55184946 648046269 315985478 113808441 339054533 788861442 439224969 226819229 677442386 49812916 381360632 95387024 465448366 490888521 923622248 874136633 181098766 269898683 450479138 863084701 703615493 707803155 361435940 60269549 278918921 734766195 272165636 548731884 543911125 423973135 325917793 893297354 56888211 206207609 55518792 488579668 42823347 45502544 534953606 246908207 447346310 100540738 480958344 569113585 879851739 527665258 966652083 327320504 634153709 540189285 799175142 818381201 999155561 558639218 889539599 144778346 676925628 292628441 893978568 753050158 617668217 396656124 318162556 429085387 791885904 478473394 793121219 749917663 902067009 603289035 932308672 152864428 153192758 938939169 203924787 497253408 990929633 790501319 423566413 853523498 97870503 511211066 982719814 53301352 981409031 882783875 670472251 592323254 175016266 115974708 126629530 307363187 998954995 306547934 595465188 298821559 15143434 515525010 443636776 639154377 155744353 561920083 671615518 715669184 265594342 598321239 339468667 124975705 744314686 410168995 288277674 486916201 236553751 377820627 754608567 998798111 620647802 319762574 969332792 925469043 66025227 807986776 104294960 826795533 27198490 505814155 429435650 860706198 832069907 15656797 272052791 975208044 960221057 649524515 843137307 853500757 152304299 700859620 940135721 322255175 748867197 553191545 459132536 777575272 727364792 936193399 955669427 168079453 943946665 166440258 568588461 138702087 750444334 481650694 155149374 256625611 392101632 623611733 952439287 866992085 391668754 793894138 888539053 161759117 3774982 792762897 139075811 41829669 287401119 810403566 874802634 63722850 6458505 899849148 259384465 142093858 109947899 162362010 145040763 604451235 216229635 892021684 914996604 243054073 56382493 743885758 990297861 200104022 311541309 799814534 230166405 708714461 741150313 28630123 911493511 589300832 693080464 45524906 535777584 466955711 197877304 906191760 855815964 148234370 716046595 185812857 53905595 693923096 489010327 321715983 249132849 789820592 772002272 988796784 565936749 520653008 563968393 583857555 159507589 417043271 288496941 853276405 685745583 725403777 159372300 177623525 533868901 557035292 740208657 730770475 850389488 454750294 930976817 869414498 553512475 527259818 523968273 602318476 613063794 202564219 862988112 520035103 598467853 115360881 275133247 16507682 806965679 685883347 602386273 656728962 530001276 962880855 938096266 552822783 154569300 864535840 836237957 662657464 403353658 725730876 491714946 765779953 574977455 660556373 691852351 928518373 923431664 92974609 37702218 964097972 937260275 675066705 674713536 448596043 802634496 269506283 305974638 541138763 775225640 808606833 874352229 872351172 442566664 746482141 611701835 94445245 261380156 438124443 137162330 199805937 552188447 210149845 100919144 471761910 903363749 512346573 997739960 920678525 643308389 978692752 292844800 155677283 99394689 771409723 449012417 520937167 445585242 570244945 676576897 492446505 293683039 858334617 839941735 347232930 162844997 688302145 956042934 210619484 470893342 409372147 162717558 259002564 143601837 395847237 870957100 314275044 537289135 616855163 785798049 206833468 75892328 744413687 967251086 663700809 272545585 224326646 550294157 465600984 785828104 58118109 497300328 402371580 598435442 612580747 184470445 578059837 558400885 563818047 680356771 94831320 985843256 954977960 911513649 357041065 52129306 838216684 970871550 519002606 750516196 788016036 562175692 555223481 858304777 648847395 958905641 575897746 254646111 693160082 645386179 393473179 37455257 36339008 44698599 808692619 306243919 395319223 515484546 187192573 241079285 820148179 908597820 72872677 875438051 471236601 941429263 69812537 738659659 839303831 87143636 775359843 485304057 867814829 40121477 697166854 450137952 166291415 498026449 675836164 583306021 353766316 456469241 174744595 884907792 444343504 749846560 636041425 768589096 169409812 983005716 934060991 764584182 931587037 5792155 324676350 609916343 975124134 200710744 961816043 595451468 545368440 126271145 561955872 305616727 307847021 727073819 616008961 727466531 771210030 983540124 773219523 498509380 991904241 777031997 49609335 64077931 780469399 702282264 678291988 283815530 155302247 54805145 728124634 633541908 73169563 156239890 399016475 944389733 861102287 62002278 593741141 522009050 12046878 354649093 403321237 129656341 847566938 852630784 831204891 378582783 869379851 818865643 163485393 767124007 630405843 565445941 493124244 840710896 973617199 191454908 112869350 206575727 600989746 869186206 603903944 445646424 692889799 678670171 165567721 107625377 666597147 453518517 341083505 62724737 693784109 621656777 674409396 104787840 606593606 716106503 779092968 839099327 61508622 155661939 823905158 682413642 465518057 292701738 863624635 143724083 683411711 804804592 702135536 173938720 289818244 97851588 88121220 536781162 935970216 788515935 311410241 746456403 602810390 151227572 438541926 83888785 296543882 85269796 156946302 418355874 947935233 527359455 101632120 642011915 79487116 241262567 186345549 579615900 305374370 548086665 788092579 744438493 217986739 669588227 533691501 136550424 379865688 695238774 82907365 726611502 402055848 120443067 993466830 256716014 629129463 84786494 540932670 390822830 345975968 743627008 208324960 421452840 911386296 624834974 317939543 94197784 961963228 19820159 979187921 112226202 192722276 96156797 133044920 25956409 931049273 998742344 313587530 644406945 381481410 871830568 859691897 498207797 997744580 283251000 436141798 972259944 453668959 896734976 214466372 861079145 21930812 441645641 847321697 338601863 513870847 989238329 790104193 483875319 258056165 212278804 847725607 942790156 373664735 740567284 551123622 461563277 443969115 589958667 678364242 615630772 946310160 658966665 969914683 578184476 633664964 156860347 335366359 398997961 907754407 179908216 303829027 268948264 702901528 301454330 245914590 354258792 335655352 167089695 537327571 720287931 848298528 60573208 2249829 350517666 897113964 81422509 78732828 812817916 88515427 588230549 147171753 663741463 503740260 453893237 285039892 922489694 303451183 746383947 746098476 376411327 614230305 326943186 133597895 644199756 920742988 240207570 556846916 719047975 78393247 903698523 944035976 642297652 42138431 725390448 41589900 378716243 154820364 688037858 742745520 769628021 691375946 82282721 954319504 133442552 625898022 414042977 123951359 586856990 397357298 769427058 648041878 94900675 735194868 688956252 584558367 553230773 214045300 562192384 82973276 38955504 335410092 302021063 274850840 893371582 684511234 122193587 250798424 133473620 624332598 538048916 107333730 636237887 970769586 129050310 563825000 999179710 981885275 637691622 739846406 726559148 639080660 800922543 441276030 653404680 594635713 544802293 871541827 969006160 101048447 504147774 17229931 31164309 703319829 358732139 460081484 856924519 691363659 324541331 208007879 83003650 551178056 877010419 571743713 612045325 334929866 816058980 635708876 436331989 583020923 383475141 74380264 157928353 363013270 956882077 41793425 155483177 135400460 181920251 969691623 948759815 421364828 633538026 173958928 49001544 450724431 219985279 459234440 664599072 363599682 772459433 234479987 319966041 74383354 759090953 355148154 690041691 813218700 700624093 996732987 880088887 839115569 163453131 217054898 920088063 191557637 310924948 603122643 828913842 841454449 418260783 314017277 107381991 493417795 481916870 724675276 495779296 25931379 998487570 936062819 818445466 682619179 786655310 406872980 938644334 462226504 574438569 504108778 743343855 794493505 323342072 265152666 518809511 88439545 566073209 219028150 652852424 423724681 583135595 902178207 960553254 337906043 466448179 580744049 931179175 682157303 873775004 270030723 755604236 688838844 370351010 446409620 300787155 251464441 814155511 371232454 808916558 886905134 110835876 185908470 115154312 857087071 376047516 467274382 357554369 958754065 713627473 746335934 79722901 118763430 948010702 65538374 398493990 161351751 714312428 967012508 647814179 224265100 389372735 981443192 948761130 327584651 756108860 911017420 85505661 322896531 863333502 180044201 400764673 978529620 150039847 51097484 908435998 295173956 187347978 606774593 402061470 500726450 932852727 824275605 906296504 372960802 626414140 835090553 408190456 962897161 878460528 475021130 912865401 455230744 412584415 552856117 341110524 339274832 258658206 890513239 211091724 661806550 82232046 839214352 636077303 480038453 944608640 38476490 160700657 593666751 669270899 497489456 695676269 226488992 594947358 919340679 667655479 882762488 878047974 340884606 96783889 905702683 347689722 228540333 822821618 450032889 303418519 536201250 357625082 262108686 28800218 86174800 181486744 629176978 912136328 781180720 814744682 648827199 989004257 580595697 834061638 927077474 572573956 218058963 433450417 40362934 666418705 255343256 230222744 162359580 681000522 993527314 757577273 854491866 152486489 917825557 131911093 812193301 358268954 519151093 471730038 872790961 483734223 103264477 780981106 325496031 250724590 701753924 996731247 326835590 804899283 828140961 773790214 505803092 396577535 732264348 731609417 585897234 848721963 742532994 791515744 493149636 235868284 629835048 141996168 459031163 302881882 135229979 259990065 352175781 60718798 782602411 886154620 620592214 474984839 956450287 659127941 531664297 919707250 217752629 628096978 853375832 298010972 524102735 472375276 595044152 989797634 413097993 705740061 835952915 944583644 100789320 653695515 588654764 796765016 285475381 136296968 929369668 606489512 128597512 988863043 492976596 784090363 220727417 901763698 807727572 861528083 524208339 699213150 4321680 670930455 349212654 245993858 960005263 55058904 914096198 696297903 842894763 114455772 685922927 571136685 780381459 762789508 539897045 836077209 640885273 729015353 903500923 37730880 220452813 200194252 993820820 654695193 183825961 267338870 528275564 350017423 101249169 567275098 575204227 975968546 329612496 935018288 743683124 560876562 817551475 787740622 335352131 98178459 55100775 968828243 686287969 619854685 44065743 539489836 877632263 590977907 699176544 662636176 258451938 489405003 337631962 519651235 668219777 143503082 490753957 903333942 738515886 800129241 958488520 716176274 858753989 423663886 338265270 652713470 992530612 534749869 386722740 371536459 666164790 299288940 832081262 746649706 129080319 127674980 178045637 470187986 478642372 34422680 541789820 499223391 724554916 383646945 778979347 669752496 694386973 636687184 209766822 998521228 866276559 332616749 262933143 758679172 209037574 558969044 710062887 903315127 597082468 859480566 944172743 792478217 131114832 45962295 928514964 72320891 592638173 662939285 747740656 969372033 556604295 537556629 943854101 584080406 477048522 201824998 467546716 251974429 356169288 906144644 116773230 465711419 243195992 815433912 311646940 833277314 211981773 498995148 564588412 58943365 8610779 597474451 502988362 895189848 778473769 582417335 337693231 35120473 351540424 39638505 923697589 732773180 896420870 827532668 701331112 12275359 361516096 332432909 115848190 180821152 521248630 875729468 595176365 342797865 732501436 124853375 424093409 551425311 355597612 48549812 51731033 108672098 460730459 98010229 121619193 975024117 773775969 166426630 65826620 84833453 296326218 948268721 173260355 844633231 308743237 111461275 672964097 68231884 279283925 374547169 23922088 737616638 362403374 975578435 470176882 711087102 321961325 57205612 620172940 888905929 226681558 819312212 38882900 830989156 972568743 462250497 877485449 249783101 398183495 82431262 686127978 324115858 908887773 766768030 58691795 918246659 443991688 781197062 758118855 928339142 282746837 335707347 872526318 520693318 646517393 169521681 600002105 946102593 398780190 241281331 897715862 662716882 122025175 626019797 139467060 671500804 766443132 939066838 139093013 373119612 314101536 130155307 823258062 975862178 588503778 532463765 565353619 461832486 818617112 689201101 247664027 998957074 997580938 529962694 525854926 364987394 428788077 894688460 747023447 51538569 840209552 612048625 177530450 656837300 406338379 379650272 206752510 993223944 791539698 418007379 723713671 634564074 646509815 748163973 6579069 209619671 294998881 549414922 788481647 373256799 624467103 577007325 280851746 720160363 49850959 222632357 239453649 140766438 696367392 190051650 173188760 914266930 210159166 138983060 470452582 168088723 487400585 405324652 187167698 548879942 547453285 165761530 133137272 597361704 566818976 916746656 592622252 33437000 805351310 38338659 150922367 591985850 349185146 69630183 274933159 991788396 672746898 100091039 228085477 78183803 108693820 313561232 359678755 518538211 623814820 451697414 439833324 750244308 547686495 971547754 388122480 72278055 96214894 692378496 641926184 418252260 116049165 825737315 908654002 41543291 762714620 716447740 339203117 653924878 622842772 509893293 506023270 479079093 285603950 250542299 854999087 234676047 120173038 423808914 786411661 269962691 87304286 217871075 531774121 150856538 81495243 455747082 400295817 547918008 37744478 778496148 970737878 711300313 69689512 109179277 902998258 670589836 223337881 612830408 986315872 854118977 243749421 611745887 382120965 274021446 801017129 288481652 29262889 257087760 946502953 823459069 762143039 182206363 565006367 13491812 413178618 262740610 759869853 99957998 633371605 249253291 572685165 672889715 485474343 600212702 668600671 978192852 150682392 509307162 521515105 284797932 446565373 152444185 504124212 77907827 93399622 606400019 93417802 35847854 367528466 715323751 93216631 235954263 724930837 878499738 190154522 244144248 815906620 697312230 350738371 23546858 422398688 579581222 501129715 944486223 843099685 406954373 249023316 916963970 517272223 665190125 50904827 194790907 948534642 396424663 999673755 774146442 723553510 196215998 711599000 42587213 89023160 219557476 54093482 200858784 634213203 82187187 451898777 527354126 685416517 952303044 21403740 826983594 590580114 106103081 796654092 76917562 365552388 100618630 895197025 336120602 980445586 37792091 410934214 595396612 434224391 124886687 287045675 489524664 831114196 20616676 646913974 807384195 891683864 873636084 369972030 598955948 584887945 305072920 926869734 152552947 70140013 915672672 968372383 987576843 307692938 534107833 600389187 988301590 575119524 474392052 820525410 683441564 247703417 270238303 151304177 818662197 172890796 40070782 688300118 811055840 40288137 61966131 271794594 643548294 155629522 134136014 732571775 283345765 485019988 974028835 493745477 407988845 560437110 554736097 378752838 343042100 942738460 745686997 251695314 712936746 466763506 557610281 98478664 207676311 812794312 289982357 711019323 944428405 301014463 783329132 732131214 455690922 645095180 669364032 766407123 733839664 340255308 775418965 891393389 83130286 573018244 759630345 594633866 898539676 215688460 373500197 654673673 449970803 747147599 345657416 152720029 571585627 292791239 714439278 250681281 97210325 592072711 412232155 75299928 250864811 721316263 780940242 27764360 573685807 167623010 49015067 20807714 466537720 814454175 162956062 121933633 126031357 330645629 956234145 731094108 614019482 7001921 147915056 125838756 220214225 431110941 800958476 780877098 668645704 913464541 871407209 98470609 290008845 635149328 203630252 718815051 385145009 578435022 185259739 751850045 10711172 935112243 441223852 992172417 831357987 954089006 656857404 260744727 552214983 216427988 460664931 116937351 693871469 477294200 789072763 259980967 389795957 597940762 309950323 613520617 780978220 880388150 703678832 355187730 26550816 484929162 917009985 300312130 998505740 15340233 817437631 213429623 722566363 209498340 606109623 750007378 676785464 165595951 258447177 496573130 587162560 763188010 211957895 676589725 786238607 32084814 810544854 306443275 592414638 71557704 545258288 144627139 873726022 626801253 134732585 979625893 932369411 178122893 958974602 674372705 446740358 809780215 357864043 92437371 262830750 192757651 152513735 510906555 733192099 979253428 648948560 212488697 882695870 661854834 759951843 398270901 333165414 580930628 17269827 584916109 612575962 487448310 232306957 192030220 675979637 868754873 126082179 561850382 593356480 702639078 108421340 115860297 830668649 379989771 283328584 958542332 192922884 340973228 807482305 300749922 137180864 173919379 569499705 85051808 829833789 867884042 493030978 93274813 7952215 266241802 967784283 156523438 979604218 463556192 394957643 186247735 583386853 887227854 928110324 933896622 403452097 869033215 550329896 843778629 986942841 868018229 104493180 776661069 869373872 489433722 26176800 289534783 417888773 367958820 223780119 931097247 217155076 362594965 252841948 840521113 364750002 574446482 36361383 274233775 994781200 767209949 168893434 49003907 837717579 860330055 298502846 214950401 997345882 624393657 297429328 904176701 828591039 583007510 150687264 388985067 669362637 203965250 307029035 342679012 228705113 360664729 376571989 162436505 728178983 978587591 903126848 529603825 395215960 995832552 59765894 860112887 993575990 310799905 526747853 191744063 581386010 560138483 692966111 468169911 144290471 108766160 375899123 929309575 141538288 246193807 516616473 522834935 216011290 48181826 700969411 918281946 789763813 202225198 678554470 857280033 954811640 663421323 511101186 384078048 606820863 403174606 910591991 351836019 557307776 314502875 708477915 412352195 244389657 786485994 216650423 552032602 304787043 637258041 832315949 352325212 570517983 945384999 644918165 305270930 239978900 898454351 587002589 719561551 444898823 162344959 612500841 229806888 244675777 120507982 96127872 761758284