5000
509598375 368851316 853225829 148761518 106469854 536856387 484705909 480369918 395660998 626648190 411715183 207967997 498069986 459402240 696996624 192043526 959453246 407368643 80584109 753395854 574950533 444684361 998216606 8487421 730047390 571196413 433602733 106358373 573038306 696543476 808067906 320916767 959159241 738077512 383713878 848176574 423439522 667487985 346089517 609105611 574640582 542626205 690195212 131427488 944625642 107398970 210635774 170509757 -6713974 512157641 941117892 296453096 654007004 941471330 491688127 553641397 370775612 521511710 859149234 85712027 -9374422 33091768 105752218 456383984 406100287 711521920 993833173 470161418 60808192 541165134 128122409 135115777 397385037 425901297 46713772 962666880 984095676 35407661 990321756 100517373 37961457 860123366 523907562 518613993 703251795 496772760 981345476 222221458 118137291 610107672 6270283 540621204 313410511 517266209 153109210 209923052 772869777 518843961 926399406 260812445 917254191 504690334 415884425 243725270 915047448 -2730932 839085215 26002752 176113027 161569211 875440058 930768842 732521728 936512097 188727570 893605637 944364356 46383340 622663259 392836245 134046271 -3402523 308027358 909031308 758680981 455636898 315584054 800016119 908597171 622656145 670381043 577375271 520516484 688479374 592927257 963539333 627152506 719005499 353333993 543876594 223516929 159217850 486714526 642657489 249091309 368648267 296357376 530379938 916372999 358175337 977838947 896885421 42524062 440976286 405608234 137369500 289030952 275834281 471373426 614483223 719224130 948715214 338161635 500514522 463739200 419795374 636264232 317209620 81789993 536592493 493164301 210252485 957437478 229308530 824829791 220862376 793506793 828222547 19351942 92830878 302180451 865733316 686851628 659072193 724462269 405411088 383220710 135165551 408327111 907540805 851771039 584585357 686904235 125732375 823921254 210469186 48678282 108994501 840642829 988702541 -5764131 431399072 993362009 512358327 401396554 173285890 458168123 86123079 402065893 830058855 394389265 936995409 498671253 669869728 516466973 976558337 313307912 696247782 64792381 651689084 361112323 970802626 112566895 137498977 531157353 986073770 987281965 356056039 591088054 532021699 843179355 720121360 983739265 405804126 226413811 554209726 36649424 495058374 305791678 537339238 642545141 89757594 710311928 608466931 57181228 897133482 983697848 68037465 140522156 951768309 654088675 914360125 797964770 424039951 355131144 962372369 422082446 200444557 776848171 143895110 360334422 807394718 972056683 781955855 730475315 149756104 733189513 929416624 69421198 369549425 260403661 878289249 723864799 725028103 605315735 8114903 295436642 10652623 653972870 841474175 911653486 447552892 -419131 606694772 999579012 592101726 798355412 110038465 967829688 562182831 193945521 103380390 161449654 223695161 607084174 620413751 595224678 156984556 361252810 447328668 29108195 34568794 436587550 235566266 609223346 654322505 473421175 629601134 845360145 240082161 462424081 659845530 719427239 983956773 74699609 322837245 739143806 934532993 79545047 32730087 674219816 646873612 728857527 833470695 475133438 128963745 990643052 523955453 949943201 628358871 718207099 650278 245991061 214588054 557100054 869264201 452299782 945766312 731788249 977917122 372509913 983446739 642597580 97310122 145809455 669290222 25422572 831954136 733703513 979269781 912131483 99147913 950776993 981801658 213344847 30183776 451662801 77387595 188919232 296078713 739142359 66202647 911160467 508735533 103249221 388163306 576815949 727166046 380448889 518708180 898024336 424652712 30007092 483364169 479596333 948958892 822979608 819215831 539439196 918079571 991017267 523504567 543101867 201699075 860025721 572079450 229283760 212690898 589257660 905933822 388073018 913381421 531000992 206213177 580744404 541455558 42818856 554748063 497866828 754121456 58796006 467842075 441629909 320739021 626339429 817383441 866585203 785633722 599403776 350993933 743481323 772621573 815696062 996096129 650968446 624742701 760575131 624614032 436190130 689110021 974789789 965275154 35981250 795790197 123456022 126551496 172564767 227871952 901986798 795162691 707179391 120136956 365539821 -1714937 621792341 319600291 395125162 45493291 92513192 939449299 642924188 833094884 292329066 839015661 899786212 186098567 941048640 305552795 48467280 314010714 156614891 714455515 572690448 774559008 716070562 363884864 898272119 605117018 621542933 292702282 430533529 36486742 899333808 713412392 888229362 797517257 694275568 872583712 705033462 245520944 705286686 563737858 757309054 560280891 480019960 388628413 807009267 451643121 948373695 955918955 311896958 909138014 344953060 250155638 444439720 747337803 727905326 208257882 643758595 137637597 217530313 807143058 490308411 879547073 316120729 267342349 905384534 962160530 287227926 580321556 291141795 877276229 966061826 970786012 496561726 290180922 436223966 606051224 760560396 125551287 82034182 480258759 275957178 957877161 846432667 252348066 492992794 615950176 717623708 658189274 794829742 306775918 454140143 882900625 371853992 17141960 158156642 951239546 470525478 -5787160 491216636 957936735 131884407 415384880 181296214 110756119 351213511 452559474 633289075 96541286 380614677 692646552 939985826 900461471 346555242 977948749 642199483 353579596 948161880 23441956 972338699 58342537 635090853 632719575 54619018 646630974 624565338 305407728 617412835 810546491 584433266 388850331 199451568 245152546 622811545 27091533 854574017 679605363 387025378 165480232 37775216 791319997 695653518 355974991 718488482 -2733203 407919928 455026697 77217162 119793251 728958358 790839905 18522774 833308691 809552792 639109895 964645987 104358493 487893775 193612951 352938255 87269185 190847510 436082209 332310365 186306672 458248200 951434147 376891328 990002454 68846167 337205699 225415716 764429824 338335437 623093635 194696995 922412324 911031563 737092939 971253837 127691567 755357857 556792304 365736026 649330252 773736696 93351611 850232092 475242873 749454834 876263399 436402461 516660747 85941988 178099571 331702378 481133837 929380472 933168499 386242920 570882205 166071316 481972998 100183938 732205634 939771053 794692925 720754401 73189840 394591832 610084109 738702807 703490036 441119057 387758591 242160333 119649021 645846471 885130500 615131647 57437105 270722629 632288754 855505424 989902742 253438148 434939624 221322780 10036778 287418983 57779059 889860908 908324862 183814157 94809397 590408950 355739011 952445300 98417798 313139785 570714273 522495900 21858376 882354215 693873845 560324458 161112576 922458377 243248741 425583807 267942684 198769803 129999259 863306042 412241041 471001767 395401000 268734951 107189657 109446422 657915649 894960895 177454874 711039819 522774226 230416038 181252041 985758023 655377648 -3456197 888293898 546635302 63260390 768419052 533963629 605112904 938433574 582830030 77383458 978695626 541707551 960549639 524696365 790518287 373526162 905512262 669467316 826867588 356658515 434115813 938824160 161625829 305298819 643087954 193852797 938435969 248150648 662234455 647004570 392842975 603259720 790954538 898927135 108547886 941134532 146751428 609809891 387868222 846743429 459586361 111438492 -2954850 463361216 656694663 624596273 784608983 84368937 581440704 677312730 889955547 428926399 346626122 543151776 18732754 694004033 309878023 579045311 -448543 354302754 727536328 517717623 683445679 247874053 301734395 460000007 518666929 138441224 479081850 173993619 331534331 57946454 993279878 241546433 923256372 369767719 546071259 717876241 741362935 567799387 380177405 636667106 865353253 93745006 273186736 948853379 758216923 396699118 284302181 563923958 983178371 201171887 507823528 602173500 762918755 917748714 119078121 994218832 986915863 939109116 563104538 -4688775 216555507 420267371 58527838 541233108 310457945 202786399 28592431 569767758 976398312 148258219 475015131 190317517 411262673 149693020 783312599 720419661 28881213 948969696 54731601 431997641 435864093 962790541 516885047 839566640 125812978 211684025 816172742 676585735 104496794 720708981 765420688 714228230 508979173 194892177 471365348 857101860 279107871 277425705 262349164 510106389 327761272 170012126 721526236 178060256 505578143 194942601 870698203 293801347 553995545 135197636 690049586 213183882 732523753 133979482 481384196 583230358 368156473 955871123 436414159 99813212 356317775 328012385 579903124 830187165 348783609 401667891 783603904 925619013 153992627 126160640 307967466 756431170 91540483 198173008 531656618 215118880 520027445 996569225 94300698 353613167 916263663 996488595 726873411 5424894 20667182 712766824 504817300 956608902 472825093 987138952 795023261 220264326 276913111 481323709 231806284 369969277 726427643 -4966453 948570742 972822209 846074456 703864667 600014517 659908776 2264352 759107385 336892061 677807539 618254498 885377842 615696398 11185921 430044485 965854187 658965427 564249871 403380553 656071047 597942031 595087016 591597344 121512080 232449437 915418650 384823945 498795800 486168274 353628584 227650321 379976966 1719713 346274056 117023223 942613084 546580031 868175896 504613657 665642562 550333470 432425680 437493163 521049174 516832084 160550830 405515149 476901224 945585735 642722807 925254252 864708896 261451069 365041399 312706984 727780141 202393235 404775122 36083961 498093787 31532989 772180675 172333656 516746119 297394004 530345248 221311370 24171041 555327252 148665293 268814096 123443321 928774423 819351287 369313451 20428491 663853486 615052352 548163421 97925101 568492065 274434739 74560780 64914855 763353699 865511414 311897958 720064971 252359382 104378699 263889693 252808869 859987681 866256418 254811666 296067581 578151971 431850459 665530818 148937095 297149066 500359389 30101285 386026478 946860544 711393506 381902821 724111155 76295846 862178312 894048816 959771912 747343879 628839382 9920957 126166778 80756920 982759910 280561101 20871367 218730881 651755934 696796507 945538001 340726215 125753344 -4832278 662418640 680156023 807929574 977726228 495034013 525069486 654200425 725047879 84053475 743811905 -4011285 593597460 38063192 83739494 277990507 591598778 897838406 885678881 715969673 460846303 291649320 937307835 656116763 515438619 770771079 414822008 748259401 611786104 737498630 -7095626 70213674 163520173 848156953 565031146 13286421 210524997 299906563 594567979 467759942 468178074 988162720 542423500 33141915 795869153 712585307 574262095 337693121 845038045 166994824 831092799 561329504 744148227 64126267 206610253 890609869 63779475 136972202 469765489 663110732 592654113 480519597 312665744 633830841 795361782 74414188 907010836 247943805 337914451 424580509 966294035 752317164 809603161 641341581 342007313 953393824 491992077 436653103 755126937 672343707 946385719 101818521 687337395 333208370 752690686 954988095 279606305 865406781 699011148 478732175 206887946 994656264 743848588 808422215 450805437 -2952864 587504236 251356468 699482511 349061683 938619492 177980053 121835440 374000438 871893052 414936295 346075001 756173506 388548387 943002601 817202463 217940319 266571579 792825216 337416150 283783395 645350789 695741109 12343573 885487741 838483839 620931857 729484916 910751195 171357613 777179407 707842681 331588271 518324097 242596757 956582046 980360446 448650818 310163451 572082337 413781523 26468823 629346428 683359405 497508450 386015560 839619967 952187940 294314719 869068656 543347442 449429947 199261086 430196679 578428854 373076284 90979870 209978639 -2048901 820481335 104024567 489814177 77516410 944885497 454210566 36469008 173501998 225159742 296953081 658276039 225705889 330266550 5481490 188413486 538375884 472548664 962933249 118262633 663126113 544785353 79925117 922775883 716592933 329261506 670656922 692527575 768079200 819228711 430531116 417115301 899481184 884328060 600277461 553323001 157186722 646236013 73371019 874720473 51923253 539772078 225857251 425941722 925757506 570998557 987489319 192486045 481978762 817088066 584559513 670179602 576518758 917270838 467352178 158239492 316401569 577093983 154610006 454327374 608228520 594687968 222793993 676206226 860367666 497269842 979673213 755546732 980974699 541156969 332717478 892513144 213227187 886568226 648841477 958356664 904977686 383596510 440739773 639436935 77498213 10302014 983816330 280832531 453645807 920381531 314694562 895573014 243280382 676787000 305732754 66575693 600770675 59300101 462967740 989841762 31002256 682190418 445556142 924630905 747396716 101439676 677950309 24157411 317376620 487739725 316619468 589255040 201060398 776828818 200174973 313592172 264561845 220607120 91959412 394008861 187970800 725835616 365261231 17730105 698011003 508297101 936336752 331837007 60677452 166289076 270183924 805893750 46142287 595997327 110450205 899607887 641105624 201249970 617462084 802293262 646462031 502393020 481154240 7998385 -7233438 685509536 993745644 193047290 100614970 228050043 111746154 680919237 322083634 409270568 742878156 544162831 137908930 332890245 744006755 156314664 584342876 823103321 619142078 407857838 170942791 233312798 536251551 281312504 623437745 805467159 84161900 359729698 682805485 805774815 228347766 748792018 617225132 69731583 57400721 958340284 797736564 919132726 394678408 396840934 351012776 343436098 409244184 734440314 695720714 12384683 611485413 94785830 185939147 95657147 97303698 698216823 486313351 801423968 697442115 546930841 547415431 928562738 535703828 329305152 570501475 761233399 386882474 576086063 10638345 102069628 945724109 358131525 516382783 717294153 592584094 574646812 578754673 753183792 512088240 27393000 289411263 108854084 424985588 342071400 929989931 720396918 820537221 616642776 745272620 971244821 109165365 103864446 655728624 245733691 532979439 261474552 122366636 203453335 183565138 452726477 383587476 42803965 485508408 38124368 198674901 930104772 527131004 141191710 423417712 583533902 13034512 412362126 -6798789 770660182 239715280 435251282 92053422 339411622 674793363 955019279 381188321 72271053 391594103 909241778 431957076 805112991 633416380 38552915 773204900 149066337 481887969 393982230 189270807 687674757 419284202 861815163 125343774 681514592 475417747 301360096 934162879 507001424 345184912 315900087 162424329 194884833 639956283 339330615 247164753 490952335 329862216 836863169 932145800 755976624 594674426 859749688 216402357 139926274 398447526 383872508 919233841 360820522 306634179 109028111 512402836 459479794 222127397 263708240 190914942 353407407 984646451 304863704 475455174 793363812 261535619 955463797 739756455 859900048 508621828 154646616 438556472 316921268 754576625 848533691 934477756 797721873 618484186 833481312 231188579 969744383 937262825 956129248 558784393 702224009 96985842 681574713 430269988 685571716 272459573 628846312 277125068 966652656 742138921 663303167 619929515 433973068 222227818 426241250 957956102 922477646 385895983 965777786 979343932 541339841 688321631 599873863 87445868 -2569583 785126475 902748869 366351425 373467165 359755071 492572579 110311328 842583332 796166807 325360571 356569086 72053871 541747845 521315185 675223879 454982059 411799069 455110515 986651499 669439322 519894124 698877598 124588713 995396640 581356736 593399357 947913985 868248969 75630375 562372893 112452761 797805746 968798388 827567056 431957552 449398428 457739058 968543441 845723826 358380666 238036558 960641982 278322895 697847668 939305183 446241427 600250400 591387269 121573003 805615514 267730963 754396186 628610236 790923176 641173826 798038891 295849012 31206525 706301969 346177083 231637455 747144028 120639530 888022092 374834014 379685475 829964655 847776465 709182398 612463235 153914597 357181417 10588251 50554294 379526984 430939823 748471603 414834467 956161999 322954465 804775936 978502162 423250966 109217063 970003074 832026892 150156956 87655364 801818037 838573646 728407509 75685316 857216896 210432725 884653782 486497074 231277887 334305687 596083846 481456490 729167644 57292347 376613857 106936675 761322953 212793297 584644688 116197384 532657493 353085225 868059224 407233970 808290596 52893704 420862670 716065540 108104298 197786114 211458655 848326280 897355288 727636314 364778046 532134596 971169144 269828169 724522853 118297587 933502750 133440731 198976193 338829036 755945580 808117215 255446494 406713238 81443959 540850364 309197943 76586912 854954674 539822198 363076525 282331837 119926838 940668966 962218988 414008889 67093952 907505490 481147330 859311454 827017800 295726285 417908735 635828934 794971180 736505073 979678874 955501212 349857751 713884508 951573033 447801420 140140296 652421982 620580387 982729694 939702985 1553666 323201482 387975511 440245173 987199809 321462248 661709373 296386418 369033343 466097506 18881556 7789483 567439346 647535015 677211417 244238616 442196544 365521306 407829256 616631766 795117443 644925430 536957188 637440429 36211500 404216419 153589982 84199676 732670881 4858388 621936926 942071099 606789262 679034012 94032266 989611355 717763871 572945966 -4832737 -7162434 237863168 319829450 67375289 695735211 240756113 552130581 193009327 550861046 684800132 626055568 571601366 905731250 171680584 751373837 70493692 62258918 865278844 79245809 621066062 228806116 133991064 79311110 904591588 700874640 -6041786 433489279 691931101 440075500 680196924 243393262 52336676 88510575 759655209 387076822 746033461 895037116 862645227 773170076 493012461 357693983 409365702 959317410 597544737 748431021 667670447 619811697 349959149 207218903 906146646 978498316 382225786 765186788 83741005 484176752 746462758 967316647 655865921 1866842 258789633 250743617 925294905 707556226 802378350 724506039 172216816 608326792 988037473 761742033 462398362 224672754 295024975 223242421 797330562 425563767 597818039 583405850 461391633 988372802 343265959 529369925 477243573 186325299 429821083 225141188 90567163 964385857 215854017 117500616 645450235 325116614 346568291 866292685 784628384 407232903 154492370 -9805822 606017324 808827693 79635643 239462170 507997642 454088206 102466965 400930985 722631152 221725401 495227739 340577637 737048681 473055204 518847705 897088595 62212420 495522536 160404261 754089730 178813486 407950289 948702635 -580814 62077347 887653915 908513814 216413497 170967841 984494453 220794832 218392229 818139847 770597453 242023094 146347750 838168845 825473907 725257494 261166232 230609926 767991842 542086344 340795417 854992611 375671531 491562684 155885641 778977567 634029059 774145930 471905031 738031354 837438660 705082938 857300352 437162440 38471322 334053724 426545594 510449557 429433359 749897737 248946026 627506510 260738084 7293975 254393779 673922879 791950777 564059840 311957390 469714269 151085597 66764556 171391531 641366951 440815635 565908139 326131201 188127917 945478792 7753388 933329650 606389087 456225111 789595242 249203641 867330036 743028478 801426747 745684596 736201837 211689660 477547297 268683075 8255511 389981490 106858735 497281847 989936083 909147038 762449572 715469291 52585596 551136793 312488754 570931745 374957084 204967109 300965827 385530081 668105866 21824643 175181091 791723280 11532345 135310522 917677609 328427048 875258966 180069545 939792206 384486276 265440801 622077666 860330029 464540868 913942975 705111458 239700122 369495291 417890785 923382776 628659768 869666474 69197523 500728410 916963260 544930270 193953116 878168210 243873274 846043305 552786494 259661172 925007003 588938407 559633839 587169445 461634977 546963031 544894112 482162564 67369809 213396343 518232131 660233684 937465259 755319040 723387279 46126261 303519382 735053535 656406985 670753995 722777163 247651203 171407592 157499919 852036974 43581200 952191735 833254564 509830083 491783944 872372142 474418766 504572925 692464712 730417277 231197468 355511665 977994245 188282037 549797259 117427555 257838609 693848533 408294125 559768200 254681490 60160647 683730753 264211891 529323519 441981059 323078819 962562119 994760798 372347768 115220533 958648052 698496915 425400382 658139581 235410322 60298463 896938901 944919970 13066478 175781380 348585548 939282460 571148521 130699991 502352814 84228155 43089724 772050385 271452038 717903075 365638765 829249675 217083025 432424214 282391883 397497018 834688472 433967571 549906439 123129959 99625704 664210611 351102713 349219885 152859684 571241356 660685644 899331731 921779779 857709143 358993212 247879981 550536309 710644437 209690980 827616435 734031351 384235918 463516392 378303365 960297304 82156721 64515272 72758933 480138881 690744766 713606404 530631042 356622460 994381109 104952431 677152606 668659169 574335467 890931136 792274132 542689670 918337238 4523644 881066300 945441825 286506018 67552960 144925197 280280801 54719906 880660197 881372974 50505226 548746188 663356276 934112847 529904502 410690375 540713702 535086354 283293524 996483394 793168401 258933583 222755645 838027995 7905863 913104930 112129633 152160410 566357828 325625646 277544909 606331836 233762410 -1850908 293817011 982853107 558018526 402277721 351000538 -4101069 874068593 851444968 799307948 411310531 558515007 407799745 874589761 399636928 883101070 12332347 279494007 939068547 478828668 32294651 206331984 364235938 611136301 644644618 284340071 469168868 388241655 555289962 292882058 244405977 195046261 952094237 28884926 585377647 214411064 453500755 813204472 914423491 935327441 977866757 631086802 860454258 544706153 644961487 586708171 616391425 818481411 986357837 241826570 915387650 511576217 843053333 798419951 398825571 721597561 544004005 702238643 228179096 403971442 723549522 419323213 49639857 859388109 587739659 716812994 130850255 270280661 271448326 815939865 205199304 820180149 -1235262 16704796 573549878 895336291 414552715 509973883 540242437 756722384 793786411 672531580 258970751 985043844 283776500 91341906 533902490 483470121 551456595 68271812 19992218 217088243 970435106 190315960 774545149 429033268 516939654 89484236 752073035 407657419 899290516 708631704 538240917 328904266 357687233 70550588 477992048 698037314 484772080 161932128 171912314 288117921 80471412 255576834 37382126 550144980 55217448 632432864 358319794 965203039 390299914 640253835 986280903 572816450 292835736 72379928 421786338 212825560 730521459 788368528 650223260 355416112 179232582 532835644 806427482 65254106 439502047 419888059 3215884 906331919 727353217 195928860 6207275 783379320 879979400 782079057 557109538 135610078 144702082 974423115 842530858 715488147 577476238 142584363 243036443 723457098 142036182 843790209 250306241 9608499 295856319 308868089 755362977 804381525 477769154 546455899 579859012 763830957 637249682 851147561 222577485 665142541 929923502 183171533 828707184 319624048 85216113 442008046 119124085 630857122 709442708 914640953 970785538 603787980 459798452 343487080 240990166 452633932 951004404 227071546 70939884 601156792 351731971 841917726 792759359 212492155 462001509 273250541 496046773 960824789 483900734 790168039 669633960 606237178 696897834 443895001 560948317 961039754 844017423 75925910 555951685 704027993 250466255 285913987 167422207 451193096 252781060 451362824 276649295 320210055 328980476 183672429 -7838475 547661665 694704087 412077990 236473706 480349460 28288962 161278363 480391031 25328383 588251144 238427496 259897760 857168278 289916825 274646614 598454316 -2178374 694368742 296181901 591307672 632457127 961283213 866346605 841947117 958155656 396674430 835645055 267853870 916178887 687063115 902164890 466273274 182386668 60286497 578266255 483499580 270774105 216767057 91030340 912974235 47317358 -9792372 801299148 827527955 861494242 917806017 522783907 425923601 473341129 309192233 422235729 924920646 314324715 992292514 913202607 -5117490 757683179 308496761 61068844 18625693 531188262 156163056 339105509 748353068 316456714 6190489 202915295 725912547 136472022 1798046 810348454 817599520 409768034 922893235 340753849 61706023 286979992 78429936 279278341 794521994 703022586 190061554 87076712 458157731 869130002 89520525 47841569 814897389 871478650 693488894 884811422 82444871 303062241 257047546 289286611 921134872 416780245 214734652 664078193 497695218 868020565 708605882 146019770 368130610 572277656 371241172 866466738 336593500 595790453 681852274 623558816 904953327 375806294 359937674 813481669 251642780 564634220 29983892 354858463 133655628 549344575 477786432 533929367 561622138 958414001 787074098 609929050 249466018 34389696 894098200 172470112 886443087 387394396 60133246 589653226 582404171 969850479 203777919 796346721 708927393 960892024 539339448 291254680 993728694 442539173 313771465 777321912 401423710 498642312 46068724 287758336 915227130 574715595 482309160 446223439 972276318 987148921 577734959 914877322 15061213 53975784 598964481 32035789 982240952 618330126 323868154 901652177 800139804 350943201 332240441 478054359 924865675 248199369 617128270 927786872 862293145 970582695 70828276 971704337 961399136 282679493 862178482 41493139 852188234 565796218 181554661 592353374 545430956 975199016 744437612 651642839 432114085 378503686 137162115 130486670 733532308 165973683 416943923 979745418 902109380 18905292 884228445 385302390 634699545 554523593 146714553 15667019 57589314 202591393 928141015 465666230 573331456 476754293 448659887 887332669 644000206 259775638 226880247 294071859 938244117 171493294 94110008 502683140 254770844 740032365 319088882 910092677 420804207 701726312 37381711 44595237 700196588 774449642 454130018 736873588 143325045 184167637 207817038 861770834 257436451 896564741 848409502 970138831 483469796 397525757 189450799 66205126 979558238 719867338 498343310 392942124 645623700 918673465 781200653 189309629 857363300 892695242 673231402 -7551686 477779045 383377881 920540945 211921895 25566280 300751755 151806591 197664301 414273129 645720244 966002480 896973648 948977243 995331235 480472234 426230899 339843436 663762772 90968777 685684872 856691387 839037961 30188857 659375661 733116126 250639120 729741812 705424769 416046068 852234489 681196469 909456046 248015323 271392140 517927249 414583637 445172604 968990526 60406415 950300421 76760683 573941087 366813056 863722867 521010105 868749826 357210379 215486661 24875411 903684150 948221533 263262927 258230331 19163721 733624437 896508713 627848753 358847514 85690716 510537281 513772608 266392871 965478374 292167149 102636819 313563412 729086827 55789955 331367598 148769825 796423365 628965988 494781344 360629486 752643861 740276327 431543471 472039799 817556960 428449785 888381570 699394577 548634758 658437487 288021304 422105045 442564696 426860 183895191 284176507 508866588 599882507 366904365 198798566 353237948 580414634 268152974 269437338 946250842 22751707 27385951 323215371 638094526 687687375 606525699 548715147 38286174 313410257 602431848 244935465 696255991 89673624 727202843 494439689 945849525 796591922 335391013 381320956 641817509 913270534 405708379 867747729 152474104 894414253 636943818 464810235 158780152 865948488 912487138 670388146 747799880 900828941 147079794 596503799 613692660 518171226 94341257 957519423 700753529 114709029 919747843 973829130 688338933 348785221 139423926 245368150 92559405 191496527 407884921 939873606 812384627 664679212 177079349 689939040 550035736 123467203 188395993 492999980 139865808 878035869 772670762 242053414 534543839 650732428 490146432 452683811 870213479 451770895 646970397 277617042 764053993 157020790 931726627 463818301 391360463 180490858 207818643 277805441 75976129 224836003 817629331 505439860 104839367 820635216 867070326 645371243 43541379 938781486 972365941 368302159 500030326 914764604 682824955 929341246 969658361 261998593 280774345 -6252677 -5415983 965272994 763103781 191256275 476100329 398761238 479745445 472376716 244258120 623588681 13844340 254333684 199381664 715916860 555158467 121516779 160202052 383875259 696408049 870350458 413581644 516908058 23672633 771094482 98292642 995662057 524934079 634832314 672562856 531191030 200469067 266366481 63242445 551775040 107814605 243407576 444571069 -4504598 83440984 98266012 975293685 704502282 591596584 876556095 570191972 408213570 292183102 432503267 -3635566 267486536 262458922 908527735 938301224 502854786 303619323 114444955 486534683 506592076 519808622 795291706 578118622 285917503 611890753 259455474 895439861 319551413 782069935 728655711 490619718 779180690 26824396 673636666 502613747 754405432 777901668 947336610 176667993 372318961 859908271 495667253 946946407 707304244 -6690723 680173189 71513462 107837609 933906490 475636876 547836455 321023415 553653209 134748572 479899375 512928662 467058591 895071108 458264057 417061884 832473353 50874559 160530247 328879508 -6442484 151238740 881036886 834096841 664374131 773186778 997614912 586588507 143470156 26264738 482879336 302647900 369604985 546704793 861429457 521071481 987308771 698093369 316836835 800763120 298683651 819054662 152239846 510957450 639179012 315783011 864104860 510728782 118528653 562390267 730295455 154077062 638030550 690466741 435660969 135353857 916224239 963458660 752555754 891244923 56080882 317619087 414659973 490681459 386799972 880897078 540211870 634923433 823550500 711706142 411269615 236682881 180498700 412492009 640721257 410771121 564434192 807592930 614589109 907510914 99401180 987501884 967211680 18660346 947502747 334247924 28197056 789017465 358236027 446675623 430496079 180045829 166708388 536936363 980601998 204584184 699659341 732344505 189853550 935581972 318216299 504806703 655207435 377905713 354295262 262326826 891972269 813618101 373039268 145286208 709045983 855180763 172466553 608125759 6695519 433563033 834881008 834993713 719072031 810257230 345102839 936996315 876611580 28593934 19796003 140389301 23800195 667074360 69185495 869744938 386539782 689943819 58019128 5256818 171312780 546125758 339716739 480739594 483000251 597336085 367414005 113014647 121927987 891917082 869268265 232278832 400897228 999174380 333449388 872992676 912323245 511170318 796031536 978919234 974213725 701864532 202269415 621530753 274578310 255729684 38756763 659760210 516751174 43171150 760098733 77097332 61988489 891659434 495563584 949570558 581062297 69803583 35641865 318232117 505701494 585166218 953776719 112573515 294624889 101381317 529105621 -138081 456897411 295920254 493638768 328994396 882460728 449599771 601686151 437401031 320378404 464010947 323235746 455397722 774541817 257148428 71191575 400362865 271502555 419872751 864506160 701707742 942029243 55076040 4735162 147534393 176412588 522080481 315561755 -7186905 757224181 590645571 193716787 593991502 614395735 915354658 229863619 995948484 822879249 598644599 239714515 122997430 174353584 820909566 929939756 85763544 956006663 242913492 857064763 422758702 977241448 275825877 215841990 33299766 551093093 127575707 496341766 744833104 215643041 702281356 60103080 246743641 755105353 12209299 841804439 308290208 592139144 611601921 646148914 812335727 265374436 319976531 641633527 215942325 667822814 426265648 917468754 54056153 143643781 63025554 333639283 665050278 393975096 848298601 620661893 512798050 669430122 858966086 135650452 892345103 47230357 735185715 154682441 638112023 888847306 657868489 563937657 326050487 350656397 792016051 758199646 330873351 428564712 113508862 651251105 332522774 881176685 309742615 793213177 393286823 969798370 117645880 755620191 687711992 481647600 214430247 466046486 829683625 71959724 792566067 617574271 772009402 222817201 320628841 546904336 778964546 798191832 370823442 830240610 879488684 171426915 814053747 519977385 351643863 192525446 765597098 397936746 561073577 250014479 854925649 319868814 332637848 921085775 966363711 162175892 331606428 582053430 974932022 28531401 500429940 804843926 562593575 951174540 845037282 745524711 477760732 938438631 30443296 195334620 913508251 640103356 248754795 38794104 670831367 479327856 514902460 633670512 934491689 63941559 506577626 882040615 798749580 974295092 631767070 196611194 701426452 93255278 739563074 926240273 103600774 99719663 17388533 288755596 390215206 663596582 750436715 922969235 570183141 83667463 101953931 92900812 972829145 29021190 186855871 298796978 42889850 343283765 634882112 515673485 987325773 475505692 857927463 439103566 594728187 533772926 566754856 203261855 377317963 777865117 972543518 292974967 198367791 319228207 228345283 492083579 724205742 582989038 282291448 378370205 496514135 674778320 476606871 828806094 993250949 945740010 965960215 817555448 521634881 3150311 35932756 998227700 818965105 143094274 841371430 780760523 841097043 656082631 335628242 302094955 733446670 652667569 844070658 -8718141 782887329 510622702 821200501 181831715 195451084 189589121 727262053 534501455 959697969 532331489 81473880 795736924 872577505 541376045 595507630 436485105 377835442 902920161 825237593 354210498 322939728 851023551 236359343 583007911 831103522 970373954 479621041 736358781 694331342 284159467 767034055 785446117 621725576 536130410 867665349 61501575 657065699 231230753 773654730 420658920 794163162 117755033 923767590 749539667 640678325 720944411 433476279 761705890 323166802 502461787 415751325 300022660 506962112 944407074 562843771 264673155 485981468 254678544 750595148 750184420 124209766 607755774 685366821 494724985 636692207 468434839 61404546 706155034 676559109 566457817 499726102 850555868 233693111 524398188 844976574 854756901 534726942 974025546 303142475 302588650 290671665 804046561 264229567 922748010 226643890 503165021 720807958 790374168 539535586 559223883 520730558 968723687 312425453 937085707 353056580 890762318 369178848 354430643 101214109 62675467 243257064 443714551 834387525 648267238 429616828 845054400 105956080 719619342 891455600 6639586 370796116 743280627 270532120 942653934 730484841 81100331 597682220 481820876 993908229 38415779 873494581 805025254 406769110 475401575 898283968 138454728 916626093 371528807 666453251 968172484 446958442 837134110 103449364 68141053 106182780 102531412 -2549356 631860513 987535082 -6782334 796776786 829674450 969935040 711924914 390044850 601148072 167663613 683134339 171693321 507365859 11959857 69454847 11259139 127751025 35410115 362400011 596346197 659346213 765078791 271072949 307493121 576069188 489220040 896971796 61885770 584487958 757740066 45456241 282434712 898375867 121247192 8027158 125416433 682713517 698625351 10615852 19463140 248891400 806749996 673851523 618043727 30714502 587682254 280649020 743633566 289777251 228969971 28461659 100195890 339191906 736762590 598050069 125280238 963360641 386675846 362089608 480891133 277594192 204076772 689026424 255501800 934794595 211769481 563967380 377904602 677589863 202606991 459810061 310687051 253098868 523707246 655990521 494109041 599924231 461684851 699032105 693223281 892571659 557118924 233985862 733405793 234607215 192843458 114954605 415442746 843125034 614854405 25680165 855038877 593731568 790710345 867818862 935668976 626473296 31335643 513109042 79054474 240709263 165317579 244786544 903909164 652488847 271995492 270329230 932296758 437038744 746875856 895723615 839428136 167986534 593629475 625851129 6253835 677311185 623145852 370308000 540357635 536699673 159217837 386888349 311967047 468713348 438304195 850799777 202071767 271063902 375090712 446233695 742682014 794071747 913236341 991090378 570533718 545174770 871633800 602465854 696328429 216139426 457163059 555752715 935559571 33843679 652253306 833861524 610469607 474324443 204369307 607021823 846115499 73230301 52437708 192511760 523327508 505963183 423278580 605479323 416570837 762681541 610892046 83531262 284884026 785772123 569917281 261207806 130299020 175231937 770563675 68247155 691407309 976637304 201287838 79571493 372810546 455900195 928848221 116396286 954029992 80861099 424741917 345870706 927076293 699484416 244822762 468180152 369130029 879661030 210087325 405961032 283515120 244939264 447033230 148440078 728860629 491717823 673515336 880047324 453565708 782705963 892141051 497731771 969280897 823025373 723446530 250215397 452112 110998831 924470002 190449669 663788830 83442602 994671522 808948947 468637785 308858518 199192932 71668005 479626055 729480304 713333377 774530987 192703605 542223400 745573102 495166854 113319462 806232245 961099954 635525940 320098043 432899228 600027829 810361437 226357189 773899565 956101056 194185622 338485633 920253399 238172256 544364652 656010842 516537303 244030049 640292960 56272669 330224191 905624851 623073979 954582687 118280560 542129666 912207289 44527010 791069388 857844678 973844504 828101899 935823972 895003657 515807314 986095194 418407338 464333402 404980384 807678438 139056829 535890022 70268437 677647739 587227185 531733781 -8795433 970954595 357506070 485753272 728664972 195577358 930561466 27391262 976913855 94942186 24891347 370195937 26165682 299794024 975535262 128106618 218977314 60339613 294369558 581715057 418710431 395701465 222372873 698753840 25875727 63686945 191016122 308644963 283683949 986137315 265608999 456075240 957127015 311901750 474134393 169115808 833684833 751851173 778963798 904617739 455127094 909310884 256613317 738102805 325284338 48139349 288899931 562098895 420500640 562548066 383999595 826110611 853812220 614028251 885330281 282288191 329684699 346511877 643074449 916301423 338695125 550863453 658896259 978682803 489531170 802623189 160797617 26443038 39066995 345981583 62603225 426432400 66342683 488950464 874338516 96700374 746064804 311247149 131022638 265754988 149693386 607058769 675253424 724071921 190001092 139533413 718814737 679774872 14350947 719169656 736566131 455662863 1536933 912382718 483711238 686375238 633511143 587146577 250002384 807890773 556602767 902224313 40739984 817996443 452128672 983112671 166401951 886642639 578980525 450717018 878887025 284495877 708373196 305005306 333825037 586067970 130911347 172903072 213711705 435243473 236036410 913420872 455750644 275919245 263983325 139960187 558526192 848905179 21157495 135236521 156654697 909442213 587761779 323163369 270201722 219826756 210356154 353357688 515786026 245147886 7598754 -7338735 209797043 785535689 489593981 460498576 241806582 91188293 606420626 176449664 480566767 679053949 732624379 988232349 689520493 765041747 776084768 788427272 788353448 71184145 37491903 178568688 676947122 871239037 245141559 142070580 777439811 12490018 727701137 313697276 637009471 319139941 97527173 766024159 360986451 682904687 666126177 735033377 225980969 400851402 110486169 247264729 602930496 106954038 205822939 623339667 70232963 939670527 946982905 661387615 182031274 226276320 815735961 712812748 825477337 600134405 101896056 517804857 169779594 457626229 951373018 570520599 186705594 940830970 784031131 75894172 3749291 924857691 357668263 808070200 577168200 652295883 644310535 280747857 536644913 366349294 287911025 54377449 909011444 558177660 422708820 951822582 580727057 76053479 685680447 945769085 725093293 611136210 501638512 626400731 342088885 434367112 70878127 697545799 893230876 44348729 501522337 764837216 14554061 871878382 949869094 990287607 293709544 113597246 327126420 494488434 534669653 450846489 567393276 815156842 923226733 265461422 479913605 871418663 484484841 377936438 492734460 446526558 499114533 532833945 500084955 85294714 831588911 575845635 397827657 506965443 307532900 135394126 861979842 562713590 175646157 257769972 733394564 475033177 860720425 136266485 195353042 580397363 289111453 793476911 537577842 885973366 219746965 504976561 882643251 193289759 888326655 308662133 620336777 658505727 341172707 874140969 253288811 409754940 287373298 507119081 979271286 522183128 948048695 589919854 332289178 487469153 434176073 443781013 334080751 36286155 534663385 940589362 328385648 551112213 569970857 163094900 127324729 17258241 18353451 231706114 635396300 989253204 743094439 218328799 343453584 324672692 591311392 203403632 232461979 782551467 453233053 228346779 949491076 976141192 509806311 147984249 308368950 819727954 41778469 738672690 433178181 827991596 359619657 735201613 788392052 702002751 769508143 487703962 595165639 85386223 711845788 240028129 914445517 951813721 640813044 357209791 843433719 999273897 536181715 797643559 384929087 783694324 631885808 371012262 98975308 633384408 146953981 725028036 -7232996 20854458 583924649 22171721 953757295 695836091 586221925 885517012 383373206 558445248 138391918 507196430 594356060 443705427 365929654 109823010 127376780 126598346 681237773 111434258 747880293 136732221 476548767 895895741 566098079 529650540 278604539 122255194 956053514 614859661 872600028 125405738 258529994 249793825 448183916 537121794 209929344 813315547 367767035 965223126 291034490 110832715 67410815 5656202 479551178 1765758 46602274 188284168 -1874244 236653446 731642601 850889765 866080668 234274329 877075983 217712497 536535976 954236397 100091669 684972035 907057183 727993674 116916791 90428809 363051881 292353755 378833037 176520545 701135056 461875408 118279611 28676675 8864962 247498685 841243615 555668500 718044886 744460850 804783233 170319745 201030811 286669351 675671488 338430996 545261241 843270643 928696033 907566977 670476841 598156900 314677916 846091891 826319292 571301072 556788943 911027886 604663150 728456006 781500767 757535507 848800084 55824227 210325675 634679687 760989970 57063937 945012038 529884277 724109255 918022867 183727955 293891298 990687396 574459642 473000400 771749676 297905315 587021589 100741016 719698245 716009690 37748473 769789803 50971551 187872431 94719130 966352013 983842605 694175545 158086454 308604429 727517713 14020877 798595388 433814591 411603782 876965360 441836932 498985447 277544951 663051281 991500884 689494978 713396850 678589789 949349340 734375549 866438402 21021868 730681709 519785312 427958735 392586469 944294160 465284042 301185411 938878210 328379400 551547214 323112879 581728307 310859667 388134611 638265298 156981827 56506462 626214543 672409346 627606714 478534311 622820582 912738406 118183208 649358491 461887460 852247882 304555560 328560699 27812785 306444682 949519503 223667366 251518746 787654636 272340793 679434527 225569266 674088682 314787994 924643371 84407646 314049053 75089917 624141904 174535694 833967031 117328031 116721862 278471319 435124955 705003186 903788859 196355008 485676029 588561530 207695186 113985882 612504715 18918718 348166845 693892865 581078691 15863073 777814516 52285717 989491477 94287512 347015557 49314210 609803578 615272335 414888123 867935562 407858715 684845458 731723144 181850352 234662172 851465634 926586981 147144353 671679637 725169166 172084929 672571180 398701074 475415239 479857961 593958716 152939487 86641078 973575698 216189809 731172924 610400906 504211635 427649961 606704244 829519956 472565019 928555454 912605001 557648040 445705547 130066122 161785069 743941353 524145692 223291653 36366229 622107475 852679627 411610539 360083221 918445975 896686973 588352500 734934842 436006321 402438429 661417552 232638839 380594194 519591060 333234388 780734797 309736377 201483682 322143948 590638476 695512309 559827244 146966344 615602948 351882385 606491736 788736276 138143083 877559613 195039775 15915619 472699056 929255676 472457224 983284375 195244568 458275025 951892731 41391298 46149550 981081387 555178791 886956749 583492101 469778234 305924625 814648096 879073592 645265417 696568941 547642045 802043931 633872925 404753515 743609595 23698294 731936055 157281706 668642867 564769098 607494396 558251188 963216682 493220886 168111784 56378366 220574138 308203350 216440617 720475762 832099098 491858425 531844312 239085765 971522545 434181843 724010417 72995337 514676716 157284869 158085469 5054375 951343575 779767833 912310267 640466748 498070671 93139045 356211302 570371510 313867628 401468155 641549596 512761018 181524536 311882867 293521982 612596754 478359051 153966959 894562757 363275117 378397791 432959596 440356441 451299209 485401355 404396368 62466325 102315246 329282265 81410064 457079712 955700140 994533833 19001801 -5496982 353817328 663593612 253957428 357521048 44185657 753261447 819912254 456476145 563691797 688786528 494339719 370550749 89568687 129295877 683209564 78797872 246927552 747503710 711564515 286023287 657061165 229420633 202609955 93045946 405620662 608914842 488916269 13798005 348503908 220595171 440297545 670780992 215123469 513980756 159114907 440621140 838100177 767845044 371209131 774477079 451236559 697282246 749447000 971996187 190676945 637908265 853669796 347102666 559644120 784116011 491660534 460681620 372238674 975507260 866220613 862999040 237594443 73772817 483140860 894485023 458575868 371912879 172458637 577967215 861460679 452597677 379439294 347338347 317595079 916319431 917795855 763588776 911309882 313648911 8363493 743902953 187511187 682982134 505915197 90056330 938937744 742742816 242271107 841011415 999839595 809458493 318461158 671370663 926062557 480322357 296374078 40087346 245945998 422180651 540051532 348741042 798860110 537408492 458695012 764196063 671895157 92405811 679876786 658153317 435598402 277694095 479707339 381255115 782734777 365664357 591702536 437605708 436988566 20796109 76613695 424711726 722035375 386593840 309251910 831897561 28267786 336080950 162471906 645683502 621897055 55741070 139213255 609942909 920481155 657962072 868809895 782131104 778351457 5449524 16840512 726064192 139940839 123664108 77504213 559283499 153360541 353778702 736433848 280537033 243081788 308931918 432213231 597819157 530513334 21390474 198737955 583084503 47187795 809534132 161770400 296131249 704094249 662423765 658176400 139787887 539286457 234436683 83024898 849049307 964703542 792470214 359819304 523182578 267579462 520341757 362203295 181854808 17365262 415630124 999152259 360837924 590379610 987827454 133522647 785210869 4270475 825406122 982501637 537801641 619290116 900143336 847030352 751497562 130647202 920633559 -2596051 938133027 775345350 2158930 39616226 893617082 812591814 629153626 533778963 560732621 539044781 688982948 192284313 854634116 870755140 960157159 810965310 785155098 341022590 117913798 630181197 60740784 212498450 390825733 467445624 800599152 271546508 435982221 672776838 382350814 211099471 144884901 125175013 662592838 802167735 225512882 643498339 649901149 325044090 860747574 158924066 21876547 442271481 893891106 239698731 747548736 167797117 483007239 776349203 431123646 762775395 66891381 614018172 753513630 811671796 781879657 911519423 286346644 731019706 904809935 811720546 16017886 828186723 851291873 480766380 512301917 50129015 265482365 171908662 173846994 162455190 823212593 984839205 947343614 80716778 464909821 222719794 99520802 100420785 131497517 536861855 426203282 800436620 -9383139 216002797 343726753 66063712 878581921 121653833 935496414 20723559 836670094 830765530 599418358 626644034 23051220 884528892 771759411 994659122 325153561 212066679 984301768 63120259 8314208 729908254 628827646 137289436 183506641 306935124 678814335 845959050 288320996 865877015 128432831 490180769 74782160 287542333 693589020 615857679 164139067 505571593 86951808 983088297 229739720 38715577 6499207 708426697 837151991 489302658 460451474 82298293 671332054 495223139 371861931 670368556 907086647 566413573 852957094 866477454 581803096 144437891 513823902 317727624 5418561 576624454 405140288 944912000 706605086 144703033 368648613 591410896 458627659 827287238 721891241 628736562 77418866 127791336 438251269 385942726 812260422 483343911 339424667 11484203 123157581 359094823 2625093 871877151 689219477 167235620 395519706 993435984 442798653 889244626 120636616 494947925 324474876 241349299 780683323 451676212 618559745 821952137 668193231 919510756 449033973 859459814 881215981 863696344 146002017 781014235 165597157 468166211 612766052 599917758 707763597 461327407 782174376 759250240 897318060 403407514 419175573 688835343 535240969 529610309 240358705 121906956 854844165 684480767 268837109 150660645 726598592 916253096 707469076 804416237 37797521 91932682 401450211 167584316 864313431 403214370 719048066 752480604 785136734 85220277 768694616 351220 619454006 995991909 555567380 918605104 824221552 842413602 734269328 1701468 443910645 653230350 637606769 714761201 669777721 603730575 29912691 10901165 639346885 978385995 458174479 743870904 144181240 993201268 726436597 369867766 757944183 913931683 542420859 950189546 490310720 555644639 980646699 577088606 105566027 133629468 633185853 297195906 919802926 686170990 465910759 625865576 982946289 927050440 951795606 833918615 202394721 28565998 437672174 600930290 810523212 299126271 843586304 86639265 124261319 749886432 453979274 8799158 457668810 542253081 142920888 276060032 289066717 427735585 411084465 679146407 81439717 672844315 32097378 396166027 496865206 542884938 995216461 210774649 65440333 498652231 190671414 451818708 440513787 841504491 717850728 232344301 498961752 476165983 216848813 317464817 389720329 262177651 48847760 981763867 383720935 809723652 642718353 61324214 293321903 76916333 325718897 175009807 679858929 93963881 214340425 391001929 690020910 191870919 753164916 697824830 180069373 55016263 545774866