5000 1694
575336198 388765742 308904989 790990973 569829644 324501742 784029980 252095521 286251564 483275555 454511077 942450072 788523408 776422156 704704418 745800511 692014120 735048456 618260618 188003269 920457759 122332678 241968167 236844561 913420210 632172442 337892764 311897914 43886142 442200348 960872578 111366919 434431227 26115273 201177900 980295628 319475875 184969895 178432695 779057489 213076252 341589931 400091287 262336887 314587157 3094247 955306661 78297164 14007250 88014136 194798190 175282525 828145559 442641635 520244097 79916364 408249272 254936999 980524200 220453731 984583391 97969853 722494496 785145235 524795101 762663081 836310874 60970993 408240059 589189951 19246708 415674496 798228034 127567048 593661765 486393546 508242815 932425722 637434516 413801956 810295661 370969790 794458519 688225438 115082684 746751137 767934887 676431683 230702638 870907724 663124523 614323876 47080655 510380754 786147080 163640816 346984781 383345736 813063332 249591133 476666383 722906541 495341685 205610323 637717803 153003191 426631744 735815384 441924473 579972242 862169912 799107518 243539607 825417657 522692388 66019749 679601705 933954491 130302354 468132317 944390253 38411263 994558802 907659650 227000155 597304902 304036428 730654298 444174578 812828416 173418494 345915789 573848235 693754479 922762372 939870082 405366675 861169640 454538353 589448336 338580274 835648753 83144978 939500414 979024225 711388864 962675626 896752854 627134011 579075316 130289816 850238129 713605818 354053776 309982724 227364171 907623402 153058701 289673986 754617750 630230035 195033093 998113666 453625077 874033661 641491167 867131770 599866099 634188190 679433695 833692491 602303573 458388054 583201349 367119660 451161741 660590508 976179831 250024233 571938818 687716462 650419795 35586160 165199590 961482394 550710120 426776364 893864357 419101894 626935754 546667214 282269879 409138290 134105280 455845844 887621343 738361116 910488439 289845568 383100474 965660836 168622998 809871192 125816506 862729519 203011438 37155884 618833320 771608074 949937657 779973131 315578428 837452776 229066440 224538664 895536439 766725151 1937009 311214272 680526652 250206808 940928197 144984364 542119417 964261502 167220419 229135518 363057317 857376480 536570826 634566073 676309790 366186004 115173357 457868457 367865917 86676926 977081432 643764095 150482701 927460265 29653316 88063038 303402143 580595328 146204354 374051474 64648708 478870496 349454969 816750591 886608867 432996978 28893396 169377328 586849876 92562181 875455056 244644736 843049468 42809606 433957650 984788314 631958570 289548558 311992620 174702690 889444413 19769229 283641835 762683557 217035374 441447442 722854302 771656693 441149398 361827422 197403579 843300552 582721333 68467236 661774181 782627355 783164250 930039431 7789618 497109722 432702803 223338477 544387372 924145773 362643023 407633147 258642222 620232078 882023679 598557121 624092938 332662548 527009818 728101191 573303941 142026997 469952120 207917480 624695280 342434230 175547509 166500871 222520121 466765553 451868836 171563167 869724512 427444740 365791305 52024710 411278337 160657601 562835886 5201317 911505160 458820337 730315004 47286599 362226346 592862006 491579683 852908359 829281373 40726658 180651286 416500802 887771624 484211925 543595701 67263362 750143029 895000434 566721470 245570546 421433926 788115685 723490936 272023480 11446439 707125382 514384234 684054685 172176916 542422102 918238276 94140950 102640908 455971470 656103634 355114891 27783316 729750174 421303622 134145952 918950606 993646890 817715978 240662163 346826704 615191714 651306895 260396739 955836424 312703419 868461060 734843606 650048792 194286087 999670154 186234517 419032345 999436545 125560467 894986473 441073077 151778913 273155564 435255733 159154192 432827316 607344090 387453658 860832981 819428949 736511818 851858895 675076019 579015105 423829677 82735433 988412832 793925090 9163555 130203672 47238250 856451284 266048777 257359113 589234077 303601258 161647840 369508132 877018364 23524221 417346991 910744481 168397682 901774195 211687829 100694861 993167834 576695326 187037620 795413073 637536863 356201767 670482294 423886376 638661776 699520147 786356552 192601443 173116746 72018432 231310942 223254207 326975664 23455235 367446297 596154457 314082079 748732739 261943441 679516186 903320431 440991220 106333890 564032600 917816814 131952566 861338462 312435829 424919290 648654127 89965560 672902850 682980505 414172738 398869865 93758439 703223570 93155819 648312214 298210116 353672952 403911641 392903422 680406283 654285741 654000028 119520965 636807958 578790480 454662778 23881477 22616092 814065017 668798369 468115755 359230783 540830028 49770062 624745171 33635077 40361821 543544941 787855836 266419430 4940124 383662414 731840952 143259589 913262761 336286389 86123271 608466454 712189269 387873094 527577119 893540513 27634942 193565944 376030893 650170004 328144798 684358820 709924333 504083773 446919076 644570600 72440526 454036723 719479941 23522976 905008071 643987817 5195096 977787526 608935758 237061835 837424400 973849176 94477476 718684549 619764443 937978726 206766183 328127008 378410603 769136302 562775874 676468362 439309489 415078389 177774031 959058955 429739828 22720098 608787696 828555680 396337918 815548336 840419449 782558291 895220731 223588910 956460246 673227847 690500905 281435354 927396289 786162835 491994147 512578665 480720651 136469021 896142862 671945531 423287758 373723831 816740343 149193091 994742659 724927777 151585144 85799713 452345255 940697127 111734904 65979149 973525781 437207016 895435623 584833167 542578952 928985305 353087603 409748440 852169034 490917532 755530852 861258690 342981563 315323177 1261498 509300639 154304554 821789406 517772636 22716877 110603017 893096008 582181272 903076522 306034518 224517934 882718187 366542659 752266134 109227877 563789250 675574819 105971177 935703139 968319859 153534013 351544698 927695506 372977572 904820001 81547978 818083908 680861651 267042862 225121964 131294550 219590796 329694903 867361255 272799225 587736292 268946927 405857529 104480708 917585035 44227504 154790591 451963545 68440125 610343503 615995495 432866540 695657169 573162156 297392341 849674516 899414349 538658855 560775754 87466565 738718551 98096332 477476962 757565456 19561351 261678351 171697867 359262820 65113108 738441714 502691823 797449366 790247082 336950904 993532826 139797572 502826179 213022008 635843099 134497793 735775024 245461823 593992389 478929915 426570398 198498960 578110089 534400483 742110760 892756727 519580917 800831700 262248489 499889121 688651717 491680612 117593248 978270846 458075801 348820421 989448565 718265071 698462510 639238136 27984363 515553166 267497875 195481410 434023491 254122862 522987498 445583266 647820441 603478052 193008833 101924504 449930046 939006827 464244258 439084079 980833183 760707125 617955376 480183745 145836037 791092285 691324308 690807440 443575880 41037039 316399338 798180051 73262045 277187781 937483780 918205903 531899867 202008806 883180020 708128076 306130041 183176101 514476494 633600000 145809919 369331648 699036582 140802054 382338596 800669197 532742388 452014259 77707709 369674279 213239808 485285084 382036493 976298265 201962518 976426541 422648633 770433043 256378682 869534330 168959115 630391337 932981763 131552139 367300813 464964977 473486361 849809772 509816287 619486769 198861367 388393179 778521601 938723051 677620828 689181307 908133583 306251921 78885370 631433665 909896722 628524572 981003399 247380099 193099360 367885043 372577327 719212334 211874917 996772485 264786666 394365764 276142530 767272624 623316112 957226086 211777536 17469956 868042512 81764301 639994172 991309709 850732017 785198496 255117879 67418180 278449964 933964200 214553791 240406592 241855692 914409017 370355995 174958943 965278146 534811334 943456490 62060109 811138082 798310947 644637084 196232781 530897077 136839652 73005195 514375628 651674733 449487845 707648257 305371248 841138132 383676955 550555321 764508994 881659580 859398221 910567929 163331428 907626189 115617725 405104252 224131163 902900930 440046961 53565570 893582858 414025826 856733190 235836896 145045689 206906339 505583418 188232295 399007449 37636554 511264890 842444148 365585709 85626005 358860260 601235516 919784534 991877786 849441976 913692418 849039150 722919357 331758678 985251951 179936628 870700098 788624237 660177451 107306659 232959030 325069757 331729016 843019553 702216233 39993470 95155294 634602888 261163550 891783951 983657734 636641255 826313991 623905346 23255750 174042969 832514019 481176903 28702842 476889555 562152550 916779645 77830091 925984837 567934273 647092494 303988854 79038102 167395927 31812351 167654533 703029503 266028330 994206500 604597864 696511205 498517386 802681927 447423225 909626782 656516082 875875460 811590785 702510848 788194708 639580697 219452395 899361837 664791072 171142463 702047483 610920180 303535428 577644783 335964573 481349277 424099624 750035861 392452171 274657501 449047040 565330648 443963908 764325717 800415103 412502270 309605651 760933001 235527994 551664802 664776481 257274896 625097468 671662653 339248468 907058726 248596937 797319724 547971884 585096306 979727932 615253797 899583615 955217311 900588358 341597728 879182223 228142889 924375891 178059596 452141055 842662082 111994270 131371556 513733718 974479278 647527379 667092187 922420890 801728591 991461823 355669951 296608543 127208391 838457338 845976474 577907305 630630106 333810671 996519299 414911396 577692713 288029440 707995693 326599859 946172329 37683912 138998812 811641022 131573032 334562327 914172424 595580523 925345833 373437007 630833026 863236232 142106613 68754034 363063050 884642577 951077502 89515380 938279956 442963639 442120941 967465878 876364371 741719964 995196904 320863888 656434300 899816611 426936227 944564392 111160816 611455175 984881681 13109479 796374729 97773523 983637069 420765584 199100667 175442372 226910766 312611446 703565446 489417348 85347400 475431296 419549512 764406955 457635024 930697316 344595502 627427002 170335910 119272284 458835990 746965415 378247676 983109880 391862841 657282455 42425518 533514511 131011198 210864920 106193754 637225252 343042822 992158459 450230079 241565154 832015187 331337602 18593314 758421195 839750765 976529831 946903747 529452120 742975799 53122089 932773310 381042680 539917538 559873866 668321981 677250270 476014415 310307649 262589006 423280905 503036076 154520259 723228166 872203768 867923427 221493014 916092583 983899535 968613129 144399241 905476268 533890021 685655376 749002601 859883376 905584125 455267997 935451637 916417463 991326848 557264615 269915770 934496032 198570086 569941496 889943957 902966425 309326261 358398742 696430731 68094518 295507156 74947284 881443640 939067228 847754764 146781298 887915801 169955427 152148166 548495579 974393426 493053463 539211613 241238094 65460663 610543977 590016324 19532960 511393791 83799292 512920988 489323529 685045333 963613266 667452755 265920968 597979643 670992548 638103658 227174774 162947151 228938707 547578099 425282167 373191937 553822259 163936677 557718624 437555835 32869853 142596409 651605276 436711141 540573342 238634800 620046718 80098579 463574754 134647041 378247450 783128296 286849930 52695840 219150006 910343402 157551867 141098930 433892272 388348921 788631543 900707580 721867853 202691606 28695986 878069482 265693934 103071663 467563326 467812639 462045361 204072117 230255978 213867209 284920754 57375410 175859010 351800543 1759951 50660539 980040914 635321241 949467336 549894965 531528353 327858532 703490350 146255346 920233931 772809158 327006322 904235603 561462467 476526680 371537513 493406957 143033003 696868594 696111407 341810462 507441517 300823962 554074423 815783825 839863166 848216968 996552382 245523147 880733679 618520018 689869136 537075919 998343621 905109718 852081402 139271420 244722300 718580870 703753194 376029632 222092328 426899873 537051559 814271991 636958833 751821484 349404525 315884106 444927735 653951837 227331630 340074469 606896300 847634025 413111654 833644857 983600230 374207995 747071032 397225943 607811170 51489486 623103003 675570032 244037740 22450158 636779206 408202808 387711586 311758040 843234275 203301911 632164902 866717556 952676139 236386154 982415470 837523727 332168562 230146303 522986463 437391284 420311481 987093949 881008481 762204888 318993019 108915024 33570047 267401939 410669455 852000904 308405328 467548518 961731874 20113286 376815428 348336437 80883604 19001576 674258261 231600588 42939985 62134671 379250813 184082671 138693128 213681459 257993563 946156475 185915540 63401634 528085679 222288512 745738801 877122919 393748518 723660200 296527967 568864404 674438749 597841755 495489593 7176059 689664462 457043148 353340852 922036005 716746511 458975426 26846951 834950492 689661933 332282422 886365380 157550009 443955445 557276823 291883838 121816275 10804585 474913348 926170523 979000712 218472772 406293128 321251568 418106914 419981062 80209943 307397963 338871714 41429050 68896924 818708765 804982175 256371319 222511201 586780772 753959227 285089720 632906470 174850350 326918717 634064743 673950023 247202370 605668633 666595859 283408330 835430172 27286602 760445410 525000983 589761128 985817019 948961165 684555601 402923080 937878757 385162445 730990603 192265917 967057427 444589640 966763385 120087919 862362755 813555363 695009784 862014394 854811162 106011854 349034782 36777515 158211146 835557501 565811440 544184829 676445433 310116481 605817414 9295127 36742712 702475643 503579764 716786525 927178176 934396755 548076277 94388833 835815629 523819945 731513286 15172448 487287563 740416593 907049017 682956157 352655507 838578679 366727045 537617 210250425 421136878 614224987 974957559 766219354 963306254 660650423 670575281 152290371 122469498 895651002 607656699 358256672 209224856 496836153 240093232 344981026 234154451 570138653 335201170 730013937 797234552 156480720 606808455 675009156 568887827 947542818 556233570 490433401 760514656 432486574 378314376 260902034 271077076 615897224 150028399 463110125 605641666 363341554 740340425 519069265 33407668 696611491 140900663 29176075 902983511 973774284 256553888 212945436 766941961 455209559 561370969 928805901 641066749 716569348 17472676 855289197 686683919 662477785 536476804 404612374 577067785 13664126 329865217 184381002 403702532 107026410 546031972 989633382 204091926 612232739 312914081 524129077 510670147 932368838 922472931 267441224 170115937 958736500 865598121 41094050 379656408 125193123 543437032 972607570 608276725 603587608 366956946 468849790 529309127 452120036 856885028 184106568 194669272 342481137 673015120 889166590 562563095 681174613 167931392 614325005 548619722 152994952 32262494 384262316 927592764 421531633 392935988 648874742 882181446 130827558 25235333 291112404 401388177 132543933 25139839 744668560 398825917 471155708 326673746 964113427 168339861 971746094 595653107 944832313 709153113 814109322 245613410 732308063 663042696 604942285 141985795 587263613 651901973 366464450 10273981 786104294 827503114 444547666 222770176 134546037 80298696 20634753 68650247 774208824 769047373 343162423 546606819 556281243 663314903 959119232 13586684 749910696 410692273 856039157 78794181 781904823 982033091 955548527 680992420 875113190 37664540 223154401 538665872 103080736 938728727 105892485 754218759 109583650 910812030 386740074 925480993 719231745 347014324 61307152 746638395 861089321 583520037 55122320 544202780 456511881 126011721 42756367 634725000 871462771 720237622 239863489 658825336 467300131 481455913 535531124 333128473 308780610 639879790 642989366 196352018 627291892 383535828 678921015 384627324 306846810 59875369 755242388 86265365 315576432 552933680 909584983 237817705 869103797 431758254 978444594 310401456 804859500 795019978 144420084 959228749 775738368 691603675 745239202 460990695 951470899 139111840 255401454 820854802 983778696 843265209 955839583 463062862 688446861 824371846 725056774 805321633 984749804 828474051 592429928 48714256 325221770 852552053 232920492 26008437 522109148 946584032 537098925 934373244 478584441 634791565 782264317 108631966 661986372 345356023 508830229 220312951 571564966 436155521 270102514 209881818 30934286 547507063 775783979 273622366 607212604 992956833 768007626 334469104 999326395 610903505 674186957 234818872 117983899 475110354 674898126 753169312 685667878 834092635 277637483 353175659 269806111 744798750 935940008 126126236 802862509 518201987 707496030 267198160 831712024 155746321 599078200 857548412 188846668 435428123 58167779 36338860 422002145 285221171 380005949 944861572 419145761 219570131 987976858 990476889 760525659 151035791 735567470 742878895 437804868 998232219 777203459 32137049 795572636 540906512 740481039 130299986 796699264 780130910 747075429 363527331 494228484 113511686 914414591 205760031 535736592 578638822 155003627 939931797 437308112 161292962 880321305 903729032 535710310 672351831 535854744 335015699 643137286 365514545 191218237 500208655 753996054 484798804 855557723 336373803 34374784 973911801 521616123 811896069 65331391 116322800 325254832 655299876 453734015 118694123 226916084 944771604 719851072 563121124 772298080 362432490 930631600 166456696 38266609 961967526 306679393 179064097 691038653 435263369 370915390 524296004 805180948 810424188 217761703 40961371 651110433 997979822 582387092 606607213 688736172 639509866 912738047 793982230 331054929 507114911 158531211 88986856 638930092 113106131 415310334 812033562 737352468 470930763 492014751 628430341 124918214 711836536 68717649 359796988 843095765 862251864 348369564 493537442 540229800 973186888 902682651 961905344 23055486 656428409 546693346 353889530 36847744 932705603 347730575 680402416 738833067 39284296 680242128 782044613 40632150 729034840 911984768 488004394 622515791 359046677 400442485 122353833 481416641 539208551 68348247 952405045 44565641 293077469 889546187 912206859 936209867 839500429 702381894 966458804 298293954 109827691 326767418 444989504 984546990 587071122 977699257 783663584 321879485 803625175 277487861 962616009 834067934 966483331 649016904 823268332 216133234 76978671 556914477 782954429 143775997 758393524 525216537 926255079 522124663 497274984 372059664 58701955 518211211 74027026 534533044 139389000 736108408 999471595 870402087 439051640 933973652 608176531 523548784 77538323 869337403 342680037 222026586 332981593 493075670 121052183 374494289 196814358 576450700 948367397 751009389 608081200 625178806 400943032 354803872 831093482 789612115 397673378 27152857 722578494 766511927 804145892 551094559 693944494 502598125 44196095 782994769 705697809 386081831 902669921 71765305 971636538 56279035 648890186 417123229 23230948 99897713 562743179 117857921 534126192 307026950 919972303 635448380 712121996 135361841 708420778 449666701 575737125 364413403 602058131 135239196 346893207 743800466 324411745 745043153 818718310 267965401 560383466 820492430 981348293 137106474 233274539 79407614 204828558 779046490 37210179 725474004 998597379 385685322 544958642 953910971 822736879 29903347 171618504 129475959 606736181 393350810 609100857 559062632 883940373 538578219 896386622 890792844 276454662 254365308 160068985 531199975 616343422 434872003 499382808 888726211 767723471 487589688 587451741 865544167 716894455 74389318 513993059 138523713 902848877 936041180 112095809 403041489 722200835 381976181 266091994 886853978 175008752 544967512 889723217 172739488 28977308 532671711 489009667 700882828 731224412 368679928 658158627 324819268 76162025 482216522 934705411 403212612 800342796 485920644 983827746 820450199 571864669 619823308 83523957 66886347 302752551 8984576 938000420 102621662 674593884 941469422 261019391 982100847 986027855 896634475 325313842 329660085 776555774 809271587 501414875 929991355 39458555 28564756 218434195 385696551 648376281 3855047 527297860 180775903 248895409 192883806 25225493 773165991 189237117 166520800 874665450 252263922 596019834 596254514 341170055 684489677 997434699 810789710 611356001 400486057 352616996 24678508 612270666 145998606 946160271 792365266 597446107 309165327 658408082 838968201 137465051 928057972 1862024 644618813 124385939 541806439 896299473 184648215 355807655 185638947 33385033 79128661 840345396 174020006 728484974 67556022 41431247 127273383 54539096 524994384 107223717 928780101 741915766 777253771 936819312 952235722 407632833 348671751 401067519 569159373 820491200 190544623 483830567 49403320 939959503 262208177 397421794 975342555 564597071 962695917 965323820 180790588 17115837 967960845 999977 555465491 251688243 845028843 416068544 859820662 987111208 803991192 860764043 582370976 309848068 387577746 435028038 557543359 952465676 516481313 110977771 596760980 567842002 388444615 5831920 389063990 466914706 827034097 860057493 482649746 906994923 146977021 994112917 440374009 698737145 744649955 894077387 901603810 82494821 160084444 219822386 626047913 71190414 315368214 75174979 622350370 47288634 588184809 296871208 343482852 546210498 597603271 229816421 9938813 687870031 330094900 622272731 175606081 136752186 333791526 198036913 753129043 70511435 68589098 16241780 334709864 1047599 390797068 365674775 157851009 721937833 924434433 146153654 582491487 887389175 89204119 897167606 216926443 525553961 785328766 179360366 670123798 833176012 691074618 550552709 726801571 806628541 991981014 468590887 214895428 698700910 286106526 836290866 265030086 513961273 460250541 656098935 82786774 722938409 674657994 251487619 534565071 872684250 55517135 336279794 122163314 310260580 455667826 526411758 372472772 669463434 293892381 528468122 101981165 572719158 974077475 80906661 861420098 717610169 975797351 852316469 675349165 859079530 757023228 395696375 438008441 574488685 272114548 279649446 781261211 434428604 478042013 479411646 714097631 232567634 698753104 272977341 132750230 875347969 939470186 664499811 956568123 313522565 869727535 658895220 915619611 821780929 948593294 70445318 195546337 530416837 661186676 830211299 227462935 175126024 250850448 709176775 684892925 146090791 904071105 528179804 226191661 850878005 554796468 562169174 833339655 687407005 746318034 538972048 613744938 190732145 798803310 897110550 696914860 628062052 694289082 616566044 275463353 642517774 495988249 907371917 162959611 27430900 407101007 526235469 97812038 599549829 67611958 302246197 563030746 625219566 181316652 842446079 795156405 274964132 816388198 327939542 274495565 412031004 705110679 92406689 343484262 349951650 394948406 508170390 217105596 355165038 401467663 373692990 292273082 474002803 145640695 101855992 190516029 438881474 561082593 627454512 137632919 431436480 833084353 157068096 693823148 544657849 181696123 219569549 780733976 377125278 975735221 379285939 62311746 626005894 443756142 48653110 980237663 899495809 72030575 674036504 870948585 546710511 684004620 740448970 483495710 359589831 177982505 277878248 412319256 553239588 164823344 17669209 526688224 511477541 439643619 290853026 182844275 390875935 739347016 10096655 749026436 814181720 233906255 872507583 986589934 189472305 484197269 617241266 860420490 940110697 715613539 762618353 606165479 125602185 590085885 167880064 796108035 76317252 658321069 335167684 619193843 719680643 915296369 657601383 577666489 475790603 69078611 306765336 993761317 862259759 139196616 622149834 386259943 413744481 831801002 924005189 347552861 209376703 995967383 748879565 15341623 605787842 957675052 871884072 165633700 730746690 527040949 697526015 146030562 472237490 964938973 569427878 136654545 993389849 902479212 594395410 245930469 309948772 761457550 792407118 121693692 972785413 925356186 425288864 465073020 7492876 294450093 859365863 412287402 946145260 319891019 851687067 590570241 514408737 973517037 659912992 458212314 163008952 599991787 135558943 456308784 529475018 262303517 665359177 785468831 992752032 225920014 481882573 691375708 556046195 283088618 759344859 178643732 653772860 400480402 392011427 523739438 861784188 22329514 858703177 257319671 992420290 395340820 307458340 641436101 314278324 14410957 608029487 618651912 368404994 250558291 218038778 385588420 718425223 372727871 818738930 243747989 281096568 465494711 251138096 684225605 902056602 111558349 430163491 342671123 831113632 862172264 968366716 380894878 300655530 695701468 386364880 785763740 740610596 964032065 898613576 73353642 225802412 626161982 715712150 726783581 996574111 16065378 356908884 716172021 203191881 712566021 615633218 809515830 596253556 157296174 389629345 775993058 755012716 7770923 215678567 809734797 763279277 485428608 657564266 300629829 93497558 368673260 316285843 896993340 345089158 351352937 32434090 407676626 91328134 86348854 944648649 412263917 422532463 571018848 996979634 215816656 789758617 415095980 381652711 882210678 750583121 762971534 232686403 877630898 420563171 699231279 850276859 711605585 928629763 985661418 709094273 142766880 464213461 215427791 38273981 278019625 887621050 101363364 623050668 541653437 436161123 16858326 348615178 133789143 437465408 276592116 51781076 626655140 935080251 20353414 309570644 7792268 833470861 40739295 984994037 611890303 194061321 23176544 921746808 182681105 526852470 259377653 283369133 989385592 54142379 887326172 375835986 801974220 773377533 650356690 188838087 69861007 135836643 918921377 744254489 668184330 551277369 341040898 194952185 92220697 653071942 571984183 384869761 610368562 168528187 207080088 774510369 631217815 335612332 339638490 460845141 48957999 719651373 412662072 284429582 375371980 889959499 28604997 961603851 7600737 352603122 390709820 16902988 616013614 222594601 424435621 650988505 899630729 647783596 164192912 662025399 501135024 101867238 693814563 995275743 978940572 255431393 810176471 45281752 639772980 326017859 761937445 203702210 424661803 992479366 155035590 904115184 868957358 191558040 692399808 216588947 795299881 431291894 237007255 765514913 860833697 460895940 68595919 545609280 322001570 662465618 497503552 68836270 739077545 139174656 421339467 259453147 963088554 913998804 17318587 468004593 486771455 539011510 512474742 434661284 446104337 784998045 671058230 439924558 552553351 85885626 605058235 748657659 273567323 736583733 802914566 956560204 603653738 635493629 43961051 212787888 239723196 314725128 927326927 453328152 88947730 20996641 181739490 884928628 793754119 306507425 629777839 643485208 454399774 142915473 210849213 237328111 91261828 188914321 605426309 407903494 976611951 206021868 873641290 132266685 517156981 867979636 944318965 35820721 86529496 689327185 868202497 583092044 22811066 291772349 86111377 601508567 638466563 940647107 685969224 898014942 38905582 755537737 300839712 548194430 500513485 454620686 327053509 777750905 985611847 396072693 276649097 329542326 22207273 25891968 396518170 202492735 193570503 749168771 279696604 320609595 74205747 492969250 357287426 647624444 685400164 562101955 107043017 81351917 471181834 380804389 182313744 373233487 923023785 811058997 665570386 32974176 246112188 277190658 885724010 523587197 844496690 931503757 74076099 795534460 216252528 912316308 121446418 695734178 437892875 329275694 222812369 28714508 372494454 534688614 420618645 181494714 444027470 209567063 807958578 191646428 253415787 115100910 920930202 291764944 464318624 230606279 407958986 403114327 21820723 955656390 917460907 898168007 184505120 460345205 157481971 260546583 383232520 392373067 231107872 593328356 207886255 635649872 117175623 167095321 228261426 757736677 350316466 88059868 656903570 940004330 979646304 159784734 410897212 843416362 184450403 739237180 721869697 287137031 59449102 207123635 620278688 954822302 788146193 34410375 867502069 490041803 154827307 301106703 843001120 55082858 676070072 454920262 916199870 319568457 392484454 847908306 781435327 817296793 5143342 149059056 430579848 992542896 293973953 380026 176748093 66352409 485841489 210122816 565620912 568242279 220642942 222842249 950920451 496699590 154517905 69284114 418955629 378983542 447155310 960056609 75879221 631171271 754044262 35039135 302618606 736926674 822264119 185859823 144224755 354479606 178568522 911370818 712786177 846542459 596004135 972431263 810278993 14520110 459197736 549746441 469262320 664159344 688460964 875500582 366666241 304005538 914606691 654749801 850441758 2828397 895774619 447762402 638304277 214654703 140227865 902516847 79912801 163124607 345759500 40033409 136154460 890696623 996797379 976709387 646757011 665473700 657063881 175265042 701852557 403393515 262977302 181372409 869857094 38572737 372404393 760574618 206512244 220679930 305880688 919469497 736410404 2886329 53847443 596288527 290074522 847495923 935857235 509405790 261373939 93164169 663446216 891553701 491153007 452021383 485853045 941750686 985337893 863780336 147366032 29912833 356229081 857933993 409441696 752020572 56477070 793509970 479308946 403697504 397197308 138953997 395080274 205421006 162515441 249546390 814157247 857986146 526020254 852303988 266917754 677197383 850376574 834281513 598838939 736232692 554841648 799443055 182085021 832518196 225620726 555401379 382542578 91557333 26960907 256960233 69005110 847571252 306747231 919573044 708341205 771534686 131180264 617429910 409492309 580372342 580223199 66201025 72004918 640692665 56026766 496609022 514998316 542957773 711987900 967938337 151941384 554206265 356620645 484147922 977887046 233534138 810290443 662105575 225066835 96622237 488538685 135435852 272100581 938376792 439029579 186767212 239659621 596511056 927093371 910669220 256962164 682357600 243495094 948960155 102487833 346501770 477572834 380497279 409087884 575294805 487151799 543027020 462417378 574152965 983069621 868671230 310118026 24864504 410243540 588694375 780575016 659570213 888373319 552755918 456107162 424669021 651067017 660349093 420655039 694047257 341905310 295297104 535669890 79899329 144695101 18290535 676523295 783790151 867676258 652371087 308076885 861985466 30120945 363608147 180383351 466963832 865380076 983599212 608358440 816581432 578849821 637649992 548780896 352846662 465336608 519126018 467858975 297653199 120264256 260921222 439856211 459749929 340789578 711866020 317271453 152311859 193663386 636246543 526314934 575770780 344336145 941124925 400926225 873299053 251584933 630762960 209443151 815573180 70978494 209151001 815861547 595707149 268953396 996853975 361497821 388504555 417793548 841207336 163141811 968501103 80283946 244281227 85655866 122944295 594235676 192264845 440850327 367847103 732589781 212179452 177487428 103846393 311333881 973375126 260670653 871102632 138653501 800275888 834152015 903531141 617407523 142918895 141570993 212056804 585249372 761163110 53710938 860787780 10487901 824171251 333051344 626992265 658615741 972942388 358921288 308516093 339866689 746793320 18841398 782252100 830094771 218417312 826606054 98018993 368013315 466355273 20798067 500377377 411774550 331350112 626376275 968757766 754108976 469163642 335156174 970669356 22002866 724376509 945487861 190406529 450852784 337256476 178012053 205872090 847701375 693420429 750074858 433425656 839757165 523304059 11287691 277223302 29153532 744888760 89189636 997421084 546900394 327483127 104021900 293946774 489494870 698428859 506163899 554460533 395710842 479973786 15101762 482920218 707790760 494685315 240918723 723737857 101417180 892712023 583782246 400288316 603798306 244760258 355239709 587049649 918033580 652044137 336105828 589227817 367183659 145874000 394420860 363875937 670735582 401682772 191109327 441512918 968769494 417728209 615031496 312657156 435910377 948848234 297006842 537721839 784290708 302873245 942484017 168567804 427949554 99688317 454940859 828021895 477314771 253005677 371633080 507767299 381294779 860885750 918634975 259213393 224671927 357705926 571083634 130108987 414872005 383988912 331257564 85516528 909690084 907308593 229494849 69426838 352873304 562699894 470981186 956134762 115466286 665888291 511965680 750926360 933638718 846732108 145597565 6841659 306195504 192240883 238876032 170866721 122790395 735732847 663055156 94915347 576424178 892434270 321989834 290995120 547528954 353605924 736956179 617346801 929833814 83615829 889958254 418883163 953071475 899335104 732184535 177963813 29777357 893701060 516455366 813215490 787297002 93550503 892542690 63871088 807772411 720401053 226302019 127986294 537143090 648168609 633737242 445595829 215908314 982820101 7206566 187132066 77412610 660677721 738814863 717386876 803474424 207180817 794418497 832761480 760743929 104963495 818889691 270316646 625539032 948331611 381176829 415816465 277334007 378606892 572793889 772298637 82290553 541334323 707037768 310390078 986595752 712785452 813968519 13676814 936650088 387980001 808552600 669378156 134486492 226533852 74158593 942621788 438764345 125465889 722504230 203596786 589742414 701652696 26576741 448548325 185486755 143792762 147999924 632401526 318192376 631428653 345245503 226488018 285356455 327341176 415903764 783062298 845331320 716715971 719165395 359959335 299332428 263789987 996101540 618099981 955301365 144128909 54219686 445311625 945120825 543190888 433586802 118384155 546388807 415007502 843783772 666103908 756965055 866479853 287033277 896719097 149522520 388449134 950145619 406448277 363976175 745282389 238203915 397024579 419153349 180830123 989659520 852353734 966494764 74996200 296424504 510302302 369970547 756713955 393994323 611455040 63272746 436077014 169618084 148022879 675169973 569418429 567442000 695389276 138907129 504168874 718762546 125611964 191790097 524921174 441474377 101324405 49247341 907269087 281506022 722784674 867901360 897710837 598482202 972743196 218290687 726047696 131502010 200379285 730017206 381818104 484701656 29300558 843803950 167521439 872631368 15670614 493393924 933201878 370638318 993161522 979493563 139680326 367628711 492130642 945038730 587675785 869103826 888512774 968924106 716130053 609087873 321308688 974108008 965676212 458555599 442032447 705369232 939305740 411328082 475739767 993183709 458531661 56209952 864424659 838808652 57080950 953210456 253272278 533753978 494629620 447525341 630989148 169139133 805729746 835930159 91811970 380203409 187998749 185698931 292062354 245101317 96475531 993232099 671595652 801901140 118387321 3613569 464701266 254656384 783462719 878310103 949037128 974522405 924695382 463122869 763771912 91716250 514167605 343788928 304582847 592382641 164332688 550941150 724832249 368542470 368408731 820435080 643257129 859449647 795412224 35076320 114657402 186826620 316191617 884990296 327439887 329674660 166353870 45290902 245979641 108652289 789601795 448094860 559977319 615994822 361920940 779075849 145330308 211916001 292052178 398213556 318810899 250970770 265568776 826524887 958740262 679954959 842110372 993529493 822224480 697054450 124482673 978910933 721959241 383022341 155792865 175187456 696183888 154380683 864643887 617808489 834528353 842824534 99328458 555773832 267167381 789613867 532579541 422243477 298738332 73878912 855764765 474817236 786016870 284182876 208946382 320604024 929706676 758776209 788672568 43390592 904808534 651240593 348756596 255167508 728298199 254531419 932774533 166930237 18366180 625850410 736058616 614263267 450447281 822437260 525594155 57482516 586656710 742019651 898738621 573476909 521818528 276748185 955577964 263879150 402460252 293830172 419280736 83656241 742905598 145040959 931878264 859405088 357831428 927217797 893747778 23437373 443433293 6064076 910207774 417367435 923905400 68529543 12608839 589399117 966133790 729767566 995722116 689764941 725557911 749736403 817401181 974639809 496200288 381582235 75687281 1376756 909186764 511756610 590270509 844832291 666503344 875147525 567163383 493933300 29492024 300802521 199005225 169115519 304713759 286278869 167660672 832710096 926168676 351309800 165475124 337821390 604769777 574671582 613041781 72948757 691724907 555497434 736785931 891090249 357523779 60904725 103805959 191827167 429544546 476358058 555003790 170027348 359189538 747332453 452196652 954485319 285428154 855248859 885152855 696628838 982858750 224700547 517493738 563550766 727961862 652620467 66817582 893122547 662690345 613516013 878925862 786994919 474763418 152054228 912540233 925475121 753953128 553636217 462632410 322208809 254541420 289160092 909026552 548636542 35452507 257133504 982878737 626186177 816202633 696273852 687058262 198130114 825849977 865075323 840348627 363671979 162539570 732752799 789730373 415720961 884795221 991562579 183430766 594183934 597633996 927332022 673794598 530910019 98961630 472819958 546159792 662778301 769783599 992891747 688744754 72333042 965222828 203350434 725282372 885979385 217393630 203929211 120308507 640879591 974442098 755051969 853682698 425677919 135293075 973352493 127872677 495290752 993668719 840863841 938007377 830957789 91522895 514526139 417001208 94990287 474503320 798604170 351637639 438337604 460467643 385521471 546524944 862000800 467805111 558691579 293348239 722833691 561180952 216529230 72953993 885273976 111599888 822875175 309950905 268488627 688691909 410498957 799986793 271900111 326560339 468695942 911733217 948717186 909679228 418920631 432779040 129333340 362559536 475487045 281753157 567638176 300966372 744050435 402567281 50855242 313010694 964199160 132044654 64890335 388707332 558332885 917172320 786862620 954687721 287993015 827317233 455840164 378370357 680863948 31021235 788850108 66037941 909608235 789570691 629346288 413544438 849067403 610122419 986001415 615246337 152569694 928637299 914153482 565489171 115461075 739819931 97362751 626396039 151111470 401439808 623921696 648042895 998953346 217060919 207587833 258918132 791557915 598725334 121033701 989408497 673552983 278614674 855326309 462130150 105278456 266311683 979773699 108418993 237912277 707848646 430642479 322257897 373886349 409064433 943355792 294314514 784774570 783412892 417912828 232417648 209074455 550790967 597020546 445914053 364685119 527328619 56540549 931864900 667993648 90915589 967771362 756811056 607083172 498059136 104415055 123996835 802126282 330793128 134159738 549743027 442262670 963268309 760805761 849601313 185973750 268171742 552710803 571607826 718549094 59372615 315658890 611107337 709192123 850133498 141058506 285641016 296320609 996056705 362365683 697327274 192627407 19590850 235076491 832086115 766556516 862081544 346473524 164179145 618191164 963514444 812441710 212766616 172713948 310102760 556417234 133400934 80234546 852835379 64840266 971233243 40125377 454818205 439303978 946695233 104886325 405712773 505603043 122943258 613411692 28451754 301978378 266847194 122331598 373335768 60121401 65730011 121512875 559613548 199165158 531584880 854476997 773523429 370816345 856042979 195067036 835189843 270325000 604583921 146300309 450484507 754230881 388742072 423834326 198649754 910419400 92766282 439109178 483071152 36673217 279773508 172853446 314267772 165753915 555510359 827450255 290453381 484863485 339488538 591542452 455211194 565656041 173498628 476928617 555457349 896049194 464604509 121221321 415959120 321319213 404323306 510623165 631698022 862176674 807197599 896100111 458912451 878039419 121149547 425896994 85207738 714403468 517985680 806022244 356060979 196203271 136841052 147019108 266987496 168328320 571089247 603892080 208005439 741359872 94327995 452580384 640884713 921935818 875700310 36952233 667342895 416071379 774168292 706207721 37159073 831499521 258949344 507697003 434524180 322278879 596539494 961242604 41010805 84045324 80141822 781167481 593955022 291856378 162102134 26468305 942893323 48201104 973346005 871109562 76618420 504713900 549719433 879952889 47807747 475094920 351139331 149379996 887510197 975186668 621231399 537840552 656865512 968628343 763860384 218216815 813762944 145230881 149099738 178144815 725948617 870330002 839359767 21074428 955873121 400967428 324330597 742051060 808830621 587377532 305328991 487481973 21772990 844201501 917003081 742871361 384561892 459832290 379205724 539159391 269677933 675985549 541333540 787198121 286101013 286908753 529774437 455708668 791337420 213365566 161610854 720859824 535404583 163649606 684411708 190643386 611947150 878954950 530527686 268665219 708969208 230984111 717365961 706009237 471324305 106548498 390618850 71401979 702257497 713636618 975427649 55728008 563025023 655951766 813899086 510682521 171899578 343448714 12656066 690475325 702575594 816067158 105251725 130218203 500546295 291537370 250143536 540267589 958509560 830118945 324962148 589772834 535669374 847426085 832120318 945034228 8225709 61399285 599542722 24330245 112807406 323625531 983580394 52974805 293655265 312377366 736269729 464381126 121147862 410719975 540903337 882270338 819189582 114219367 479478637 766760112 953090827 416985628 273575953 536970497 153646313 440609517 980702194 590491562 70578131 157107448 160532871 288025181 390330507 93284836 962832867 641722049 298744240 156186708 669623718 187237299 910888056 697159829 364740302 243549980 446195984 535632794 195047512 57343290 944312689 438585755 640150008 54529808 57910253 891328815 55250228 449075263 831188463 200673317 62485003 378088354 313085275 189250321 620667442 746244893 413073075 113918130 274487391 750088965 423260591 954729572 213234061 758922047 823316908 108430523 641361176 900354903 807038691 798847071 762300235 712217969 621970708 16273474 166333749 937117949 994815411 990754681 439687967 299291827 560414028 88733217 146749227 572644877 357088283 804081257 400834725 961210581 617306534 802731657 667881326 413650613 502041508 837746331 948853520 927029371 973614534 150443806 863372943 439745080 618450033 233449761 33341371 137797248 63835928 165897809 322951074 553989893 372221135 141617396 168498830 644905411 141681959 953465524 825429322 154119604 983625521 580776826 496109804 413691979 593598729 491432650 436095562 315028218 33524505 481498197 983778145 761243488 289518949 90356193 896852266 899545870 289346435 500377764 603379978 366659588 365275950 163286434 435936239 602831535 6000056 717045212 392083123 773141653 46754139 953325985 668641948 91963218 278768667 26215093 252840530 560586144 843633417 60341808 871297043 539831136 348086987 157392680 751497114 777970609 200564349 61887172 504135360 336623531 221278722 412031672 101535278 545599271 26876602 370539176 239138352 388071866 531541621 169254276 430479920 284244771 989085296 946083433 864596323 973841574 32572269 986766876 784574410 282796987 803395002 445150669 571171500 238673684 499702407 613546335 997520520 344414302 915089162 85211095 95374787 463033170 124973145 607754660 6863432 156539554 7878129 729200227 616536761 158807575 944736073 112077925 537026782 263633863 312715329 646734838 715977455 339992615 186627214 704640618 191686148 390387120 544345006 654313819 991306426 628312116 887388530 756740083 561925047 241668158 538142473 298419537 920467030 859127234 179796815 115770456 83781267 608209290 20832214 66182703 120078916 581484122 376909970 365463150 359368630 546120535 778561279 819760045 218752510 548389599 721407163 661298972 483740218 682646602 691550596 877964719 572941183 951903313 60141742 986549419 104235061 913574755 370263731 317304525 562265732 782708318 769394217 556946420 591782286 18529348 938354963 494623800 500787945 454641783 528255613 339436928 852322730 269884166 729739499 61254204 69055134 700056692 722450289 750060557 308112408 209722369 84786376 611273196 638654127 512393779 527173401 537496614 619512862 267847459 324186010 525035673 945505846 914645519 317943271 866357342 68287865 604495244 831257406 49886642 457566187 36555988 211952813 292097487 697206178 454680036 5432343 35220719 245458083 235827728 396645886 43127571 146926055 693013577 942144305 424189741 381931034 204326475 188314022 219248041 428396477 853671408 982634555 823601431 745943010 632170322 226355602 824014928 769818401 838588430 216828037 627409882 678777741 737971727 823123990 998685038 742214337 783803231 141467946 751909939 993629080 110252689 359238165 948665900 149339842 531028783 190864633 377962251 873916441 871700030 802135522 911703021 756713968 605706451 228990205 81150683 285674599 849623207 994156182 830152484 321427347 126916006 270591419 232634360 751108413 26416452 343491279 416326103 189861994 742101107 725276624 209422656 31672274 958913408 126240996 785248211 74516113 545059112 698918599 152546173 882038985 95331046 275064444 604273696 542825347 636761812 922412917 944241011 417727315 921242399 336264885 966850808 329963068 236817115 158298049 269509110 941171605 50167780 222884317 310781927 340910088 39341491 642710534 466139955 953195579 739091618 184837056 66031255 118067869 242064953 717694964 746766814 687202384 154741916 36251208 731206610 936922540 350773738 228690469 875110992 553163867 585441973 568020822 257557077 87818008 569523467 531786172 342566302 721518642 137592796 153154442 526772215 487928127 446380979 424920654 569516545 20562103 204300628 682552535 938406578 740892765 702558108 625780390 844760709 746252332 461478457 909290646 722365986 198448728 286033806 450080395 723084378 138577134 245644816 271046510 43469972 109927355 419482514 105121857 620185219 33284357 883538641 323363024 667183329 718955044 581903757 901786304 990029020 198985124 147374642 311722150 919852305 25057072 272378487 403049964 280421824 753380124 224081817 962188445 646768498 787228758 167531213 628049411 121906316 305832882 332652461 615962276 460138690 956703814 962266728 13315361 45751256 896433378 124159808 209497951 307409079 804002390 127848424 712112974 183324124 53902567 482659045 101106321 588555007 898887360 810057111 416818656 831657261 521162466 111104592 434430227 173774751 638740051 912882319 14085551 724800564 487112270 120815762 185577543 810470501 199434098 441934513 661135738 100188164 642503450 966372468 403702012 843922867 289422884 21771652 348900961 430763373 141720245 196987739 813059521 362519414 592665726 579832409 702814385 715768371 928761637 509940737 944990633 886817909 259962213 518810265 496481988 109067652 174294558 414030258 795104244 5200876 957404565 93526545 30822862 843731845 902625226 698850864 121483412 449422196 5950954 893144529 744296117 410349367 971871205 217498691 622804240 248402412 281719788 999905076 412296350 321706835 311935656 868970388 796883094 349557071 287537823 734825567 709273662 623470073 61395458 149036543 186027333 663289794 619952466 235411915 43844191 578385915 243029162 66399692 492777456 706996419 979785941 921374905 382844394 629811494 623341544 600718991 283215306 47091754 334941913 184774270 206355507 771627522 296722779 662675553 768252615 703484164 830093001 231262714 208034171 914130482 424834358 947255012 66135211 749601754 210496073 872007644 150757800 171316802 66661988 550632304 499014943 568215142 196580262 887783803 312015757 879189753 896241189 812498443 590344298 968961983 158724265 959029 270952448 457975364 765196995 986348278 664237444 712231516 858617316 441539980 471621161 325607135 119812263 509116492 410689514 619945071 498801540 621664212 218297308 358474294 624475935 769846200 98274940 569998893 665084485 822892471 990598718 688869044 239296118 914226135 733482540 547552669 112184367 816106692 6119158 740850436 320520994 185737679 958528769 614296105 783007172 924947496 458194188 528119394 296173374 343140008 294239015 110004458 65174224 766131282 899835568 477275436 689455748 119866801 753915826 361851668 911095581 624820818 994910943 478493443 930078787 441665014 581967245 544790332 85627285 843268853 362215631 388213427 599618949 506900859 113625958 185108524 304464480 658159263 231159090 681917696 502329439 113492474 514765471 577072803 886848051 766116913 95163725 265149959 543989980 541654746 170541782 277903690 942045290 856581931 823934628 82060261 562007120 222380427 521955931 138216603 670068923 491924448 434430651 456708740 492836321 208855757 272387400 586637770 502982542 990700254 348490749 459853874 963358290 799792588 917552572 384695594 85114535 454484530 282069744 824864202 464981458 142436826 405843524 768773999 984220348 613273723 588903935 608193851 424100700 88074187 147623142 526562944 483338175 472973786 464679487 813509883 609051711 72228043 36391851 579287741 954260673 505699143 703052987 337207174 618011969 198100459 401849810 144988784 547243086 830058540 878074519 876816708 713767241 837478854 910174688 369577220 609561044 840092413 106756417 451324634 943303359 462505632 676513338 922981386 232116957 642466027 472995941 82675576 622951378 863295700 903570671 671492857 349921569 875124758 141291 368838168 629173788 790428441 857138323 950157640 610787392 645577342 679305555 935601243 421841513 184444613 91153493 351469796 177235110 183015709 713221691 512171270 652735760 585345966 273933023 962596027 371831211 726696885 537750660 305469980 272924139 435757716 368533880 515456803 24202844 587597403 753718638 792478338 915445615 589748485 78625018 642979035 659815314 67948546 115593016 639854820 404892755 790809119 181999394 344700092 847199769 978013276 37393058 901551401 795485622 812178655 637652981 891860625 548382874 292592791 889780254 664879628 239241888 290550087 335288516 48144781