8642
175519894 562746268 400905663 426546285 951806330 31203311 737272887 163393552 439949340 950906646 791833232 145702547 354833979 503201898 581883232 579241353 903879173 702679619 949944675 167495143 542754884 520526693 561004505 662921161 847494320 256777838 983133722 685059858 114767167 164537438 9112143 854204230 633364625 952162089 832556662 332916200 167185513 748852348 500553038 90122642 80501443 48163875 82249448 964597814 257600341 70340739 234190033 160780096 6737216 138227860 10170511 11677632 606697055 407704650 675058360 474785986 880516059 963057127 666982234 730034107 726988187 445819759 647455857 275766186 667286737 159269101 661285211 30932058 633640441 776905849 518158389 115359024 970630492 47656896 259300932 587707062 516592440 854839027 491853081 278206803 839345448 387009923 685403919 171301311 942836018 319541907 522278347 167931171 441236695 38333550 684146672 998696287 46351313 368473016 107209767 27329164 78839306 326912469 898990686 193066974 178349999 532982868 257885473 410357067 799739592 811927828 48827981 314788067 954016866 970330052 107866000 236911418 712064278 508336719 157317313 486388295 316597179 740635915 149689108 235511551 473826557 63674027 720223694 10202869 337682452 270352443 379966494 307200378 727760661 605220543 794294478 81666156 572798612 802733827 962981083 555870760 688687518 988809144 324477661 721345132 541588087 600644337 898173871 695735614 358146043 44384974 950191848 205870859 383079735 854634892 161057625 915139870 920299837 949994393 108860969 140886435 100399907 496943189 649951284 197428912 592027444 597444579 617848660 182707679 144131025 744057251 83868698 518010082 881279135 208979594 272567021 754848571 355816841 806232039 511499140 438432567 581947905 19746320 437186849 687098999 466247662 73210417 874032754 203262633 657595698 936093924 381709182 343036356 758728426 654408756 859582134 318270830 836173918 64301465 168403140 530862439 657272522 405498011 957957358 155361481 607309745 867114348 597518200 362861786 837901388 499874168 762704100 67342170 413756583 784078760 795773108 513052797 602406467 33356723 203553602 333661945 553063565 234258642 536050236 770648586 525355757 828108464 386024506 96807607 444481396 18153778 557871876 786025935 533771087 89161734 31965120 957682689 67242031 607273947 642042056 792309258 205652177 616141609 298468656 754958497 957572696 598840093 340320548 125974565 835701228 636816715 191945941 365122285 549835626 70211104 330014767 344309365 815289541 411547483 389239245 692693966 726574280 258403863 745481199 13174680 528806190 62883717 204687605 993967661 753334810 639567252 132400257 564365355 321694818 487358536 904524670 753755427 792146961 255362545 978772453 414785239 632513679 128457202 93949059 659714700 99046358 548475720 775933982 125311296 971413087 871395637 3366446 585212130 941867234 549156361 516124186 972159873 627871608 966159531 451226051 617290858 956330254 541913074 528587346 158007690 823674032 437814570 255116824 157313034 791421461 263324584 801686152 662738832 224487864 95790529 362430947 115996959 772337126 255400935 325051404 246454870 332373731 26516134 224595812 299645264 831465902 22811227 475952083 727243461 184904188 817880138 199045 562593616 748702113 638073117 667745143 293386709 475196701 333017818 348230448 567262555 240718862 284204333 372455822 974446956 776847051 403005519 405403599 963909551 577017499 751607843 67675894 883392518 45068085 896287035 117581415 874381781 727578034 861967020 590026405 51761353 313325145 173707271 522399045 537795213 36679971 514124475 413664751 899515818 685643313 345406999 936427655 90304872 389871576 701987626 689677723 823370775 329903551 953008255 249885197 328880821 695373268 340952685 554690098 373062933 466916953 304782702 404212064 884804724 954149602 220840382 207082795 244383354 695353457 502006265 40098851 682289269 552835956 371418503 396711451 201175905 555336409 785976387 638844580 925223723 913754115 284757349 523790620 816084339 130601225 398821316 19686319 209904179 977785172 828936114 573007697 18413338 719765801 716706182 789377821 689201613 851690308 325954866 109135462 794538599 419931033 916098650 662933920 724532363 62428781 448340294 157387257 456886934 184976841 940688971 735826883 486909409 100456034 311984660 931329071 818169460 198635992 12935958 14756101 294478897 382597210 546383166 710641471 686283488 266799669 140019154 630230554 670029436 737950670 657655311 145766502 75532016 871702545 92633553 938853236 882392828 86800175 115766193 348502842 385178951 852707921 87836308 852621405 718757660 295099226 325179230 17251902 874941382 481259140 525946004 302470152 300361388 440664724 144888609 233889728 83301517 625605520 247253853 214756431 478191635 849296979 884317848 768362801 280096584 790508565 322314429 742431767 373817170 363097430 511831628 739747370 860199730 514118388 301035113 670119063 164012066 832864064 199151048 441733550 65543006 352097980 322565995 457024313 680910006 341964225 666274822 138831171 137967819 17698741 918486093 31603076 843246542 143858579 856616567 72699655 422427915 341510047 537294023 840990441 699101512 175841995 516894500 225923422 230432716 537275352 624206429 885114811 792879348 56606555 111485192 820008170 347657312 567950846 713194407 331324861 599710693 467255314 105337505 923026208 511368229 911959359 184740749 902090504 124768966 37235568 847917155 743870388 203151507 985643635 489343194 856110320 788619575 396495959 402195742 740818700 389450389 219051514 759490785 159026991 360540901 812417121 283201355 808187757 138329901 323340509 697635740 481892361 334967796 261728730 270295882 8836685 691440054 740906245 995833327 529283863 742064245 36270315 508579113 248356692 58967793 270015489 177864175 720723015 764925394 646197782 591731945 282305257 471393663 953037001 490429617 444018469 59876208 823930212 766178297 423956902 967188239 947755168 256323991 871055756 947749246 697369659 931876533 297999058 565789975 115017959 925612250 645032432 946484308 254381716 887077767 189232579 842782622 564195911 241055121 634086316 342208664 359923966 736780054 680554369 410579588 813642636 288930762 914970501 369607574 458159084 369880212 542813362 542653911 286514722 737179209 57118039 977572289 890966242 495059214 149930743 108059533 657834040 658230809 59605178 460666782 61838588 949285580 977204898 48288249 393238044 46966651 446837964 521951297 784914231 208004511 691918327 944990003 979199463 38113149 640564885 505043414 944150135 893994223 262256788 82096014 657371112 224085341 716541750 973009057 519828161 201851766 219324760 150478973 778485053 444139381 416154456 912349956 271913008 957387253 372794761 123871032 920723486 744911483 752320919 76819557 58574133 144436418 106995708 317990168 888334357 72519124 743485625 434811044 491158459 436923527 526977054 813281285 736509871 867931718 228510416 969231615 666065779 61123180 987646517 144079036 639185175 91143051 409948551 444790585 948909008 709236898 409427135 776467531 200717860 944926609 896594332 146611734 939873591 854074653 178885705 525499738 21834914 176134919 156719420 90308091 942551936 808246579 905730137 2022666 207145948 838184028 880387060 133787374 453088085 289084104 228221340 317984489 298758505 180654735 117081363 599114792 637894979 660586453 859126655 569236210 302259989 35166510 638709446 654286195 938303465 142277470 269522606 168789046 673210942 33658605 532815970 494212686 656631619 423132510 389414548 52746671 364176972 830015944 785997979 707685648 841580834 570886256 832450532 174754466 644126142 464838924 459184254 911496493 859271303 330247220 131185808 54056647 293671447 924264383 57822225 487938932 38710133 643367048 155477480 513485867 273161516 849681178 182878964 83186430 237460574 651021208 181649703 555128804 165962144 923041236 796565007 882101584 726897523 974663193 588197098 358406689 617678866 800944651 613899950 361214273 357230643 334596098 618102349 320029584 584000296 551932711 353179590 909309292 650922865 643976674 231991445 281439277 123767537 862776601 957887068 729043516 817231250 413467743 867722018 842366812 258780946 829259533 780430646 851137573 656790998 948557108 486818944 139867595 955201727 952826038 123547838 333644205 563763678 297260590 90321037 613257709 981634193 748276856 851796449 64308181 341148168 197517862 351569555 831830737 713729119 31974625 922640719 208423380 299535190 488591228 865611035 211893194 527916060 862343110 531626718 349104280 588506486 87733287 587271025 854701535 24464208 726059654 97740647 789994911 271146102 154215186 824591880 670334326 793759805 483224295 522016592 170286762 558448158 575649888 102752318 521552859 840443158 257156982 204445323 790871881 399945024 512164829 208063369 927895199 271613334 446675269 25810633 542876410 473710505 167096465 864870053 825968895 993191131 251269164 342883947 485730425 134877608 586203599 312648471 805531450 782519360 38038313 53611106 30163384 384106274 263556590 774078647 586261436 74973104 57216910 34754171 709894283 448059645 606079231 798314538 3684289 845995485 42905653 224850641 636377786 177433561 26570861 809309745 101066795 871145889 799611873 11506876 652673316 373748606 182014212 212929591 845281423 46535848 887386494 746137137 482778115 241657045 989311240 190265834 960148818 943009686 824053560 631096174 41657633 847575357 940355274 490105599 511082576 568655319 749907382 691006877 868992148 267357268 137480387 524111585 313813475 944479351 412100843 858223817 281206568 986849867 983029764 107336494 663280240 307363911 528092728 775986674 543785974 13725561 574592369 963873049 267212698 776493316 142497092 913779264 720734367 879220845 794106724 261258134 850424272 698561765 59602325 435834632 106270558 677512823 245903236 199801027 22214738 53028621 525258420 195855123 29141308 250348111 5551282 408167450 195789161 65864091 387205078 712753001 909292453 591339141 784096681 61275619 776707722 153197402 842615163 413013358 124721906 403895150 600383182 116782910 620298805 256891857 104173986 226968149 245016648 385678254 254385046 791889237 886855066 298750556 159128584 671104299 233652436 657070797 460698383 694157814 107091387 64658122 992916466 886862965 418773743 582345814 509677473 348335821 440495185 726690784 193645956 539926509 26077873 691433289 988837657 439570481 998213624 778642071 323324112 889818740 771087789 968513823 988403583 273800337 957898692 868419271 852784872 884007202 915810039 245811586 598876522 694008661 409707436 246713602 246085867 397460367 565455031 835324248 507146717 262630449 330830842 25477480 264535869 993302188 705549322 585319309 4614352 572217575 47695195 403554177 197962234 962460824 615428829 501511883 754612386 494910262 499603775 729213108 658557811 171732021 745559050 658315638 34381320 453309090 922002322 299024490 664133752 946825520 837521388 548179861 468855679 583342539 822806430 365540930 757385693 847426542 413505244 451275774 904303160 205296885 717502403 933109490 6346189 905132422 963084646 879188729 556982830 754558055 39820004 781589735 576962596 236906592 740702281 702565043 599635276 585276684 374191991 16260080 920838214 681683023 988391330 59565712 108031795 782856212 46111757 855473938 768892464 84170670 461908011 75972023 85940595 812197139 712267968 840660646 807711380 657375787 514091631 235469864 285483010 437863702 349540486 945982641 224046756 7562950 408077179 1937898 788389636 78169508 992275275 894809027 374978290 734474785 800379700 300167323 602991129 839406598 728368446 887509216 589114481 251224064 279588707 157500967 472980407 136055048 782749355 31405620 614572749 887693107 47898008 874658775 182411890 441987499 818846121 437317224 954118446 687729592 479772203 654722948 56378033 853875829 994824725 823356629 347373011 875112739 236541798 102362265 737194124 81775099 516761202 940385078 491080437 810568542 237608897 374822554 586658835 589737817 100307816 134560958 25429376 425418288 607838456 671768648 485372937 214635407 391180896 883112823 721003187 995889815 686810842 607679496 798873281 428809945 208072392 630553371 204590491 755139142 577628229 756858205 57093282 354243103 82178499 692277817 195197812 110770989 184219581 318739353 687800972 947240352 169509511 47406480 89097904 541316060 720683826 851302641 761042641 964536388 808663115 710005525 291534369 116474727 241251710 939916910 327613541 539200984 35579616 611993510 314153779 427417715 847927598 607837264 204270662 539038942 809708743 774970656 288615745 172123924 640973585 775471008 345720497 821143499 998944121 347455376 810197275 302417824 62677890 980598561 822151222 628808926 151011559 388472952 10451356 897032880 41096807 614023790 237991521 806197831 667874943 964434227 861665015 576946286 283822991 35818661 850148027 632160387 757326215 665228319 770108716 137501408 554682193 676788536 208057486 69386114 389051366 755554993 353829566 819346030 761708484 24096490 579333800 950384289 861542796 372080062 815762877 781996773 868200758 727516733 65638652 511498515 182260709 130094034 642490349 768715693 984914673 94041165 461730456 260804931 633050512 103699611 196183393 522431667 389505527 283824121 269148139 410859763 129834361 49559991 2127461 554563556 733257380 833482413 345309445 728216034 376935648 44319450 951676403 551478282 454382027 135114228 909654076 824452909 618195317 676425655 171274611 910121233 812602853 72505058 910986809 447465328 317101115 183682943 641745006 108353708 871078912 600778751 472732935 263800679 855423839 888738079 424154662 886631465 385752203 966701045 275350296 178219394 589148116 942305254 781220300 37559290 748230880 161360281 209114951 336214707 957993910 749988335 547734736 517836414 183618441 8670607 533380492 890538012 525931030 506433684 169168752 292689295 633835342 717503622 825396137 834785469 5095518 370182232 375162928 615957427 864772847 388571471 326943825 58557878 987080687 748541324 258181166 187922458 510182275 338782546 929831280 286217383 497118611 780921502 232471917 806763583 484183794 667661069 758645691 875219573 797388577 821449137 317138977 176730753 528981391 4278700 847042721 876980382 418442352 499947619 911110195 434942910 134958180 441521688 467187386 533549636 307971327 482468210 896044371 436165396 709034540 409751287 12968766 829846972 957595440 701484881 186356829 615707476 797977431 78998616 555401950 59618333 578936580 62079436 199764215 951207359 808017084 992884186 680207118 171569071 172026686 859191352 5582386 904115974 167646349 886388949 730891371 126084985 605760673 375700609 962053897 712277535 304923367 513110189 641586368 464569235 180157503 401636703 509566878 587696320 20580902 447834446 452726407 788875231 918687558 53807271 633361032 615174223 87044750 845640278 973197292 16621462 609379681 73524756 33337871 530545059 537907924 179120553 185402429 7512222 474362146 761982406 515091320 548545494 41700802 883417888 120110831 237340618 918818308 505372811 12339949 204048869 350873678 535842467 537168299 40969930 525966222 412549061 748743002 490120812 896747010 460463611 47397526 99034938 66890106 8173309 900018818 528440573 698559649 958080412 144082126 856658975 182870553 224696066 481535521 50720047 286864933 9488010 110482495 705327805 956718783 373684980 201662093 738520307 537371940 746467461 610501933 544516919 526892417 665528131 327664587 223477171 704085457 701319467 209698407 221019467 20174521 479890114 751794345 645466470 699486435 738673595 414471458 989778089 328428706 427520868 347618630 21523361 843455607 508903537 956458709 592875898 448260106 486607970 549771746 89877638 907582556 879554097 70262149 348230850 364305856 742654527 126033172 37306997 787473235 771635951 145677497 543896002 581455415 1785579 209905810 678674305 967484209 898945408 588342316 385379239 577875025 936097628 444686432 618522848 934765397 44361060 31832133 170827167 524182081 929186555 849013578 855447623 842099355 359770627 73682985 398553548 747351645 976965100 781623389 772471917 558691209 528339525 256682852 61580064 15416961 466604987 13723745 903103219 587158561 417332256 938939832 551271056 450819269 626972924 706008503 198390620 656760645 384082392 564188348 971555660 315283117 842416806 761461971 702537235 276178811 538906789 845598517 238894007 764503303 749409257 186645273 162505445 508697406 286555135 533947920 874975403 369114623 80160278 219401856 875373047 621561222 457804094 397916239 146222786 762144515 172418129 508867807 875077188 31324408 852109350 594646018 415951878 783712885 314988120 841501474 586135949 832048477 299627848 284679628 82018989 867103940 489406190 465352187 782474759 641352227 576522424 870951464 714104737 763660410 276681017 272106189 150250651 431667499 739828048 846960137 49290556 140039600 389875221 406980910 272957992 132837730 969519058 126095366 672449830 170594910 74401566 84263320 678905757 887966981 770249320 617441031 367065743 612299030 367119081 919473186 71369653 60780991 880168104 88218336 535877357 200476547 568656058 248281783 88155640 795420233 994869647 268937270 320531010 451736723 620732739 962632764 22609077 52240912 235915458 490209912 699866740 705647441 16814992 747806933 698048593 5035454 952493911 274521562 343296564 131646709 131213850 748659807 15895410 753700165 197413710 693931081 763089177 491703592 571451527 297554760 450658218 454065919 895747069 467516142 683400114 211611671 898952474 566670276 145719456 349139574 254184282 355197139 98186319 236076610 212125663 117151776 811312431 943609474 357939524 667466365 12291922 24065457 354902609 721643484 330526525 238893814 217717008 578875852 551807622 228469568 481165586 243918424 113397624 899210487 542297030 317948934 124041978 267422476 236353474 248684809 717600330 729336742 370415989 79405712 792894768 390738113 97164847 60692134 225600695 872222807 131415756 753236032 911617576 478143485 612344224 332461008 344981343 627542445 908870441 577609554 896241597 387124615 970876972 391237280 912113326 729057785 974638514 793568340 335093289 422930043 502217487 965123909 586360820 915014626 950481784 408760762 389224059 381354033 580805229 277629077 511239062 676396916 540448088 763050905 144407863 174761055 292944750 273354075 225374412 952694986 881074148 20276937 122665158 722902378 511916459 589470445 54843068 436874474 397288062 326842809 497483677 917819395 303728934 54356173 955984612 573041350 279208443 408647107 172336330 896411519 552084290 6041542 37952273 615701617 34623983 821548528 704856157 383433780 341792019 853379169 122853212 665509455 464476273 863261306 644806145 957635779 174505297 624376256 212852561 450581335 557854933 858284979 237690534 183010954 596607058 983521771 267864040 879091842 155878051 1391421 144772017 735801993 828073765 660542363 781267017 566215813 993561802 488624884 82581241 192249507 245940023 716714031 32148222 169103434 382394335 180604631 751457624 725646307 966304443 726786875 171010917 663870024 839154414 466215340 598377480 206081917 274845949 643010587 186399269 820193053 644150149 907414762 739766730 810613805 393538322 654156415 729514317 955734565 420119410 987610162 163849561 344924824 783180605 52712138 436130206 699737239 191619714 730734846 152305062 876389375 947091846 827375553 72414537 365276617 572920889 634886713 363508255 199295502 208381818 571372960 430509585 918140464 662431509 634057012 531174378 796024691 903647886 843610644 358620751 180201403 2518821 499876651 840402841 301256018 820151019 659867379 16420451 313289069 781102273 336328890 561385962 17039362 962483046 497525731 712058646 836986834 791717525 438990202 974190624 22225973 546361377 621837606 943219716 296156948 662861384 976824298 999601829 163344951 372631715 613610303 890910500 710803065 983243954 582035805 207764449 431310069 918234156 133422529 860270482 183601157 74737350 818657585 365104434 905645439 928104739 435902708 476121989 190429101 682718635 481824415 772665473 58039178 454160840 453657047 348170305 332603305 409194398 816447138 689626328 583460378 647310110 301214066 470735022 290270064 954371396 556647803 248487189 202040542 179714726 84704039 789765016 47852703 252705838 613746575 686791092 624006914 219181924 241240468 998938873 319468690 819140073 71052852 799803717 769507383 583359151 592718923 308094218 753894204 523581405 909544008 750818143 189346082 887693279 657713989 203558198 414674493 896105978 683222148 726340587 953087281 70106807 738014004 484338900 949338632 838113864 51225510 962060812 269081440 78992137 674509289 553649921 678734805 691560908 915418427 969538116 403465646 532909572 304244840 152069985 379476359 922634509 20529143 160274715 487824111 591581853 878003281 442812900 633855823 82751169 394538043 932910153 367744239 73769263 295596992 418948196 547885913 248071636 999691262 825071718 968456314 176758916 224752209 690371859 202610315 464985380 510621314 750609237 385202540 115036349 768383670 641875994 209673354 32677928 565221705 615877669 43812651 91024760 165785096 661258793 29588557 742886863 214895702 79940200 124579817 90097060 760823582 97037452 612327259 713235775 354418116 49981480 904852002 841302517 144379677 346754176 363365404 911707738 517367659 903127490 160553538 762455445 374290665 908708270 904615637 87413318 665622465 770085114 977930611 539622522 656300171 557135391 767559118 972077848 364000537 656443764 947036856 750804600 505036385 518642239 328663018 40923914 247928520 118794946 648585829 606901725 21695731 958267792 335537836 654023032 66755362 232309667 562832919 812652328 537546008 369043480 592376936 649144566 715360105 432285070 394103788 209701932 371186527 635499354 251479332 290494673 583715672 627874854 863050198 536647667 418415155 763416792 946485835 574599933 714581557 414956491 881252156 495613284 461609846 250084363 301687824 946848162 865175743 558717671 491176954 741714000 603171638 581364320 163325233 417538362 540255738 23655154 532863086 519692390 818540071 965667907 114238292 124309494 990131379 483159403 270570580 592713735 4052957 586485041 925782122 722650516 635521401 577476135 935998053 840464377 355052612 649704807 80055129 713134235 942144755 738825105 222658145 258040610 528115711 812725444 206397719 214499561 872387019 362795697 115440935 791104825 249173739 270128277 787648139 592637456 818631994 643335028 200614730 849729191 369493934 978150725 338259263 796314915 976169298 746072603 801590846 627592973 982393122 696789520 38044884 572905840 223277250 475513372 478855719 550720266 313272198 652001113 366353959 147153217 24137131 177992918 218753716 64366731 382963074 331606380 421646741 325977223 26532209 298255697 579571185 648326824 370323421 618137771 936063279 871309675 550521423 707593705 162652729 246418123 96469845 423855901 240082675 963725038 4810193 166375142 460804760 79210815 197477740 494448196 392677916 791002586 47542178 247630920 581637739 969499838 935116805 805498341 474955630 610123417 157993392 327747467 594448235 260329782 17895731 362690801 889300049 51641635 341907576 228291430 628014933 322329397 39602882 703984245 731286502 830775341 302583842 37561171 111773320 779303551 577735720 441391514 941895423 653860504 474244736 280324706 491136362 221678756 243085311 727279647 29171099 479905495 498465729 593394647 445073303 525871616 186782630 141950835 562760488 575224780 472961472 470840231 353040923 992100803 171735265 427786209 237118689 217174994 761817184 923076796 668158705 249625868 277790087 480328040 133903851 55926461 415069467 959382699 542233825 170048802 980367701 97304864 707437176 307224634 709214135 142813910 942089006 823965159 783524657 219595298 60274506 114433235 284210534 850894443 968308831 349734561 519178943 944092198 114014751 418737409 230804574 804064324 271520185 672987589 258931939 16860054 630337317 906717526 277373367 279671587 483787958 739461694 349961555 522231368 305709805 785685677 627277519 948613009 290201013 450785019 967005415 934935791 675852318 101775357 936871660 588511689 363639581 35349374 613410723 28948917 386740102 646894083 629858313 374021112 985538993 635609567 488903121 477224220 40088052 514251912 989328291 257174474 946015897 516748495 818357554 34908278 420968844 8495246 563542813 638927455 64893981 500362241 611728742 247087305 269907125 664596835 57336955 506471076 250967249 442661344 381178507 109556052 431106705 742214331 191708365 269893671 172171983 241365402 654198351 452393241 208402034 472545508 763039131 943159531 820706739 457166587 414308940 231487396 777356471 72466768 386933901 190492329 504052135 867773215 110363957 301676291 711783191 235007138 596785504 917629142 917844873 671717227 610658893 460801898 204090710 703117563 768787594 854433623 581560584 696163447 485548234 832313906 646784500 574834351 681446972 663123157 334835827 391953606 712030542 404728902 672609158 57677665 842191251 271540202 905643203 812069589 319934247 258704723 972412968 358760303 966690547 218522980 111465096 292306119 123140242 659445957 322232687 363240335 961875846 85140679 1627764 785149343 815028887 729116427 233773668 912173814 868265916 994087685 537598618 228308222 697466100 274182608 944352275 306153598 527469995 829057902 833893795 260291293 500829067 997423858 131957906 640906179 253804051 775952969 116550457 605068850 5869947 682466164 424710546 581615782 240949801 223744549 835762950 667861 97590249 268317508 125372108 331132041 631202340 549878525 193113755 227892523 193723618 373847618 343557499 240317322 341539408 643483005 211877411 90476139 753801043 24808005 227600748 376653051 835758439 254779415 780393583 286804439 170740073 256902950 867966432 528110925 591979904 888479274 393709124 963446833 593655506 870001279 308603894 729687181 369695732 875717280 937349579 447715500 333376803 91530200 345252213 321400958 401355144 761552157 914230841 273224580 303550438 585652092 836460557 880963142 972018715 414547936 205649930 941638366 433553172 739443276 529010068 525773916 755848782 238589085 810981480 701270154 51955927 674312768 228576006 362441522 279651256 718855824 625776913 457897245 821460885 53255471 641914023 138298286 320744387 826377176 931691845 587838350 478588054 851663823 215374686 995565958 421049374 310718616 498432780 487438951 838024416 142688895 866959594 614098380 920703855 178495324 3335052 159861744 626971174 882793676 117320732 394308267 379267322 629956639 71505676 904450126 414902327 252084217 244285719 129412949 655203695 110177499 173274107 706691184 840829450 967070883 720315899 709814441 241527160 835430840 27002019 891656757 208597999 318900375 129426027 557919413 176133115 467607669 677643863 382514726 56614476 353871723 588367054 71426852 136645827 872966854 490322809 534631632 780023487 522174425 933009233 143412861 738551357 93474748 909072150 145565262 674362695 63922133 950003170 22672590 711018366 595684366 202318556 134965734 434857648 205384901 528211709 386027971 544346336 844988493 119848444 199857985 4151893 556010896 951146644 907852836 821025383 350265345 59544557 717660239 693703245 781518969 150344088 890875041 228448506 700179161 5465362 794152704 596571294 590766040 502922985 19929131 421069414 756203813 94229719 42493800 27610207 142301966 897899183 378291369 962723732 35579506 657772940 7724833 611152562 323368134 460852207 902234524 333530325 858804938 555466893 780688794 442698208 978011401 770626194 326535278 376756543 615905022 107450282 711908488 403330426 836315243 937641357 476719856 127401018 985579284 378113862 24432288 241891553 683708122 268477359 694446197 792731208 378377034 743918342 9703255 916819447 787003027 703748867 943352493 62235530 359116170 421029483 816267226 557651843 252601763 409261500 723259474 422455524 546891181 604077649 286026879 897349635 229575835 547554698 378913455 372037091 912345365 168758306 521093327 304891391 500353162 465131047 609378358 971762117 236403562 633059104 86912647 966934703 1558985 85033784 870422341 385467354 110130735 552037240 806024526 960233460 849281718 108139957 394363963 189441548 925808625 280836035 347695607 965615128 705449802 803534905 309245777 962392102 645595159 677139449 363984894 139218261 651514927 620505857 765066082 167485195 550584945 55929551 573561291 4234880 376822767 449538802 411294599 294023239 856048216 110773158 490025874 110218817 145050285 158385507 570090882 651237419 723690127 908369862 631661569 638169497 750901105 174085587 846530434 467188480 585275296 939585704 335517248 741790774 557461067 294979281 528406960 951639883 26312673 42926978 370274882 334789091 997614769 365313366 492743067 555921134 640007987 742984079 298712503 822338622 793773132 352138097 21688535 479731170 95118092 117890804 466796177 214767962 398313130 59156676 629561446 44559263 849455225 776321594 48226005 707824281 226779825 909759398 373380517 172507938 76732155 397976111 184932745 904858389 341072590 400175852 789234668 231217884 30875144 339971129 489525185 935825868 25008623 31121176 999968181 90126297 109856702 872509576 842737504 366499724 336631759 29037647 671409485 266732222 66827147 626233591 352138145 449386228 525225347 452433067 202359713 244052373 185470641 136694451 815208237 355931295 100370287 395298138 967285753 617512588 92976816 458228529 171382210 765166930 186170640 329114405 396472379 487582503 607691624 58147463 132120677 403536301 605753789 463679180 309672002 190024587 746566080 120937242 460841536 164767875 474300048 422638193 852214405 555072288 284972082 394562225 885119596 803723124 419656024 164401006 965431751 731304230 51617079 861436970 280296838 124604565 23775171 438325312 862276791 498858009 366182383 732935478 946907093 164795257 726569609 585476265 133174566 759997666 200544439 100309506 39231836 708311161 6861617 98309707 650733419 21149180 980580093 795300521 378085414 326687894 667342377 807879732 152965570 767100375 96477824 441066703 856272937 765879396 5236741 716071493 588811394 223633294 348658969 152848786 117577188 55557330 79605060 210236681 224132383 495049377 823891750 610796967 811805430 439973145 544888479 243012842 292538375 571307581 48343616 377818364 97055658 412102013 330263644 743654676 250716009 325058333 909417207 393612294 711128980 641989052 399463269 851370164 845170454 879596970 872888483 623883491 534291402 339333740 989830506 984661612 561521019 779279501 540055674 811718912 161536599 352702198 315258718 157941655 14699670 909508026 26075962 139356626 630422034 87012310 609779157 262782333 172016132 932668592 860053567 188565300 911258927 193542064 671125486 271123719 395427644 527226334 40787318 910631794 95981448 694135802 215336147 895261318 457512664 318893940 176954916 655928121 535213092 729079815 868409269 270859207 133792611 669621086 395708505 490187076 204074499 728286266 306205305 715753662 984097022 26377109 513385332 829356967 82920020 403833481 310288031 39175924 779217693 80738225 201537852 275684622 219069692 966975530 336660119 232569393 349100294 861373191 910899479 227118301 926354114 749433717 157264910 9729852 579770567 421328674 828639207 324588024 598669976 299696467 259847926 857554817 172092995 947168964 99040710 364408038 816674493 565502623 786532016 104980929 106918327 730691376 42241777 101894085 4678979 185073937 950459275 785008543 982473400 784670488 994310288 489014848 956869249 18557286 494550831 691932182 53101811 731623819 910004542 662926388 496657837 571181518 445176440 593142018 359082435 526161507 334972264 612417291 902622251 355222943 285877923 243521081 536158040 966031833 22388028 296073721 792361631 860895704 823259782 658832253 231029279 212741213 659269179 7809424 136667001 55560919 302483626 970565770 530617616 450055276 227417752 294663565 566231489 298727096 496015920 88706177 779333910 190658348 435065986 832786089 145067941 440512757 562473213 62975245 344004599 153865290 111708754 787456422 971927774 729788751 736410040 665581937 372371958 182469650 497995981 324406427 157291708 617316015 201813924 954111024 33159099 761451887 720221773 378175241 216640810 149816225 203845900 185062390 761178147 175265136 271868109 117608930 435865497 980024208 398004468 545861950 74728061 696868992 503877241 631013448 966023954 905292725 546339091 437323048 352862805 14082468 423443638 408336141 16034702 836930199 628386100 958220368 678512747 775345618 130274502 796376308 307846118 946846628 469163288 852296122 256817660 422563525 228493060 985609597 954111850 448347836 159367997 462688826 425033245 950915695 964144810 512387233 298655279 514417390 423919183 599353274 445488304 709462505 201036352 488501383 299751237 383606422 479305882 446703262 943232323 104768854 633129596 801008425 385670229 607677523 669344838 612732727 124044299 87258534 215071859 463941552 784986224 368592011 199630935 159364882 603924695 908080238 781123446 114054545 674102801 460562667 809462654 661562317 434049166 903600151 80133965 213521781 575056535 4133976 887830143 746633890 855268684 878337108 127747652 836294888 214689014 947030439 983008567 977564087 903041363 151921490 112595147 670526603 516000581 139910018 621603514 256855375 504804021 558750149 250839592 150314628 719768490 499652674 978266143 893159625 616181330 350016097 445802228 199516547 776593555 685306853 21849355 930336230 499823091 430822643 271362269 810298525 984780903 799576801 660409923 844519798 520554872 594517087 128597601 698558162 325658260 260377792 16491051 203889784 579043070 66327628 478991310 159068790 826619326 855897221 342571564 328628151 158980915 839530074 179681704 631765687 857536146 148035780 36759452 762348367 400364297 347026905 296503937 722523161 501378730 62714037 196439868 507293416 628583689 518851091 2059108 159347577 409913657 572489585 972154325 261075889 23197239 559637383 662370202 786266370 959542232 280721006 718694119 664954490 336618613 845179732 966294926 869108017 992653503 650941228 99187834 689944401 620433960 283332404 373784833 348834055 64027375 397951638 90327504 313474873 207052275 513599325 305438729 302654 573569059 942665785 560803683 517746951 6033936 604938346 723213121 189833409 126412341 221352146 840560795 892828080 7242703 157408292 739857104 336985298 256398893 817546970 829381604 355291143 741398907 719316246 643521740 5344708 348184035 629256984 625494613 961789772 594335849 796993474 225038352 751532481 91879917 977364231 266293742 71052414 126342531 328912750 403569842 258660673 142620480 76558503 237071642 604681334 299439841 368542990 977921643 325387987 425778444 973488474 560260811 210041916 897700571 336727202 624941832 22818891 119957762 244253550 449249723 206621965 643059390 454072220 78628184 334120606 136361312 845475862 557485215 707681151 505304862 37889792 679945005 615457285 219474850 528827928 117040944 873336907 601004386 276449203 525918697 55716089 196968002 83609726 358181388 531709202 646948368 676607844 22579970 356990358 268677976 777679858 982995398 986802430 352289916 431168140 915038591 294714618 90305915 44596713 866973845 815122811 204728064 433374231 246901928 423321183 683569056 871439112 824206789 4989094 10397953 711959624 178839148 346300242 498943979 507378228 343734722 733442565 347459807 521905322 216516128 161815331 383734493 685739716 985705085 854342082 174082241 175836026 693191284 645833397 380523830 57673031 907547642 397198512 619692546 539448552 347619496 7739102 628826742 151256421 411807952 751352632 610257681 5719015 52487346 368432790 144242280 716985739 313298455 184162178 227754791 103274139 258680382 890783990 445870290 308361099 822790652 793813568 370975411 750989650 102687942 855709112 799135684 565892123 437567837 361558532 393768207 789811987 278710957 326366800 284239038 814327178 814884695 690962381 945837263 237720703 585539684 453580033 609775331 285388204 867750356 744311810 690403253 407740738 467527607 133811552 342650670 777970002 967369968 467944900 513429662 746632410 256598847 772524123 911605076 210079796 672593148 468504152 993071443 819209973 158472181 149239407 177378025 68006975 835710142 513843268 679989440 760678266 634525341 907625967 907469932 318994097 835085094 865980516 738939030 811487152 951964695 462226384 631608903 322843 315877454 293587807 532908643 367230064 75513299 894190337 270224341 276006605 362281016 534908671 548335127 7656284 632142843 667220774 250730522 217515161 653846337 786749389 283836355 982677942 344741760 925955983 692735556 746308171 863357039 625430276 936034353 977855031 670902457 359522990 292628282 626020418 517442119 201959252 348263817 827902366 520210016 245448699 103364303 509870531 237194190 363766530 26534236 142589734 933993104 884250032 806038899 913229209 372215452 192968990 945456515 711747886 674430711 447891414 983649427 872193023 246941763 754072183 605234293 674553040 124016102 35345904 930856409 587190138 82201623 860598619 902581701 554649876 740378295 491477815 823599456 687886511 563376811 827200419 918115281 533670031 920507392 638646444 81010865 183640264 129272123 57906337 196316182 202821727 770437323 145346580 44958245 509084188 187786137 661455159 258497055 975104158 862254789 733751642 202540621 710549271 785990075 867957749 828514250 243846469 263742092 445880594 311783764 944808177 772194064 973452235 276671908 857443899 819993358 666457686 33680303 885318601 208295085 937302237 235004436 914557269 84715969 301728834 628499962 648918434 358899344 857310037 307146779 383682154 606158461 796338912 31175067 708516233 657354984 845374164 341175831 162073144 616793898 102116645 445896179 929070898 465941212 747086936 33501604 794851953 196987630 500232642 655360812 256901663 958816641 305187996 195518387 207907990 90682143 96516037 626537477 733638664 204127696 367935171 156249199 771459509 960071803 830315291 759643815 999442638 295471304 826514699 890216584 65634498 497253843 190701626 959352206 197815915 669529293 727563605 150693782 220058599 153832859 76520084 29994761 715235349 100153418 301494894 366395797 552344543 733258372 800953147 100312966 385498492 481768717 828014205 455556312 368339466 271331853 381455523 398480075 153623696 139976189 86752653 282290559 724746550 373064513 147132903 54260973 444419072 175435537 206924881 230862317 105424114 930053147 282795500 142376535 296596877 798505493 134137235 821415165 949655275 221405518 665029209 740521284 205714292 992289542 583669252 415009029 221874073 632316287 612013753 953417266 309669618 74006280 572506205 187411545 324685828 130998961 34414156 804909044 938061214 653523867 286065696 862387046 384812579 320528076 924135893 400118210 865783921 992566502 583756924 990198029 768347920 514333762 775314281 33010477 387667680 344021030 474791206 516613279 669091868 486934129 571007708 142542737 45926675 838909970 737305615 81069586 101367221 123289058 135864590 540850924 749385401 630242734 989884459 520724640 992947513 639301533 311381722 440843601 186303220 507552111 351039319 79413917 864579606 750572115 258048338 1774991 202484146 213451228 787441881 835700856 575306265 845955163 610707127 197770340 771628733 866156148 275772689 308368914 575105548 879463783 364371707 104358001 110395504 137154359 335940344 567418689 858952181 567966973 188002180 640962151 436781290 904339834 85066844 238211261 84603140 668689185 318642047 162538595 68524179 491871764 527544420 465801492 96459831 109622803 367438655 743747174 18211497 474788726 533736015 536347518 677468918 405183454 569638856 779754608 281940338 511534936 996179702 457063723 503437544 342057435 551944255 169872597 963691704 27053607 57859557 650058054 117514764 407953631 48291564 521687849 256959475 794596299 340188117 496264050 898854354 505754457 92865324 850595293 519731464 522307621 338029710 447469544 975683187 993999635 652865307 847282567 695296125 833903733 877128000 510616322 930199221 246404009 213979995 341217405 573084044 301484031 233556320 98382303 956140180 78877327 672038424 471591349 255528623 976356040 154320442 616132670 517281722 385615623 285427535 690725301 319181431 585451120 901209387 879551432 160760473 994673420 787416965 537010041 131367847 427424250 559892527 988033576 743520377 223286772 715533515 717092664 360282683 389786106 150792464 297845827 368227001 491644302 732538311 855681561 57025320 845076631 157668983 122036108 67600734 348160083 347419309 489513416 550901599 523326571 895715835 284244732 804872916 247231881 414715455 585405997 431237725 52558261 105820863 324084144 586308365 602152638 400927701 575042946 947452782 85256125 736736981 65278172 633845249 973976753 232177625 451046569 981695094 901088798 308765823 782392325 313584787 432384744 500257665 464848760 400683224 118701792 332758594 218786848 6004052 663203526 744973037 263176886 45146650 700758562 795439574 301380479 237254879 890935671 636866696 376146906 778023117 9880644 603431193 174215378 319868670 359709445 836513241 724321390 584944089 750866383 8125705 851338446 986524137 812806158 476228972 933962202 892005898 723281410 855686971 871604539 653725897 354650865 8359467 434507432 342917438 208276031 865588723 45795620 186969022 359635817 677873143 470094347 982286636 912003596 38058758 765332926 401604954 623478391 85784562 991594021 284708508 78721506 672552127 388620988 418956571 140398662 847412598 628882609 961283546 911165514 927614370 700058122 638629409 537463216 718838037 159548710 964729350 416520660 467189005 341868583 405600203 622697382 883148969 765276095 286211374 576516553 576459768 401687347 923185568 250136007 950207061 481217607 244395315 130447443 973661800 891118353 880553437 296903441 744852409 829179181 22847895 28387147 247352403 403994716 730621398 170999127 398678978 718158992 97858302 588242987 696014691 897045325 401321606 130600724 291852293 366339196 550994129 570026459 449135692 665944303 460024228 360326961 378398757 427079462 127833842 993461367 180614470 839270018 375447685 928690762 275126678 743355206 860400217 10962721 148651802 654295664 211989582 589876737 878470873 279703324 428186505 380039275 813688879 356212034 449818209 394701358 596776785 915388612 313544882 133364021 336705603 440438097 429540213 796543772 218893680 434338984 574699504 805243911 295485868 443712094 945566149 189963434 639292231 163137019 982372066 948379701 698775240 191504546 492020987 55892906 406852305 904269847 681592975 613277611 958424188 404149911 221022317 366438472 874449999 830707347 845370856 817905065 753522816 843581116 781111765 152261481 617103082 29340381 304414456 365750764 859493015 941035137 705456440 563895432 163124836 872995411 320786614 445334908 107350196 779891005 947635468 181979569 152292317 851823015 688092165 610403138 154401898 446404366 210665760 278334773 179967419 216679481 770778333 218932458 10309297 314819827 184893978 820963075 37981585 262941947 25163879 695337523 667928500 643812209 537358246 113286473 243499776 641966440 135247907 486127007 252075977 787875889 315790262 279384628 755095569 797171483 934645143 474703698 778753017 748322804 512059029 793342801 703446812 383767744 596185659 392372845 759689785 467710470 445705076 216105530 543058805 917079743 8953035 675588764 915765608 695046669 200452513 728987227 109883568 176585046 123063248 648011988 809119948 10745620 813681871 361254725 574876169 615815349 30526811 272154910 198278887 29825017 299778971 625834698 36625785 940856439 407641990 22128163 476553693 964898934 417301056 911704988 5367741 816873877 843802551 490808173 124074789 436628991 146144164 9575276 971875986 974502666 612596738 243343281 297333189 317153067 139473944 753984242 629342944 787722305 723392025 965884470 821890293 201368366 743223995 470704496 999408675 32667564 481467718 13033839 821765191 163021671 689630712 397299560 583583493 304291826 779172680 391994047 830209012 641064351 752540562 91946438 131327388 655345888 765913506 523698736 537001314 316501775 88210865 958598115 395684390 165275607 620446052 31149536 803258633 392014459 492520411 30942934 384396592 997010065 488788253 100887840 801419448 353754366 669119741 806087714 168103488 474303547 318933365 254061933 58040314 90260053 896771468 544119694 245218424 540067287 674894730 773349417 410837757 974019084 715044912 482621451 562834277 480859700 614882426 943799463 276577549 947271420 249272981 705829480 630563035 734928200 959746198 769461012 466992707 354908416 15350530 224962658 812146548 699881802 181384740 609743416 459525037 321043705 82098804 722612356 783180435 996203865 434281513 369074683 896280461 728179920 597190486 764872276 529199628 494700036 1015575 465543060 48596779 538945713 278861290 865670324 19159260 523724968 601690511 722135011 268560494 567630264 865640200 156383844 726523399 661609030 297663672 816198632 302661954 336241212 192271858 532767865 781511617 246817108 629382375 988154518 501542825 867816564 805769551 60608519 227324748 142114236 338704668 167618549 937758008 801220893 433926136 787653222 828981272 238482481 780378388 229102087 975340305 930684029 832839785 663096317 266449498 619506646 953504542 515716440 532693806 336463044 666984707 679752623 379756463 78303428 257791203 652908097 137404438 533332577 185905328 720329690 790319459 562852453 796493075 149070229 96044808 715522168 456264041 851617052 422076853 775616451 603426595 924723473 718567567 83594519 412709029 3980599 880586099 360456271 398348705 363099574 41809148 187032505 602901206 733238837 111707200 325220123 601889540 898054497 729926700 333833284 275570332 345921057 959679424 266996192 237155707 941649843 825768760 636704601 699053417 694534564 128704249 588923791 483412313 966836710 842486968 329350442 37600608 264316747 728399392 349305410 905203732 923351416 295619795 702824048 89369494 304240695 70951514 547994681 572911092 590808360 681989962 980493161 735841684 416027697 634291274 308308339 195057597 449075490 555760386 506065456 848937828 480693386 956480739 468666274 967843115 272300972 778892988 579944061 347609557 700529058 731181595 644238467 241918978 864814500 421383567 3286575 838581628 479301955 184720756 501100647 421401071 980712476 432734171 95302751 216495572 411567401 751123471 819957544 839328805 171913523 526385905 151686467 601792852 724540920 714392210 953788203 70592822 447890130 560643124 672936448 947412387 105445732 43899186 307364203 736101264 602374287 911133255 196032545 872424608 103744289 953420609 558695335 774780294 147282598 538368811 81130427 458895260 510706670 488636624 832308212 581213897 661631522 553855779 763516851 867009435 372356140 654998222 627190858 445490005 797374227 242640836 930782324 996117798 976386629 226135807 762704069 121409334 400689431 399471857 746376302 808534708 907348968 465015888 515067081 667170775 426713405 233313499 12785439 597215419 962391851 622335390 181908444 171571537 356974367 653231972 961741612 171437161 893527413 339904662 620946294 19520117 918706264 863614671 477536218 371977763 149276180 346041825 147113878 498182164 746431078 568082472 443046462 287280373 626476207 98136912 1238007 446792644 556939682 171626334 792380985 413567970 776212190 328439364 214071718 695151568 878910529 731814777 270758999 406494493 990915017 939154486 410096251 12993255 918238808 480426676 136734488 769163620 232943504 724319052 663854662 376583829 155422177 105500275 918198669 163312610 78942027 533100091 654000290 249355685 625257863 799737915 399014921 664899756 837354521 364878566 989483837 509547572 881203755 729002220 601418503 809204672 280660805 29962691 993402139 635517869 775204119 871110068 851634510 532899109 671278608 483823416 105709795 77323107 290520487 422714182 433808045 884889574 253929845 641279756 585517844 318407225 241647752 708553275 872077531 852476125 990312079 886214098 854939077 590273242 583795869 33117615 58622112 919212599 327663012 986040265 639733385 948731490 138470757 245669074 619660211 87470456 249419864 329737526 262909951 399028393 810380089 394152684 381440128 525307169 265647520 123928192 921029473 158745854 552008654 272053168 673979864 496757029 101870281 453018098 659820260 427642404 326678178 724244875 864435078 317827469 658660420 770491874 306183365 514929864 872503210 836246541 446283294 347941328 991790786 946042901 606180573 149694942 114490353 719199343 125289194 506255503 184999700 267243525 713593823 409375387 627726307 179680659 939975023 913280677 815331505 552085376 159535436 879817868 332053677 437984358 42746992 380059993 274640174 206318706 993088234 152480465 793145011 416698183 918167330 947523992 435139457 21753268 81007879 818534930 917870288 442462758 300868008 405878401 252483807 775452640 70989280 814784161 98469817 473037631 356845 201418469 562128604 76188816 186324192 710853998 562821821 615790734 236556019 475439696 894554348 631800042 84862640 300169453 614091163 674626994 513082164 22259695 255678120 339683719 623858248 786446636 346807043 318721183 115438629 588834415 832303756 867144136 896757095 883952421 512675351 194472820 403555478 652594407 753255832 54160410 108061113 136112874 599660273 721651760 587296495 492509278 340898183 717991756 596540121 382311272 60884240 763310929 276907377 258161583 24525220 893646748 163760058 686408018 33613360 804370887 40220291 366694323 540770687 908418544 888525122 885192912 610439311 273542431 84871942 870982443 439430180 785833985 615550412 223466395 900781961 67372481 395120294 304206537 631180573 562564639 164183323 1506963 667842999 286083664 712684890 229776042 329282010 46136052 67451091 149847691 867947062 553208609 802094784 634279985 988580601 433969959 401015934 965726644 764306740 9532721 631089263 743893284 989751378 287177967 103555328 679092595 350686301 469569064 96117563 314858829 189731682 311009876 550575937 305617050 912749726 315815884 335665562 95897567 289830583 72391180 501494877 22049692 453746826 902350247 296281905 565251508 237479165 136966350 28188226 900461025 228827759 962548395 391397423 966759677 119113894 181774037 407842088 839266129 594718130 955794428 773451470 582153273 787693329 485586659 450017620 509023632 774595895 823270326 502495855 396389848 795357903 954872133 12010353 670394237 704344059 496379167 463390277 921405830 541051037 491391137 489036920 521562029 497005998 824552025 860329855 715804588 357356957 522873632 546119761 284084224 934037388 690374353 678341998 820361605 88593548 383293614 677746864 245778396 789023078 251320459 738244989 825081109 445862856 776757292 429460123 208366193 239909171 944741295 446551619 28558112 917398103 189362336 275692687 406155902 715277922 442168372 114781601 259453261 741314763 204923976 645563301 463178281 878346566 808513506 509376809 352487196 69455454 854349002 664123801 341231689 774814117 291537386 882427325 199508323 178615881 290103069 343147007 271944812 258067723 646306700 376035217 540409204 551032074 234428775 194844046 121972678 858108718 149249365 276174059 584563803 287877009 489758849 139974288 352734942 475542884 97408635 992756547 859992031 697282910 209018804 201508070 525724531 263834742 814634765 274691282 935002289 755851597 648604682 767747753 714887394 28978675 684245518 310029966 97950088 600379752 238690449 410761102 744829745 704088027 863666498 344933803 433364142 813436020 6225730 709066030 638058875 196339827 958389856 774719710 240954214 58633399 440533165 602009368 416870096 688296660 784570639 733265823 216571336 590330808 75423142 632943303 582601904 371337768 915984253 926281892 196676618 714093774 13031974 442055928 206667499 243550020 306724059 126306065 800788580 878850408 779016199 895106157 474704265 353042696 467610001 991794727 65048487 229762943 474179402 897134817 94042471 544667252 369516777 315055007 793276707 581913148 487611567 743406117 919889997 970535612 453476500 71041746 556395139 921780697 462392734 619377829 47613312 396206049 909705089 505304444 13304153 914775270 719499023 126452694 297582395 940854801 915065680 458912110 364322745 277447423 462636182 968439435 760459759 593021182 568097421 923723504 477327451 918684249 485396109 917088683 859483129 772226484 73589843 79095477 315779254 945782378 488073523 274895922 138587215 96969280 208245359 503308951 988158005 989050466 596615451 573722764 936817662 647255628 241953114 131115921 591230029 306295583 225597365 67109723 643681655 607606814 820476626 255289589 237865939 220385054 170321143 262249814 880482176 615944009 667212975 856526637 4848851 998274931 559228294 493499160 836688731 340240364 475375816 514169094 325500204 57366257 383948821 243079924 811551806 897063218 696170031 327923002 397143204 72160339 865408136 720943322 49196825 281908749 208366470 267214806 225105278 610723039 335941286 341398681 337710220 10251319 721719760 45886841 392941646 146951077 334522673 46725531 78964544 456394559 900693838 74978209 932740168 444949579 96201639 186954864 913184307 313345055 41381966 134334435 330903550 392468745 210649805 644964694 561362836 192241441 781701259 618525819 126965592 704116107 326556507 878226281 379986949 695160279 386014872 161492228 297360467 439553794 153912234 766495266 160638313 519154473 527783741 98288025 479846993 762891409 504042704 290823435 69478116 966249752 115401891 89103073 577485928 688314902 391493485 896276324 573131327 559323152 799918811 125232150 889888378 48194993 757775817 906246283 892827052 848419417 842598194 852649110 95072033 634357877 258277323 661386162 546199721 277798126 259802648 580253962 486147883 261534304 567027254 183186128 213205121 680884477 708541714 977029768 5779930 187809480 928432042 57839961 368241279 387356290 816617814 839499891 116795481 440421121 874529827 681531705 418475403 444054286 523285063 957130132 793777666 11114062 923779285 334638965 712555960 903661676 697963899 347463023 473555586 325191726 485902348 787289707 527426542 662625774 234681572 590730795 498298317 355369992 637848756 282888283 819532964 76027395 462300618 21984010 873290105 322166968 400727749 296895286 144765710 338071086 540964909 687675193 11139939 229897628 814852791 883086994 796747916 614910299 801635686 480587357 16260178 817702744 879566365 276552765 634543850 688904719 983501606 521731132 30681878 694800407 606984503 442606828 269086914 147481927 886641620 908857137 710018340 263398547 372823215 954899515 690977224 567794455 236958343 309389474 77295146 735026733 115733939 506311561 75604016 398801654 833815822 929711004 992802719 564059655 295907778 890665538 504132608 407774751 711881221 391931212 776876914 303937198 763724396 324675326 564541275 745622318 495696319 169853986 270323576 223593171 252178212 270612227 948881239 958451199 730885563 653498699 409117953 106107898 857828276 87210136 199650868 588144611 846355392 773375980 979583398 732444448 592660987 53263922 768478298 143253535 768952790 111221841 12473261 129324087 262387462 757480227 101342411 277549035 957224643 30237641 149769746 506251095 153354312 701012177 291945074 671981701 339931223 663937121 81047086 701183181 347126718 677412758 855247476 484748283 490360491 513153316 746496515 704609750 29755957 43449732 909758899 707912623 981129409 956076739 612622717 53284732 620500009 664318677 560078801 609720209 543758721 683790410 230200794 789669083 625960183 907281303 170454474 307708046 141042512 161734452 680812531 224550595 517034519 893369824 763217778 544132636 803572104 800297407 574138511 937944703 382303216 654412239 585016720 369220574 317388520 934124266 77659010 677346030 612076009 940370627 944045473 37984447 89363648 270199235 856988225 305840826 16353249 130562130 243415713 542230418 184524796 73706298 413472726 400408972 708658327 612911398 195551672 383969890 884016278 822294272 794083010 919390804 202396309 994087000 561998400 689883206 196338386 392110112 592684010 707899527 309664890 980602023 777119009 977107243 145265468 135772146 698710850 480101278 87987933 570206938 599202739 567138271 258562163 374007372 773520096 975572347 137485376 643035022 929717771 806746432 511172419 465300023 870212492 876448383 179591641 504448334 153580977 34630896 175189363 336545498 862620756 781669087 279186964 70015527 705204356 907532265 589169632 477739513 698700733 339666138 579562365 249661610 561091087 233509310 53426281 478100089 650152954 63001132 119214743 747875780 238618382 280251377 907296620 227226600 468670423 986161227 658540725 652697508 498775192 277966439 920450238 122710659 438859026 437805795 349126668 622773424 906467000 841690 999754875 25510208 667276262 371418607 135831790 476406770 358221099 70910697 334882463 103415618 507783087 353490128 666565148 452953274 897305491 514513858 231945245 63729197 333951965 551090992 756344642 152643700 70759080 573923417 823843206 916892348 313448771 762590327 147915900 302797119 801035176 111057362 244937946 590937789 616089491 198291663 83057670 841551078 132949760 215033714 716145853 208006307 847304915 540724515 378616197 350524147 80954255 91334858 606936454 738380014 777883225 911408072 688774520 816154620 910462304 133320008 120730996 912871686 560748150 202788040 430411856 587835954 810813776 660621675 696081704 18769626 682489908 185172971 767847538 648356403 136247904 637117028 713755337 672985077 387805883 530505444 282709809 181719849 563854504 370459959 592714727 710397600 894298870 765831405 976407542 227804227 909700747 6142081 647945497 421135026 555822592 578764644 60963476 49074459 147237755 181966464 333678943 258885405 598530240 374844781 781872383 835627747 267468360 69245940 323274830 510907472 809250124 437129283 182764790 640968931 493048569 789977163 126770942 275019905 524844324 969692381 875260959 67608718 426916127 176299614 211083305 964066915 873624326 878938666 984978023 225666563 145835396 686821931 403311150 745248512 679348653 605867696 846894407 511977233 280618748 586139649 2892412 894574803 456928797 231509118 768924152 955135876 965014281 513815213 135190372 798653778 888416430 541307991 207065680 250941008 496586886 75312330 97294775 414892908 446792114 289837085 833509071 115065200 130307581 286687089 19630069 553544491 448252791 798560388 63508067 889624412 308339081 300093302 218399358 318785051 919657530 320533004 364370547 928460484 413231632 780259168 785390087 778755544 761273748 309135629 9800992 735751676 100056516 134067184 60129587 165968911 855406937 441511210 379691403 278486202 696780130 619480182 947690017 964866433 460429769 564744419 782226831 741784459 897806087 898971668 717734487 185863167 546992921 408684020 17068595 513169014 998562622 669757513 391590671 207276592 39970178 440793305 875429689 647616185 296688593 556845023 265640049 915161951 440634734 916573097 565136875 941932517 802584623 684517346 906190407 568982126 250613093 227964697 581866616 743464668 258304919 792138666 650291981 738150842 394297939 745414593 8605499 176786299 251232163 360366089 810473016 432360616 414908574 808795765 410788548 407808218 549067033 854031189 724004884 834447596 713075330 885470975 468979433 620437675 23462320 212740386 645353715 135425662 119106914 851989610 666099899 318477282 736740508 450112732 769533248 515839764 822202731 476686713 291197551 105985420 933163480 730282748 735050056 386864745 369787324 933680461 252045953 452868914 39433171 1530440 253152965 866014810 257159598 585409268 283397381 114988739 867818333 848372955 543927935 91482933 638005150 230986353 616403988 688592508 37325079 659436032 25003360 212510909 729365283 531623850 482731797 327330276 3771234 905172370 956766092 218214112 487961187 171719481 836889950 204130240 635302952 126124736 638910102 87735455 914071879 344302530 243439864 228848120 525725702 869721492 663466472 252617479 710183887 81696174 305883604 820786675 272278089 284262339 71305889 253993059 213887502 688718374 241641095 794417452 571012527 623776941 42578499 29834446 900937003 58856990 452969671 985242706 850695930 27261890 54734054 938305968 701990921 107350840 954226639 371486238 150840043 481720397 652331102 340316390 295754220 542437135 751547388 751962013 124964127 937157764 859374844 2489363 799537208 86504810 385017693 224483777 991704176 576493683 330570474 869679153 286103591 730787539 17118256 109888067 965720690 522603968 990339008 318677399 56559527 956137472 979624044 826936221 540513164 874285143 752066999 685262404 240129203 447019844 764714359 428110570 320600282 303652976 325666199 960274757 604709561 785614016 926662450 392192423 85811 468809638 543519321 948807173 859499646 59741794 671771878 687309707 152062418 706100759 203683588 699157274 668238739 376987617 754019671 567251874 166550101 981577529 647956275 359133765 521785612 131159440 122771427 851371200 731472393 85418485 174135327 916305780 559033643 17173293 772858219 984262199 42084966 298513262 489219825 591235888 985663461 783582072 111523173 147213910 774712678 39226951 722816216 289106159 745960948 603373931 677735574 350294033 405293150 710840946 987917545 544392883 791517333 732446313 340178621 149956835 805186553 851563417 936884931 460040383 337274447 902718512 337223952 709256944 178340132 979919136 919592454 96909448 216649069 891190407 61867150 487163472 193710309 753435178 870546330 458116349 119746024 653047024 801793688 813695653 613854856 413710732 630485802 820009458 12465086 418802465 304799631 782484478 224284972 622185794 545035853 991140077 201526610 227035371 654272033 692472472 401411930 1215185 930362456 449736918 915060836 569953666 522932331 803780767 672868679 467032688 103492624 916579847 190239273 964909405 733241885 865645324 427700056 839008544 950472077 79242138 336806916 322389977 865198346 962719830 55721861 310525275 980686289 169921940 656831827 19531048 500152499 121514439 11380006 557857449 621178078 267946099 291786029 521722823 201562849 912557904 269044281 274587464 190309328 666129070 9709410 639525982 623591457 27448947 753546410 877218727 818814572 329043975 32399641 276611030 869880937 557353195 490777832 178348375 716372568 883303699 639175010 627693450 541485888 798195810 17411752 501609439 607633049 998127901 578368320 42338526 267968404 88157127 227142035 729735177 73912054 300625075 100391705 866360739 683848392 394930379 774735199 907290137 749832634 375438002 693000757 786513906 176513138 118485248 815306973 238378194 895972315 797777651 42650098 946208548 63879877 961255873 409294521 430715088 647537734 453984241 387436893 887089047 568838441 720052730 862181186 408577252 794716675 619322038 775433706 870068874 220462122 846626019 749178971 963998546 279724719 317224717 458205776 953033750 481640423 482066616 25234025 23580574 710042446 12044221 314373877 911611493 521789459 800597368 597263047 58097858 177052675 285008191 525207798 896910147 41078260 380382292 496211106 412768653 42865421 116267481 105183471 195064065 465385433 167234794 551406452 168373514 976978830 757941683 738257216 263875385 255392201 977728407 918923801 673199806 737686638 413829323 397567473 818600317 949213001 693995868 981999372 851252932 315487124 380405844 666182426 329533172 55959702 956624087 81220868 246446279 198750662 53193686 138404044 740335256 49517205 740948566 740835980 876975554 853039967 220483881 201026038 449876663 194101575 338658909 489441117 350155967 285182563 976082793 531869585 504520203 675933807 844965847 206434296 769540820 529512887 312741754 890019736 174788601 245790352 485564590 594532477 150547927 491341661 834196698 297798835 916961088 268570483 142969218 169143210 39217662 822873579 658034274 194845075 309070724 593409097 57272559 550630424 745081227 449913391 891768725 8360437 671519922 785919085 661168098 439678117 866862164 458895776 811060096 437900921 65731991 492944349 342336095 4697653 965230503 414249511 608579502 528794168 211969343 714151146 312999945 844482034 22150974 29240167 629945991 955031379 799060386 746467513 685191494 905695328 498973975 942087071 597840406 754906978 711789144 794126922 938520282 801470962 51493044 432757652 609277200 402824379 481359000 569253627 195196450 379583762 913855029 889571079 32123735 894633142 837341655 747421806 971076256 808215042 659320357 971627677 740701894 386312511 950349130 612196328 99995465 697637695 156271232 735601266 483712880 909852051 869600881 937532914 20209594 354653968 555500228 154236512 45642180 636311998 225334632 393306989 178301634 462024806 994474947 645082496 492329905 847917008 567878234 453217458 82431879 602836551 542224754 897282912 588194609 585305927 712376965 8690994 1114042 570542414 633633221 77031282 854579184 859550400 899792593 846024019 937581711 657795322 946506003 591994642 254202631 997208800 106698782 765095739 630945721 233781221 997009828 93260224 700684621 58219156 922343818 495227864 456294230 195854000 465681906 247954649 551680520 894452155 9994388 22549877 94739866 341744188 252254270 417081766 691599474 527717729 631513001 244018950 94988538 853607709 136661286 345070561 79501318 767410647 125259066 503185063 628795562 506572892 351193639 575849635 336406005 449909543 465506103 161288227 129537331 287679942 476882995 570573667 701242357 466984004 238900210 972067084 803117049 756656161 773987947 805491308 506291860 904610191 877222982 123822200 405784787 796062238 694837069 401508648 131194845 406002929 955165760 22491060 787234773 723372298 809694441 616313301 378697701 707810196 656976742 43700947 286881172 506028532 963669629 659940970 479891140 56958344 425428347 508699524 75947893 219810197 247500698 894941449 200711718 78157150 963174845 232130131 360985078 217873728 193604564 749348000 87744500 269791660 431329992 268613187 132620946 132470053 973349908 476171759 658688153 690437189 837414312 460126828 575928748 427169336 601340014 511018830 222843981 647591058 556370295 413501978 546801559 280183309 713575624 704918944 599963997 327907984 457412407 910628474 8634305 318112162 926591042 638596009 255380483 314626984 958877637 618421199 202898191 764820591 135128025 599131873 478433561 978969667 973097526 992783098 101509835 723240155 414996331 187758304 826076810 199377194 471196256 903887661 476576143 749361350 259516683 293466316 761350210 175142533 74572029 946571549 7145178 276633513 720164235 531390980 542402900 128567196 739755439 469545113 757185125 534328301 55624715 208527617 818420156 46455254 818883389 866646044 169627632 480198648 993270757 992454456 201185266 178809336 677387083 51390637 522611817 875964648 339974971 458588416 446829215 71872063 479827786 969601483 780378986 204993704 27993237 602962309 26662483 166890591 101353301 648118249 773811221 408067699 289571216 955237880 569895193 838890069 646133811 350350096 371090294 64694496 832550547 239365555 544313701 281801913 351278545 578711667 222029647 844366618 105442315 466845227 847143111 625931423 532933569 494694239 38064942 682788361 767513403 948871887 43775535 762239557 72758956 20391820 761647429 146824667 94577214 672442658 92950109 372710562 75341973 873928333 391903819 955167447 640394751 20669217 651404963 340094977 899780505 825995419 229130565 542188795 19344830 544730152 545533678 804317503 697010976 134792063 584399310 37440272 740697006 345926137 146343448 37065246 565728048 683525516 107864412 919597069 714460299 911263348 74718668 934233880 419347959 465784384 267241935 710976383 892544274 809372919 261840655 852475046 293974044 351910319 927132138 753168750 232496189 421834252 632046138 565797751 770460298 135744621 939626400 87256044 776870585 992367353 975055924 556492036 517942929 312335423 124038891 975159588 564063529 735818893 854884267 425179166 681859203 86155780 622650109 183107418 650782366 951628629 411875150 445726014 846171511 682769736 126462578 326697911 370577664 125129039 74169196 204185363 549469285 221419716 120671168 364981280 809563234 246374845 134511999 894273880 23712310 651764695 952414549 922065237 288470918 105714009 164660868 287929863 164874246 780298204 353405158 302244360 964550414 606367922 301228652 10739895 574502620 251166117 354099593 742790875 573361741 807678681 907433523 730827445 39649781 81175499 440689516 814313857 398105524 733229060 712159624 45813124 389032810 132298998 158615415 993014808 696899694 986140304 775387681 531164192 19907031 679351100 494807811 605613604 219987742 550608991 20722855 368746981 161488323 423777915 647747751 977333921 74715577 501563856 542222619 470623508 760820075 743352869 650382439 480517920 131020863 958525922 433591053 942095917 562224657 717968240 354641477 851745556 795843687 308426108 337721183 650834163 670948033 242114040 636364324 760719207 599613141 454736036 262161784 494145928 756367786 373831705 649447905 658177383 912445950 572158671 163423981 176947522 5299064 210303892 370540118 224993091 7814078 58581609 348395608 930066831 953493012 85391566 571028859 671745121 867461449 213102420 468989704 762353873 395944653 731812175 459041798 982232193 312480825 545775587 532185992 349223297 92452618 990983171 295455283 644571684 574708709 29019362 858402105 129987749 114442860 780438564 294887158 382621672 141627666 649198050 488932039 179061402 139492599 220122704 840129862 16978102 387296694 186354184 796957664 203831644 409755022 653892385 54341212 147288961 619284196 413394438 681656865 379769013 952580044 11507700 539478415 446970414 909000623 359969271 733551275 606372255 453015171 609765714 261007031 318065455 646239098 632908587 66763529 26603712 678098064 521416246 125254287 803806622 677023491 895701337 843266556 935919535 651536972 210949020 43447863 704861630 258876688 427209256 545504836 512972704 693797388 666037821 707430400 513092704 516070176 22531097 232838493 273293594 955944138 590998989 421209532 10639861 467464885 680297516 231713169 948519754 811480622 587324004 547506029 942220090 400862471 742115424 599502696 229022929 181429590 821131118 520917372 714901292 943879997 365373125 611843674 458807026 363863993 974513916 913337212 533379414 233630881 664636983 943705602 325218032 466922058 222894731 378422991 29299116 428247847 581483241 77796434 30980817 289833862 781282643 22306425 227353944 286692318 193702334 421160976 38043710 887430090 566251556 240616488 602470228 202656089 101514183 47869209 29039486 464826751 972970516 562496796 393090534 310776021 533450628 918408567 58934652 443244655 620451328 340974841 505035864 352147745 633499748 287157958 599209816 181167615 510615690 76012018 93667013 322636523 156692316 660576533 678804454 663822401 402801973 942837472 830473854 306371864 344527361 695172674 144648126 122259807 198101985 321349647 780163173 316459765 215446047 148367810 923001139 648825930 185892299 20097338 143784816 420364087 69132067 973755008 531012159 315882867 334375288 598216025 629404085 498361300 674184641 119573985 718144803 56050944 868799399 152791158 523125688 664244375 193747151 785251801 128839227 174428648 218789773 809751646 119981576 988440108 188538010 793800303 829773634 978303217 618739860 880509206 484482469 516292989 530507911 473487099 176812700 146522723 909908073 787127515 821400214 124454972 133168253 473796228 982270080 819631113 138515771 852931874 508529262 997515778 371813040 450403676 710899349 506647643 546493942 947156861 959298620 16830894 250028149 536077098 765445896 559201327 530614020 890921029 917702882 72577532 262299000 252562983 53371208 456008591 949844979 193525000 710494086 774611340 86194824 810713952 790395825 448582454 6459736 395779770 819893789 412083072 501885482 27216354 617951940 443887544 44783858 536465717 121276014 685239657 426495785 532568578 72787309 498444728 919663395 690347630 134634350 720703297 68077492 556219836 283023524 570435285 938691049 624638863 873537611 571173635 782912582 305908516 685695066 366514581 467186443 380464579 252995924 279065003 861612948 718129943 649432318 966487743 114692267 212199812 419956683 24371940 793881763 454146109 895740291 93826627 118280553 114443735 142755660 131098885 484022139 800305477 612726889 899221825 498035670 813654101 698726335 159146401 188961936 2668271 168147393 496921874 545577123 578595404 527428754 582609147 848463613 549422539 593856108 787506952 871187332 813239227 31299023 955444302 330526034 293821955 140517680 628139791 857609311 184060372 789438517 509496612 749049399 436435869 103292848 933948911 580242963 868548914 912680497 450400999 24011084 52650142 155831301 103469194 273601208 245973150 988160176 384458873 530715084 669695627 566302937 101355420 764990516 594380168 457285468 466961854 1183216 555542954 295016033 293101952 133016166 921968067 549519668 293996380 418509290 194398510 937123287 453915964 223486201 731026888 801832916 235464361 880227100 28297174 736219124 519082816 13817815 865004912 954983423 439751417 880985005 376899817 208260526 348880102 265720384 107849067 496550159 920631044 338092049 881981925 756737505 468066765 766532690 788229259 195824696 458808748 828477119 10893996 635623082 981768336 916570531 49579470 278972908 618825982 151481133 485028325 470312623 435178093 102922794 306928958 111243253 349740365 370292859 13151327 314759118 723444276 683990831 899329621 561562232 985976399 445131076 396578879 449555470 788152942 308629567 695896208 709640438 699514668 830346541 100939069 253209539 57629779 41332666 713031355 246590136 290106753 772749320 721498011 553496827 723202222 472433519 714250651 955505917 285663849 683167452 782665614 682039699 772869316 453098931 823189094 707670407 149824526 633665950 901452203 955739743 362682795 399752263 331910181 411234715 463222068 942083949 376383889 232619936 465187379 303147581 932567866 892971726 583616727 969130342 583155964 797142204 719022970 532610138 791959868 459822838 958553249 736503876 70788584 169469953 964771930 66313184 11305807 202651679 212747478 467705278 256928346 67747359 877311448 807379463 324671812 54520215 245158398 74274296 553986059 572409836 441063332 365274349 861524688 897483791 645426516 647002988 973652733 102484058 364658878 558244671 622887961 703708367 442019948 350471539 800013354 226999388 948226933 132429630 771428274 968905146 216215368 631695556 358763516 92489915 106777147 708495427 766832959 891373926 169931999 12927648 594871548 603990418 238192451 838774794 22174044 541676504 848047880 442917945 273685964 119451535 384459084 771501271 186915193 650450196 143792300 87898422 320928331 406712303 590287565 296253219 634545971 141809111 661231960 719673207 664830302 180350957 644089296 225148286 245346897 85369278 851360617 105850099 700458076 903664592 226649767 235171131 7607842 859872816 219877800 292463869 886556140 960662392 363103957 116987212 96971827 825874136 180865640 345746172 887326732 455142474 796394224 894972647 24186946 476086352 546549632 875260245 960100134 552256631 692013872 133776649 677921397 979900062 419738970 828635353 141179450 813943461 195508245 821019095 116614952 173460812 398286300 20389711 733773313 452591501 946323704 957931884 919324320 441872111 660136573 230314028 904029449 904306166 754242823 819233704 521238665 610544238 325409271 545587978 429193592 857714662 757648198 582835166 64443973 495013627 354355052 121346208 964552387 290182721 209613236 208806718 721043211 22657116 945238407 984001394 301818488 649982793 139716370 497819131 46177523 754282451 39259197 173112208 450235644 834067230 327099011 528867896 351556651 590092948 941179170 324712367 111354343 574636081 885492237 195241151 232537551 537179049 338041234 578584370 464562330 231984576 942916704 856734376 56370708 162815760 884657854 279049034 775964143 43791305 567776860 311611620 329690336 92778325 390424290 146999771 611170539 108588914 825961533 272521810 888504213 607022175 697682159 960845897 451554221 512154106 591716672 872381485 767720683 839389040 863569783 515452944 806967675 500910461 749454659 952424645 716277471 276523783 296026513 302275790 727834022 15053221 361790810 70231403 240707006 946912263 56118196 166896110 869659381 579968380 425179992 957630053 20806195 635363620 329168918 725176268 992082569 700881254 952654914 934410327 351178825 589611924 647015055 886803619 762432025 573213374 834523193 143805712 594797192 978145442 432430227 968719793 782298145 128201438 557657287 479562325 344237918 692822522 651055496 62340294 19960324 122352392 281431460 140657431 172516176 861450971 734585286 340955634 672111224 45843674 253538982 141972494 720097781 596253322 127157969 598976204 160004237 569743109 515439425 206137580 792621168 818815091 969373591 676042721 796771040 803357488 27546733 771109330 491573602 991448460 826924484 590514694 422491092 778027979 181992828 133713793 6240276 464271761 439735927 128838654 478271408 410793163 229554834 313151740 755884454 574866218 938332560 993531434 591455603 780664575 877067769 35760392 409143646 213684815 30228125 37145247 753825985 829675394 559038154 717784003 185138656 336770305 53414449 114767168 956421127 47413157 174695456 129380633 529121749 948236661 979956148 752910815 296852157 785079816 584339257 413954455 69336168 620505271 728245765 795272289 441413822 881329816 192004001 868101728 100180533 95637420 200358782 761341529 823813266 527221918 814541530 952069505 511205558 578826782 285007832 240301835 747033334 354309138 201440904 300101851 919793091 804734843 19892363 736672891 784705554 503966651 14650862 873259467 356812526 551770028 889356363 794941299 667931505 498613508 135826559 683744629 193547570 750716237 792156761 227048201 421354309 387245172 77698060 897410457 935795325 859284689 811962899 667330326 409455662 958254995 659130604 626841054 346798129 320395270 284155338 706274093 583287918 716495615 235190023 342695667 985102609 548018951 284564824 625168430 722185793 693799481 741968752 953911235 839027834 504753853 320841222 959135504 416535522 47946056 714312031 309834346 2266180 242472473 384403084 123912248 220903412 941168170 34083640 642830609 337227062 357899089 182924463 401739627 406925603 101319304 263099349 124253982 804616522 313312233 629786248 445134161 145091868 279824002 504226047 929377195 588201454 833687380 354568159 276555590 213102780 504760988 776981883 863607929 761061416 258151140 70912002 356944034 399101532 763058582 303580601 895559439 365020013 462941038 423496414 18528922 418937522 681884904 449006782 764649591 654947623 351205478 306175310 594794232 426359540 164361492 682610141 716376289 540924219 280284928 653369780 71074688 240464516 938270703 825831445 845368776 395121974 742190125 540181209 824827720 120085727 874741153 101911956 995297399 11867574 490273693 581494265 563904208 286014995 429929225 268143192 614562218 609814224 913401336 303452864 510872264 333698162 543549171 163274898 982994375 188223322 34860129 99850963 603644895 25882126 230337271 294836288 548996276 575402610 685631732 680052841 598807080 614145924 905074931 88863372 942315353 699442294 558461385 847828097 125122344 455454441 269770506 502139751 684950191 197829015 920530252 506914456 534679296 358435867 149133023 951404825 883070525 907051202 392857214 213704645 108544833 936714093 58330806 344318850 716434719 794346012 99173643 301891697 698061500 607869675 620768700 464992194 758168103 780867936 928935647 135137322 953052001 672247231 923842910 736037191 297905447 466810174 114477680 807517147 516160363 32213722 565397808 999644156 615276746 385640460 451850 695134963 290517212 977098445 769385623 770584796 254974165 779292526 403801873 884627253 61132011 571892083 285105262 228800615 629511973 58751888 627142216 691172921 539653031 526146239 957477592 192538830 248232420 371548939 756200474 657114414 479474643 361736681 17105874 581746807 357853270 723619269 194070954 919994474 582091933 494346936 508739747 800891068 7808270 186664673 137346350 893912936 247570457 660541412 700588765 990477450 151354516 656249131 995017632 565141310 485100147 795913453 827342148 38981863 124754581 814182605 387160818 760818819 956797104 353333054 512080505 122326399 796392122 273373485 161305480 425031794 476072926 979567141 664375306 618426933 628752908 551104375 362564394 234075933 217382846 362067115 153937739 141988166 108552179 377790055 614888508 801130268 163804940 637725650 74818259 194849384 968627705 875717576 937317009 97026783 629193523 714924346 586920762 581146392 970334301 37112480 917474175 496807832 846027270 238453886 301904211 701444995 252150444 865503801 454423596 276878851 520993733 343962793 148932030 739459505 507989325 575604000 609559592 961586103 998495486 611442262 197093451 843311860 176225445 484581610 399486868 83468597 501493269 819531108 325509986 173231262 744470580 335832469 981598208 482298728 860960158 73655492 933721306 134024458 898976569 336117470 912994814 568086444 682965421 677306061 307532760 114251820 7918194 257378720 504324122 410249318 373744747 527280297 418220994 927736330 49822391 9138317 142319612 386326639 809858831 741598653 57150182 957397658 575590930 816580385 471241736 232446976 810369896 275870399 106099229 939332160 246137810 734614282 631954269 962097292 233140482 310896365 207308946 796130985 252772544 4947182 515632913 153884401 771914641 581723224 894216274 756823238 408686650 5556164 122920073 481159635 414018553 181891919 296458359 29183564 714634156 281270983 861987985 726302681 601643798 459143559 139552800 561034195 304847482 205962496 415958009 305143576 370417256 861875920 218595259 816465634 314045940 327300168 994316831 18767201 647008778 645883801 615943978 124488519 518247154 210856193 832597855 617058655 40771600 836865269 102971182 960684606 365156634 700544776 720089571 42739933 835145798 415649923 823745021 697641114 238243039 921711162 651855484 84830513 416746754 950253447 432320685 876172386 651297284 895211014 574444975 877487743 329050058 717360065 940252675 719377838 215658962 232266231 506455630 477693453 392406680 54406241 899197670 738490 956508851 584672997 273243528 451332010 987542808 238526606 532978434 694115412 651471859 349739924 654158394 707862254 368332792 54813610 879475462 441628021 816449668 163695669 371497114 470373708 899274743 242628910 584877394 666317393 200432940 336188565 869857025 773861403 570928349 637445611 491887216 64073501 292361179 211674168 403191863 94538717 678743141 595920345 727463752 35452783 791122706 494903238 935985940 484787429 28362946 733199371 704842605 889164051 666699587 915464303 783017237 251112992 332000946 165031398 983610804 920815192 180276998 822354409 918097238 700924332 794686520 19905201 148312655 182124948 537884149 116480772 677598138 376509525 943106244 343468127 730901900 677921698 570197029 339169139 606999771 556711653 204309707 342958630 935479236 150624838 227789807 177063381 932764128 539157424 902829588 554522532 743167587 350301468 485349238 594600607 945431960 549981552 774417220 503370616 824007174 954747145 150928703 705496820 239439096 622911646 951837747 821891133 248280026 890259852 69525275 934244257 503514277 342452997 150887932 779036360 666527418 340586774 967288344 411599181 162718515 42892875 320266730 594880513 843056483 744203440 643852983 947872956 589783555 787260512 606914880 746555941 695956419 568606886 29226857 430447862 838141341 502122932 956101803 267033403 534571281 392985436 330691284 731385676 919361951 604250169 593814456 272756755 722381493 532220765 558003813 495878254 840767256 745767313 417811974 145442241 516136488 391591205 309939454 273159168 824049453 407319278 230816357 263224658 148892299 257874792 84576549 104482223 63253049 282180059 936735494 901073983 128342443 154313674 318288511 670529564 999087087 377810717 974456209 157039550 322489473 462197819 154875094 13330383 536369008 240614069 947644926 842811578 152808660 499879429 48197631 366662425 83966580 77949117 634700327 142982730 502818645 482159293 244896741 127861257 161205049 911517239 808615812 419808343 92069080 345665720 187803524 289378374 756953764 830463168 883539742 572969847 296669922 374443592 550360033 493278330 623106850 414271690 33223162 259260647 442620479 710566291 711861875 983436524 388433564 925999939 64244715 812900893 841316191 324285647 31247296 393572266 520844356 503743678 156616839 239892387 70499098 615632783 553733911 383898462 979265580 521462252 472314561 241914773 658475624 534822262 517963997 335484300 963710881 527425276 654369979 692196458 309355347 796581257 146442901 444759644 829310872 42152252 655788649 221422858 529101168 49952042 181668332 812705222 266790498 169619245 261125066 462892082 586159138 59155437 856156830 405851121 59423637 993491874 892894027 595151408 393262454 83363763 209250980 965589922 874801992 805774058 167107495 241163148 434122954 870978261 326338575 571392621 160752233 266763934 298782139 154138589 520273061 643399161 839853219 989399713 806807323 824253064 427307299 702606095 645547536 520236254 776794725 540418621 719199921 518544714 842831555 158071316 567322975 669175378 766894287 847827235 221365809 944475297 893302372 857051940 983318071 686732753 871277749 114457439 146155435 319007090 485646790 401909310 874862796 629352850 688582224 882001872 935710943 451252512 614770163 326302220 976179303 42063753 992354084 721226367 8702041 844495468 287397923 551633322 446863765 691057710 966252850 620276610 840226573 658532879 249258712 982862498 877330944 438626752 209760536 525804313 918843615 756568920 679083273 539406669 726416952 597729536 812360529 589534731 579745505 94772072 936809795 452539283 443035173 482478011 230805311 638350505 638595918 609536420 214626901 607184834 577830091 716467490 814329818 506182053 243592746 937352806 370034570 565523907 815649469 19832993 116468380 921006232 764034193 74236510 971065638 37711039 56115684 409567063 187554135 805136106 167684423 968827706 9056413 531707445 387149057 854431560 537784433 255320121 320713657 718396426 763926186 323090858 327079742 208750999 303042507 579130707 848526493 613480035 142199690 264385069 697391494 884359405 503987120 299323625 804249591 886250168 478418010 971454557 273885375