10000 726
613446757 481401240 38638988 272815955 380877352 302724625 845789644 30816066 447283365 146866718 44160622 212291762 213742291 633542104 700529502 72233385 763444410 700548068 428549449 75063952 511219090 461544344 176420844 892987152 215159817 937116061 774297764 702852367 533516622 38149258 411732155 316428595 507854996 890097212 698941139 217079824 816924079 938525276 565943887 536350674 47707682 259663922 128734040 936344222 560805239 968833371 44048850 815135992 500085518 357405828 322702550 698728240 154274266 636601290 939897407 540722582 637861978 738652696 785047385 598317708 534980036 37100776 104533032 73171524 340416469 865075809 658571742 643094596 617739736 489211718 790678545 659097306 58025785 624259813 866141483 248443099 107175023 584599278 330245585 749400260 837537656 615057010 160540778 572075466 716461326 420988316 924501597 333240051 494294664 506025504 915520682 353997963 510431151 78746792 554301980 518502001 761506019 64525807 195988191 346027620 761528882 462377032 107879499 78026683 324693752 340406796 885215410 149877809 190381873 798168090 81561273 157524687 139196316 108901776 386286318 691170203 758969285 184034310 10731747 526117157 524131680 378601086 145965036 903247743 36980464 63358641 20043975 196441809 841905024 74896922 202778875 959418946 654448738 789818063 689291402 972007168 937254943 254316502 602056844 616717611 412762154 89117285 344228285 117969327 522177911 867460921 415865797 133841063 3211026 856787594 643929092 32049541 387795407 623012083 225070142 961995924 207382909 911109486 455065575 846999884 268529512 426367284 396097210 479718750 251541495 235178198 999560276 204030841 689619298 736759719 775849208 514915712 476148431 675446728 439683621 301657766 349820715 267284768 360715836 848828212 596646947 37210345 518489237 503659777 203163482 545535340 389021990 547521790 220011812 256203438 305661528 893585888 98177492 369273367 61521495 497770604 560755724 724178665 65634796 800804680 197848005 429527845 129425416 181808095 681577646 255317191 911888636 176046065 136120582 192366637 866796729 32314858 745726750 593818588 70257749 58133730 50841933 4561294 688075513 251505882 774010923 906339706 681766622 358595250 646847661 813413316 965941620 313608686 881761575 197178953 400312047 981054153 376093589 122674214 813016821 269447320 763215886 278386298 635840822 418448436 46574147 372561990 626743675 805011027 965821469 625808303 101063132 316779142 528764226 3860116 417418438 426673785 511354795 720577360 926207864 921353743 50666112 527272674 565517267 441618239 764826735 353466683 536055940 448616549 894142601 29594746 966808674 2890163 9288069 741601821 750933799 401319833 599924168 417664059 427319136 522430323 35561288 336115502 925665616 885244411 866522291 102660192 442424676 109787308 338803787 803646431 8566262 388461643 557782508 630429240 505837836 106981642 999188897 934903524 584875095 949960469 428605516 512808594 756512 117743919 988206399 786365459 795407130 691506875 28237010 357667016 803505251 847196601 114318809 414119341 548456663 912998699 319304735 167741979 861333704 962088358 46495680 423279393 735779775 156729059 204319054 232626361 96323940 698597489 393086795 749256298 376796371 82618753 670675051 642697640 44857244 596009879 454845016 49931811 271909110 184931816 777296184 362093138 96665473 149080614 509455329 601218423 639428939 2832025 755596255 409443870 491839335 931821686 404543378 495495108 719315946 242259238 26889749 768225410 284250939 276209855 311624159 604688823 866198268 234485191 682521773 46628610 390759323 114485587 10708888 736890930 750097594 115651072 137802645 672858180 504363330 273980209 341229507 771090290 755957258 736013612 134621197 306464219 351312441 137269983 40012757 731733436 6604281 467740235 58201202 925991182 819643597 207805747 974527447 28224327 401370555 441339895 835425769 223577849 997152954 970195070 955288605 671639191 984633297 250540685 697259419 154544365 343137073 327098750 858598589 953239293 855972756 18488591 625997604 142323074 250617462 526541873 581836747 351901242 371868038 63205844 704806424 752854593 522344993 840536490 819503493 239125758 110906014 811583635 112090817 580087711 395721823 948439404 41955835 812987520 43739287 992608267 862151868 884422233 133926974 151105030 774563359 328675904 589645733 41984926 635624400 449637965 652370036 780643430 906265306 901244688 927863286 411568041 246482645 275718579 890295842 397092576 931406147 467708466 292222300 704065360 498812531 947335209 155863990 743772759 344805864 864612933 497947744 439119434 318253203 121523715 845406195 186849590 633130892 682416699 41164900 230918 269712618 102765821 774707356 292928528 777574772 779532865 934239303 562453244 558660619 692423217 815596850 144726399 153553723 817160564 926131065 596956843 507260455 902621319 994606934 146086380 563430403 799027658 27461837 7843023 120361296 153515807 938115397 582474701 255562976 963923120 316643626 274144309 865674367 772167606 64600976 342036149 135690980 168737110 265109540 153034399 564988224 443680624 103712224 40136126 480324182 127180454 435562518 794220214 295433692 466770160 969257161 112852367 551624766 869196283 941811043 275691571 515386159 508777328 773818492 919585804 321118925 344299766 19035120 910357403 965948930 214682416 76765576 252796594 367603005 346849511 959462793 845934475 925089141 454421834 795361480 784325575 615423182 874568774 913290358 183228412 90898275 807158850 744294617 498908832 861177948 162741804 637722621 796630066 568131973 886941371 270737108 718879856 571916633 600591472 291985498 677046465 457623824 853750751 295480969 64157452 173663688 842517057 366530427 854904928 617833887 602324738 67916224 595693191 511170231 382293402 271428067 270824696 831419188 373483552 230049510 346953599 528092899 752092713 738826624 301402403 445443140 395191356 347225208 499480935 366962135 590162645 670616149 748251824 594621400 539853657 758023370 818441842 28721593 490167379 658422086 19083531 422041398 161336608 748220288 908711403 212891158 752208506 844212840 399994360 775901221 563615799 879061402 498791103 230227347 832995556 416399420 353757992 117831416 741301904 535301568 940830249 348620897 791249590 522144347 549039047 634465140 890258276 498742776 696213859 428200384 129813854 556443654 939717925 189687775 558004602 605541821 716539206 227110859 715710569 834293465 677730847 927707842 251544747 897334872 647047807 559503432 208556711 828923976 127260738 644817777 978553233 26611705 606986797 872197584 403944640 17724743 128768796 828398793 502048639 806783139 598973502 41014656 377918737 135046968 18038007 30953785 335191187 229770890 836065080 593978346 83060098 712542242 604951159 149684027 185222856 762365970 939204916 718986955 471729582 741645648 145132261 56294150 120108701 278053338 562143307 506135974 478184210 293171071 789893653 335947684 550310036 965563722 356279732 185860265 897772705 235829517 158871985 831890218 161918062 982092452 772840338 428194666 149006180 796490833 401108100 815607762 934536308 823260464 427678548 724003240 969931207 698410095 848633878 726413513 611033704 234690312 603866186 260160629 549038406 760845309 889793942 454310852 137454179 886522136 167295081 600308301 265260104 623912901 836842921 155048215 120379668 852942754 902210889 620127557 991342218 683799709 587942832 998003669 479465825 206619288 294782748 381113676 338114738 909395610 893836510 576404334 178544992 897018836 269815924 15201210 781499471 178201263 536870237 462653908 774747222 287245904 854882533 27764698 623606313 934532649 69238504 193450550 732781554 150595642 120933296 670502134 61548184 823345073 212733157 304151967 23858621 727177822 382514317 281373667 920506698 177413262 278411773 341521381 934048186 27355807 344663200 246685955 527889939 766828314 352080353 95534301 649025808 583572043 405102279 758262123 667490410 837583959 186411807 130796697 735553053 10814166 865045014 585604193 208890113 807917196 539221684 478117212 39326450 854825476 96545592 25071265 908717719 984877776 837375113 282389213 496921755 354141254 287026604 1006121 233520974 610018467 940077941 306118502 560069871 208880711 620145673 400380675 456727301 597647539 706020581 600297759 430947749 658984643 133921835 100214241 897045906 145647081 746724515 566425934 53119214 80664784 907058910 408911136 370223613 772339216 519206072 725233438 545423538 248606231 665736335 532951889 236601247 595700741 869640115 664296518 837881410 227659060 472948694 877656420 624487188 997771866 616950719 55783976 681073685 383134008 758915361 814234529 394702386 46738866 321649910 240527470 568311180 92551309 685987272 410738967 485712072 102496666 676923010 982702024 855380989 117506931 116021764 625074769 838689437 215671347 365033218 445986279 650023172 889698554 887158887 170675307 242048899 708527448 655667055 89606615 413251110 711647776 863730949 714270701 580313753 209975114 832245670 7350581 586690176 655646989 642670573 221340252 459182810 135944739 790241107 355450300 529203469 157939970 477388504 416033633 236793451 102014827 46239632 558002282 191199006 468178961 827704990 88896001 45416794 251257324 866494719 293293906 364837727 799610105 316118054 301026246 709068565 337329159 652146921 832942498 837131025 72756346 925902999 841552170 782876413 942234167 652462907 793000277 514727657 981146698 259311310 626226204 583365477 82187008 82906561 254412137 162573203 932077474 163240874 905130395 29965108 492035230 783149190 389032881 608428419 787924699 119262823 811205934 193539961 465120520 308587139 804598990 986413947 3666488 943022934 220846719 979500926 621332828 818563815 292943041 758862500 51974678 343776136 579904020 192892595 867960714 990039698 610255062 369322707 713604961 371883594 612947982 563945520 804184726 781877334 942615612 401906061 874627313 2527868 82534925 140739672 790344122 361918668 346172722 209767515 190864728 639969030 771644014 211054646 68757924 28575591 69474238 424434618 882101807 640460865 187015274 333400680 913271520 406868114 451456451 810731686 702827929 295134388 703815699 292469855 728243428 332262637 940659371 364948832 98477737 701646168 739034751 472160376 319584727 359665840 858126718 649660455 675410202 6716950 634716532 796248389 516559090 650173250 508670646 894705504 181549585 448660692 675634711 31519188 93531918 197644481 802919680 638696188 700704520 856873431 669280033 627086157 716296251 260821190 437964575 943580799 691475534 600444110 304519967 807074713 556055905 480437330 248490623 321503665 862843366 715758254 521417801 975707055 476030598 21477770 84567823 873174443 535868113 840286505 763180869 810046381 980147461 808538966 286560529 425434726 53937006 671784024 883575242 956426625 913289149 475438249 583118836 472646822 789533664 373886922 380267658 839311502 306762475 639281773 456943686 655624543 263050157 152622638 450245169 176756162 112724275 12633727 995032363 127280937 732331495 910122936 494738506 531355395 478467015 870220527 469435197 134575465 7915231 655073375 127115461 808918955 790880359 56677914 588859005 4352496 42703913 444223475 993031098 871436500 435391427 912337249 416070315 904358586 259133835 176805709 329059978 768820487 497965100 582964271 304338670 587356377 677183525 942911211 205898998 913408269 598376374 531859781 620062001 946900506 988830339 990118156 428060137 155955986 84842782 382327269 469873125 969287323 778366288 87484252 258122358 668987524 687556171 782025536 744538028 705760896 304675424 881057880 247803215 949463769 924225188 847364565 811190113 225454531 839457572 256458262 128903239 806631207 390660677 495879053 351974306 253373388 182868456 588154079 879055640 919699467 481919475 123702298 273763012 774021030 798446974 210800398 40449617 528591787 16158419 725577702 524512246 280401971 17233254 988624270 491492042 701913253 218774868 36533126 439641333 57929937 26966697 579923404 424486872 163804369 96780842 940358680 360209826 32390950 208916529 748813744 470348880 488085721 751180592 700345035 559271599 585025381 305359280 213343070 742182476 780816040 503198269 612444066 517901364 849309647 150675303 324437614 296244126 691118707 551438363 513729429 807255429 25995420 475887201 867347724 866973478 707260232 35157164 118198215 451887447 444478404 475457617 633545126 17927697 528755698 156723631 897907736 260940778 987365470 413025355 616435365 612588062 600387000 403540490 626212906 229418907 743404243 331873157 945477140 274749064 426486272 804722537 516109212 708824476 298262547 246998472 162364846 19277694 275531383 363202413 901276286 96722097 926299573 990543008 732120248 996931438 284588112 102527610 935466636 524653331 389840110 246711472 687938585 219644628 580452380 973657747 515857551 598789400 843770817 201054363 320582400 23654954 236566355 425121381 367588225 806028943 289662805 39319963 936454903 673646539 564117582 895520794 437496502 147943062 761686493 90132999 951744148 560857953 606963011 622625635 196280282 597110362 340660808 93306995 289770680 335249319 159797245 557644904 830578550 103044468 79017865 635048211 108763084 172202324 562582404 322415876 962887930 57108082 375149144 314184966 381791063 788094699 121589415 967217061 707177773 718234306 516804051 565994576 690368213 195744984 940511566 403055936 86585456 525779938 775799196 835108320 346373806 770567772 284226512 862408792 583001307 831928509 509688690 876976974 304590474 697430962 384705538 610856265 595778405 822842631 895818883 976684801 619678643 454744232 737018625 404923670 721506572 637760415 513978013 778152253 596172934 619527824 811141379 425125242 229018710 600966112 894844047 642992860 781157078 831657680 594257397 822125375 178344050 643294881 173279779 57326501 795327695 473722686 52317257 302345798 19221175 556855803 146629886 570922163 931736264 50281534 760880257 701258834 488134718 653845783 882747922 366614234 126538668 734613352 199976670 194918142 765122905 745832044 100037565 280270419 250826152 82470736 281053075 422807112 994078607 583208117 599305221 177695775 944190859 295260743 497957065 278410156 896922448 842229544 733829923 208478349 503756656 570191825 568592785 503842728 28037286 885875100 604615562 261322028 972632614 679467008 859527183 340337253 354652899 895155372 450086707 619309534 992612518 18198126 679823508 37154185 678742122 548123033 295112960 342284776 633890299 259539646 428965715 464193637 616539614 47093771 177945369 173858157 487288544 621791760 440788789 425544560 270375520 243014522 421438486 801939360 916751678 925094544 975606274 370986981 984001068 503325337 542178155 494716078 513442908 899957251 408270964 746145556 258654794 830681165 561231114 312741440 162023396 769728099 917189346 749541658 783221155 437588627 334781433 620869575 122289829 976629990 207855154 552466147 158129334 403612416 371374592 754884998 610368960 647100778 490565040 507090095 512875808 314049603 877710888 790299112 213518738 887196599 705886174 74230701 881888435 663599997 279008389 994511734 30227061 307518718 397747591 42365687 774206434 371509616 749146240 892521077 604153373 830960948 558496947 189033099 35722032 468466121 173964907 711882185 700741432 61273335 109532221 139655780 732300825 521340599 327288321 433863681 782200794 912334467 95782573 885705292 167727160 864686717 66472637 706699681 490405430 486400825 750970532 131113057 890389625 407950543 222815800 337439027 551893718 164971410 430441545 406688067 215406549 66043565 754262374 827419441 455269855 166703302 976502899 882401130 610784820 359733964 580149455 10150398 339809025 947648126 862513296 722575542 553194154 990775952 501362883 761140921 96577328 194075926 795801060 807857880 22952145 584238464 729806485 357046696 816752779 75680199 406095951 489464925 214062179 910727351 560582933 871061569 250435081 352806883 825684466 79605143 753609107 785329043 593495076 77335282 47685341 171093381 712342490 991108379 371626499 468827117 951214870 989758852 43892907 45852815 515137125 751888307 966204161 576209541 91836058 137354459 145980114 157554320 106914560 863603290 903321881 996014365 356127230 256181654 689315870 676515523 295476900 887330015 857190391 264808524 628606884 63851000 526444354 148846448 397999062 442692281 287251695 262259658 442000476 448156272 786937594 327603856 850558414 484049860 733933552 430012701 152983175 779804795 27937986 250743863 832206239 370838271 302847619 387429267 279779935 440752255 877929009 523196054 457876881 939842277 834471510 7181158 963930111 686531096 482436541 731873298 821821902 134241212 75438416 680612718 350918278 563156481 808863649 401667620 476428099 373194139 175722864 700348801 896348663 714861203 508394601 702568816 939036839 981411606 897281669 663123402 902116532 85206136 875853656 358254631 889334160 459898909 431538233 784865201 198395555 399438482 722567955 848959002 633402010 194799371 848602633 968711854 968498694 865623764 702384359 573543032 962722044 952705909 727572753 874266967 524757446 87025740 485772435 629855661 644397381 31334820 503936629 416424759 635365983 540959040 709095091 53238920 707891501 245758311 104399274 445949403 74908883 351781783 562369874 192700655 664999801 840504251 48836636 667841616 972546473 174699759 255717698 506344355 33001324 121609113 299752383 529918338 404617035 358832183 917798756 785973426 658475993 926209718 991295565 96090519 403500378 364921602 363912992 986168076 429807159 17434988 834670577 276818642 414508781 492770874 187358548 298139002 94459463 668263517 773142213 877411413 901690354 276820568 228630194 438137135 703238858 503703963 458920135 878252450 784303816 604452929 377587058 236268948 767755180 105192742 628398446 694896077 86900580 705009860 857964253 999303687 530823736 656677333 31204534 904040455 38710963 951956559 904437777 760709543 813404383 420600791 449059346 813369019 900399476 587542217 409611941 5464511 568648237 202093680 914361733 355384165 477131008 123866832 188927048 110566441 692410240 923438686 488296867 728129095 71233709 79976162 552975429 190657764 332237824 420677105 750867965 444273069 397109110 890201247 670894858 782599207 875339069 725059608 338626671 307498427 67786252 365127377 382608493 751013574 454468238 763470382 406392436 182659343 494725478 547433245 488804560 990989463 723241773 178374423 576340643 597512893 452410506 476903264 421596947 831789747 448758727 248115090 966420434 315813342 500868693 296660422 922069380 936795998 701274916 974217713 192502739 420272977 854417924 582610930 355980493 473282268 374850054 124378989 438122790 747374891 696333951 602532007 129067570 510960740 999135298 716981550 573108525 112574185 509025405 719209766 545163254 894851808 520005424 37610743 471301313 396162619 80448590 29230015 843315307 111611927 282560374 89161930 31023925 153527404 455021308 956736125 510486920 26709539 754578430 823595380 980360806 792706711 840891312 705555855 791522148 132581361 845747958 834405761 133562077 604072573 451810840 342738616 484295230 755791080 368386915 187684772 231131221 327244129 489610144 422712703 795147667 788283443 45499212 358702539 633480532 705864371 757543242 827005949 256856991 813114053 189208682 699231072 250323561 854860060 737271930 983267316 322370473 248189394 559259572 397617202 748643068 62098914 136226322 338100204 290904337 936979923 256306835 169170685 373060248 828426036 473791846 736845941 145983512 756745663 862873641 308002184 729955158 345966084 595815598 566471230 50656998 517348370 385301325 741133215 50769262 172851642 624076651 976826571 706349382 629106735 56631220 108008961 524495769 397005343 317928448 926942916 291878672 830663827 724699931 103228056 705469069 828558780 871669961 726623552 787000424 602200752 688145948 474555202 291183081 542180198 312691943 841033673 550521630 659591760 526127337 632000137 505819507 268454378 688285681 438946651 395426910 200841396 216753162 434554289 19844799 71960681 685077946 769070420 537535699 111378103 252141638 378411918 251495569 582166485 921202018 287067460 17773438 813198054 176921202 3314 335097688 296378423 99014240 447523546 737097098 572145121 616020488 688813475 46331113 169611525 331614725 164783675 995451491 451089085 562461071 935174425 251388665 803263989 907506620 597300528 626052353 629643195 87348795 108725298 898553193 990628223 673562190 656679440 8232153 756958641 347444931 977363333 228846609 394234441 864726590 505317603 984630127 588843271 590607638 4164418 313398541 535672891 300589553 667737194 519796187 460436004 403056166 235694803 18782800 470785679 919052003 47538082 900745188 469165487 123616301 155986495 339424558 375687772 83088261 407681546 808521499 495273276 553247306 383520904 423778917 615424498 289225751 531599072 354383984 728564216 44070257 446197696 494449622 129453881 323654116 982964302 252917758 618330887 193661394 199177961 181423017 176453066 882157348 763313447 566584898 127986311 330821672 348139519 833251934 974022660 93838620 349630857 409532940 380171012 836830291 402927775 600425400 791245546 280281530 231970505 278265062 887456729 672529613 668052213 19719288 158619534 868016429 132345055 127539693 374441413 104412442 885552268 648974891 337311013 768399217 471060990 785302701 558235599 780024736 578024219 890673744 682965975 38246197 963290828 659068392 111710382 881994927 251350010 580255738 721435108 22904420 403719257 206471345 198297207 304629750 764907545 885814574 739482595 136509401 939204885 47783326 863552074 704367504 927309545 647637549 122150239 445923409 890919227 309175109 341175519 475420660 636908951 615132511 418788063 684937501 950561481 50681847 722697502 968701069 895582324 951191183 209346872 148894218 285228335 551560382 553260879 274920683 737070506 469202667 896254524 949596677 150634672 374756323 745706752 453621209 844661177 883876972 330463706 214262617 441178421 874923832 175493451 44577737 651846045 315089672 704913135 428941975 675103778 873917495 963946719 127634311 308602134 115830567 56230629 354691480 489961007 208680155 183586560 280514085 159251377 223334164 383592929 223250021 298659160 345292336 10203304 87955903 676415342 61622023 403246720 547716039 503584177 367180689 58817084 506224876 137593938 844084461 345704744 300812251 554981321 913158358 909572335 95896479 605905231 930944040 989049209 959727120 965576285 131966674 546044632 484874432 281281073 864295160 385235676 343179379 464730700 501832359 965950973 857442933 38739460 464811294 806769900 731939064 510303394 907017627 701411145 511026580 289901894 535872929 608086118 957577243 295458516 90227783 736584121 562114436 84929272 844964069 739751252 621083513 281317145 753178120 981705564 73307074 541302962 282603003 34346183 480283807 583838116 880798880 1912501 307501443 544017485 740017216 193424081 742880000 864354895 327821224 109267944 276595099 526249349 257909169 971905315 901162804 277687186 851489411 1729563 883070967 525009256 456497879 70372315 98537215 944846747 767859274 344550148 919892116 633528134 769606042 797158971 683108151 119272566 319891060 385032115 714893058 895731665 18360845 842943341 380826135 423524385 533517730 875481590 148068244 86168553 980524504 385760783 820069256 755062977 175823034 240892647 987089630 765954723 906593154 7142205 911351996 507155595 253723346 205013799 204952579 123719478 93354716 118798312 362508553 388392377 73879723 870579961 247516006 596502336 319126084 166604210 382006372 957580850 833311769 801340082 329389440 513605072 776875344 264573573 793580272 810894866 196751319 547054597 818569026 610585131 609546378 710189682 499866332 933192570 647925428 653152353 272081770 783227666 789901254 533687677 430234601 37211741 32295082 76365831 801886422 425185225 271246765 103194581 92243244 922171012 610222237 626633204 709168889 856364155 183539338 388366580 244911022 136383111 104759063 840520538 456978119 521089960 549601394 703878821 412073643 24050293 740189300 957417905 247509811 743946380 682113982 224404545 419781207 50052124 767275396 150711621 363859064 324091541 809225402 958000651 369242206 342139139 107100011 175714518 491662561 747861391 728820232 714759580 705874536 401384524 909287725 557680466 458694183 539732402 809312549 276823377 953045696 567402346 843650440 93049743 611931739 769550599 147644995 672739196 976078692 817699809 768288224 129976172 636237264 166512572 158336586 938575832 274543083 513996273 642331973 235293055 23024406 303104876 196094345 389243654 284744228 431609481 816556058 683796169 316986789 616078605 641127499 7811361 994128642 114214083 875001876 645607372 7068802 150533957 927996719 847048864 776391351 680254273 510095385 637467492 680655061 421646558 939816569 366183420 325470372 962192877 142149668 490116020 673590709 421429906 820719197 842383213 685890679 390065712 413259086 80534011 660160417 20847243 102918175 231314921 530324840 407120947 71157766 161042232 122323256 449195392 828695078 724054504 187034065 146306407 463859418 634687871 55929336 103169291 714324610 458967803 586480997 370392948 478334035 963379851 756801317 636603527 564190403 366201975 780338646 693220204 891946775 356488614 255959611 148175503 825839464 361558441 352037172 401828180 629137350 946203488 830110943 70188712 505646445 801187312 146893283 379051219 335779351 892193371 648876412 768816707 461724225 237438258 752936942 523843889 728532321 673937311 892949556 340283632 14496590 954218308 630442773 210015775 954765479 269566002 49151345 209605482 736851275 334195452 816408863 868623690 877201732 798192093 687024109 745849547 916646553 198626782 11306473 564364556 329052984 943936837 282809586 261509667 715565306 298695822 236825389 378787893 635740859 800128712 89966206 940856970 736334019 777022211 231553859 692850744 85159721 440412794 190669923 79767853 416129578 809854334 392675890 107120347 99828484 182792022 6460362 965089667 540359352 88487650 257577838 340793825 188749722 791879843 925294044 457116318 234394796 331572470 467818601 186298640 244266292 738627961 96295746 300881796 644385243 940950153 758270283 325022226 951832404 574456265 585790656 473210264 103544415 774707946 885856164 260367362 981131905 786567705 424663705 131292196 685023080 792628992 799344324 272752865 984727780 81045848 695133660 523134482 804545220 984234729 260508840 236094285 993859213 813749675 372046062 602421339 145950076 81038047 753022378 882163015 114497576 313519024 133652712 145978158 822197272 100295161 76570531 680086714 265432910 42972315 294837843 220347646 322389058 228434288 290974656 879592616 307611398 345418909 404746113 862585309 156390186 86039232 800695622 255481918 810910183 487513745 11665726 194393266 926291938 711523455 647373792 388031612 382029286 739899146 189228965 612420231 314719975 12269349 296346685 713472676 616602003 214243071 52158788 455759975 698925661 63566135 13109977 285852060 651041602 832190984 531458072 362634293 154328127 457487288 211050788 246799987 554141510 929824596 222429148 735573769 51493302 479530180 299728653 746696905 50637895 300385146 634711675 294453803 801237844 470323124 43420900 244022653 54030864 69477835 478220393 137932886 822323013 893913993 254851025 674390130 168039763 406699962 791074193 688657666 793270621 499223304 260558607 417924011 893854270 893440260 463489826 652430669 812413485 394937757 309213363 18003767 688316269 785235029 682838318 229814493 902341502 158559155 2043476 818795371 334646734 77182344 912112542 792931210 76094947 626842485 325495345 559409993 258806172 467690742 863101149 520466371 9505267 842379783 968187574 753394798 972467581 53231513 402928554 981346821 71648575 420744380 857823971 19588938 977961381 922548835 334030715 211554708 31943610 296590883 58451151 816030622 89915557 792357123 140434194 327729989 914933738 671469349 809792720 450277865 405995924 919365152 34838232 577136956 110042616 469674509 282386026 100757239 233549425 722701940 251352949 626264258 648993759 250635795 491294679 555580 404746484 2072787 266325222 95185299 43105266 319995251 206948600 904460371 575226935 521853938 518015617 685318059 491422446 992208671 871613452 756211192 743731018 657504530 95770330 864304937 961699753 801928250 1428059 115968697 444760086 30764012 706302604 730125987 12626985 564181728 137939208 633212693 962781016 786821520 333126933 729633439 23328777 443217673 431961417 471514177 343559951 226344661 993403763 934675907 4010474 609976974 616915353 150569000 595962736 36914348 991829688 814911656 141233169 23456060 34694921 914988375 918489572 966992278 310062225 407928038 378152950 717647089 676866116 451438 467254801 198138779 377029979 531245580 966892982 156459339 258583588 566716403 569856380 773084476 949269229 369120874 813597350 740601579 115260699 200484630 271372841 443464892 545843215 656453680 801466455 66569573 552486386 271706277 386032715 722999590 384121002 473602977 139976300 721159428 910789124 931688066 985624717 916214431 205433986 789721079 656413206 716893292 550108370 618639860 353039583 390763619 247704857 528561709 343097771 372283825 322386150 975161839 970369184 775691598 411206810 138654454 122789752 735073010 83073197 181294491 751280890 186275285 848538776 452283369 603411578 427239409 485944892 800060543 361525990 33683982 504302064 974728274 380249226 84865551 710097815 986975417 440132949 566008863 22941745 757055383 80742500 618487116 912898413 469441790 890567728 558241856 363052853 341204133 501534899 157948280 654931240 91621607 886525965 43259113 921105156 7000283 926616767 552131095 700343903 589182637 789522626 873720790 312269084 523283431 427360878 872931115 773356044 915143389 599107246 296714584 952668929 852143335 339156126 827446385 269359588 956994972 979573399 900098423 755544708 799249612 55941077 408976272 226573814 153114508 577864268 844392554 854626509 894860920 256238205 833072595 186970720 418013321 954032958 398502491 824659253 699499168 526325128 676038283 782722221 650861732 187122168 266763262 333737507 655723086 591970839 284555768 106767556 679200508 189392940 340754558 571338086 814514097 394655521 517670838 448203080 292608426 336192188 395749596 147559642 653571716 452059002 670398854 942015267 675209658 960050794 160918811 359267971 721467668 896699404 73025476 836706827 424506997 549659224 406328240 541902979 280471698 433164931 939382882 172178535 495341529 819179006 187262345 644892704 220875473 750442490 653177568 613483189 314734368 872638067 512067970 368375782 124176104 667712739 181341145 905963148 364579163 932128119 905933552 463299413 309828362 747723442 98198883 442379369 10402286 444077110 399787234 151411754 945365135 568224906 526435643 964553282 81900055 912287354 502003087 136291960 828472503 181949140 730915152 548877262 311225606 823484445 866797969 517553617 847420232 943812471 415356834 582644818 294261319 951944408 980621675 584998796 99936927 713428918 565262147 792028816 531196157 429349489 316376042 927157780 467358714 851856156 333212602 608716973 549034656 738849860 384322646 421223666 840940625 871835812 543646792 385761044 587127275 228552267 866025785 373510585 499142503 108316417 601349169 497521209 773864085 328901524 269737609 873121924 144480862 541783169 789333646 49597433 485564786 954554640 258642296 729475472 326807829 56526916 186276804 450437268 80579662 396190225 688632611 553421245 18198385 952158926 147707315 528218576 859147603 962345413 303346298 270489568 120277156 509571174 13782259 52707441 822671325 574924481 295063214 856882618 296200739 340428750 667074849 706179178 154243794 397505628 445864127 482907302 605642658 35283303 618880769 372375815 27711700 845748302 414086548 795933215 632198127 545180170 999172156 523924268 216271533 239496321 502795563 127488520 16928030 682973038 661839518 647036946 338777898 364140548 262710701 648842538 28651860 66754052 382675056 638988541 34244099 286385259 763993318 863339218 830851033 296355668 477389484 218241535 490824475 95765127 464426969 309253671 259800350 979498665 692321141 133054820 885040153 850277720 49514110 70245690 51712994 135038424 720966081 170293953 553268708 516863085 357023306 403227254 655906973 519060272 577291398 390861458 912542442 487672224 242764611 717251841 586323117 866254621 602769664 397809521 425847660 292762404 533836690 336105517 662771683 866688618 213037374 921658446 423338647 21785465 129538673 454454325 818082532 231755663 297504137 487534751 200575512 589480059 851250296 683396199 51744653 417485310 239777560 227812424 904382873 737063404 993261803 456946638 20889591 506302937 421014001 413662885 480769966 411800680 631766464 642882878 320696244 475550408 712885615 76365967 881316407 533902349 184787624 842912146 514324804 991192980 264413813 611038277 387797402 45567210 338428258 930520196 442229010 781668633 106976293 689970965 420621560 716482544 776648143 825650604 751429273 441525000 729247848 968058800 561662257 918220671 804141155 88534869 529864467 918228535 400962051 399356808 726170188 779286728 764254683 432527714 949513638 215290942 146898397 8560572 108081026 230073660 702699476 581949825 592086013 165527944 457286478 24688402 557473831 15320287 515814830 864288774 950288908 381679096 388836107 194049348 444916541 466732647 776135019 841068901 678844558 641152579 767393710 354053744 827941526 369993891 937921540 288325754 24330804 674477317 763755128 557006726 307193784 185274767 223260302 140945262 101070968 210253316 42373127 23981008 286101630 160098102 967475741 80327214 291658705 562507317 213658381 58964029 667388289 711395544 163602300 618056575 127428322 827330451 841421635 541506419 754784687 691331289 623751252 206084945 777974174 447405547 365055847 493082862 521446461 907894903 613654072 446830259 790535469 70705389 447519722 271174690 329580812 591193411 753802822 262739590 905345785 571281051 672822897 372431886 612133867 931471429 291097540 416518036 392189112 463169101 336076399 544558643 654295175 882181648 655968469 967458433 310031043 244741594 554158030 960796955 57830330 566027542 816288463 582336504 459868738 184653609 627789210 96993841 741886241 714473006 800576124 254584911 558275061 556047349 140851409 817016757 522441328 362817546 585226893 656625940 837346975 897605605 541814464 70075066 152182865 402928215 767888561 687659103 359381789 952259833 932030035 30429950 397161975 302235474 300445744 777160119 570537536 580148846 569363887 1960306 805405709 473634161 366969354 168747152 181189369 939983412 442771967 566288570 255485354 197274152 718312568 925558382 382201098 790392244 572639293 982964482 560232163 332217260 890058870 933035262 195346637 809220016 991723722 936926407 699132606 876493658 423571270 204685127 360411278 295015344 659771617 367389230 528823764 318234741 393183148 970483114 120421410 400744162 467969468 981867076 315496326 311390718 963595510 681097659 30614098 16883824 13636634 878043983 934222963 92558250 448685741 187987986 342588842 478388964 705384589 467662977 799074067 614321591 121790665 468241721 835554599 883006034 510280573 638198065 979534779 709417651 59991605 440225517 109592185 365191113 474531923 698672727 446066868 482820722 658470375 155962932 471309794 271866901 672035536 989332924 720614347 481875318 929425956 209605744 29268146 618523577 281827859 600393541 524337478 651535486 184416776 602355372 68999879 621011210 177290504 337689145 789113189 494823623 952883886 579798994 507731641 550619856 247084156 664598630 507552957 785850158 3772690 997957758 547214547 890393787 432867688 611053414 819251669 174056848 289475230 216650518 246525316 97548832 461042841 876696070 795502724 460713423 668621381 324142916 155944231 888996042 626718153 318324092 414610231 479311233 955326843 168775682 395180935 218428557 884986807 917145832 675854566 843047343 186800190 382920274 754574922 990237746 430229198 274953748 982803509 539263307 775085052 590537197 174433789 877805672 673819432 838520608 392082030 373686176 786667627 618356217 444684790 746743167 963953690 722368094 284537228 610835631 496070782 96159120 624027522 710931066 328459721 159129566 852880555 284615238 995541037 125748352 66850930 101372220 440164277 639981702 598070628 375640301 948139248 801844264 318580189 163354662 510440786 865358255 978582857 812222241 791648874 815565206 359762862 590795161 150820763 918077618 119743538 785990512 834054696 342934099 74921220 406567269 932313579 181550568 582673942 684595134 371225866 190435681 8153237 116387084 724187238 331919920 100182719 400479621 419070308 506875223 403843864 690801153 576872728 717972109 946072646 832730564 971493393 890111342 740685614 493721306 844884149 682628165 730576149 761515212 819882538 509630964 281881316 538124941 384466481 327316181 767725337 172766580 250691304 472107806 920302701 550506239 549830233 814841206 706697047 502595618 119828397 669118869 772753572 644721925 517039342 187897464 282846847 404251768 966321565 357660651 304864489 136918199 884629154 750812211 779833425 767232114 131323903 239113997 406808452 682916889 614494177 197375987 109151799 912515354 777014066 616598148 621183733 842542984 466669922 431628233 266727594 611800906 648073809 225526075 247776469 241246006 111317841 903331912 593779601 606953304 332724270 427570407 238179227 639417446 747098783 208462052 606526667 410068547 352476281 945555555 350379192 197529982 275997867 27260202 547783421 194723132 86201516 55747667 582722389 872250870 16043592 470381790 642913808 189587826 831938392 532523393 313205226 324148991 754058016 465028761 247046152 473053565 777434060 422894838 93108572 258729274 104956963 596080607 992204079 425301622 299461355 11661911 321671824 653063670 884169035 620378090 30614900 721621107 85606082 240104952 849212943 103830387 709407 626540253 296213460 415522813 681231106 397074671 487188458 487293213 898964466 610925875 867888560 3291583 272104318 934922833 929573111 97138517 107655045 824315848 142849999 899500751 453993928 637837287 667573781 782571754 488761065 54619193 46102687 963214614 676014541 469400099 381740612 599613488 928336090 702654110 930697471 264283824 441027352 420572240 638204118 817522283 229825272 717050237 663952054 945236064 955747765 176967394 888882126 652612590 677933889 249732346 156120544 334040177 46793252 354664067 632607447 684821413 779232141 162912825 531765861 542699006 930893232 716810985 533198538 419149392 307169433 211906723 434862746 757677561 981827254 455281466 187803176 81466780 663228402 364563205 674155482 848928156 364408568 273233402 723934858 640199357 573590742 767402520 610483204 818441693 413039399 401929806 684652839 212190 624036717 54416728 216925753 816342587 401714203 920875074 929852768 769739290 464487990 80687844 645328532 311772419 964127337 767045653 63217436 796887745 806596251 507019206 823236892 338780575 58907730 749430106 414880115 469483683 49955975 374432503 495189714 576118191 755142638 57915270 362831943 151583540 174244683 100264541 858850367 558288454 412248892 363512757 206813483 594835088 538536249 40010798 622694218 680641898 219170668 613775466 932890544 85982877 460186233 262963149 406995170 610541072 907588755 127798568 302912913 42951082 242091645 432593328 298700222 638250241 927683420 84118044 901346349 664173303 776883801 847592314 110732253 650127085 808527212 639775889 512166313 844778167 308732148 16343479 876259299 864272906 151518308 239446058 263793322 706591568 109694220 726314438 714659290 963128879 79061771 669760783 453321971 411700844 29738586 707013625 789673395 42832355 429845857 211027588 108901612 837503359 342869429 923261151 404125576 361558921 961947464 134384503 297396966 827920665 563965254 491814069 406189430 505853627 862244535 719324999 968307368 533895432 893113612 264014749 116774721 970860208 460690222 916610491 503028514 20021499 474151047 266806530 699422424 756704343 354313990 135830944 900535411 424376150 53953213 129837074 484759005 300773659 5735305 628601321 869255568 185539799 370923671 419254051 878714841 316192977 290734344 157391730 930674329 695102007 825498359 187662037 179726108 47900017 983085466 48803446 606275066 676110992 650338940 83292421 548091177 502169983 565064870 642169101 227031209 799380010 226919964 675427847 129421963 152391793 560450992 616156954 718835776 728203337 687771384 157180098 655614929 103877412 504839575 175193988 344241058 972380873 170371377 159019478 982746177 641698248 492759053 374524091 40395470 694625295 797355060 906979781 956318448 304787569 845508351 941550141 371624133 363872441 153818136 875868983 98830657 797319082 609394849 240994643 681660520 4456897 889754403 102172083 130030472 586474999 686946631 627045041 939094468 973452622 243175881 460274071 766079452 98711712 75621251 180930306 926930725 439005574 525912679 474698732 506006795 742340293 228048106 44991551 605690388 1785409 528538416 744895381 647530240 990245999 779968199 960759640 136137472 395034338 546882518 521682141 477390636 518109624 674257236 78620778 665877156 406587658 196166972 775709968 408042882 28120262 948964818 244070548 32798702 681040952 757133668 829139755 372361057 273150829 22027458 179220739 9329151 995785482 13390348 834913091 174507824 404542843 199219137 94239455 963893223 573404582 214945467 275359216 350741937 652146792 113961733 481842101 705311371 836592155 623594001 611990477 782679091 103888083 958815267 231506305 636427905 498748512 204001960 935612418 473235528 341496826 52480748 391354448 40746300 226176879 247230535 346224883 867785776 205038913 187345956 778391033 893613036 153872290 536288676 632399848 389536664 595594057 140650686 324638761 757444865 726228858 392699521 275088684 545365677 636415162 212935847 897696560 547284504 717222262 374974578 245500404 667471867 772117932 462026240 202443689 546888286 69568087 498781839 445638545 826864272 682943821 305555577 770863392 873144771 270068519 630542246 351329216 944696637 59833533 922850031 981288501 59630687 461534252 35356680 432099203 307774618 959474508 142208895 901446425 264233266 715536103 807357527 784640006 794810022 253022003 618657287 109960984 479844353 814457599 34047721 637857561 75410697 591243039 469459268 187279176 189028955 561752271 569930866 120574917 991140565 966801708 453854749 309922352 17279017 177449969 436233828 494260275 421861124 460586813 201610316 821530416 915568178 645819249 563615611 632471020 193870812 468289815 771836506 648967324 254316922 86054832 868921483 6303080 97260835 273600266 300935285 162790854 786107207 284714157 249160711 131263732 528915199 6860387 262840744 846528398 889846453 740304501 492626076 119333497 559606946 620796342 659707616 680717117 438487336 160826770 792691919 679350157 276718171 641950379 844726550 957636812 904911894 92342768 328234908 548727623 184188286 692544833 24992805 556129515 193538945 513855459 545010801 366312391 761202527 731777441 742625967 96505903 714456295 371338178 907159428 467322914 85883428 702554134 44963495 346053908 468774287 446174430 805646342 676892912 880478045 622835056 474303266 63567043 462869793 105826637 856654191 533828842 487223503 774794402 777771108 381175242 557489140 541561118 985748482 752250315 954850215 637820007 660697737 361490835 45951922 778477258 360966519 80812680 485200932 225824993 418762780 277350959 802068533 582185697 860007336 266620405 417249318 126874395 55301470 678983716 491415987 248336769 10692295 43923018 211003639 280522063 839150680 649607328 369911335 829255007 793265756 688082794 541175040 738915092 760794254 783240255 599881622 396748979 89632277 15636501 549092910 615299393 444818686 645734382 413965337 835253066 669544547 999802684 689165331 986327020 173879602 933083434 430684347 701640360 388217412 374737959 800784909 65603228 948040763 444910013 364920523 552239623 665872122 627689281 221628091 911890330 259539535 474750971 41226726 113767597 74478692 182640944 735284185 940837911 545279029 921253027 432669108 417928685 322425715 58133843 303980315 18463095 883996775 176325869 768523498 625393040 892846961 6561260 236275610 145204784 585165422 290440713 547029302 693088397 298815372 70030958 113732586 879154039 652730393 368911696 140971714 845068964 256340103 300360078 213432102 171774063 443384665 204354731 446732223 702753724 460757001 853129437 77810042 55667246 199309035 773089501 552106408 828394679 113473670 714156773 831975215 313061036 719176456 941609372 486604500 103456693 336827299 782555797 519307586 626044727 68316687 517917768 255845465 897366886 62878967 949042692 509728096 338976940 356367775 651283034 849793686 425446703 382435575 486242855 652008555 184281773 775880178 292474635 951069446 324914740 239049689 857741595 861227107 479390479 595299501 671487875 46593068 404374577 657871936 395665777 386581920 753772119 746763860 266707281 636033853 885126056 314592730 381490968 379824268 96782968 364951976 276020989 605561145 929704484 797477703 814847110 822935012 53178462 393249633 617747439 995320838 865535553 801627415 743039202 487996516 362921027 142384217 900015985 917982458 838754423 254892245 621462419 507058359 364029035 362484423 108943746 501603192 545430323 999629821 127022160 433838039 46036377 528219028 722487743 961335396 498941631 3026790 103503540 115821703 146977099 159863343 846869796 589726643 685811516 950267398 77871203 367895017 314232165 748737903 918298754 106463201 926333178 964254173 349169095 285957889 160579357 641637657 766400677 384835574 135975324 570392511 556233574 859490785 340444077 99505716 864917936 326364242 215688856 598944985 581837708 43452298 851983246 559487343 472205539 102975209 543644890 75573162 507788052 859742342 13620778 590709179 596080109 360759024 874683997 886982549 2348728 889507304 461240844 573867912 180807899 424707588 144848584 884599375 921737686 601032900 767536762 925555046 357658479 438866744 774846478 997044220 305689553 205682003 288283149 29022368 952065421 767587434 302442831 743003738 88657474 772662215 868970561 819876173 207822264 91237919 636151082 382758249 597996016 296248104 194693877 255991160 33267783 320600237 949562278 308273477 550433053 116172071 174165124 99584872 852261930 656024002 493599589 895024058 967820574 680482749 75308166 261674079 624522284 656863259 433559119 132568032 913290039 969130258 291011174 163895205 10065343 573342014 300850866 677480133 774892177 994769900 625584940 527285357 917505057 744430424 358086186 3253445 674719153 768225067 472497096 458649372 739413709 906992772 431501909 208524065 560789621 397520704 406564544 83699390 638859632 955662576 454831163 80213642 167349775 679333512 165848097 175206684 310644641 167363770 566511779 813891102 791972133 418990908 912261169 329147132 46697304 243369399 135837229 482109665 95518597 131348547 974938164 966059251 975277637 316836961 59323682 491989193 937830542 119786768 389444645 877539875 541962303 493329622 848050542 992963918 649869457 278848823 104587740 837614676 321040911 45876873 491957796 834411215 418261595 669770143 915828910 352110739 941367256 923147430 935468152 819686207 186262781 468674192 269403812 481783695 163702265 186035456 418613002 262483676 149666376 952826354 135371369 149964671 793785478 320066060 500221952 664137959 964211073 708744013 124154283 335665506 583728472 204312044 307205472 658482508 587577293 956444877 270406016 215507255 261070821 132972430 281539966 339249094 851857403 563126063 962289296 347501471 72653782 432961206 29732420 760852765 923787277 42096899 806772347 713786196 127856282 475155870 610319050 93084623 406031555 298226685 771381984 697447355 333238951 233878418 753123367 807656097 856783235 494970011 957053674 884022778 701915940 423230741 433159623 669027918 826021269 911961632 246185939 465114226 112183068 456072887 871660629 133879562 660918618 215638256 969084205 782660420 366480120 824715747 80844782 771237126 689871636 728661244 714766864 749188896 674333599 406649811 569965573 703247037 679585348 437800867 67753196 62985805 477326674 311701502 941400964 832885175 471160734 482123033 840217005 373589431 184369906 759859635 438617310 369217883 863218263 986778762 808672718 466152807 399015730 734669116 407324164 516427536 188547216 293855198 617802641 333880680 482319754 581900378 126267558 371091439 343266484 202515598 446514596 533637591 280662587 132143461 73037763 657908699 105429022 670560224 98699920 417361266 670608636 456763795 747916298 721112458 538615765 768488835 307078319 265979251 473238810 614127256 672250232 572991492 697218058 854685723 86088475 734923248 63462164 157704219 627848071 611137189 301412374 606088871 329176983 229179349 305312248 17668132 94101436 351102766 396330634 890068009 22511615 936685187 278862579 436506176 769723414 972620840 238088054 283062734 882572576 67207695 551292771 488669297 840445886 328640482 626113841 880953439 968840122 56010169 358454560 524517032 904584055 738296243 493769373 162244053 342874517 425496558 298346647 624699745 186117993 422668613 94688063 429112030 938206716 817062738 217512044 907724688 284992180 849595449 665508061 488599212 839739780 466750394 99123709 588624966 908003699 979768846 37484211 36128974 362889049 798753917 408491456 690464601 208009244 289142986 143768395 855079799 848067821 425899599 298061620 434652221 455460138 476782785 506884820 381949161 235791439 196698444 719234621 330564863 120012459 353194502 635237031 547817373 392905207 390640913 677232948 320198223 257907219 575387614 368327227 360173903 698542350 839342877 319399201 326517394 656251009 809646348 680816213 269177499 764040374 872912671 585550078 451336457 560635093 602346652 588022847 294048799 332644906 120783799 747862813 659161375 666691616 243043771 510809254 989932280 251861489 276724333 652821900 814664645 659991883 58334820 33768449 720927045 899813091 964703272 342499142 945342455 100620102 470544824 772515103 453541616 603320326 283770048 286839491 952998124 977859593 919501663 788129791 664042018 465390442 617074471 930978840 107696703 898315046 380003392 393484203 926700862 317252944 971972639 773613442 507321394 483943100 20689514 911690736 252132054 710094333 570487002 79499645 435624822 640771501 398563671 589095252 724067651 321535415 778705655 300276459 364052108 520499710 855204785 230126075 248856005 864194221 397431279 757174862 390978463 740548767 173981067 134422376 408391972 437679547 912364004 896873212 793043055 188405640 682574084 224510106 729079841 559993601 803729893 407419397 919173479 408967098 954908974 994530699 620253550 836060866 757555218 349733437 553706966 862895338 646311228 644545865 21271178 690054937 951299141 314670936 437715166 923727460 135171799 424620188 885268942 631223677 970593293 814436074 706679234 595251607 328720242 877996343 502963488 851463774 753182790 284202270 52628710 991677286 171112504 123323962 76626128 831200840 678782125 256246248 766338680 676464499 424614046 429572972 173984136 530214896 852750740 681934096 21745524 744387190 654298601 928508468 489451062 869584285 749175156 528959819 184386171 953875051 144336569 443957686 985593114 611391060 63893910 729477920 422913126 63992702 907681663 670249317 622775606 157313947 225452932 1540794 966246053 271000520 379735689 869639783 618636927 746690257 806971267 816338579 854180770 317131830 399733606 40401272 259862867 5799097 739401349 494977632 150807598 459440580 444757891 177743567 640585507 713104542 539028675 20194699 147463936 663244100 289384608 984227397 550434968 363108461 111063611 494039159 911538799 43930221 123638652 618161870 676547886 460094871 497985293 822436746 387210411 847607061 835843422 163957599 396408181 435075013 302164111 126986628 535349357 953942752 948883620 29083663 771580040 672040239 289029056 511310948 111484951 515495786 180083542 320273036 239853801 741827508 330610881 851932280 453266159 317702838 872057932 66977152 646566270 756381102 537122727 134034319 995744646 76024119 733863924 374614505 159688430 472017202 438525425 742714859 589456984 897246053 562726403 777654815 618457454 315962685 310723271 76359594 576943677 174157831 932143707 113888244 915808346 273908306 458455608 18288778 687542888 210004637 592335327 58143697 199585968 244043241 554973252 184121485 504032173 825088294 723671011 98168311 374118522 119257212 540123564 933568598 568092014 831911424 49736467 471674013 804036531 574475297 762443024 33548055 531562031 66903083 932464635 518470703 669994283 78795708 663581038 193166804 675175597 991783064 707571588 986823689 235809400 767679999 915656826 866188155 75827620 992923208 187950417 241704718 745776661 776845980 789615957 678993501 330255461 988367355 872713493 148022778 865311283 351336234 339684028 498852442 69359475 662128185 683273251 918555917 266111665 231155318 934322328 438720274 123543518 522312973 522661716 848371894 148305749 648773385 866872248 476469867 677768509 909320493 74744342 544059568 172736548 465526261 431133822 104921764 168484301 53644626 331790615 307955215 844822251 682471879 990325907 656724206 452058497 845754611 22566205 74306147 723541884 51254305 79392558 168236345 217758060 537420036 321170543 655839692 923346076 499377871 694797806 218145405 139416873 331632562 912670822 902662498 496867982 982232018 433385935 929958721 472447661 812251128 180907395 746981916 331358231 4618277 918169546 560104593 110822404 214492366 424061140 25172422 299869390 660671329 678731121 824822024 676061037 577445235 733699455 996090029 469158856 80764765 779168560 298280641 474561974 823275719 691115974 822755783 953821826 875265784 150707393 776199036 978968378 594067635 926376630 576822901 800713430 277785840 179506313 250659753 339244462 544815671 451864951 915488367 30001595 752354649 327074404 741006222 232912571 774569571 465321335 337140077 37443391 363558492 526116393 192485167 659481357 568149233 634196969 635428602 852069451 606143122 360094467 8108004 579749996 263604870 840020490 87554045 270368659 27464123 654324756 659878766 935929601 37462063 273799054 793202020 803208828 90832328 56241958 231288263 579681534 420014972 266710098 90847376 9723473 289633543 593449560 431489428 993102105 445157745 65091723 247903273 176158873 664740639 883311978 497137914 735591804 185265099 941715088 296683976 865393185 437235619 55559620 692881451 857882414 665626562 946342533 950499663 814677852 846871055 101530574 496878821 342402997 837773895 162835964 797514076 634359505 765680886 525646671 74110339 28776671 718602324 526375924 162842737 761440625 967775953 462688506 561228314 717987606 225937753 334483457 447720080 125782540 444160739 992149372 974684084 348957612 658270347 781483644 833946173 879727635 706045460 560611281 909714803 754297957 252829500 270496493 347109763 223008376 633930059 470426973 112575698 994189527 92341314 547567337 255181927 63267635 788960660 730514078 220204752 786174799 459038442 177431244 390773147 314153084 978382968 141387156 284333087 880666427 772797639 90671305 387221924 55835561 564793876 47736041 726575071 3082125 739626912 744159232 878595992 323179823 510921648 234049710 304656600 954484843 714794340 504245110 908245897 819343181 295489332 767382857 510911593 980211495 922782953 38173236 567459016 17643653 988000511 828960726 393899788 758809724 203682514 968406133 896288626 369125573 547590992 448592496 523594364 520714838 880776899 694594616 2919843 10051097 141390081 619154550 949947928 905969055 850111033 986225297 218082938 780333353 326801087 374401023 552729525 995925683 134477316 966437487 742090481 699465279 836841692 670835710 721414452 934560149 176630332 503041727 164802479 788489617 644083230 17047808 130573285 963981711 816160372 998411899 638697791 556781224 109156325 683619096 102379287 564941085 163754740 757237198 640310990 883334739 750701702 428546463 133615576 518814019 931945728 543642222 974154155 228544337 963695681 692346490 901155205 7696820 28988045 808329145 846900235 308002014 816571035 865016057 890377485 300625684 286584385 837308035 216345772 252645390 935161700 270349414 853422579 623957089 882604306 311215412 932151865 948224421 620354385 211222807 486408519 388842030 213425528 924434020 170468111 423055308 624571525 366307974 718584524 835860924 41886247 948024475 510295194 77390133 209232306 433329541 379730712 420176516 613170104 89384544 985203368 285616173 971710152 5177936 998956179 941138717 384488701 866656111 470129748 468454593 388837871 684222623 712121289 79979106 113483814 18775833 226769195 566593328 366404104 698386643 277550894 513192264 469741422 983669695 270782311 938701600 948342219 207588884 384457893 659359790 602186329 60136303 217920228 48823370 784294653 736986001 461814548 361525939 123213426 859062020 27566032 577137406 306813568 908025993 477722000 482628602 513372337 987504217 158722878 395180885 555889498 498124094 132264293 235684177 54597376 894658469 915283349 168396782 920375522 517799204 853116964 863261731 290327058 362506109 943859384 693817738 196994168 63604709 107259739 929689717 714391905 58613829 154774316 515536720 913931779 814252789 984314901 963057479 858581550 740344593 890628285 545980980 715219555 694351736 931582419 980376798 130788388 297617291 317987691 737129245 640671628 728671524 335593703 690382106 597609496 261290080 262594075 619795619 304992181 545501126 704686905 871348850 90590810 899170019 60126249 516186206 659964584 642740937 253279295 716866722 372320923 342273466 677036954 942354670 5350560 443911615 860732370 724811186 25580738 946647128 949889191 779272076 27489997 562864366 634632394 745699927 755365430 487905781 105736143 365948833 134540540 320486232 331817949 767492117 163046248 156472291 743356457 416772381 300315226 792571640 449585217 935446193 804739323 707542859 29855326 569187536 597185677 356278290 279481473 153383542 313630583 6161507 683153197 884337333 273289387 543603144 771781952 246727065 148920642 428951848 259752709 287219936 297716765 478913682 409650288 652400085 650602143 553670439 165993975 586298975 416725881 361310231 380443992 39030600 459045179 28866934 607044622 109381337 584295088 763913426 437602686 276057271 107372266 617399493 483879478 249845585 921502488 287018139 29271121 726570574 469727356 534092052 569165674 437010588 895617649 882826459 784564106 826827704 345651710 647429744 939188590 492468627 801470427 159062719 991700303 195496132 331098405 545470594 530682354 37149682 857308418 777441278 408957708 823644237 715496289 69153995 4840635 228311255 716777924 293714258 358015506 384261259 644993462 812420245 265037641 171494349 815646516 868847625 267741909 171388090 887114231 70464526 607465464 776066587 782150371 525279786 335599904 649856832 101246390 718947694 395910616 525207276 832484048 955522477 752209456 456658354 974999281 230251905 666052 468432359 774312660 192305558 879679644 61004463 341843361 149002416 169236850 375868953 440787220 490310789 239601788 884328268 271274436 84425340 389979314 159781833 609669403 566933136 169880214 307409019 769359063 618358377 943836049 534445115 78400223 830342015 464068911 363124817 783330254 900901846 634847261 840837953 492809582 290135512 239063981 381428714 462325700 556594928 913421944 748909667 934920196 74601443 539622000 273469050 60754651 211599309 29769204 453299932 786125160 474916759 223000608 489247121 920873128 967591660 540287563 203448843 721969927 641368698 960888602 631206323 107497581 764914776 862864366 464787997 663859414 777832678 298210715 493247995 636679033 314039990 652777973 397428545 716390400 70570096 401311267 791078918 624551079 525471689 957483755 898060400 252499405 864958128 354130461 930562685 298669805 965320087 701013853 431684111 802642977 665390336 624303453 266119509 430020902 9744764 500310488 973012145 439784170 77593434 159653376 307560532 147304693 973407040 850513930 881270241 344042555 583953047 416633714 103215011 326257340 552374068 90138119 655923229 327478593 169674120 557348223 158613207 303514565 331199409 15241679 327568876 739211405 666713166 584701552 719129011 263226659 540324576 268251621 281128156 333572911 598357086 431370305 907929479 961429605 907862021 983462626 189152598 637286135 951599788 911937514 615800405 898345960 744478860 849124473 626337751 927051667 777191763 68344307 729079731 77073695 418207525 620182406 958445961 93488838 356332065 184449454 841489477 848979582 913337562 844783863 111436257 983369674 962308949 978707091 471312998 181558855 579842211 644650457 875535287 497758381 414334080 53752987 336330332 955603601 159896032 712396440 247466042 896363886 9109682 240667797 161165528 440545659 168504907 230494659 149721658 911520857 963558550 207810554 764436258 526759182 709228195 584057473 636516415 779282571 412354593 126598021 21541297 400460499 72067212 278148345 484771085 191049170 468619675 581438171 436130817 648679743 630603197 881806820 658225550 774891048 237668221 128802367 578686295 894480492 715978717 762404160 728920884 78815374 424698615 6853964 918426889 843786400 282499028 688791968 308204748 381435015 554598188 350333308 550207807 144719031 420144304 632550854 260047843 667791063 679160869 782856542 758037692 728083287 297688942 401016042 45960181 173479004 686383949 715805713 709900363 972814003 623298732 905504173 230326911 419953826 524227940 497593649 667933038 972017194 339339454 786680231 792865535 794573985 838991735 324048564 983997392 457648085 789747347 233967549 305619621 221166401 667657557 826281081 124181995 950091695 768232655 889733007 688440377 286567690 621336782 87393198 124890025 166594492 806179641 312489244 81355185 820627271 21297710 955146980 758704297 581812513 774819913 601139900 677283279 671272725 956317037 955114722 886185794 466335110 617229555 976085121 618007972 252220419 552381427 882975472 380027982 178027459 897298705 285261869 421738204 419948388 659073629 101604260 962237524 718700335 559976284 517480316 127060073 762147110 266220164 599682958 513090774 56229581 925468939 565247581 205245520 753072654 361735747 528022488 973330162 832139307 876311927 424237414 352771434 964538245 879429839 992103315 957086295 753615263 524593338 622659980 24494012 262304270 389604189 845243297 76471252 229033816 342260464 318471952 309519338 293103074 886688997 744800270 430748479 389178554 262378474 786670330 823900967 524146519 421906006 543539978 495433996 662109492 224223590 449308592 169061032 679541044 442148166 401028118 145120949 202234842 589936747 831585137 93167070 547794458 119963527 743320277 976855495 787777289 896744286 892106778 285087825 968288216 98151841 505160807 458001592 334844038 910459084 703057773 53621392 413533835 2160278 714410301 972198826 597359044 533722068 192639305 324544777 910209047 831055821 211027491 855221591 883879083 894837010 672978250 277712118 335865688 55524879 588705037 658087719 883674442 855482541 914235199 575841962 56600235 605018909 175934017 236765733 904971874 904135681 668873288 88605384 19164165 178261563 552695642 723965923 111596394 955622327 758331924 357033040 127706687 112071606 44242472 785682205 490175601 352018521 720945336 335588268 468490628 622944460 646246961 445536215 752521661 314139952 463440831 736436511 948437216 416140178 888279602 822909629 367750902 508743653 531017733 724029104 459834872 241987263 30045687 691228601 884633176 91777139 310225862 903101039 971506895 384508957 746783006 934728768 156371499 716426132 612443894 695871334 717331654 933749471 282530576 332110195 929135041 337616933 527452141 235251307 575538422 878901431 70617431 692966586 485195855 841517750 986615417 608189019 683066418 207825160 371161191 752294157 47352817 484652460 205171250 701913102 80638409 82209518 889037733 372291778 684485398 348055657 963430756 249280514 469122506 219421550 153354568 168616849 902435268 3215194 641421299 759951061 480351675 261070321 3760484 180708028 979718111 517028924 145119523 554853376 998379701 41331404 995187147 972210974 130721352 334117971 13015493 717250317 823474582 740652950 447520114 486244784 451733738 728508570 215693529 10666513 394212155 105689902 596529420 981069199 454529461 883050531 39760268 461813856 183175000 403982461 681973740 588444341 892866936 162526229 313425089 167957332 121488773 452131728 331618153 442171714 248277891 717179001 994836591 43465265 920622333 755260195 211186482 463640832 605802910 597590589 43528473 490617473 578778531 867288485 815884829 773727582 693766361 585953192 945074161 932312088 864392672 312432694 302736203 677919851 889364685 564620877 185987545 146145181 304054811 13935928 236068069 871870083 635396994 300119218 512547402 686745854 792343724 625825582 808993509 589947383 747132028 89455876 883930385 112999022 193158258 180331484 735864578 517590730 218471163 333318130 675767955 206885464 279296699 569265908 803375416 922729870 440786861 369627169 395200123 782251649 241791413 227283038 529254686 766010239 386768268 347436873 941985511 786012990 969943044 886052669 147334133 639769005 640084844 941362072 623080124 227036061 417478987 764642810 279737710 491850848 610281899 86540119 670483290 880127207 700683516 341695154 785860346 153965121 846103779 758718690 843670144 220436844 654960847 277138637 654128465 710597687 21660699 98610377 871948956 392704293 54398961 139574849 880850750 973748201 445586641 619191908 448653647 6924759 313783200 140762156 774594498 700227893 627686672 898821810 491682802 295936512 834712983 991338543 233976011 562359602 753514028 964760591 462999849 408504904 359074870 979705077 839812034 79239568 972941190 505397700 635739121 949575493 520733982 636177948 366168503 211654068 685126145 359806520 708927077 269521312 258529895 970242163 433733611 489321301 371756407 574200017 757088468 293963564 148715152 338329667 800735437 689442036 453301341 273589591 547254093 89853481 529260414 281971074 101931273 7408932 512277273 92250606 116774962 40454424 965228293 51679056 651105287 52149472 597198093 391913811 407822612 139713718 420699737 408543717 657807413 973864147 457524808 866715197 612558075 731776038 665040700 743455753 807327516 695400845 32921308 448985341 581412411 697090090 153084529 225381695 219411536 826253676 545523209 440717934 893208864 927788002 57314002 588026848 364504344 722083391 23023506 64677998 958320282 527203631 316537297 78156576 946872467 717170117 654756723 288404925 643552946 859130602 333710315 464032851 92659528 925109037 100116301 697269054 626448402 463579256 137726219 891883316 55661816 448146510 670034556 382502880 412386294 288042548 999065264 630997916 994658291 613434411 446689419 986586183 647279894 364799938 800838326 108964838 845859911 570590462 564810461 942456690 825107681 845324750 684905453 967531236 178199785 668295971 377762326 108785586 601304480 42523228 308942575 461868264 511245888 162716084 139628344 131287900 937646552 920013999 112879756 596973652 134496990 998209315 409704832 763516607 432247562 526505822 918725164 616268185 902130557 765215283 612368159 444543622 621779964 855005795 668712670 75825088 943955215 956838383 129961702 434153320 677318279 895775663 765733953 209349512 903757388 206744647 314817494 238890408 900759430 421405179 764242293 333217174 624068962 70285235 122211456 850672534 920080278 349759256 21360953 168672252 749512463 713978751 395527709 370341419 451676491 51838342 244760876 159286621 295079380 520780832 549274267 193447461 85129003 340216929 802002943 629069279 31255123 376011526 826049637 329641445 427151220 83563283 633477401 856038991 928812003 615675174 143914629 539728248 62868805 793270937 131354345 358682388 31854050 990230458 996627239 993510354 823029809 633334091 873788213 208506902 39274177 994793841 532732918 326022202 58381242 997989242 241187263 68067838 486680270 273438298 599701872 241537129 304091922 369107372 104307886 331230781 79496017 996418621 51619806 839639325 558474540 831213340 768432809 739575468 783158052 982077240 179146302 569310448 521669300 214945327 149730814 890880784 918647173 195519734 583466930 240221491 912384914 304311746 798725735 287697866 86615614 72165032 805804113 224962734 617982373 400919566 287198709 63348205 488436577 327735491 457955890 728970691 136421874 147451945 228888074 586209437 901741773 979751949 589320499 745789879 53322231 809983370 213838939 479564274 171199721 289188412 583299942 963594664 449408848 455370099 88463109 136994140 283268802 293992273 743765277 63796910 98286811 582114515 326122814 572681195 537030394 503438092 583689352 900140226 134799643 285384403 500181021 42016407 174859058 750750934 419830515 878641159 986176793 514149064 917529820 854205056 746283308 17368329 453861987 492703999 640238574 616366710 832932743 973349993 822999154 379939627 117942345 495494917 512472181 407408625 342137043 964913642 167874109 724164559 184969804 131900390 537079611 494053549 176722836 418500519 50625516 568900107 856264981 584178497 537596719 997959356 279186555 890098341 779336073 241925967 396940768 234307240 999773433 272807737 681447661 537880147 360191080 353760905 495633161 589947387 367631933 96608967 226951032 432558165 154502284 995851740 605089904 509606355 895229958 164806110 168609603 19959191 198153276 401349417 774266780 167280215 178886043 746952137 150497428 506193329 348456024 138412856 69722855 499915096 272007583 6333840 909290282 696901577 336187316 687524036 835323738 449323197 963397543 690255094 869834788 338531970 521255705 542793048 949050877 287041459 667361927 382221304 210689183 463142383 516865146 915310096 136411245 602888515 856577256 974402121 148173382 168938052 206434131 505962053 401730991 569059928 457577315 890150690 317647666 441665481 338081620 216094658 682812188 954049715 261415187 35704264 89490792 419765188 717813358 848151147 277366186 329238061 735644768 153878576 291116783 44842454 268351698 139411214 424562875 987823356 6113743 344893068 952315713 182324850 78940940 300073133 778682503 317636606 521613248 147942533 363755742 912281520 971186990 202673838 811411210 778988207 90490235 545600022 976135125 944048266 497564038 941857395 930152721 650411056 791797695 177933041 940698384 326152389 417518862 875968940 734912997 675479315 536108564 656063862 847843844 77761621 985962873 599757167 222988115 151413392 913621326 847195804 972946825 776960385 561044245 613985780 441099605 139822984 389441016 72399216 397366094 953500180 254705026 375925664 926154416 658976474 627563592 467352776 282823022 699938919 585622534 409252370 638605131 78320115 607858166 405928040 573866098 414160322 775021822 992873441 911199713 328021453 694411551 164034518 892381617 431646049 45227105 242357684 760562957 829804209 568877466 93822138 765951471 224072992 842533800 276367354 513632060 121013098 675358631 657790764 166019425 539782830 640335697 471185681 224281110 893535253 742166390 225095168 383079857 273323712 484351429 485170460 346403088 547786995 394987735 98014673 850809096 850800672 558446648 415865906 539273865 935253695 76825263 577488778 961010754 900449043 259986620 434536446 659151333 899136119 570726932 610602496 200540780 886455833 367827047 313434151 497929106 849773807 948560067 462486366 865294906 420264049 65939419 103226365 898683973 538538661 840959854 580728252 797116482 758946729 608911760 551379181 629078188 407546495 465805262 70814987 582423415 580778895 694290364 302474503 140957760 221442790 153739013 691562388 124675497 369642149 323685132 19810162 691516045 936521313 548131088 645981231 252535424 994896133 422969927 470846695 660982462 865455203 171537023 482731015 785229248 501958185 18387757 671524899 763377851 106419329 385504335 201044579 540119819 54140153 589732045 8365404 114794847 307113639 308941519 413089315 321886795 291289869 309450644 437577726 873236569 35013171 482180687 953766348 142812199 918025214 957664524 384714273 751046742 229863853 89383323 410156569 313291989 19606885 190674655 584977317 157364828 688094338 164285686 487250761 758971132 840495607 603040146 151896409 685646331 545418496 265213427 568208873 660733479 802977900 880657537 579267937 274011437 556692228 243529257 348245446 165696135 764823489 718342723 827228801 644295629 781467154 603609144 476988719 290502005 77087049 378485286 41847165 304539784 562775395 287894764 520250468 712287920 536524725 633551844 91941369 480921482 107013020 135942296 492274444 138527526 571578046 698780217 181720496 136772075 107356198 777853024 593181419 90404080 433882419 628163860 745322476 729485129 385901718 778181370 961214790 196931372 657432126 828656705 555701678 671066527 792768587 345454213 601889836 733047069 444621942 725856726 203406006 285552631 338853033 551043911 904272355 614341756 460851540 438939136 871150166 243126043 108780292 456155158 483109620 803196775 597429980 528656494 734707366 952099138 340034257 259478807 167302423 736563513 798229357 364614850 351562148 260110402 104743942 482494872 510285600 239802677 155593176 758036675 446392169 756927894 840275930 527068734 270329644 511995079 554733361 764447335 460914278 275170861 253630495 812973373 213428363 618948085 329953507 330088180 668675133 587131259 264831887 176950198 341809142 664831071 612530469 290331780 224654454 295397486 704259717 147187043 982184327 271792391 1322017 248554357 502230926 350921985 217879183 679809443 820627860 947070645 584276824 300870044 356078830 455690322 918545068 584088280 906557608 189462091 745279641 6489524 198908616 762565735 145031650 222610242 92271534 903385923 867288799 512833593 669956553 250303435 739304678 497183912 244257873 929586315 839951455 718388406 82110687 157841332 713450748 125815295 97829130 22787925 535753979 827303648 57846505 838845937 8264431 211650308 124171134 898652782 275985504 25020176 514839126 236997570 372813932 148191789 163712316 779426416 129181011 294313374 159607744 603682773 426393122 312421107 574571088 358947798 787992021 497867100 724464984 8619854 346161109 536832338 411597889 871666849 92013415 661953685 611764142 132813282 455528109 672770309 138669453 345598020 89006532 98132422 760823056 902126224 592063579 637564566 326588965 335079807 80949542 797654796 28857672 666154839 17294318 220858793 468730973 162344536 435368768 587009733 919273625 738170811 945341036 926281641 368831515 477803601 4418158 941381973 646509198 386958398 608081494 634109960 894111212 78499682 651125512 259383466 122908656 247625840 6031238 842954927 348319506 888101504 211758896 706539000 701696927 857601267 125939601 809631545 180102621 544497336 803325135 422350708 130509727 736779464 690874451 813411687 936187429 117267033 429204760 816338322 107779033 278072209 722172720 762495218 958082000 510882716 872332810 82118611 329091700 586085257 985509064 709400653 27728631 818197217 107417017 998555918 88679384 350403110 51102625 453456581 601258097 856288486 117525721 982988506 627022939 3209661 232833256 927420701 921430990 325924135 592832273 899090393 6599736 370303667 39872631 570443586 844065450 258364760 543725499 264467216 554883654 795131433 515732007 425995000 626422101 360859625 270108591 978230807 621312657 781358038 456656988 848908186 985105556 450546216 97374936 540817105 399714901 74177590 716607915 164288243 236188914 982121012 877387503 364625593 856699319 703720398 145016731 122080125 882168140 556382167 136519894 120380023 573958103 855171691 636258195 66809726 967384678 364993997 143334501 753773117 977747599 155128067 979803267 431410938 539680287 48209189 866525025 592499449 665634146 982034264 637948594 557656186 578686085 151702610 980073225 592435919 599903282 582210146 87234848 182546358 513154975 558544240 170008711 476885009 87179605 820089662 205873974 604775898 587225504 301665895 665450539 645072418 972131241 140780951 572635650 493477788 724224568 437604898 775954424 642928389 598170118 822150259 603723568 43801066 755744456 780555081 200172403 312517997 386901516 396972212 564749938 633576665 114721787 820297400 744003155 689308605 79621261 470414497 42010953 269464753 861923896 965616280 884137478 222947036 773525175 763304074 494357796 345913097 36960884 554619483 105214268 489804438 264291138 940583549 518272257 65654588 681866226 262822476 958000656 529978352 856309911 575091576 290277706 281192330 410897702 808446528 236045782 6441368 566482382 54764988 912409089 139148688 749024075 600303569 323365755 327962414 46249094 758965311 938099458 524824015 731632511 999497493 775309509 278937375 555860142 479413310 985317326 428277254 865232822 656170099 661637722 253436728 372330625 559373286 746363608 743460193 448411016 989623925 516718072 153776410 807478384 388311099 644556543 961277176 406817858 953615990 48911815 248804217 19204025 365514823 106408730 729619041 575946116 491439196 10065464 941513927 762190574 6970227 925391675 37685791 178710591 720708034 419790526 569651246 663721037 937946304 971092609 419569958 253707163 712021726 778046611 578113884 122475008 389910801 95071834 704290555 580124161 707801234 585297093 275813845 404885244 297471912 566433146 168297986 191410319 458586236 460852044 255111076 468001498 281516342 427653309 330100510 969627834 923066335 430188548 836730736 614855310 752783183 641215057 852755683 92698096 330987649 461945452 222249966 896222282 459442089 489303077 110426756 928919572 793175411 933397069 810005329 858157892 820105269 470051352 788398476 842058110 831916765 600771032 182508682 916611170 410843650 159766057 686369133 623114741 682491357 163806193 370448985 915218496 909748240 34154533 328228459 240293765 237330651 336116076 377208717 811437225 76469985 413799810 551960188 518353498 586855760 836009116 595661983 441032356 509597049 635707744 705116640 870083997 92220017 759783082 776842447 873929586 315383675 672723396 422930814 888247224 373755950 253143680 308308400 173353999 975875951 734412348 211768108 170864515 775972226 991718253 369005189 539023625 107024647 875749450 878120319 11278898 999855468 495027992 669432006 347483241 299542266 185975508 835055472 139827417 92937228 559889428 559867963 623124701 754062731 810131907 288085144 453537036 704446320 236068656 367833375 467875718 673045523 564902410 532696601 729718496 292242492 568994584 471044284 360427780 656543363 780703632 631454274 282504312 610734573 992665878 607167154 980296217 198398935 506128864 472325340 663254506 145499585 663414456 771333183 240715096 889418632 750642698 664371896 617798872 199957343 269422790 723125634 484654116 982935259 155624643 769212705 573574412 201173932 675994698 730798508 431931093 377971907 476513675 505802575 687159569 269472237 795689466 434159760 363112228 396027304 872338285 543368261 359930047 496001669 280661182 90278995 197910882 148036084 435618264 231113548 596637633 201147952 85791567 462771499 785928902 606307959 460377113 841982026 279188321 859524691 370283211 363745969 38941266 560812641 145489195 919378583 665835301 790492704 120152915 211573545 353113750 762114478 9061842 68372310 810434805 18138106 399457614 200251101 114192066 283065422 145169407 367736221 714137394 328699789 6089049 231397939 998531549 282410718 534669883 245896516 965879851 75691886 991802927 913773727 889020469 593635038 112115536 124830247 44646323 50646586 575393838 511601807 838608233 557429728 99569960 688265286 242454310 487704314 755880553 745742472 627941732 129029613 380653257 281947649 373982826 206296870 130553082 261169940 188397981 54904899 546056133 79496768 687611864 780526584 913893271 974881169 862012152 107072630 700599816 748478627 841558546 186827929 36451459 841305568 949022589 276066557 660006484 959383905 780396660 189789905 178773906 651826556 902034456 860844924 225200148 952631683 217945418 479534515 178175517 206284021 801379213 204316748 90452332 821455297 538367849 461628171 679994462 20098625 682565140 920976343 639989341 430193241 440564551 148000759 167676073 552252625 425742152 233758461 872536538 616750826 190412275 625575655 265964252 649073730 421656197 57078656 257811063 445246557 56886040 270520900 881076919 659021835 111253353 842617468 134210942 928725103 59326546 486319475 419091799 169373841 821196637 382985542 109312268 833886958 353642866 778187717 690185906 497232222 600019020 69833306 738464826 241456907 598625669 952721545 985875155 804599691 933622303 222153802 905269927 54042853 447635397 605581436 867617825 469111775 947642041 487240591 495561898 324225269 721934984 654119121 390900804 298388200 97091699 486716950 118013511 650788110 274439740 271347019 52503396 476144791 338596196 756272424 10808868 785829383 883783683 791574849 298157836 706928326 946823023 140788883 213750026 956029404 542489820 426127746 681743266 75699825 672026597 921714508 157320881 726798327 868132106 235027126 252491962 861463624 224463343 655454345 142854589 355411859 641156036 519077588 267170366 889727203 102876972 166552009 348761561 840145337 163391290 94465365 64619913 415517746 620170048 381423886 520495621 858858537 857643296 313347475 431818758 535856342 747247756 762923974 999331714 953617825 459337856 548493794 503515827 37324937 274299020 995740487 173778561 787074361 310649944 481509570 257754961 771501718 135714200 758229453 210606804 496488160 328666825 343171205 860558542 757130956 516849400 606682823 934065141 734329101 473591464 523646656 558642611 811980128 436556945 198703021 273848674 119164342 748608833 605100061 748336173 454695536 623697789 255446287 332993102 640092332 950782141 203371223 987738267 605375853 94537276 639391386 10355204 793742843 639736775 98413476 383263193 273334993 130562333 428343791 26133756 854213534 625942516 77002122 320629475 448848437 357026367 69236272 761688517 125623629 144797307 392410442 559339748 458412885 643966049 428741757 878680595 775554582 105634025 222721157 211265947 424896725 889300128 898018994 430995880 187877611 430022871 461958477 692449877 91990623 515213438 629160276 142592401 972589219 547735748 432043433 201371510 571961464 794062315 203268238 986262428 590582002 848936843 304698955 222271275 859226046 987160583 633649437 894672343 992825046 661253471 712398990 696700485 557069403 787018280 773803955 676463025 218978767 815750839 222809356 62449753 179761437 753777556 829049769 281797342 8546652 185309398 498126465 218126835 761254800 587698317 177850507 775975444 528826072 720874883 781416956 110908645 263733827 189715405 573239429 630369130 940595407 217026269 255767196 514601081 905150831 121587026 899105031 535522549 582304744 43547057 70270603 999239535 614646046 722681199 290353730 778290678 280099052 764347434 829093212 311028369 493834270 340917774 616635639 769622862 157725586 707772575 635325050 676679984 198378128 461133828 932680027 161710012 99352858 290908327 529976986 56666505 927841945 251966115 276321629 568076017 358129349 394993552 637693382 816685550 465607063 998947353 737086019 219485127 427462299 837212584 188285212 381823419 736200233 817484859 6982216 425564060 343925609 275455058 270569296 420566425 786390741 592539551 571596700 812668908 377291094 575227845 42277061 716254767 273046486 453357756 21748241 775692606 549423777 325147424 703018132 879091144 758830093 903487125 329917959 214001623 57745630 777336258 944030449 550850953 190824936 222908185 163954227 440756536 698267349 826498224 675755551 611352980 774976089 510640136 728623482 87774897 754820698 593761514 11355463 311264059 305449656 703137623 512440419 373363857 336721574 103323887 988678556 837009343 642646545 22980708 918394374 581774822 469792504 450652732 289333975 954282276 18958893 4637415 563125538 575340443 181058771 838702342 766148420 927690346 629396494 457420239 832118538 160082579 168791928 390096681 185115944 963265633 411411697 878286293 158873722 34795576 730715141 940504353 325853769 926222938 573590262 615857558 777937281 709290858 699942377 317996657 571611471 390204580 31261659 751567165 162184037 765939912 518297466 795634182 663063300 173287306 22700361 685647554 280868794 955410661 327060774 433568691 816498824 14273280 210287189 874027966 216617135 712465202 104952655 694980886 531069594 242856557 144559384 112571382 773366426 659889351 627401407 607145512 666016451 369233489 171428600 658828172 300656845 4185387 721080263 624220303 979047118 278819870 588124534 340282436 575921640 774386328 18657395 29980411 957790778 943099998 710102909 686954161 885497644 723224633 572867658 71739132 965329647 890513389 728086365 573913303 684123787 288166740 232913637 394482410 140524061 429615881 525507871 218515986 814159258 529424334 928713115 532132292 545917230 525404846 178582323 750416208 371297436 738460754 898072930 497645358 854678546 93815427 616968938 720665117 779096121 794439960 461666403 258763116 764280912 414397637 178838904 422579309 79854235 486985111 88304061 68730455 845870666 702278763 808111612 339609072 746420756 201137545 248107854 251829543 255285621 633491492 642426170 338679614 124473851 141973008 941486715 794829271 291734643 619917757 474193458 802115234 819250400 965534987 32498813 519958629 825252796 323672476 983100009 419919095 304904242 17220602 17012041 30110462 167926177 422668191 249035638 509738880 785541277 53186706 147703313 440727429 243116248 755978393 694771933 124575481 213232003 442848973 735740888 470595878 692732293 378080029 398495128 34374840 395468005 103796225 822620260 108973405 148035882 193665922 164790291 619676126 869380456 491173827 91231822 271036600 415869903 923335111 772628496 147836985 819475766 240499503 486992541 773322487 373221744 299203778 291261294 773456402 569656251 727237456 663822213 886807152 418607920 176754611 343844096 325562361 428944003 120904662 183250047 901843644 236001713 219378537 451472807 425426271 984048604 672215907 227449263 106635775 679888143 16382812 81764188 986973064 125601604 450025086 329043596 288892922 500536188 207584449 902259808 370445722 245040492 630654694 751969032 725384465 77326811 293816688 567389570 469150584 164396480 953502912 144575479 974376441 96410709 228424716 747652365 526336583 994239371 727826502 39511095 608076321 776811702 841350068 786283764 991778379 839478245 67646897 209667170 6324659 1699424 356067820 880888966 188955121 284820372 376616528 35847785 775797166 80052608 801699927 100268947 698455440 638318055 898315341 77023501 736996823 972438684 692373130 189999765 413531131 814246030 947034625 377933557 62561107 230065970 28008571 328851395 437781690 901213805 386598856 897537836 186868219 604431596 740417246 343075037 6905383 792963549 830736735 263014642 8606863 907107308 972133750 945847315 667930228 525002303 938202252 509782720 474025909 57529174 876249403 26928671 646676359 590864764 482121256 522178028 880877972 2632617 648486871 721652201 266896633 63683185 47912299 634173295 873840588 101547273 475322223 840063141 885476331 805608499 412315116 567582710 923723185 107451149 572912013 941794785 613584678 600498601 814273060 213282186 186094342 254625103 490543404 107955340 738353947 819664653 618118272 432728428 131470933 360322996 729723906 187731033 716432509 352183814 769995416 8675549 160424775 639018383 778020581 364513730 24779481 620971693 605095466 47225964 719685775 21457529 636735015 640103479 266014797 302711685 764390092 848094110 966659976 708737382 905152401 212173781 696160286 913347333 86040330 233128328 555739457 856434960 172620131 774526949 823350854 875823860 218243453 734518051 615356285 193007090 216891051 723435296 338391166 965350123 547906274 461480874 647730830 438827790 854575510 576911448 966130071 388076724 142458093 453519216 240398340 858337588 370158793 720744697 692407755 918432406 73843949 576820371 199186555 166486015 119914424 510870463 447699062 119164023 395539695 869882743 867933312 947567908 445517810 234158798 661928279 6375650 670788767 167285250 16226675 922166576 746443976 201311311 188537131 596141924 232631469 776008652 19797148 281661012 843218180 609049814 182670156 146916204 688975095 198635515 366337606 947281369 757930174 734219841 734270270 17135836 909229806 790329515 746168653 764794176 724899898 430451210 140581668 677552948 84900892 714582746 132659970 299839806 389806584 697234735 564652419 240422996 454339926 16185265 673063502 950532262 905214678 106589599 419455024 228414831 573859083 180616729 822715444 117407082 278508020 373576477 625908974 385079903 804559507 544948434 661315621 186881690 538858730 346595144 619354005 39893187 923544483 913612233 339213533 268335496 126320682 718472245 120470187 714708039 563028385 267320526 540436812 434434811 232503099 349422330 59970748 975375433 43511393 652590996 884293489 657044912 122957783 303775595 74970406 909713163 817608288 1379693 758943581 476636935 177394592 73479675 862733423 782370283 278332698 855709323 907594392 42887497 223260326 727342981 419828099 852377432 253776765 238558145 37572291 863724970 835042559 371623947 633354845 269353978 910228316 363759829 662505324 494859965 25567736 428864417 349577756 901910655 217931138 202191185 211535290 36646748 834788018 636638429 44965455 469483037 473166648 656709843 254903335 901237907 991450038 368885312 254150596 728073605 887546544 392149011 283732988 32857780 557975357 867704447 403004139 112173931 870911425 13573317 697122467 896952150 141609399 945326994 494459947 768711657 301901530 993586412 748300314 214116348 420012093 196678740 651200286 258791651 231136182 978448738 433483757 932787970 25562738 459579861 501813822 116410774 778274502 772069332 322205823 48420070 124651698 249542915 6806062 870887055 688715162 733402438 243523885 938276 83085467 162237346 434322336 174558650 414127707 149564484 451647567 680582762 874840389 913627956 420910195 715953784 951246246 272475633 975587010 128728621 448619328 659384675 207172880 551233278 544342968 873724784 192092974 441733701 552676341 538353909 671131155 72398959 515404361 148922187 249971082 386185183 305459948 671779357 442567613 752696634 18994828 373535401 584125915 368788295 747582399 61975824 10507196 702094625 127357423 986050061 925568445 872404397 288315328 872188770 490714329 578989280 234254829 102165567 553675143 449958656 812877667 250339151 439742730 440185505 632998802 389565925 813855092 464824383 267677323 469520232 249217760 365892180 679541135 62939410 473417453 717301919 95404736 182446654 790450130 691457363 46271681 609474757 389642068 292814638 464534521 713506904 832700193 899655691 990252418 253017862 159147989 172717556 917456250 558358627 732428082 597635963 231625570 998306984 933148211 198560403 175604886 149584253 187671214 171731387 155516092 425949125 986245386 95009062 195186069 111883752 422386448 170433073 868214556 105283268 850050795 484825288 723549345 908525371 961951686 308376951 834540497 38021518 828868988 861485283 980507435 687129225 510050030 393776389 72226931 385219619 997129957 604691457 536134403 926586788 258445605 248367844 794747150 390157537 273691193 232164564 829343523 407588199 120415636 979436282 387595882 764275585 167160536 434360659 927120917 799894455 280330074 240347249 620792107 418105691 233275888 99533945 261112822 969828788 416130836 888070755 711084405 921928558 590175628 279580828 282711539 952333411 592807225 780944324 379599722 238277040 318594329 40387271 137612999 691584138 144608937 668428485 147773234 333090885 686692549 470328738 596973077 181901549 726584248 753970794 355239968 525857968 735541436 556633776 444377382 678046315 350074728 781981789 516757360 482863071 889197352 856355970 537570217 554260808 391636012 415498256 440676595 265316670 393286179 277708547 520762175 948006091 636661574 674435354 284579415 514960135 958046630 332181373 170504368 668864360 120227055 422067125 952469830 30375987 159616974 193542520 997982714 116398873 447592901 159049249 989946093 171437527 508330485 917600640 789938551 366647006 405310333 191790394 539950359 800189856 296088170 93866569 79605861 460297331 176753611 118922783 956423252 897939761 429559126 142624082 806365596 61914267 786905176 520995949 522925043 546787192 12306562 688688887 172200579 12618080 429093403 218332460 505521303 620154562 549155804 250696128 788935784 20768355 620387072 978810028 216147343 423074383 533844560 248811092 41886117 107331739 84756409 705427952 220426931 229808625 231628857 851045871 722701871 176801857 399945139 864694211 200169828 70748584 118936340 465702972 225605814 533068896 277764450 462876085 399879263 299621992 597460250 806543143 818669168 391043917 31841039 660565224 249223377 5176421 306696035 581307385 266199964 232514382 669547500 34603629 736041754 116493225 351172260 562020897 306733127 496488331 965022615 129261499 208369220 854950476 148366277 384556589 658389451 428498645 601254868 183563438 825206205 296466733 49541991 295846143 216970024 645933373 477182118 600032816 351065355 95069724 764075869 754312488 364977773 331581337 63551100 394139755 686584667 89492928 173650931 47551488 377258348 687437008 193181234 544924661 951319443 627825863 946253773 855046750 176442242 561002829 324472376 636663909 755530327 390414546 962948856 514393090 814246708 627390944 822833545 591422792 601545908 815692769 869469880 629321867 64069100 120513530 620175477 759559840 646870959 255258749 425875037 810664753 412856954 190926209 632911289 655718393 916561891 3445528 884224685 704424002 145237422 82831235 530039728 822984075 130000880 123996883 354527449 67653997 656225467 869288968 809984510 790056776 408700656 341132568 523997419 534293213 916947867 15106707 961728476 197997020 576698141 967006807 967627597 371671624 24002468 841859979 628041506 450678418 943855965 359106421 578915858 198521827 853549633 766588381 251614794 454945639 580247616 941799421 202732509 726121595 24804711 52900990 103928779 102229825 251604039 471689932 31780113 697250656 699339480 818884936 644895169 82803474 553402930 359158564 255003043 473680864 656337652 738462080 760691231 258415783 845769119 978162584 209368469 431142284 317586035 91018334 102748037 820960084 898026988 987356852 447587267 712055382 714210358 568910654 231369966 791972225 865855496 453154202 995468646 524649480 478492764 457546077 429456550 632829328 351730611 34386228 514144020 998414949 307881001 107482770 595771391 186100052 977342891 824437604 740104773 153689708 64015122 556316286 681343037 629422618 54193472 7934231 70671360 24058767 878371142 998620755 309037799 619746392 627038823 351264191 154712298 737185642 360075157 889679760 360768626 658498578 863394301 408966309 577304810 246935210 473863465 110046762 937399650 220678305 724418734 595267211 187965102 992015665 914842807 947655499 420890180 772261532 51442890 568368244 319906532 57698489 120260936 311127455 867174546 986448532 452861707 898421577 941406301 518773753 755440980 417204828 583318187 106267970 578876497 947284614 95852684 757595188 662490696 305401958 3603560 482915574 101252226 620400807 444242914 999304087 863906520 925645856 358555914 809849053 14250571 177191866 511407367 166191831 558833763 558544443 908403638 549410069 816027564 166010225 628233161 470441622 134172184 664122702 34413847 719832839 397126623 502976143 807197424 808060801 519368048 718230094 412668647 16262858 699588357 286333404 429080590 679818326 771844906 135642214 571222640 393440492 225189468 944932346 33046402 681604296 684582398 950371777 324749501 620141456 89810904 543626198 75225168 956567972 724599843 836454840 132875703 962874953 871811177 309228257 112002043 159578931 628378009 187006354 328098691 693445054 341757460 290617495 60660336 826455275 340629933 792190377 304163603 147906459 112270955 906910047 664742593 56059692 104899637 963455091 717120389 267258812 47505373 795883059 429022593 51747698 793235278 912207778 677990690 971472468 573420942 415796121 387158958 728280929 184309358 518686673 718024308 213618115 477694994 587902933 814104607 752242628 462266544 407260771 835524745 187421230 676098044 330604556 859987720 950729062 734144758 828895858 616090300 950117501 596438876 116638483 718882479 463981280 417629258 484159961 780311842 21483008 682698458 532984795 646181082 581165667 411383698 936354130 148066096 244481687 822149440 331170567 702673148 210486212 140549916 449477241 370866847 261665002 655877098 139717361 102575980 284860746 49507256 210355356 632808661 389600572 542255587 28537035 13654904 678007111 898386356 995126233 45423951 447755576 568485684 866386495 834586944 585573623 883813181 728238334 995527720 744723550 474202266 677058217 854965612 491756102 978504182 154191459 902070682 721896882 869931555 369857883 186902042 869579087 68205714 658582902 48746476 97655861 464587076 501889780 835969174 788700007 637815383 446947098 686641747 147796538 425006974 797559168 266888000 990869588 736171159 456244799 703770946 223631358 456787596 173979704 591832349 89058631 158473842 465176347 522304014 141286242 85825571 120935082 465524488 630437557 642625463 280162391 811642186 285187536 213983802 554169186 742701112 524070558 32302036 338502952 700913741 547287928 211468101 19804261 247035541 824086253 878953622 220061021 281018353 872202840 205031803 684249784 220680071 188389525 136135934 14904964 938012012 335574000 292202013 278745699 5068664 828200899 842120965 257110862 31767873 536493843 683273574 534921936 84374025 869124748 381633139 357300170 573159681 611062761 151739922 501886128 382603744 336348772 417415425 540465916 380994928 199232396 492603148 825584959 174359718 362040701 840542636 476647766 975570854 613869198 393495338 748959799 801651618 615270068 117879686 39673725 887929467 461503168 418690149 128739057 322089375 418841304 712553275 982641340 906465498 697911741 87772410 360216566 870137842 861445050 85290605 537869397 641591498 304206265 440308068 530831894 987488889 14514096 199258704 165598392 798162953 878090170 265125772 901579069 349721951 533857388 397701175 95671470 554371777 629197247 353588591 51766245 530747703 708750687 798185974 275831763 963054240 667889609 177763485 106733809 385991214 763921919 998573593 256767069 982667597 981190802 65098397 130023863 726194711 75453685 900816537 309857965 488890916 182493609 635641057 858358751 243659901 763018241 101566321 177526254 826446073 366236788 778511472 248278979 681598368 44894773 97127944 396595829 836277755 931366699 116012751 978225405 229868898 342934713 819413310 688046212 537103754 577125724 873537697 730012565 782024351 781720357 933225357 723322357 997393762 468749842 223808897 105384931 277475537 546381243 288004390 106762670 137786539 415457517 881343159 890355737 892854943 197153893 916228830 615026264 311859038 38470031 599505253 396180694 163980118 770569496 93833405 851282779 972000599 895958849 579743075 825000163 986457515 280426300 838584153 963317306 69820273 507173155 700837070 322982948 603814809 800370836 554079942 959861726 934767842 424529694 916839937 416442730 141722035 393463999 909093729 258604212 174787651 334344517 134543270 209290965 206731770 257166239 27757263 523497237 114678327 779459887 640500896 899002428 565050072 781967345 983143096 518264869 219875096 767936137 860656744 857812454 870356617 259010267 895547745 542126214 829048165 231060019 158156772 391533110 529448619 83797514 170625961 86872758 496096646 294609391 772449958 505118300 292346893 761425224 974195877 222044411 145938633 682202223 739655685 78383880 863970602 123763409 593612153 214640646 71068465 19297101 835966036 537058096 482815952 854056018 309974674 726416681 811817579 796862155