5000 24
588446502 752696044 281338657 730384878 100695590 250032850 611405708 158690099 122796360 770371957 710031686 145915351 162555254 228033704 736241150 269013706 296817999 919496267 51328840 49968966 788611961 117494300 117926270 402597806 692786436 500437753 686508212 290502366 643929176 792700970 223523932 704215440 127353476 148959359 441383469 22609294 914308681 484447204 464202486 711290667 83497701 553360110 243914148 585582676 95460541 479408320 397086868 625590837 395720400 154669140 709163713 803861984 159687960 328307102 386999083 547210632 209389629 420898227 190270129 414899598 570602014 53803536 98899428 371906004 366100998 158944947 644861014 695446284 291355131 497171586 597402960 685070399 547371796 655016197 684005523 225788240 564717210 711304752 98529802 248510539 882279707 377569064 146822754 54469974 890192152 390023614 940665242 116829131 989119599 768836055 135635758 350714260 444245393 398509490 627005699 343374259 603631415 284586505 246526223 81263371 47117553 712723397 343538345 896663240 567544554 151524038 544944734 411892057 312543913 513736821 875442559 78013044 476163992 311538983 476027752 864411880 979960864 761388521 889715281 256650550 446703321 750935023 452298438 128054440 304610955 922311265 987244171 384663250 689683265 412307671 591325173 149939789 146706007 890122128 684756845 882316958 860212137 928004283 590411377 12379793 18251738 536910881 333303820 350715690 278616844 819111906 582302880 469071252 129742926 477464661 788758091 443837584 3278254 965705970 546006692 420371760 754715077 592508214 774374807 865803014 992341424 213782689 647623359 824959747 612887755 414741560 512999215 287043531 425155906 218634279 304336775 727228451 344079239 590845074 72552683 304090937 229527596 107189384 964857931 753380271 115060446 766066841 608237056 42596480 603656186 381236484 981727460 571384421 958118097 919856169 29700678 685166668 662745701 107643804 583372516 29507736 534564990 17735843 288051197 695154052 460583887 756952713 349027071 844251224 180569351 385287070 132278477 733226640 287006458 762908164 29081692 705614389 502869244 943305537 793854817 801457953 926069416 717680841 66556047 702601066 648800671 20897195 310194802 592719140 574230146 98069118 994522140 132851968 668183599 29631602 582811056 85928271 83038067 513743072 324475339 835770122 531406574 610631736 205763069 854148288 639514747 206757964 811203366 863143310 389088885 794268655 292588890 660375316 866925216 142233726 82279540 952988779 750335046 349113043 765488043 828302774 934919171 58921354 10507076 719977660 682801198 666385164 599909588 124374868 778472675 370631410 58513197 205693083 94125888 351794012 761961295 328124030 422070478 802553893 309589906 273862230 220368338 622304257 20448300 795816393 573172457 12310909 478020271 63912925 476979509 383960913 735860577 264047530 860489592 546770271 227385204 408649196 964439777 51701596 653629109 434265048 932798592 438298228 9427570 835579871 425946154 792020365 609840888 544426206 673697398 306458974 172266995 316576823 943903410 66667751 826203094 781540954 130662502 860191047 401297492 869981629 620491826 269734685 868094429 77122987 286821306 247389209 217297144 721590379 274823054 524062804 259263938 671272665 843339644 267514523 791499624 115623295 906817679 340743467 224805532 257076578 111503349 769038129 458053973 384166785 968934597 174818393 777298137 887280913 990352404 652192737 980347542 805561662 678515512 300914834 986509630 173542723 524506685 667061554 929402166 182574859 748723610 239432665 622358884 251545476 127527071 713562977 107140202 528351268 492676749 831566918 608393890 273247619 162388669 519609296 999737682 103090416 596889146 892600179 139756183 325473139 615189846 346957360 123271243 86388561 159852554 116348155 333736650 249016970 311901935 69678847 929960029 530260407 251678194 121079689 570496504 621704950 935132374 437835032 822671849 806151218 740207749 500286278 270071285 371783870 744991287 965974768 715829226 45885188 571788385 588607284 271374569 613737675 434258128 661216985 341070774 574474977 966207063 501040440 626365410 678940641 596697986 107782164 813058945 793112881 976248247 326496053 348135723 138915104 815677806 321315154 679433661 103965245 202933730 260197005 36787120 164910108 732467724 200942546 860765056 256891970 983052097 918026924 220363785 15049137 22213479 678987609 977660967 405564291 722272002 508948464 895439305 29488788 759435745 9379950 362411945 215740175 761444891 13261533 804582578 283373261 138150107 848325497 100764302 668978046 388276972 231474866 525158118 97557520 956792151 27089270 463951712 367607877 561442065 547540978 565031977 125045468 899816545 452166596 464696424 949109725 455467180 492419549 601946895 132687910 728576158 685741522 301360933 121733772 421216601 247329397 10982654 516043857 48720906 475663486 505213165 528934098 568787743 505207524 779478321 631882760 128774939 433735911 84323248 135529949 189686300 965137467 940537550 458164260 542569531 55574189 377065344 663434470 558362776 355148607 737950331 202664934 165516348 741283864 86121438 676629816 444099482 104240455 5189384 858068196 448279021 766408754 647184627 176524402 800376833 386613717 62039485 646081683 849672266 386499511 72484572 143266779 79528390 865772691 416959043 123085167 893449436 35820871 704535406 360984602 380415297 895988879 230850385 219025081 9360486 987113056 370964207 50435868 712927084 448180265 309484458 513451861 255336807 53469203 405495838 103353567 3407820 676300210 749488947 816265695 677048766 516206718 189347746 437331685 177128165 988497999 34964717 581284859 503892890 54056421 848968087 589298651 242281776 233510801 695704596 303136214 486661181 873485600 932128084 561897141 703675398 158290301 801872464 488145953 816497322 759465985 574438773 351720087 718922640 629701494 525360799 271816097 640530762 489197669 93039691 404694967 355870696 331051373 678327564 19547616 817400892 465655270 759272932 358904300 858421286 8668550 984552779 684293251 682093608 760722977 405167646 354386198 950457862 815216302 113011068 490090385 921241497 277049829 631863186 466977818 295736531 313656301 401568802 58263573 342157203 75962852 510619397 59121268 853824548 166956758 923814581 984481915 414263548 439417118 942556079 567490865 372376991 99480983 503917391 675052132 118222332 531611870 587117817 649338404 437912502 350378015 195692412 693333315 196478663 131454697 45824565 406187809 61263109 375164136 904146950 533091326 33266812 815322448 702065342 897625975 165073294 554795406 520646928 200530060 800324250 618358617 863911628 684306586 44766764 576540591 223841509 985832238 861026248 117517561 463433464 956609143 88053979 312534623 470043743 989215738 28785251 969219922 920901630 580432539 718935840 105716588 314743392 586157636 762099201 87832375 193730110 975299302 160612986 346282403 169765541 683552686 394241867 700420250 317660810 763132691 343380384 3551559 622851140 587769219 175224104 453502555 470977322 244744935 397324291 932667487 31805228 636425672 965639330 871035077 820770945 920671128 462384350 537254697 457280249 817939634 201551046 724488261 428875968 830692852 696744579 272201858 617444721 826382149 544524706 986434372 172916273 966478038 565502163 203333347 976030397 279523807 24406733 318907457 340342115 200633429 855690457 452447617 160654061 491143776 144051013 837636768 647468105 804765544 216975419 639524641 638180214 586293508 274453988 719506267 266743256 115201643 991099850 608276406 871436665 128882642 767738283 512247907 419386125 624750524 992379285 317139975 716119251 126099841 637941214 391920240 279279010 529331922 545382424 114645504 622964935 676484849 654172203 153898858 403320981 478296690 512752724 715386654 949743252 175275350 174428698 509290587 166136999 859557952 228390132 869749318 961110887 137437354 822535907 662475693 516830539 148179450 912233176 120869507 130958492 8969137 584107256 742042040 881923664 425921615 502591216 626516735 188483748 682360325 846139811 848117421 966748574 856382784 459543546 337570294 218009545 466583609 509856319 547169678 470888444 286143360 58397535 671670701 347062288 986004028 895296187 182430428 813087016 756007050 467386839 746585377 46043850 90430769 130095409 540951391 781670432 611558214 782345050 474784807 76116302 813931763 94456918 901486589 732289728 340761054 270007497 868779763 915763827 273877438 308089639 846187227 52393884 658025073 997075058 773580978 430225389 120150790 799007545 293215871 658499550 378034271 353919895 676774121 403145625 255346187 773225372 324362949 627633520 365477608 202770660 466096369 23835469 277410715 793442845 655455864 40595061 482562073 330499976 551275300 324094598 180717265 885949753 10538724 384188671 906153829 774134393 978220321 375817075 989028129 223165395 892351473 485365278 86263155 703062546 341748879 397630619 25207747 433266290 946504334 88319010 874200802 675689470 462125791 452962535 248443237 858969590 15540580 438704706 486205225 197882767 869643487 284834180 653156619 937189004 202878724 294844460 623104470 479781433 213521628 226858343 86903563 768356813 620691721 916724611 627866627 513056282 427985888 596954418 600801626 124358178 427588940 387958591 583408345 942519377 99052579 517332005 208394065 490247260 313343237 892867053 209221515 329205079 140470370 244657540 401577629 838224366 837706803 224118600 995630424 403699994 519258069 582213870 932805579 865731295 604536032 625818477 130684492 690075916 138604479 650241776 649740283 262941618 611189924 33940479 327907682 986878721 270603598 951032613 142690950 445791477 201271242 601550257 110325636 822346688 883837328 421670569 721508988 793451047 746255292 286543068 98248817 12007380 720762780 731012769 135741012 250259272 160548517 181592060 820285023 612703050 14190375 314164295 988020428 797315796 53243494 956844981 329559278 792943499 662649287 103765336 814558956 357239544 63123158 775244603 269963098 735153004 788537534 418558145 748832792 659949393 174728095 856271173 352857553 326237460 472855724 397481304 915055658 60815562 341078840 348138352 664007346 866118238 561512421 768879224 556210547 651243984 579838728 455900811 440024161 999158673 518002412 31811101 443603485 746227595 662410353 532956401 881480762 463938325 418538864 78547793 488587392 41299372 611104596 325346472 584800313 491250175 353678343 830864645 274193592 492208047 499629070 374023933 665761149 838501952 567421936 977218221 668826157 590525236 206352333 33238045 364112776 514502199 766397976 520848608 588962725 446852666 682705255 177567678 415286627 180330078 535694583 558410593 814502660 303575389 895528815 883201808 828182551 927195146 711671151 658390205 284238989 279741011 942237809 504888218 471751832 616482526 172438743 334381348 418014951 673050890 13956751 587823178 78765821 955578144 642242598 211097867 624874578 901362480 283415434 302665267 174448579 500618542 561700708 675512643 137323128 631968117 658444381 591791941 394922005 15036921 431352144 941813596 362292879 545359335 776616992 215383480 9554120 535951162 377531274 551527668 696730493 277417614 397133715 677830670 779014556 187289600 915745278 641082492 432217090 460489360 222816317 676594393 204611752 78427904 866731171 893819617 594891747 925955770 266935365 493715239 814796624 873196545 185961574 649889578 953052472 535076834 572302978 428930364 766005407 335793463 645516540 556127644 321371952 666917351 678148397 17819883 91069228 200308720 580598261 548407052 861635744 316528382 187726744 964784163 913189180 743671640 458697511 963233646 744827109 132663045 102523184 734953240 505545953 26389127 938861123 543282231 274177152 402566494 453794636 626739633 228257810 592016041 164338741 320707429 46245971 213881357 547695212 646519981 699891672 923897743 697621388 770111922 481802782 83460935 790707919 320800361 874743489 117992554 213674184 81423997 819736244 642976107 921149583 744986955 973900303 88608766 344826426 856705827 157314481 382634494 819362858 286893306 596076431 465239394 840620425 690398655 538314775 134034897 996592876 180375267 24833809 350564288 299270013 623128390 505710711 50641211 889076940 920931558 639313919 908169192 500678843 544879698 368659414 177893949 226976703 771168450 615362489 938836889 762837621 208859259 399940178 217474651 109127025 429791851 335273721 561166104 916198327 19780255 406439292 921191736 666630555 689455293 650451060 514782758 235282292 53698323 170211907 12731209 357984132 201679775 655419073 300340462 204049736 935242732 624076025 350180998 869867454 940006274 988492709 799893409 302774937 916153188 294981228 327169524 439595804 101738531 407398604 839128644 266396842 683344646 660231848 101113441 427773866 929963930 113074678 547937711 982089301 618701272 286897539 367796165 709312867 40557655 509383602 862739252 471044669 31112555 428671639 657098512 147530988 816460873 34188357 432888508 835206938 820517737 76361796 443350401 232486735 795552585 376872884 477282626 621578461 888141500 260862809 695379185 746491341 914570594 624938471 707836800 147912292 280755414 428721556 370175340 642066463 18046197 863138689 347517569 615758811 279805663 135780818 660673580 194556419 850926729 223817100 191920999 551057546 337966532 775793672 235352607 666235605 916646382 457017092 493850747 264088329 585490952 409018776 328582741 779067627 115824681 554868156 89493417 472146137 979951446 224367986 208425669 102059122 433081063 244536823 80266750 652136727 622241765 873860670 896828498 719230179 983265566 592034652 306923620 895753422 121934676 900232786 307887833 616475117 188556260 951725791 875588587 857133948 863492313 962098101 26644587 548909757 411525063 413515282 891188949 441311020 28394908 472165968 940707986 633465236 827004201 123970191 270372865 342832234 341150377 12964530 920022889 778305759 759085172 163751788 205415151 720743959 419043402 665379873 162687972 836758455 326196305 83018365 505251440 494071558 136667894 208344643 430367967 309154393 764176966 722511616 964875201 888082632 506457723 76452721 318253061 387759221 542583539 516535269 671498650 324589299 87134776 286317801 169837557 842932894 675009020 246292960 457165151 510158491 451999790 693276340 378230782 699196137 813404272 38554525 866725179 348814663 140035192 553129893 238794240 846816628 566233530 503194185 259695073 331541271 102066038 89807346 283889044 365590953 924660697 502938479 415791883 923977505 904468772 372015765 155344412 633990633 35443384 898702403 602318299 494089191 309857391 43447273 537346847 572158224 686395510 720556886 348049555 638268764 631728717 860595328 791589233 595870637 950990036 277350294 705356957 547040916 991312222 852971547 879959488 442841234 944371023 414572145 202166626 88800001 926561341 453136279 737525878 45015574 727561979 244908885 919173037 504981844 78565315 527860294 60916416 974809238 444869219 477950660 984575309 354969980 734619332 660986048 926389560 396468748 448982838 756432624 981760202 622912416 549349489 877217252 215904778 588348950 364625674 169007757 558718855 210593583 574250586 572967069 9572511 626239616 903012878 179277320 554563250 658508689 333468101 780408915 955774544 896282366 698019727 927134832 332998239 818854326 344714774 164098810 374084040 671060647 341610960 651687723 87692535 436067307 491309417 915160817 595670495 519284003 484482236 760481568 534585553 136353890 393880674 35388794 57640328 43834694 671101834 71298333 164509080 865782550 57955785 172067753 936436579 884650563 112134897 413802093 191451154 503574326 459949475 587128710 117445299 700352572 231320814 198484273 832837483 12776581 616924139 553192869 629944206 454281564 785564558 329707234 134822329 289535758 153928780 843997240 493846564 589659422 346166080 305549557 669791844 171762099 786299566 229467977 186785109 164135352 934645644 12520789 238490993 364955560 668556582 51902258 197403722 862292394 650818475 281431654 875534618 560070392 802674330 535969548 256107600 819899437 320344276 188586323 229769348 710683512 856645348 569628413 697559639 429556329 113118798 832284739 51042402 690737055 90378687 261259208 617761304 108665000 431899861 467696827 478587818 950115320 930646799 925370291 111032366 885761428 343547767 34252025 546463690 29181246 121200606 38210839 594864373 911419599 440234630 365728102 121167826 839064098 294815584 364019545 775497562 92184295 807906684 477900133 448295231 441656630 842564818 622936025 180040009 912863192 145555053 396892634 365966965 335541663 421545345 311549062 960334444 189920068 813516956 226771539 990369067 969746208 331358125 758398299 891573180 993889205 558293616 487035527 38075504 677675621 911306788 15373946 240299238 377246502 225916319 883532749 82411716 393883877 10628674 175366735 221781867 547969597 829872251 127906251 461621582 52302750 84698048 722073662 188023269 681381394 454158593 82709380 855950001 119369876 966221024 900257098 659382974 946015843 961905309 50985820 760003169 248939316 417821790 93307217 104661415 977871109 945854649 232618870 425211989 507236114 787740824 527074418 540865400 194666930 780427989 320516631 472127957 272876133 863330471 775081156 646354286 580890233 924693224 407446375 925386367 168274339 782398355 789233001 542616847 611155573 364438961 899679262 309503205 578188376 240096776 81877476 36815269 977803375 769873100 891229814 294266709 720426031 586919826 115208061 206340719 711952031 363795839 408732315 441874609 476768219 88897121 172980447 560963969 855154106 913649286 24231165 56776139 188599573 617143747 494722031 115266569 232411977 699261140 553033890 160223578 943224248 950186340 844885006 434592429 582531493 110483120 332500378 28478711 704772854 788664806 597629927 118200747 76001650 678128942 668268390 365228072 737395464 792604760 773783898 793350642 494139537 286692192 791181988 800676240 231461166 175417214 693612974 180552842 532588014 955333713 157724582 303888649 9448126 601065839 913393567 261869633 31838634 500065745 354468932 372689741 680023997 272777760 839898825 992275239 820024852 465565183 238233810 197138843 685188465 78728239 479332091 64405448 395179926 921711072 91783537 802808696 492028828 576743030 858935876 158793457 135949757 741170547 511924089 498316967 137664046 590201521 151603231 307739551 985996744 860390630 109849951 6548654 219250978 343723861 319910837 21959215 878807408 986897991 695317072 840813464 418026698 495842768 480553017 214922738 131228197 416839212 475998577 130268219 48866374 679145845 943129811 23123175 364405957 169083977 526590952 68293836 110670388 537244805 451419884 801131314 49079013 580543880 913402018 926235383 919542598 96452293 696691623 374714494 221477807 338823153 29310530 865956192 992889362 190744249 286973888 518700608 509085155 650394621 892919015 97888155 813103697 23191863 875275253 812507717 19148849 566717804 800914925 50314400 618729251 547498873 930060146 323172257 829920217 350184995 250174536 974321106 403949388 3013232 448361611 375121392 162033268 160216593 280535692 696337369 675545095 560045360 222211297 198553201 436446080 854935502 253318028 217953921 488835460 10035278 360045010 351677923 465290476 119772787 237223952 19215768 331669878 751924236 662730516 925305967 344924709 353956054 173689203 965353543 51063217 616542729 397509539 733348848 248311759 879142696 535658877 534239959 439838501 609968215 849824193 434759975 775562712 110053757 724226078 629655424 947625711 974800604 613852156 80515935 29814011 582109855 978836327 115619761 118447527 554163371 519465487 926304264 688913379 724194588 279284955 550888625 98806425 522085857 868061617 245672639 775775419 181027976 719752815 692641755 166533521 920690145 464478962 148982348 642769747 276521185 951900537 824609999 280839661 886392362 647352479 618708725 130677731 409020631 298698952 250538273 753631230 237020775 695262992 268387681 14037932 78200083 120490910 13307916 761057807 103346654 823141206 930740053 916537461 42233147 904824224 386130757 5748647 770625625 756349978 562420977 407375396 105698290 619816048 268522510 940815186 528781768 627628398 818427119 179174551 814829439 228194746 858573588 587804578 169735848 634898193 261325804 833278441 38369245 7760439 671075171 636818201 349602919 428868979 978730492 102343366 581280957 313310233 733381183 621304719 167456939 722668246 474737586 241937370 971558903 73007958 797476455 619616393 205872085 697249845 130687997 46829823 587951388 643074373 972644375 524663844 478956901 266488166 270634216 2545557 632248421 409332002 712774820 824215857 219420570 279649291 706500788 714833598 333067108 921915723 832083452 265589599 846404396 521892905 282079417 572182350 901307294 455055319 835881024 688602375 44407292 191441217 637273544 302442915 334287753 39379003 992140505 887334573 700006146 196619059 670798504 971214602 983998269 414497615 668020423 778387654 146963016 811590899 44844060 313491341 123024547 437448948 125656762 611117216 442079762 761476719 362205388 648064490 908584911 383134106 722913097 395341079 56085334 558751234 920519832 660446974 307891304 942591210 509706184 89981873 116641362 958287790 402177665 787685293 328760214 166623901 356932646 202783173 119570165 483273248 900649911 78312296 246184612 132018998 945684278 34787490 36958540 206017228 645555012 354145827 853300670 391104215 556676319 212773229 48045309 642553103 423773059 508632463 860483209 763153155 509692798 138212895 742944589 944255457 412197511 653243955 547361459 725685536 103785292 809658717 324871990 573449223 961679579 285528825 594017960 927002576 731442706 634369436 600650886 799652839 970042985 542916521 221054705 435636678 195813163 501412370 635603083 271632203 734204515 551007666 822248366 280930748 934000695 443057487 728134526 333624515 780658026 423203627 598768946 797318930 899999919 522196556 2778546 602734449 533141601 976804559 496981001 342421694 827892879 943432723 358163362 337390509 225787870 199679227 484782941 638925728 998510477 731267267 192102840 856212475 605956823 317107004 885374688 663754425 143491505 962014571 899221690 857771752 33002261 30624493 823147374 40139579 92838721 111750645 446871963 133086137 208489817 662652460 527640213 476009825 118251600 255329242 387057918 842623967 435599802 847901900 995118246 518674640 719551082 50933991 528164713 202372039 292185043 436213107 48600040 753599096 828230837 605356603 282219606 292710703 984808162 659971177 782762928 482443072 789734792 496894271 970089217 143367010 800103528 252432967 685071901 55609818 369857877 206333283 666279817 746846768 413608438 764286833 504984432 932490951 409688613 99284934 636167429 59341049 687478108 153374186 78691209 446662303 566411772 950585273 342737471 300736936 497175117 658745831 421438513 375665649 502048622 577425019 265468125 334981109 298258834 17160842 370091077 716526236 223294997 177264591 668486329 262088163 915475168 117820707 182237022 333743208 603037716 604315392 683184271 223840661 174921868 757084952 811903350 275826760 749025823 604238873 259938959 176069442 896135207 855744661 96933851 620644451 305282559 13024829 779534914 228383322 432835051 707946288 954330027 622005201 592668812 901486778 938325665 455930570 769817681 166491133 676055357 945973517 88096403 331429325 663738739 202129650 942318033 443198919 415056354 278462263 540607907 812747591 50270025 730144884 463200446 310569529 829296581 395325607 184210262 684489901 871374941 704668866 345061391 518352977 598756150 114053425 296848665 277312201 26651316 130875617 718422845 412480836 930993099 351926967 988118976 661464551 216636848 563073449 771599640 260903874 202371006 341991358 984507539 686654310 885009401 898077761 115652663 61409356 991991720 463710276 436220391 47383281 401136953 714939324 700481194 108910041 950811637 234391620 554745726 800193326 58049062 952594643 978753531 910869288 591377370 877019901 468814644 135805624 623296718 429788652 232020628 516159450 864521701 940815544 898206724 588990365 603352496 246144678 724944041 648451163 807831742 972614948 430815731 581397122 130629722 722371303 216282695 662951057 639862240 803974309 638640031 341443812 917723013 971160149 808559428 652237868 870022086 466219420 798850714 900090537 587278030 515618266 923336498 569421532 350237855 689013816 930031484 726910992 883947772 999515910 962553378 428098483 991483630 662239388 928463898 741054603 920205352 808257423 124609207 458671329 393813531 921731346 456308254 477521260 407167837 952700065 714099546 662138330 998089369 43635709 493643132 297208738 987245972 374517813 478018322 948394109 945696705 577821653 404859578 525973252 752646049 946868335 78252262 288443554 945796592 199244589 820045089 184094772 851691451 699673885 835496338 794703112 378250251 322263064 608507043 293010829 295466384 46309696 998623152 635512477 300645661 123647794 66450168 56987861 256748537 579994935 25531774 489210700 695664780 969333890 250954068 756074739 175364387 667377993 556923941 756415214 259689752 68631709 764494380 782415298 378887391 582223727 428354400 494372261 315981911 898952848 208417006 179713498 650616398 486907547 216431687 498269059 731511428 336669793 200284355 800808074 608081014 854021408 820959694 773213160 394285778 78226116 546174324 141767329 976011795 195433155 758561999 436550977 914136160 92748477 558246544 953087073 790764354 201912106 749116215 65586453 930259935 572733965 699519642 403431771 590807553 359364140 125347174 811616650 39458705 830352460 828824487 77976761 736522268 405249812 368336644 797318951 295493834 460078392 700552098 558301362 988597983 64951876 927434503 49503383 945171498 268553074 950805891 861980631 680240360 524617254 863529434 911017612 43507082 690633446 422605725 507737097 673976415 604204572 460167362 976389335 641802472 618972995 31086198 182751394 833094284 628491599 94464567 88612950 569005794 447851544 328627271 313521825 679052791 853311606 862982923 289697393 692959362 671316730 36432032 882634133 221025394 754136700 853124769 5133041 617922282 222302004 442150351 804750910 25840240 897073722 561232745 387140291 518835730 632818526 693322142 425607340 282357014 268508335 552786364 371056384 905456734 722150875 927717831 480966358 539711826 530176543 631252348 283653521 281905613 99575760 536681558 464881112 204816043 102591662 264640011 622650614 269206552 86371700 973858387 249296351 388176475 976101401 71240818 481417942 577754571 207727930 475995695 345620810 65698532 267281543 380974893 935695243 843292686 280417340 878519012 68879449 539231065 259906074 428410096 917369285 11376303 756949033 693221658 423575373 883223105 627619003 889188545 28696907 263868581 819093459 96003477 240748550 919189842 995207785 422479043 242938017 121910 531241380 515720127 771367736 748211004 758971537 685075985 989962254 453065617 619399177 15610998 211347602 411124430 636421299 244380327 773740337 355729121 663343348 475220144 664821387 30666771 541633946 657752241 843238229 550278736 98106516 123035037 711812793 283929083 750135513 203921109 193493637 125598385 387355266 313787069 992774280 175866880 190229875 950235417 212064372 917427340 626030117 313391684 501391756 893970940 625323474 673131461 962295128 944681757 97890474 860404035 215332760 5786075 237283986 926662110 640335106 146724116 713775992 372430451 831181312 820458322 77955248 309293003 505558529 24988194 476182416 348766343 576812063 744179430 956730396 324469635 438128757 554304942 217803811 172138745 636262693 614061916 720814421 273698205 670829208 8496255 277479758 487155722 764782684 20368453 631031025 119444533 349749682 27602195 788173411 547995503 455362882 631179791 724183862 100350569 371063000 752857761 59812476 703725676 350726804 582913548 469829045 580694532 532586893 819220605 883651977 314963479 270658698 498286904 225046441 719114729 83681291 436069714 507867741 156999112 267450639 129984810 24332445 836950548 6279014 850111104 904531965 620118948 169180088 92942747 425117184 742506001 325227599 108351281 34583827 468800969 827131768 188498320 222609951 196882237 926865655 798700065 562599496 135166516 908117579 683292948 321588162 334188330 333193656 39512461 487374632 994796736 174303224 904759651 790478606 781121885 50758605 993378485 148738356 819522487 81924626 397774274 110822330 220641646 822694914 870677878 175610653 183306014 987906283 168171120 118624383 342991190 687395267 439370435 441549906 57266740 958290285 797211152 226364293 378697355 532451438 258828777 91130202 178885652 943475978 686755167 475827719 873005413 646219161 616424532 356964755 997246934 264683473 627609737 609148509 154751747 585357060 674540800 63812490 623149728 394304892 874008537 266811199 501606102 1998152 372234104 506849367 315272630 66721134 870345324 274873094 131373040 72340391 696433273 222923207 397233638 677816272 393961960 24049987 393967353 970705117 381486187 431077226 441184116 686875435 910464200 456332342 665131452 590573952 354558280 706090521 186442914 306368219 232509406 627447501 525313021 66061474 146187138 147366129 191164223 902552510 95957859 151639891 632879651 734670028 205266405 884044652 347563277 47267088 923033300 513684685 66820789 21513915 822827503 975725933 65386506 158644387 538136588 923420298 613363721 747645587 934644445 809747160 337043341 165523716 505824573 759399771 280815170 92506804 991998942 395832989 992253829 104379395 712391456 991926266 635727323 806365607 604362088 301762324 343419915 255143411 507332062 461030661 380314706 928469263 279636849 233983524 630710156 636700389 486335778 341272217 944041090 283969213 746649782 166737881 731558491 984939946 67394854 44076089 61114546 583699997 832259327 189816219 538814205 736225878 669372372 427299471 523774341 941058343 899783486 560294247 503920182 252466473 745630475 324423382 105151448 693064646 588350750 252206898 321050636 696164876 333334697 783225648 327253557 766120970 274107925 562383748 868938068 521768978 726850521 970967872 535701178 399849354 765341824 821269959 878463725 109898243 846615931 286615496 846899207 986160772 75696436 184721504 757246507 574177379 172541174 930134584 45294239 291122722 639813880 59119114 767517755 641000577 657044828 744313048 365462919 789031413 753574943 908193441 100041624 358081025 452092655 207278879 593343975 817555265 780432556 32837135 230080705 548183629 955702526 940389101 70293931 435560908 483561357 515341682 934332638 745140519 864588273 322699388 737601088 25914309 349106117 885562146 854068343 959580248 858789913 374406442 152309833 87526154 926174011 68273910 720593739 509479066 604285361 893021456 197957459 573240584 378752117 139138162 239307326 223922762 135969713 443016522 496682577 887668237 901595403 279131831 586404119 896429453 710973083 13559828 452532623 278895415 34074222 557522475 416787190 453811663 859630302 400597583 770350194 995316920 655408968 548010360 181818006 579999421 944164483 30115911 126103314 943313520 44103144 678262231 921425721 62683045 789043078 328095331 14540309 98977719 585268176 830790050 130141374 27415333 256886482 116925668 969735197 921328039 865062527 389347810 824547942 110288953 310658423 979457452 472032654 225304118 944377221 608113692 741465236 673205921 18088091 541650335 469021138 208426126 872377930 937865884 155500874 33620118 28447103 224343630 274954854 597641963 238840947 392694844 262138899 506777310 807471654 933914196 551342162 615948920 329987848 882112511 916133981 615836256 551063408 557081115 435373720 295108807 684797530 510093897 112854944 594462920 371798531 758320513 435214981 411648109 805107524 175548198 835898203 238629090 534219988 827150255 473468037 578339880 80474979 224486283 968515475 795764857 702625859 152398848 510493736 731149867 84538994 805518236 374810586 529076068 259639047 98227131 687261316 184720084 626358969 614184498 516491173 782075686 377779055 489798290 180250195 491380285 374464324 906656042 133179838 130505057 753180546 66412006 979599939 229478903 354518084 987578268 523928413 256733103 256236140 653088801 37012951 448249409 689650390 904224381 430147697 377043786 333078614 478549313 603385314 205582558 582590070 146924714 384286883 400770497 528681818 900681928 633292088 388684240 521736559 588100093 490263253 117350836 633644266 330514052 877592903 388410410 732201017 783992360 466217778 36908062 438286677 300204821 252153176 255848456 887029214 913351451 593501132 691443676 719713767 564800610 240319764 102586768 402255953 190924330 211896656 497108361 934702305 466702926 982184356 431218662 158736243 869952261 235011998 361092782 97442052 310216351 496950775 170090422 127689988 856261040 801890340 953717436 425046444 496458174 222058578 197097145 983890251 866921754 320983938 69412170 212106776 562559652 405253634 704513609 454838768 986879023 88683172 233598728 241326179 710356800 85281203 321356639 316207976 935901655 879882959 637867456 821968707 660470699 516137329 806625305 894782274 830422851 206014186 199130103 479864366 754543452 797208155 359215100 763822079 127295858 538734073 731029750 389475077 305065485 194954069 179908795 601226678 595539623 314765767 268472822 873516102 156622962 473482815 324063107 281634980 923149650 306191223 601060270 807207265 638502153 578779338 423901136 384458931 328586218 199331476 75673718 982496636 388665300 9131185 943784565 997295159 857041596 515819517 399264735 601960150 68740922 460228587 93124910 419281677 268092458 902180030 891035318 620249167 40527496 496212869 525107612 832046140 546162529 736966574 398925897 613770029 865786040 93617666 882655355 140449092 478551352 921234674 536499341 312131991 844678225 36809907 166248396 618617927 670034936 732584920 837180213 204594687 206662255 142714798 720102491 350823271 276964508 795791152 700241411 448019215 685092818 48009614 916452752 490287472 767115478 981600010 576271085 911084914 601737892 478315633 955852687 196342238 309470505 52974605 639619133 925646094 341030551 658415481 457444353 656850498 927770334 26147134 96563130 951621527 50445457 939530156 135039614 939794038 709794722 873165062 19935235 620145131 613312636 34719723 557671 547683405 458347453 88878271 939310072 706462864 584628456 465345755 30675411 7298978 300628736 988014756 10142775 432771997 637397009 644819151 382977226 339069738 675682997 244184950 725173170 644923884 173926807 505874846 875827358 481162470 655204145 841039716 62175026 302740737 308263273 249273824 505787618 899006132 586925372 310618498 241411465 287741699 674552245 344230688 122220322 944097932 512108322 14294058 758631988 743061530 110859992 529397782 703690791 25327779 505221086 586679523 208411565 900512066 588303739 266870651 140548957 234227028 271020741 824273123 128720751 187476760 293471632 468980389 555577311 18526543 784364871 691038171 689612601 185845756 121510177 855688828 840956502 811122597 68133080 435924964 399873725 615113724 240149838 289658013 399098754 558782630 555435071 882684473 264686738 243928632 273576345 416218582 675400312 424220619 608261606 457279993 698957000 593482826 260549559 330818327 636231699 282857649 202511221 21686091 811704604 791226478 965417122 445393211 155621417 789369552 501284005 594985840 255925935 15662348 851249121 777650300 992994674 628559758 257426354 301365823 596835525 246906993 196313414 95170127 455252553 277988651 857294162 57806690 679748030 29842086 65785506 893173732 692851864 439343170 247249566 428338982 557808275 597235693 741816442 837388228 571591355 85761663 901098020 58254843 464184761 552439592 443225265 460222824 458685973 228277069 100461626 187364948 253131473 84022282 391403935 329188049 27367729 796834173 993177565 872096555 903113590 736938918 658201049 109940687 750963042 739076692 275195677 826719278 545949028 774083042 956964091 852181038 489036536 842276629 492622929 896701223 951974461 906470935 499936563 603024205 551483781 377631171 718829650 739969066 104857293 427215645 1662909 98583566 587901735 767749065 303788266 634704051 291528871 140510759 639366696 485787335 925517693 337559218 802050396 852783854 762677437 691860866 943653015 630502762 28975020 949775167 811386904 10626129 293510772 467618712 950208893 487664604 667175048 472337359 672786470 95099150 775553590 91347990 53100863 621767830 591155164 336560413 313092399 962821616 992392168 370669026 264486489 166286362 562751206 11342527 797419066 421044087 893347914 819667946 817653394 670742364 501663750 125268150 519630985 837065731 101549157 477678967 635318229 324660563 482560000 636332717 708860341 787693928 879155284 991574800 417110962 368375847 824900565 646562978 386429285 992149866 717066179 456635464 77632020 916056777 193971426 217434159 330755107 376633508 351162515 361995658 477140204 602018230 500083191 24007414 773702292 716436723 130109652 388434691 632407974 232530192 172046313 613618282 246117334 557230694 658983230 728581569 864297746 296642528 615486930 515356041 455649306 509014837 946454857 204129138 104198512 539668447 95672405 32009710 302005882 538100027 413777575 879591217 248581619 331176091 872279653 262233786 697776093 816511018 17261685 167672214 90597883 304999064 386843280 617144567 994942438 161992185 121451727 779248919 906454991 361636756 499873410 9059878 453768479 870704954 548225451 587192387 793952958 129290489 679106103 22800280 460773445 186816999 516275102 309948690 664166723 302550143 246062177 191083906 602617921 739646318 264735723 533522327 119362927 175519255 437398613 218274541 699528109 543728050 220788435 5633520 207136042 194009549 489859124 25506071 244783475 667978975 261401360 866396558 825141520 349249019 371554547 125087045 394206022 246908403 780150463 506507044 53505899 778464117 823982472 51725851 921491741 58942150 153483692 625814164 930140579 97422357 30922825 389555761 614994540 658509309 117286727 261803128 479805633 258780185 928585840 360292309 452373677 992394252 365177009 938011843 195995765 347900049 238944152 392389141 48707383 361538074 243196322 450116292 566070459 309604860 498668048 274181643 254989289 562519502 982086018 237637859 498815386 974501402 525413787 640813821 437494022 43585971 977847923 574554750 869484625 435885833 386446359 447644603 978379630 573471803 823787376 523834042 144805673 978614797 373133154 503418113 239016541 957812551 360064464 141606025 508335886 93974463 726344929 862655047 434581978 90963503 75237061 628284663 440223164 531172477 682931491 294735722 728381185 497350148 879339036 433200541 646406668 931952089 810685658 139371631 615182133 516561517 700332518 857765525 260118599 300009907 75256810 729196325 267310592 399729730 550618798 385432239 773198183 236868839 290079307 944684849 214919653 955638392 107406470 381745472 474816613 152649767 357853215 861836673 282929379 794379467 304469582 575022684 676670960 229497162 893560772 804129632 839816454 45790708 700009984 312891914 587774123 288162199 966106094 110591675 904132873 537690446 381831377 178941374 355481439 983814161 397810240 404989464 46898183 805935246 944680499 373839426 378759465 505484991 17181896 498537575 988440565 590828415 535128312 683630285 224361449 249898845 418189492 909508740 632725902 572298550 824249926 122317678 15131851 845205405 542205522 756838207 56740933 555545702 393071407 36550253 89533518 856517160 181452381 975558280 777830838 431436626 604241751 48973341 126672030 636651173 228177776 778238875 137913632 964731987 305897096 610883960 931953222 685280323 338406411 280142120 402271490 335672519 46098629 215165814 592186516 878824031 279313173 741727915 184184633 926885159 237397181 603859680 261228787 341177557 41898007 569503015 424551418 631746083 674623074 277869810 926024913 848926913 595021620 990126188 178393777 753899579 508876351 605404803 355424364 207590971 233687763 249590620 93741602 614545904 429894721 726443315 649277008 790123242 243909654 703072290 102732867 294792539 40178477 179290432 438823289 949793811 783781901 562497940 67471934 238546028 996000860 530958352 242631925 631281217 388991412 292047015 779553230 433133802 811296229 892461002 485980445 533203799 809756918 969940195 9395292 169875833 680295146 297670692 889819218 848622166 448475531 332151435 955792279 116434757 785717221 18411095 407725395 2591584 581462352 741540349 636158974 729770966 375006427 191311704 836309400 889666260 502143563 974325927 929995703 457114533 634245166 745482817 875250737 776346145 680299071 973447708 936984324 515606707 911053432 143066881 396992066 678755301 256443512 49718671 787403547 436458164 49885497 15150089 264460058 541910589 298217558 251626804 973895520 629289392 484170760 566183520 552578321 446503433 220863030 55557603 725186469 103908113 524378244 9451358 667634280 766170817 104306019 372786175 825429547 270402273 389063023 856916611 481316334 236657739 657839175 716455350 375584506 424030482 38336570 248892160 577669955 835303366 654021149 295518381 963952837 883689429 691835376 166746960 179742860 644407313 900626288 151172095 714638040 186420587 832973109 294519492 499079440 682577559 488272508 958641394 206738786 309785828 791046273 464750678 384583796 413516936 405839858 688439286 795796903 6442493 204113215 366851441 100737441 246353131 71767596 377838226 252060213 753960676 214052033 348572853 228754406 405779809 986506277 702818136 157612312 658009004 605632964 499556563 879805055 237502737 322637557 237389026 975247905 734672946 885933846 793939939 33226235 167748266 730368059 466039276 30644677 270920378 399267521 906401772 146595921 567942387 328765363 532559365 619956089 635825704 988440765 523891626 713475517 262894345 414939421 810892846 925744488 698695521 527620170 863400091 466540928 151188206 927731473 794677033 853093079 488673595 853131612 49815687 725382041 190406602 122019390 712373483 669256648 561876542 865529 630210047 551205043 87875222 601444453 359078658 521106074 366442392 265800716 266891675 272357365 126862538 772260829 328311230 535763605 777887471 920735644 999608687 426406112 251431003 632249927 886939732 202633383 718310264 65047337 800507706 144481145 933990035 750945584 640680821 102580594 777541274 201408999 368077014 28718885 308165543 318663759 304577333 795199294 889441294 687765628 382329972 524359419 359443665 196313871 865488935 529725070 306605240 200857805 972674327 663331999 991189720 73586665 875274457 435913550 548842049 748609323 224546774 543324230 564611736 853470744 34293709 748116415 124202032 228953989 341959580 638847082 288212119 626114306 461409696 923125616 614198557 735076623 810515416 529478198 577268738 799526009 639415452 399850359 501123416 321034652 220898577 721620175 63575122 170980753 742425429 177166570 337543748 953156349 704423066 729390548 83402685 156008581 100095649 54748208 234838353 350447336 704230091 165846665 640171692 297304697 362358395 545392538 526137706 922721924 809438218 757194482 238642731 655882959 103444527 527634315 120186595 68737591 454470123 836318893 770673812 125541683 281571338 681520530 278124213 745230159 104697216 556153489 646547547 940678434 960474226 931117464 346470445 904347717 531371115 156731913 960452508 667698397 998063573 790003552 808269568 898834925 28550467 26368332 191411625 922719563 214054799 34916478 875159865 15706286 752886453 788143550 686594960 448430279 89436899 187870099 405127562 238600928 619020186 887153224 286004206 468582360 12333116 614648114 995682718 554621773 283594008 879905255 490365002 759734943 409679732 575409458 834633545 394544310 190448612 708374522 169758008 323444384 8056724 273043538 774772042 590759065 865227535 650344173 58361914 201504682 341855608 901989888 953025090 612464763 779140987 368632823 21936827 672951884 507047203 495615471 170265428 243805819 4945283 94213637 482855910 150603172 572777574 231136479 880586673 644296856 776252069 824598108 694539659 430428421 344112781 166611663 574607040 147314566 673443532 968268208 664405601 145828352 985867927 671368222 879723823 262248282 625386543 434504248 773551196 36471306 619716226 841230607 910238005 949070313 264562953 214847945 879085299 623824746 770526127 777365442 419851823 309599837 268250153 222287718 636063007 248628435 904785430 51230904 621802971 798151227 922438413 510030470 466701330 41859840 728991177 592607716 870454928 278088617 726393049 981933570 491254979 580475403 797883195 585513938 573699305 97912917 762523722 155269855 924295343 637163892 167890056 971411772 740548506 311507105 581204858 425797707 888834890 13189327 498839632 571131015 423576389 6849338 100494712 444141645 268714890 865499949 975301568 859525759 632046594 149606229 938468334 825923915 598945008 581860677 906212533 913829080 197534669 205397797 186742667 588100024 788466348 378964965 722469467 115491270 260590130 229000839 338926762 682856792 741556952 836683266 798749064 398105433 388859841 549162618 952673646 752724078 325774484 344138841 870734139 948631718 268973138 387196248 787883387 16492666 290998627 670132423 176808256 303512283 365525051 50912144 735864269 792944781 389943008 256537751 765734768 844276842 539417877 144507311 919185125 115673618 217919000 782724041 694061644 138894669 167380503 162074908 114656094 329362429 94585540 144785374 310487055 818984306 317128107 483724512 964199286 627529368 637518181 990164091 506049668 261302595 376116317 555595009 960199161 776955304 595754683 124049006 342129089 845607609 895865442 270291594 45109202 793523775 318517991 962514329 46949036 704098130 644277948 110461997 642259657 485617913 191856387 79930401 239499579 25668911 399012864 428467242 662651705 724829745 316496625 576676436 45291338 620804527 761959567 254478465 534192670 425286463 147611636 123114045 179869149 12272013 628994881 804101626 377422707 993327599 64167641 86333995 190858723 713586694 412769141 166179883 662766210 159601323 2346564 613433231 988160849 25307688 973623877 840132012 46420450 522576317 17753232 951660623 677199632 184425717 620090000 681555979 526366261 769842929 125284404 378627452 627418170 841696511 992349521 714373736 648208981 164995545 719408706 697591064 381277706 747320382 211827308 773596260 82454453 659456440 29387951 770357134 713303801 955145120 323989218 680919336 446624149 885046898 708649218 776742097 860210096 2948873 921374805 739608122 399669036 980902801 363559398 804073797 383621978 16867254 412381753 903930804 858078986 178558782 946940612 905293724 169804642 28546607 965956152 361532219 104485150 403006578 623295459 766455494 267933512 511846741 2154441 284264692 73375982 757724959 507309934 404788070 225977487 201169955 649048344 101486249 484722888 678451502 82654715 900732256 159082763 921019821 930696523 232219743 900248159 746067929 538719176 247479382 866257392 856697273 365589948 250139696 755528093 590147332 448556364 864559275 153493021 913946573 389911465 998686928 222696385 648252694 985367487 987537919 531462211 457648548 526748726 610939200 969192688 794644123 311679518 655734329 729442378 374840412 696328980 724430540 328136374 607989901 319590592 900015229 837359526 314512716 308902599 537523355 117769993 326154136 188783488 323489410 293682333 391804784 334736658 170438140 598742851 751347066 538966703 729726957 949920851 602071330 732188094 453718777 569321831 277090981 219240259 49388420 606860665 278972526 95257308 735743210 168928358 838868314 793964150 810970887 657960368 334773009 56715748 624590678 387368279 431727304 187586624 842389549 970467664 926790791 607388234 107303376 729374428 756013248 398404508 352209861 181497439 862890393 321026424 951783698 482745560 382286896 467558253 165242199 702085713 854508808 389973667 917956717 435949620 109916912 147818634 387716668 891688179 577209220 812724715 132722739 975299505 480415801 709379451 26385248 808996356 461203767 174665922 797441801 357912307 729765579 14806038 876549011 866088953 392039607 849181480 663903519 229251829 675828317 222488559 258680313 232177575 893841325 635177606 872635690 519817559 901371253 578724576 324847081 546998334 3979496 268033991 8979200 453591827 570401194 222681962 698178246 362318244 122720845 996020956 875974200 79159813 547755847 324019493 137862784 217020626 548005853 318483636 360755810 444272490 934691428 182377818 869282829 518042658 251366491 24969949 329933685 873775611 386529060 513019674 99491400 744943450 380877943 741598236 546415520 83964020 365056416 382458432 396944037 649647464 231374582 982348215 490912958 563474803 849066258 412748713 538130444 336985185 640152928 609413752 643989120 163000011 714044740 252732218 645722956 500827020 457169680 584642653 429950321 966498142 790200850 885264937 371266777 389846692 832094492 564519576 669682897 275499839 885810513 507247719 268232686 630981815 682971080 688454310 602504467 820415785 304472286 343470303 864322544 997732186 908257835 925098720 800993895 125643212 306123072 666009401 405538612 20494718 996758103 679509435 373894047 206096809 176009390 606960399 535731064 990434435 571718336 148642863 228453582 457342299 906981887 82138605 367827017 362355670 710754640 88119210 82233204 445585586 937463206 666658537 889379462 862115292 810426697 788927710 224891308 164337270 449743413 425879665 911716306 85494524 956171453 923596710 387726005 29938909 215685983 849981400 126271755 967382253 542894893 443226318 318525612 812707408 83915806 658369086 22922056 339484052 134613572 632290979 783992342 859011735 664733072 734208575 56535909 242074793 986178816 582698078 21680164 768238717 460152169 671530295 784737463 990994680 762361 70779168 859773868 928817022 579394786 632597959 513712236 427428782 497731056 116818181 94888476 541086159 942620880 168399497 443066220 533358884 75658566 348804202 138644073 749078454 990510520