2351 39 334 550462662 597815640 806123977 168883448 824777069 702095982 375441996 116795638 410494033 617388331 395621350 272668808 930238289 815679274 952059995 866911706 404647986 262383179 761478032 86676383 815709467 904235823 73987599 263875979 905409817 80968639 451132294 966402776 844722332 327626662 208748872 887719106 843494392 949885138 447267530 490045707 167570918 505232887 120639527 889746552 766719488 177846540 445107357 874671953 616560968 548182987 126084366 89192421 645403810 211250229 323832448 739883268 542986581 50231564 68893341 242798211 556564877 771144280 986988596 229371324 566449884 602500579 161181110 210488331 954950837 24805309 164889017 345066834 594342128 183597240 416611705 924970613 964792905 918855404 416526162 652242399 374943969 266592309 941618503 983330812 751632059 516774064 105103231 37585853 346003520 270715714 914927810 330383127 343603900 697661457 347241216 383368068 343242462 469851400 496935370 978375296 910939964 303130200 204740823 123526157 901141709 164319473 106036353 491626288 982142317 63574797 160512581 125682801 871012444 528132774 614458183 911954015 27973823 16513531 58950859 481083402 30577182 740271119 140467389 793487239 844757220 822329130 119168554 62562416 610136803 390931798 444486085 144461409 73496525 739542755 3340899 800677756 529433532 717691619 754845055 410391270 676797355 967446447 583570871 221181768 295005690 434736480 815225165 226929998 823691502 511105622 24648358 80107563 911065390 710712757 507153614 726375444 817828935 676697059 386811379 616962240 793746218 630215436 241789926 359961071 439927465 708300702 772666013 257869280 952261117 17435341 843763380 381755864 61813571 248094992 150607335 611500706 36065786 977800354 280696729 511868682 398601094 96429058 97394512 207576673 350042544 520894579 202805558 685278972 601016613 233006717 408102554 499042997 617907186 995910762 310570605 817954664 467939854 63161546 422607814 668350839 28782033 422128367 220792414 825304135 101847669 842926450 66269461 773124801 900652700 341386924 452248683 188880338 455492297 115209534 124001031 478182635 221153765 66289801 695063092 953558145 852381116 456961335 819553887 766981262 793784190 995678128 94078874 615640846 465983550 563690150 128209436 607079555 255754614 995245962 542527167 876888690 613667713 393326356 292985217 576728036 96863264 766120895 353532419 759570406 969909494 283087946 168721933 318722057 946221580 687674424 128269320 480884450 773809742 804762705 148579714 751188107 54649867 45954847 82253230 52436769 779623801 154835826 345512417 882745156 132616494 391584988 771827222 503297178 932567208 757512758 83621739 538369099 677017287 859302425 607350946 806800262 83816525 106643302 807364257 67222523 366659173 522596799 849007858 818172000 711287065 866878475 118218820 778082029 925823963 267314934 169505512 302260703 684452861 408302958 138052949 576778232 116497720 177854247 788460196 99905789 737560105 490250520 596990740 241518647 477674703 221694972 63557767 716543731 185155855 623496402 944436996 507122434 4748080 127713630 241670451 742210362 794948704 868091558 559866596 491946994 389170989 574796149 489468296 222620042 343772684 697574107 389766326 950691041 864669653 478358186 238091944 9385949 352918596 379805179 722461883 102874599 751747706 143603112 702341107 634458732 906067323 275587279 746904436 511142749 291777198 524748117 89188106 145406896 431785568 206713440 172364194 252105692 133900865 168635612 407904207 305910881 352312293 47839736 574687302 730345022 867477316 716196774 752446562 275126137 562823994 963808542 355311776 938107291 708996616 187358555 230490404 62101553 217510353 924664220 240795699 312131916 528327966 939430373 304044727 920122882 762815835 105883004 339214526 581307115 470844759 532712300 872072699 158274724 52142536 863298309 10524740 7266383 141523909 778087514 741944338 25258513 914410826 875799233 160466180 54274451 343074231 706541399 260065884 863206530 92732497 125082490 460978560 585622800 802383040 696206157 842791546 844515952 580917647 817142327 444467321 722299741 17422000 72013156 819729998 782016660 757325301 489650242 749485296 264097621 847540120 121328902 572797944 929607142 791233716 209838885 418201638 479928848 576132041 245584347 765466074 651411360 871870780 154356391 601552283 256385255 994800596 472683981 729015444 850715451 710560575 855644882 308489490 285670260 238001803 195428612 912335111 478703215 20120237 118254576 984603786 970401679 879014653 773816298 209288277 850062135 295701944 779068040 113600070 927372113 477235325 527805223 991230942 50833866 449964753 711086437 701329093 75401491 348228763 554701221 226669380 195088034 848816808 60013454 749109449 393338735 763106600 283449996 239636071 835994231 384697391 73237582 621498707 37760829 29327925 780274502 274256232 612077124 354178710 858755372 871122340 447890838 661266451 694723964 919653545 22926144 117900624 400765939 95219517 761168851 240877396 640035605 882622666 803853541 422941708 17961642 967679454 449026958 970443975 260864573 277934252 862443244 4663483 63956380 161045386 131157663 120609151 342359899 418118513 670106445 33581967 40813393 469191297 853783839 642020044 890054936 578104442 838109250 333446393 833229457 402212675 378111336 611714623 138660446 595437414 66423876 526901161 944776295 105082002 107909650 998598569 523782742 24317976 823079948 685716625 554954266 94274927 169263094 501988635 915698792 754160817 684170387 566649570 406495029 301435163 644464685 356748519 343255613 111640977 622279441 778216461 678812032 713426711 446250000 658923420 256360383 274079577 170474752 554781122 63749891 778154276 502337337 933061645 548484375 204705003 128951321 993072114 401376265 940815683 829862272 860893002 14352045 251654503 89776213 722767055 925654810 518862772 832529151 538839204 49035051 886361646 673118188 169376970 785379582 345992954 150289421 379577260 305530745 594539746 327944536 665491092 281580224 109024724 855649093 394794547 367710400 999517027 113958226 534857501 819403176 68920644 535523199 38859338 272589418 236539859 620256467 168870295 965082943 22295692 735177685 107679811 80479776 475537042 272945939 245814130 69681997 159142187 754799519 764640430 593861066 9863745 681964940 998576737 972842973 874066659 554252406 377064027 779987858 810024386 393207799 169573458 297052471 573621684 260015155 836805213 694683616 530245685 76141133 191592825 766713316 730185697 840953071 645889540 774143838 358924027 977918663 599421509 939894957 48385514 982627076 931590882 349169908 367574454 234879965 291679079 619240091 497083535 889471754 883713734 490283980 589018183 800137289 673328082 523942134 582137555 772793306 490686403 381934414 534281933 153007364 365186229 727267657 625273845 984114830 9723944 362242852 803455403 202191686 817036673 61330780 473102199 679855742 700866184 208567094 551813506 35080841 187344361 480480568 752045850 361331011 204684723 39426990 719240498 985606791 888551899 667855142 61231839 430354102 816923322 212110068 965019100 255153462 821425547 130760623 161606919 793779953 436023534 578353586 112705762 871992530 851955048 289080732 354760723 495210060 842965473 798613200 288782820 278868946 806181412 368208886 783389891 995273568 521148258 306004856 761653443 643965169 641010351 378931206 603482650 461390086 147832196 631861523 162451873 398763813 271242811 562824021 512772951 7496280 467167895 825315656 833293534 200198058 814547001 448788908 598481404 128924846 399711019 359161859 168206620 327965688 397459546 626916116 247439819 384116129 200608276 374027627 664987963 887971783 267839118 106901462 629642947 888306442 943469152 860708329 690298460 416066321 264088326 423559803 93396774 59582211 389142881 284387367 67611617 774573583 990058548 639577036 317857141 372506596 232342697 513932558 267397482 937017657 952936137 897324242 137774192 407302726 105560583 130342342 169337561 224196937 920521142 659063511 904043802 886803715 274200462 723235768 160270926 62467384 261397547 517833570 591355058 345879347 350539662 148537486 711861802 996712511 874487706 349568573 571649211 898716719 880880792 473743409 853650191 355459543 551943092 307911537 142668532 156254096 185068925 523666121 369420253 473576376 176387689 493415239 597755743 292191024 65276750 954003135 991574453 12220380 108960234 225845832 781226557 915758887 25680221 88326845 483474937 47645820 730486442 68843838 976966159 649639886 659091257 56862124 788655690 603840017 105375576 493481264 848894870 868754878 353776821 694696116 909683335 261431123 698321126 467043176 938672083 519396305 13569505 839327551 609979091 703732028 287243908 795445615 34356231 128245023 154225934 427960565 607755663 210177285 444874148 544163087 31994290 491987201 38393037 453553600 895257435 303311911 181640183 485694543 515254935 955225360 492042736 436719048 601792280 42575962 716094829 533296505 439476405 669758246 300956550 481522038 892769768 781447577 172261432 172545303 628849230 278631259 423955170 471970677 922743083 264140315 149929672 568778224 954234851 346348552 207115667 565499051 402535554 425288281 4940751 647286030 356213813 307022791 361103212 346190404 429322191 362649358 769541694 90654139 933690437 980099952 213078653 246634406 933651762 336159537 155733318 241600894 899277652 93429276 504790295 721938557 358872845 759025148 33590359 350747681 873073379 951568676 814763980 349734063 831701504 110388456 830490915 458042798 60248754 38289954 272089451 985983080 466239212 172164014 80821146 344261228 392069828 110009069 556251399 662921743 495232243 76026438 82811886 438500070 241163096 158421409 757731311 21802061 299022197 35321578 623600272 287685091 913276144 338674836 806661046 684737548 601469460 94507027 389016624 93181550 443765325 959062625 67467820 683140724 376010416 72773754 273486784 361335246 699836016 610493407 961672546 909259503 206585706 128196375 75769968 134760334 766264986 573896746 553306026 836336421 289874596 576092964 335880627 110903157 821725772 805867160 217920915 742989568 540036862 137276442 726261048 424460686 663934791 976961732 569517040 707189417 779933529 21807538 653756144 786415648 308265867 661996678 941976528 578935944 454420695 533412836 366727437 599611318 536640347 615912439 474922118 419674950 669818584 518218475 628516864 409496856 911718710 992925040 847804322 837478349 283473150 437591870 7844473 279489358 267612638 905938315 731093749 856389446 711945001 623725462 739165034 886225827 300865621 117925664 136695953 551013145 800297339 613471982 867042820 730993566 820410842 312582985 108253893 485160687 26015315 159735421 486864312 615087370 114829294 619976029 64235556 694223026 643982421 337459133 989374006 236744175 34780756 737804535 643965 711362187 211120735 824108647 110189935 316756117 175121676 941673455 987370467 366650594 117940628 531218548 579430293 251736967 335479383 726021214 704367782 658290272 943420757 550028316 55384345 309884813 359373493 627292318 877679447 283717616 48962370 43031001 384124588 429623728 122982120 4761927 526308295 602787512 376962876 660888676 680086334 846932280 209667058 401396018 642851848 509025315 89404772 306683574 707577857 70277040 290163986 177308025 18817129 366217690 345248796 443387911 299606629 332555488 812686282 364795251 196393853 158843845 767055365 142560721 710075421 163102417 178616795 432378043 296762388 8748558 276449790 873984461 540485911 960892363 825422662 646234409 366559039 944461597 903701291 387624436 523518855 782344793 672103499 239491287 634611279 186144156 72668394 323366527 537042908 610829123 730521965 931302941 894281429 986209907 574391006 257529318 288195783 336339346 838102379 792014228 646819 832459468 799871719 582103779 785018171 506339983 497509192 996607509 509566920 514436623 81069351 311949423 731547239 380877251 829118019 631436985 662111383 10207206 530778110 991460802 333245372 717214455 472147934 733429978 636494752 958491193 479574542 501853271 502559469 334717492 114555354 662875152 546727859 814673202 463326775 335584229 642343400 962070979 126932536 339946037 543059940 903344953 147503002 456620646 526002401 104507948 122990905 687170912 265969537 858162936 522600344 476987922 875445831 76407866 376858462 356023788 662864924 156443991 194997203 981762404 633824460 697711861 366875495 175363697 138460551 167247744 673115692 734448915 653487456 737132454 416788055 636118473 737959889 673159387 165560515 300557337 781340469 330359254 149971821 504026891 15830349 407151378 795020793 124705710 110860732 496908110 558529068 380767634 748186763 865730062 167336048 604201805 120853670 650571288 513470547 27427575 774567516 39780855 504136968 86245037 814531555 56903803 339462116 883517713 876186065 860912950 711390434 8732616 377772964 253207809 849813280 401444347 808272444 425945717 592878432 510714071 425841755 777946227 430810760 515432973 744907052 628899997 927740962 94341714 448421561 282287066 695829213 533425632 228085876 877790934 189339914 278396659 414677935 528603263 202806047 229484622 675098659 456563849 411566135 504663476 21942893 104876523 791663761 105267822 331989132 316768096 675841549 779853259 371102821 590294503 613769906 139222427 39953471 563724100 63588651 396926644 73197384 682272380 11384132 480187246 112779790 865250909 117771890 62129190 783937286 431409140 487620169 715855294 9746696 177334036 195497219 975560731 69107152 135898838 747396608 85421222 204863103 327493139 996014656 581187276 643369497 584259052 602800363 260571774 835594245 192511043 63088073 678722226 582318224 243973183 217755083 156296672 450615658 862159564 894384000 213764229 60398119 446772505 877676448 794312099 416258239 640062744 526752645 793569599 962366990 305847297 697598893 796559586 834149461 737625295 690713658 240595993 452373943 580519105 70265714 688578806 112735933 222337499 562419775 876594828 814304467 240232802 361057967 2057078 824653000 378264164 353141365 148875344 798715218 99787822 68582758 13185085 179408264 855640787 516273149 5856608 69913446 446373292 120477144 489073507 923832908 214220243 240047161 771573747 441633151 997187750 729343623 295429441 951565991 974845514 414512330 852714114 126705743 868086822 819417138 400159856 406293097 318093156 200738192 594570696 607217863 363863411 112354778 471044554 52029347 685787271 362183340 372454588 224292888 229314583 982783170 485892199 699687078 383826783 283722368 792637080 715287474 311517660 496469098 506894753 378246147 414125010 421562284 239106261 197948231 43779785 391047826 555225871 687560332 1993228 326181649 792077100 365914823 766454569 625801533 599905932 511017296 882229363 814323665 470385045 715420772 996222851 317661866 89004080 841760162 493919667 595744588 327509066 205095567 146805410 570312027 591870549 708149522 8283827 559578915 723017668 255197688 356562829 814111250 213678482 373670769 546285724 514415928 409763004 689758609 269119375 590351822 873119426 22374608 160527064 334158252 170188330 999172234 361594927 247209425 303982845 203852672 564231951 874109662 578809160 585187414 198389560 542387099 450854301 980982291 392453931 230042481 260863375 70251684 975795889 382973167 549310009 805283160 861709141 259362374 456780472 969793893 174687973 165437389 128801452 512349282 507106805 913020029 672262332 350239435 400632411 494043765 33943823 841519233 328092084 610949495 807184339 421532487 831542750 972575081 330613177 848766278 104719228 649255126 217747575 492914057 82594422 914275691 672540485 681742466 431590518 598666874 318717793 338371715 214920043 108999034 882721931 348055110 532990474 852698244 37619593 641518438 304306248 893762264 618175652 861707492 368693217 858123606 479800361 885116323 576935124 395178758 664494314 516542187 908965349 110543248 17703610 461950186 453344538 313487813 846215413 841562926 369033791 87027220 498284789 644020524 498344290 529998613 966284958 952328381 628073303 64545282 547813075 370880667 321857077 613051193 700384254 34669289 515684822 971722428 676142732 416028072 393776219 602489520 760866671 620695363 751346854 824344033 323884698 963589892 136608991 70040637 189796745 837434780 124294896 141040981 840491446 576947615 710001417 289343199 310352677 119985669 463089692 433973558 283007705 151617707 850026081 190319576 383485276 935554256 107084244 657563111 209394491 173302168 4991154 352863401 342438792 979245709 742980608 823682056 756587607 916840473 139070980 744043795 55447873 461522956 788116682 780830331 822597604 539356188 361782432 6694167 517835872 877939808 48374938 399466592 65815515 378855381 911262991 375375606 87303935 439716569 264744986 286045465 363355767 252789171 410140698 268323120 701118325 364732169 780775474 584603718 95150639 782795367 875875529 296614536 281488989 439471807 428821516 711555016 965185981 875500772 152458855 797028861 671618704 205497870 732374800 998007745 858879002 63786585 292664956 838941905 668103461 229184837 696494824 482393233 289206910 301803575 996426449 907510406 822126455 95102711 806398332 308580569 670264932 799141425 594744687 92100827 99670814 816504820 940391670 100301179 436661123 752548405 454242463 633288146 703179251 246683981 839797694 23481752 184161749 262357623 978995434 211783083 191931920 59278931 952022142 636442255 441435538 37987174 6421785 558734057 838962637 116629144 61340190 905694723 960874805 155301300 255966261 47034956 857441219 255539691 194554824 666013141 599002485 359001681 722523527 321553108 65834187 832592479 754477284 236909605 535594828 907994735 332293272 756563396 928508415 404278852 745039644 913491284 249985010 643417471 822921009 597345435 476587191 159743530 715277401 337913347 112131298 921429298 257501531 308769563 415118476 964401893 569796291 782094612 673134547 992542584 681438047 523536197 396820312 985665411 203811523 830361512 518463167 75484290 633964486 820052314 284857138 793950550 548439811 548069663 896337887 953239746 78438233 844620251 167116917 351016432 662251627 207271706 376524203 623075049 594878241 154653065 594897850 59329824 596975653 542239610 629355230 213266408 149696615 967979364 957330392 166660345 745665434 852324961 127371887 384051951 120673460 815012527 304775146 569174987 367194226 370294832 820858263 95034736 623381970 354781417 908211016 370499623 103841943 114210694 967473105 967096604 545628104 263612885 641289611 820294366 149069873 242353990 611965652 960145379 805542112 437881202 493158541 948252929 692452777 435396241 469542042 465212918 555054499 678430722 550633062 724055522 673665449 370506439 278335836 217677256 986873562 58304006 497764719 53160209 74478362 905603465 639658387 773668872 319079311 586711103 745440833 240398430 216951076 410235065 365406199 534937512 442225929 915617710 715406262 673576412 539292977 548248183 993068931 413165528 242021074 142347667 595311334 210811355 664999657 894505252 805545325 560351242 69536435 969547633 359156522 245230828 970386997 848085858 492904241 143894511 267463862 299659527 796640796 576782817 908716352 814162962 874019463 109133687 734471970 452058712 761606547 482650057 202642032 677688915 866429799 29976788 195437185 578053539 662373290 292872695 953179248 672479624 906951691 556209782 73125789 285315946 189019834 257406970 384933929 611860818 438917868 437001487 128657277 881864302 820164442 14504869 706327235 982479760 718277314 672602512 227605355 425280432 610152549 242672392 472550312 669501542 665628295 282001194 532859633 466369137 78218483 223688308 978183808 716264498 2243956 402452813 535599574 821178929 793034333 339751547 127469877 246971287 12704002 636517803 538278437 463943347 804092989 197862380 283564016 470996854 628065514 25030708 878958117 685067254 52409451 384036314 902099224 702457582 978760484 931030810 973327969 641362493 298220288 964696981 692017497 372368739 931552234 132354766 649106336 906949639 889465941 350025389 573293466 869124723 840810421 983681024 487562477 207763478 748799236 443536629 213400836 208730113 975716158 910462370 327789455 622098283 736860645 874924158 155105025 648294957 108222333 164558052 217043729 732010311 366410769 281112983 828152121 323788121 468815277 216974649 954899770 786855211 793708769 704934610 517689750 441033765 992969028 178806864 919813653 203222231 206332399 992012033 676887105 849660275 879443966 412779546 36282857 471849038 891441427 77792051 919656353 360280675 300474323 621928137 432616257 54595023 104918118 22718651 130300002 363128406 871299323 255738062 927674084 734665693 753013826 46954793 571082603 636603630 769409520 538355929 198822365 828703031 721274175 341842510 488703461 602961419 524041067 656075229 984594804 18901727 302295094 344644668 240755002 193476046 378339940 950173960 241739569 269499414 626991168 899694402 945444115 734574745 763248150 109336014 24191711 559306333 120930486 915674099 292977496 222751500 32918520 707290078 125040262 872915317 140546354 264849694 906965555 321426441 636721091 369458985 71555182 800811871 275959692 12718550 639948812 803399856 395898738 45301729 592402722 570077275 380593630 535608683 9406860 408077410 255754556 840085111 627976042 225567980 690528895 385997678 567531933 745231041 601150876 441337756 159625294 824553425 462825994 125326257 524099944 385922477 451975496 862815296 139947289 988387852 664200535 318825027 272003157 591865672 379857724 897067925 737541459 787171038 572556672 891041142 593663502 304716786 234450608 48796427 398931653 524525512 96025052 588241372 176183419 468753996 379237660 668544597 369820535 299648139 659340806 576165957 856108486 432571704 31649338 721770337 242528180 392500008 349854167 62408642 174694999 204652502 845245442 901061219 923241476 49806304 607175526 971897252 451198167 880919432 899988655 231226314 691367216 282676531 469590286 250819964 764660785 77877742 71165624 542405191 17875521 456867812 33384807 747905820 128890251 418582249 756467415 213097677 806507648 196123378 862214474 728379027 345650257 222601371 141780997 508547211 218265974 934011296 910770641 904724532 999468585 735268708 211499899 629564658 259454187 554510701 567590996 922360975 225198847 918119397 62607025 317519285 462123242 38905371 650630252 853858932 741863674 69524736 564150625 174617282 645271483 590864299 28570098 989882103 627261571 114540501 369089412 783809613 431836135 438060638 423623936 32498022 764312132 101723590 575312210 959168197 605340727 855749300 574128621 597858643 978098981 280752755 607754566 653389020 700712372 883295600 353967957 175186576 30187600 639651773 377677335 485991298 732376999 623482258 968023566 481937708 358397229 943444934 874320063 847899625 702418329 642282586 20499763 21568890 304094566 116272879 584882295 509826946 519804243 815688010 900679708 465332234 104165604 324854231 941728439 89666558 142523102 133127203 273653346 240902573 162549711 378756449 807692089 123429197 244021379 222899942 239572446 794110324 103550608 744490158 615085046 121427872 856315083 873828820 303573674 172583089 993772497 765408541 109034791 682084202 90208896 690340718 410245406 908906739 136367226 26462290 447829316 360495449 396158633 489044085 356766163 97368589 803352501 268390955 45059336 534967393 92296848 830704618 65505699 263728654 421153515 490027723 888780138 304021425 956669374 121222413 811451814 766045001 438054340 783384722 21350308 454266555 445128188 665588065 467657013 633904206 758106665 240709666 609658158 394302768 505153363 759226533 443190249 678711791 481438276 803274331 764848579 486685440 197236236 374818523 33268124 743498043 766569598 909336671 176384858 107015260 206801073 624256068 357732454 309971332 701679487 319899534 794873388 288199095 733682697 949711713 37195936 335174236 252600369 976695177 197951156 142759872 37956894 195745523 729683171 241126291 191403964 682321970 82152874 620867433 781453113 158816251 845526537 465516346 245344649 742541225 588866566 201276898 638410212 709149625 14967082 619107234 371259715 832216143 284840194 786648733 479679206 216629168 918793631 802603356 393687248 308366534 168472598 521828683 462341193 191274399 145961217 729390905 332678747 220658158 17388797 184107484 336675926 551171977 921999146 388276811 817192525 430201065 788421038 472048770 580747159 522166189 587902002 188222433 841910606 258426135 333930595 994041773 101174995 523696781 886321778 809097614 218795080 130253849 783459733 444692495 775611156 403941610 377958532 309080354 701322339 440166865 851636220 924740249 297708452 13775813 442982720 690401454 633154825 73768031 514710675 641060476 919168522 900920927 108427199 286390403 253450722 304572965 775535249 457947432 809362449 368980024 592673626 116056882 529265880 458835907 489933679 517542991 4654016 349488403 480133546 389294989 722563603 316698138 491903208 55042529 74354017 886697199 222048393 188440227 44654589 393030220 919183091 45028368 443183998 177906191 617960975 354385351 681516863 847492537 403883979 326712653 891911902 590361842 872860310 256803465 150828224 841473027 825123814 833896008 890376844 250736218 678188725 300715194 478750124 775102730 781276672 530109427 475597775 812590920 285276487 555219051 681839978 102659311 728558352 634694526 80911410 246732541 627134821 335182829 544699811 437069844 526577233 908995676 599805820 107376378 180280934 937058770 771066433 89546009 690668346 28610620 667660216 340802304 946112997 616311017 477594476 736987360 759633284 584927503 201304366 869767439 507730874 696968773 191771534 944969864 518276394 102520583 821995110 244530538 433885694 826097462 500073296 329684341 155253859 512584853 408087083 459959952 84751114 487253325 505404314 886840133 63106473 483776617 879956868 552279875 524478328 626313819 118808981 336288731 548661685 746903414 596631484 822754948 23368736 122922609 45899435 550959960 745823103 751565546 976161883 264478612 653049883 223389153 620752517 774446108 183321154 553196601 793620265 894960116 677140675 444378938 816533771 637163208 522376053 47096082 280368689 109395813 836751280 622774607 592513126 425914942 127192786 229219174 514010043 74881512 316769467 871709488 804920577 253418398 358927953 838312807 917776463 87912893 679060477 945197102 135654786 386797641 921297965 579188614 595875000 401430375 99034576 789165530 998439124 73348577 297943261 881932404 944225278 227734949 193483980 359472645 360931360 903279686 697083675 193138977 35925353 689259897 772243402 106009792 625263310 52519322 344396767 631961279 223274116 732048933 101062115 496311901 792952456 440775229 879542372 664780990 694652183 90600232 637340273 846114156 776757558 679744720 192302625 892230865 611858731 421974596 322661132 602821309 208049921 188323893 16850128 605656806 364010761 950886265 566109581 104338787 894227028 973674892 756918890 371287857 845363513 496640778 894742030 155401902 914382805 906973238 458475815 333847073 765869702 686424439 517283559 543268400 932002416 936341973 796431745 792219751 530315768 75447680 169407153 210331064 984649547 482772554 644920881 212861174 945869016 962496552 145895493 704452953 96824274 984309172 765950000 354683645 371582639 911223982 903722172 200072546 973834155 209097846 717135031 955528173 278356806 911578260 763807088 926282854 235561154 615619889 688676670 444852601 896167590 262496667 287134201 841802549 818249533 208373445 946670463 647360911 208397592 2695108 786977329 387017952 885086600 955821139 336212339 827107427 957761317 458187600 375178287 574510776 76784202 678021949 621698387 871107172 387332502 501663936 359442510 266945103 548374124 677479715 660750743 78239812 147957620 517487828 80453414 222796660 864165656 446642150 62288121 50330355 416756232 501131407 107931025 618092602 844871606 245608360 549962866 499769251 92158683 489272112 922093734 839159025 627758064 63079625 421160763 514237893 852872118 631876153 309679040 843591722 700580270 290706411 730725580 583420682 552729250 363704172 762156663 221591222 214461722 901645294 355508447 675478882 410704872 210734280 625666213 256383910 651647133 613840883 230253933 157179646 442447377 873326223 343301730 938394699 596758751 355516252 724409519 564932177 645330918 681430338 520931335 619982903 861062345 187674569 999634718 780503049 649722992 341175713 277059629 542298425 744523653 290037532 555324274 675902234 773601528 4525743 511517614 913806692 570950780 55263093 765151397 866802867 907286791 747998635 685774241 644622600 740508502 165102901 711093232 563320390 758369382 964852248 657419105 729244854 72417276 256163070 179083979 247624068 386168607 580761525 903145095 910894399 841522840 998333360 689210609 407059549 65283961 247306372 592595690 630592436 73947539 487277677 800904281 835884290 256324606 917716678 840493221 857143143 658264981 729480852 449438013 737926118 684215671 20950780 317114896 633606120 704854408 258937289 343301141 590102456 131334893 337561575 134735813 839132935 906314900 808581610 581563292 984934762 199556522 701542024 30437531 520272087 459012642 289792795 419876041 427058732 816893749 915408416 573107117 506018216 979923933 814433210 580446422 436544880 267361112 820450351 954901075 703856139 796233643 500878954 66262843 856321255 447445533 623744632 994695719 811194066 357288375 950639627 375351219 257895041 242905547 495009018 818901249 736739596 426618986 289779647 104580661 833802352 965777132 620133367 231887610 929886220 624918124 618675430 153345787 892760356 434119754 923915248 863585387 962990945 516507815 978215713 209008254 95822159 562615020 708821414 757315565 431437022 156364355 702205522 245688182 930685922 922147356 712131610 443234906 403657875 631010986 815739033 275971294 746846734 468216676 804185229 986875082 970241234 826401156 804288088 377570797 347680067 766419595 64183424 240775831 231505450 241413307 820592687 251698205 790251315 238167963 785611187 835385688 131074413 788744311 161188095 363182886 150325198 126670046 655088169 471361768 430272941 795318562 996808170 782020867 664754502 792202459 620561441 47935839 680366650 490181477 381925456 148181483 5977612 250944093 839998493 171402518 450429604 949128743 520136147 716052568 361745616 636577387 596157150 578396839 956805822 518043284 641769043 825037570 836193412 263325776 621043045 594394858 301620889 72817683 972995569 536045796 20106840 56110995 339591923 799353592 23724676 653072461 320638735 204898613 612882879 824303615 18539273 273983019 691940625 801940780 794134605 862285679 618941544 892310427 889204072 353657882 862288658 376581848 685387916 674750282 640729156 86778546 109025808 27508896 45591447 536845755 923421422 849518273 299665797 687669708 937331012 327917014 257177584 227790974 897376979 250468875 720254620 261375921 988311427 407758867 27144624 258479625 914137565 66354594 160807481 131016044 328411535 671096306 601325735 990871941 107610092 433692223 388592463 475006020 565530730 604681803 321114855 633059420 962003234 512087771 266077964 78134212 496548691 597294135 835472575 921080887 683737055 85599406 73157348 744578484 686875596 739570448 867807426 156447486 742480580 442466610 205604486 470018076 416249237 967902318 149497279 826205914 169398962 29812768 983133155 940579143 427477169 625783338 361124553 658805813 996371147 973143920 448319277 619685821 805666656 791112797 989395248 707745208 774341232 742386013 91954389 608491078 154661410 140963169 477410437 443408459 477474625 534876766 167056268 492757485 113268153 8714701 57121946 881981208 327510303 69513517 660547138 699624954 497526567 55870589 750713726 234962311 712425515 26835650 652340777 900722678 963719595 907944583 354869123 164860225 652463815 643348568 452929713 189032361 221067975 569611590 238453563 244453937 290409876 749982054 207924621 468937502 124746812 561192018 671437686 562375293 287653745 876313510 295866027 783584925 87077899 66765188 710254405 795851921 618259330 229855505 653089855 466984623 684942964 337594101 35602425 80487699 675718437 706239455 325121720 857024541 974812154 41297151 870050083 329657582 449178109 989373066 49388231 468608496 16506205 204757562 389527701 565715275 158927338 452692939 978306911 229301104 381927837 986570623 858490974 165637010 505058574 329149083 772939695 258471976 594591228 38485992 619039441 627601773 785916361 937245235 166965544 983974368 623873019 547039949 82700414 470682820 555755197 760734731 406507389 963758753 106553691 712709575 49826358 99828161 496434890 314788317 735746204 924426932 744666141 322111151 335372042 529096397 519644433 292228514 715922105 924353698 857112706 877732767 771702347 343083663 322859764 255890835 412975171 418841908 26711307 510457071 797393290 252025843 265783315 201381416 697567724 90636147 579391609 599137592 540883609 63365152 521997903 662725147 795520164 747805352 689852364 167335251 580206983 707026559 580184522 198286949 780393374 769986652 182138438 622627418 111424679 311305402 581444324 192795199 769323080 635197016 717020009 497911717 140535945 720465081 40672831 879127329 3202134 762326693 929938164 592029901 806906366 54169254 360817851 640441542 254671799 755036044 248169705 91074476 434915863 782343402 1012089 343827237 551942812 253199254 143513993 277698649 783111206 833981485 430520283 780852855 286486904 162798988 638913877 2471215 327417786 343653720 71154561 240950071 781759737 641246839 696390414 656532679 22356646 925400981 72662093 182433820 839688723 889206177 990422452 681014264 381959418 155831373 275607135 285025824 423695349 823744145 730033802 959599069 919399686 842442536 668418584 216838268 144728593 578984721 398863631 724408782 112395101 580622351 675668506 198727848 403299352 75752746 863474949 360490852 612555984 465799980 752958789 156975711 77812730 386109733 146430574 890338937 311951470 901378792 352221370 625799576 31910377 856760715 623802761 210059557 807861641 688610283 707202011 327458957 711678037 720596262 273258200 908944833 396969395 846396703 868077641 652330934 294605808 343499005 297330972 218900710 272515260 214626732 579933155 923921870 405971883 419588186 934538581 997793134 827866293 463494907 828431052 942058956 816954550 237043398 381575366 480294001 486344175 637105334 554277221 937498858 512819331 180950539 992414959 342325576 185553659 469971142 851572814 42220193 778694851 952924208 882413456 279990157 523246762 866538835 109747304 762350249 147157862 72583551 105638571 739193623 716177422 900459719 179447509 669809916 109706398 795960450 372960898 398764545 424790134 10186 486101749 894173651 28133083 686573056 287481236 294561956 533707125 11133254 306482281 9612199 328902351 556378371 116663459 194285975 519979739 122684003 39213331 558526769 814290283 471491285 526976176 51470261 157674169 917478539 683928851 818792809 161340384 252447997 301918971 521933846 345638240 130926950 134350027 65878921 124481438 208203077 268279047 765286419 673226593 143122142 173118683 816523018 995311191 316998583 973025940 580154694 703988622 534261531 695865380 244091812 27848187 413425306 732198818 274974087 142248182 196310151 757731784 635525970 385499836 518880377 99775603 845164271 445869804 903528394 619393831 321356363 256290571 248655387 47647113 701877207 175514368 433745358 236062178 610930953 961339288 550969995 705234339 873217753 595745539 409967548 550007259 657868868 703129941 199578384 524743619 288001741 310314758 696275195 668221747 182264567 108176755 127444789 876366122 469117132 612411226 200034103 492750409 949051481 841583458 303019713 797204824 149798959 976634513 392843351 341173697 884477924 796322516 694880191 643938320 737081488 906521978 863526532 981057145 634856785 192943033 97681014 521860434 553335239 342611240 464746024 314241428 110004376 973803587 286233457 703978334 526742509 724014827 826940396 744920690 911665139 14939363 447514999 447009462 416500060 991416404 789114040 789464757 849717723 13609033 364070803 392971804 772666027 756669748 206517173 428350525 208194825 881029480 890938637 759506063 857764021 506032028 243666509 840385835 661681782 441723246 965461869 267502929 498358931 311990750 651289641 592069089 68453722 522664911 724373630 92639715 126237084 917971593 853345585 620388096 912880431 70351418 438102600 350095366 299217771 626935408 560850318 458477415 542386606 704075936 809301779 80598970 898851288 164550307 614792106 231076409 92351695 685812020 977661802 654401858 789448957 271534195 736939566 429634775 45941453 235013220 383895061 493276445 518652209 641183089 598253570 819813088 899871263 781883108 715066909 777622030 263089423 467668334 541424208 350251576 786070911 790328227 574947018 930326804 69645167 549224059 805660800 340926717 269853670 771881427 215148967 378772849 514550123 212426986 391960635 399359378 461726860 722286820 671863932 249208998 599113818 718154059 292580204 443029143 654677227 117540489 567403346 554862196 323376599 24049262 929473593 962596590 410173116 171127472 97325681 638959836 855031739 49465702 880022285 363174327 305604088 457266061 680508004 541600287 161528861 521684356 543520401 512223316 893104855 111732111 731447283 780777661 487001944 651535959 526634413 483452005 130685908 83850599 30377511 606981497 386783748 845263281 203975563 139026891 699431334 199872520 414090825 882408274 451640058 92120996 574554003 174595752 891927366 212457121 672226786 531232650 164857172 217712767 880797039 550223708 841169903 913420451 313172155 499854755 281625705 509657301 940688135 625344648 38800152 14771649 433797853 603218780 768575957 496136566 25472645 376082702 912184955 983651817 6825616 249458871 974669166 763857267 313321042 335127055 586047505 321682767 431342175 306263028 644314447 997893661 620347157 960620778 770234387 387243106 819034386 504363926 399964623 330012934 6093242 652750146 162927865 476587988 779435442 546031197 755177354 469905917 798223720 32878840 741155709 987212949 104721288 88296777 601450326 310922005 994784136 597584940 37459096 603549144 957679133 127638941 424480846 89728670 178082756 311499071 56868739 324490507 411997498 34184408 547140042 489614633 932040708 756883154 154827190 176704994 558635240 634118332 937460579 184722311 917805682 673827271 653724396 869521996 663161713 88805194 569785074 9183945 426869111 610813759 13102876 927711354 530854236 681255619 267857553 685894208 674935739 940754586 873551487 964111583 899814259 846602152 90307736 657744766 409019943 429556089 173183376 204181545 644355263 216443578 267763616 43150930 899098085 783767485 966747398 927445836 431179913 982356729 696308867 895594191 283299934 871104392 414122459 814391159 720559706 799521704 383372377 447079749 820336442 823227707 297996616 878847004 770097659 551090758 788388987 847238725 249230434 596726645 658872006 739073772 273583989 299419798 591743106 692009632 643466752 574981402 86798349 292668887 188858642 561291927 48229448 772907367 198511741 384671048 605664023 516881679 593904985 64814219 960492516 41596396 165087361 418254178 612894237 192481028 567673620 170657011 496194482 861657023 529562357 621884168 394645400 881395816 830306636 617535120 172696136 357254320 666783492 493834780 751916096 980373036 926872394 817395811 903388289 105948882 679682068 963745470 274233103 195936640 205675160 755215276 828979573 22129269 626609616 232173904 713217854 630780886 401475837 166591470 798639229 591826986 263640609 343193713 129146438 67002591 321453699 540059880 811841842 118880451 847471407 236281093 250139103 400703627 292376948 91537565 142094702 741912911 245945700 719728682 387211779 577146636 5123671 313286988 445244233 448192801 162426216 346813763 932634859 23171794 786190838 933536631 195728156 922788297 428200997 113033713 672746256 70394511 961303387 640609759 357580161 701062935 327924931 269565972 620583211 92900148 274132941 747854725 466003279 800604446 821287596 639189453 334638644 934915058 901102294 777188778 848574881 334742063 653640584 480046461 385423717 564290617 43711552 621154766 366488528 390692057 986453825 854721990 775855159 361854395 316311570 514980788 536831347 847092718 264061439 758859145 99159650 247306344 279000215 967554395 689912933 960571008 572765228 921247717 805260257 974892658 849342038 733945606 853587646 185756127 964384368 50868286 457246955 425621066 955256346 447820596 408182488 438940571 387790261 457891890 829757946 314222240 869932266 810485927 714072906 98972551 195552547 763246500 148202438 732961894 815555089 818099808 752155375 629248948 608912932 444500148 451968330 494366413 502379798 270590880 484304095 923711089 695134817 309866948 12388285 831152965 2535364 118248936 896269428 521303120 178067906 924090228 540954777 955034496 58374690 943755000 961294150 948182563 591405680 787560614 677128087 855833966 336488571 582719187 475205422 248677114 208447701 388826746 227624623 643127105 306939734 727983544 467593797 627133477 102963610 278657105 155392027 345430378 380226942 396003370 207971556 252614455 198324646 452123085 690742356 34099865 278627834 559718632 723642277 728867841 274422309 182342862 342929427 726565313 142763029 319491828 176548192 890771602 547293310 947575669 17359441 218981904 493129047 205734287 532571950 785785660 378511451 600443940 757368390 153180922 316978056 822116410 263168105 225342097 449361316 934973307 789972844 90187822 310182067 434415286 464248489 4825440 361781890 812278364 4931452 312166813 690302752 859738372 418745287 278616252 78535519 259400167 567343727 379357562 298348887 787846500 153820124 507030517 461682916 199554429 766897277 712240179 953200675 307180121 926907714 908113052 322087929 164144320 938670112 887999612 893406348 329864866 453390993 828455555 575908295 445613968 350997521 625402692 128387035 813323585 835435170 50618809 769546681 845058063 533178185 686147517 775114648 636070775 545272462 392583825 359291253 402867357 143386368 804491096 300827534 214842565 159749039 55228314 930917606 986421211 770618032 521008069 936136645 856205548 520000413 70508967 307683381 622044331 701479442 911163125 932940422 582109677 806971441 993302984 160747466 254825517 838312735 627789083 405450330 20613641 478751621 819306830 39700047 892805571 111622671 592828582 417582089 434760129 736947696 795602890 704470188 193665293 244305757 573043272 140873886 140672981 250269197 715189518 484109323 257263084 346481600 150398705 284638561 739173191 980911797 4472105 633476564 345009282 772143666 824397779 68996059 530096473 514076415 369741934 461525937 544342831 399754731 106265182 331470293 314844554 443985990 22698349 699384202 139348628 984911973 364850245 832939352 516780444 698486818 760254199 946071433 256551827 309140826 676140407 255981741 113054608 663233133 550172189 134002198 500232012 964593856 423314981 271437917 375524263 85451582 764598320 407409115 353895201 313043 563243201 524193585 625142369 948515568 998082241 724602817 613285554 872167434 667951612 162544178 66768513 561548315 22216098 155713263 254011361 292407072 648814278 290323113 2169095 512664473 719740130 366076625 599914189 573081867 870963282 53869599 190798131 477278337 722934996 693204238 70232538 582036231 17027598 276250205 269542535 822043182 786549768 711538063 84253094 797542540 804474798 790733164 681067716 670137400 975573327 734486654 690443028 708670802 991329569 248855957 73161708 873156217 906937786 679753796 166131525 357137235 83335832 535771489 236649022 207017737 203789467 46940040 303858072 175576264 412670598 140691353 145101883 627893825 319456641 994125110 217996721 165631529 491175834 634693446 696264358 986378426 807790143 305206901 938544494 240579120 8111301 114700209 56179839 77729613 149423333 894548654 434650866 696044502 665574713 138921571 31825158 298981140 222058947 521980299 767436445 851672148 327920743 302398246 433143230 401782631 960001900 896513269 690203409 392524067 855800832 847159297 978664038 61880800 670097585 595936532 784831278 240058363 393110004 759985470 747782400 740275798 405845153 382299730 197276182 628194518 545246325 610348902 171061197 138130148 695126670 107242327 575586601 671077357 340217843 682443074 879190350 934710242 336983562 154444556 916008968 982060985 809285920 30532060 303441476 909748714 906318565 690599579 211044501 431341810 647257837 728884347 311209904 720136147 209862448 815900525 323620080 28128402 971380362 52199593 411520211 964406456 153301820 519678250 576307066 847226834 103239529 692368431 129255213 328849905 879336346 753610172 681595605 458372139 927438651 298244375 491543681 516852504 284086555 314240843 980626401 82808661 375420400 66453928 554678990 474772485 991540945 48192065 288900544 981526347 95911866 643697772 671251030 935020753 67307531 239621958 213589970 227353156 168263433 917938733 353560986 165963733 194632796 75643716 563668921 913068729 538714768 393363954 320915803 943021994 538219924 513287523 794042196 250238309 345620797 390611205 71365274 582649642 267968452 488286477 459491015 2921791 349646916 321817328 755272856 640489837 877788989 403305450 484932208 869118849 440034068 649248634 913947862 237133772 655454352 670200292 456501490 342708644 410967391 594189486 451902740 960466401 556751503 49881379 91276077 770286433 955316501 975271635 532760917 910898564 488307785 272414225 746359363 643899056 603095144 882563188 373614552 635736782 982645009 297979222 44689812 292155339 585046985 198710872 412724511 307138072 350638711 727549404 91444930 450285867 244151272 813272457 93215723 804660732 780585036 673581259 888084909 861971337 190588343 344475473 963337533 745321810 649540769 449834381 435363446 126898141 681634407 881295159 108139606 706349875 768042439 644912075 745498495 150211425 250306920 31643398 798759095 453698297 877746256 250175341 904129896 78211982 256149612 808524486 334386721 319347259 33686283 919735452 26217235 651338781 342195555 193113791 784125588 435905748 557611787 993394626 736136095 588536070 232882303 585772412 450167379 50488540 244428192 144219527 457204848 871050372 687632433 624483780 682678237 426928301 270206555 844438229 958018340 380088078 681503530 857110690 489654260 970756831 292134669 20826837 686079903 587053917 240150106 627341662 887926169 977561675 176824263 505467119 712415743 403381356 851377394 794517888 602491917 753631242 117326555 452352204 153032359 620553074 948313189 384762067 167572689 243766134 387250904 34386006 932726839 297988073 732040290 670083422 390634918 798565414 639956625 901902774 417304977 895157130 164703962 736109932 117056653 870771190 76878614 593384788 265097685 792151630 29416448 880860037 297351110 646894332 164535224 27916762 808346724 102015085 250104898 754574450 623969748 792681875 193265672 26302000 507352288 664321633 545451092 358230331 346369910 504543314 373814743 719512447