98 100 490843693 89022939 280424554 947457985 432970873 745752328 777194544 465703569 792806740 950562688 625135024 443376934 490908748 510985452 365823531 538720779 838484986 27628296 983807577 135711757 209959288 221630548 689601095 705200295 29574992 339963349 804587422 173391459 243109407 127191275 985634677 420769225 61759950 31452974 313718762 702547628 208370669 567677721 434739312 568907462 992645549 11861689 918549287 237683915 714599033 564588289 788559006 764946096 795448171 6865462 71376902 527175914 73034465 413604717 898827358 377990741 336277112 431509456 942970926 265991252 106980525 927296181 525536172 103174660 598567296 107329536 91745528 671895749 988551598 241116843 684382812 350988775 941467900 218803205 372303229 947617618 65666359 289939115 290516963 687722237 149446082 264666705 773701061 719376568 401411357 846633208 595689499 148742761 180319880 928088896 927170724 600357030 138756073 205080677 293219681 264719113 543127890 131115833 810483382 563220767 100 104220018 452135330 22100034 180010296 820684106 327536845 102482588 890088539 518115474 635783308 53478654 390093020 362517149 304077682 170564066 433007765 47132239 173686236 685455918 247107923 753804652 266096458 116720853 365810373 545620124 454499172 371813850 644230208 275557349 40611707 781155510 102125302 432180382 494623073 368633614 119167955 769547024 961163859 855752964 109682279 813075214 393961011 594633186 659518466 730945852 441863944 633259564 117170071 111722563 997320513 545290044 167968725 22977059 650582251 32876024 486036422 998912584 37037482 430841534 101499961 883336387 381017605 882022330 548764542 826894609 85910489 455796088 88303548 963298861 592279360 270105820 492279098 239206689 326422363 171769220 767019163 48239437 44248475 426551651 460326733 624261250 304814792 544639335 686258991 350887016 320143732 238228370 874738935 425570728 108994878 512636020 343864140 218556862 95267180 239456692 184597858 657083976 170115174 521589369 431547763 100 192646483 197983147 145401251 401930642 726509538 842069617 672425521 540507684 572239987 137112467 428583361 39504073 712443427 327707628 445143605 171218693 950586867 58565602 610008210 32975153 565768184 941773540 265327592 949095435 938057395 250745932 291692227 849605934 47869927 4938847 321129218 463009119 37117110 477517247 463020958 152110633 82384224 585721376 296670234 850554231 385561829 840889374 680628992 537843803 896740029 52557598 975320343 32206774 61858831 209013545 605887329 608645821 742595301 337928567 612445316 633393560 335811165 160421896 575636413 134703089 40685933 744012982 125758527 327610202 52913701 440015139 704015059 267979473 522286400 600035309 673222866 99435777 358342840 634166114 50194019 367472579 317159188 98618431 431503329 602528150 780362713 504933478 160758470 234440502 703424112 146580917 465664372 183224763 769107271 790548290 709641208 220749708 700692309 813467032 860773904 970502651 261151343 337581764 528244864 362748710 100 925484670 656742613 826150608 709623122 969330994 864908624 816981879 57718753 279811742 823963394 311985867 353278661 84875689 789701536 197032276 661509207 76144465 71610805 870978137 370868332 842764030 693263134 929547018 641656903 77404631 346451073 687456723 569801753 391815281 5694893 696755975 248153400 235743621 193966376 310095213 298460891 980352499 939774410 484406158 18460312 845228203 710306430 426988271 27074593 47413738 254588965 520136963 651532318 507328855 790352040 586831130 193245319 451049000 724683020 34268454 27408881 188151347 720045266 110921695 596430904 735348021 865405386 413071466 190222401 259578215 751982785 991599378 324268024 30637434 775655397 784714102 550483052 20985421 864309826 921627952 659508410 400701768 104538855 963641079 311221370 773832273 354810272 732748286 276961177 924652629 890740606 827075517 245087878 551105922 873083574 945239414 524070606 776109959 762332932 749369112 533888800 721019220 59118641 444882611 203133370 100 629786728 716597873 620129979 676776478 746377748 729184046 280499467 993738534 189843604 661748849 198220680 547697307 518630415 887298230 132742140 402310474 248180446 45892429 580149239 355755741 652448973 646935320 503657752 420310406 11683759 620194501 141123679 438969029 586486568 667435235 976302394 986920011 567807008 509536536 491024388 634298606 383731435 470588135 234540220 468636095 239129233 499837804 573790797 931962868 498196440 495601854 941923757 18415892 301899476 155802953 393734410 902192624 195482406 641802099 329313184 342111163 1106649 232948362 313379663 325028986 671382404 457962170 138811613 649276237 656897154 149103456 522452399 975324923 110057237 12770493 346484973 868907630 945688219 12519150 545763707 334645641 988625177 474892035 102036446 803764815 629717393 573073502 235247940 913253753 551780742 246152071 421017623 91415583 856718793 565275323 819201128 82905659 875560070 601606231 613609845 700375004 267053912 630257321 74858794 84994565 100 500186853 649567752 809452926 657146591 814149031 456115335 650621914 831108103 308688490 187649943 635969936 923243057 504107750 442228740 503331743 261064206 946530552 454433889 226312281 470419023 962107950 988990017 120612949 178135236 903351204 568324383 726023559 969923166 472795988 117020808 554550644 406739036 382308761 91358027 517096386 608877866 897148673 814247602 976213650 183468139 646381871 837897 338396854 745924612 939325020 366650514 754459538 331994265 291987661 749930449 41611776 502360901 685572591 331567677 5909120 576811721 779401293 516540776 156424777 472506114 974244664 530650448 29660700 888721090 887007030 167383937 56817276 503107540 112288624 149717391 120219727 363037489 703950115 479324332 666170258 305452600 28620211 277624367 232374020 568708524 189130551 343245186 408529525 220544537 416309511 962073087 58473359 950244288 764968172 471622429 842373825 524800617 547650666 94103362 935782218 127641810 632054682 367368528 260171430 264975467 100 939202113 334823557 335910574 194354554 417239641 36666375 848461478 561084036 431168648 295336216 451081453 934579109 716631702 776877506 913703354 438751447 773708108 464323152 707156895 191411282 932743855 113281734 921192569 737957865 908266233 735792028 88682370 622305598 38989757 966436159 295725942 727899527 67070552 756927257 26230359 201368964 823703390 521495167 57917411 769634920 114931342 974523554 581567865 84533233 268352961 434274396 86153523 500159773 980793075 13779120 773319793 469575564 400073923 645450224 845951180 973133537 429735330 684089879 216211345 287273665 804275391 978540362 117163696 562306740 251791062 988321542 246065740 517906269 718057984 111570155 273766493 285513436 657983941 135811753 333941633 503763920 118215541 757980977 621934840 309953179 641681936 500300864 58768215 76123948 246713616 119004437 173930944 73387825 927251476 975084150 81338425 544154582 83572567 366183524 883719689 117340579 56454496 88870715 449773940 345246772 100 498602028 733006307 322521166 204625714 680394526 667788457 553998853 548912232 720192989 368112987 248653864 522723726 208190191 433823768 131820757 607936103 376036617 325669266 328487283 128174575 118607507 439242440 607750508 28194239 11331773 513975589 787038371 69439028 391190433 895181904 584299462 384342441 364388615 286610854 469343493 365989314 627875181 105849721 410665179 859682711 377577107 50323127 66070170 726114016 391537078 288914879 528316306 88565435 974448489 130922102 510262430 858530527 369024660 820176030 978773410 75057384 349285559 926738646 845562932 757125496 18480295 274722082 535922492 884636826 958369379 39738316 922039724 689226148 993399349 86297853 486380636 22404635 67162356 947918245 774205442 463058728 721077242 78213726 357610278 24483136 21225700 181047881 68138936 410114373 731181343 254779638 464902866 868872897 860430674 453254630 38688501 645546749 110238472 108296423 613627380 268387149 98599039 345621077 17451448 420145746 100 978935889 397431134 771193600 414109560 297671986 611586400 377547038 205278299 348247149 168562310 904970355 27444022 662004843 887887580 927886551 687521747 729171791 925078694 283232945 746540366 112156891 897615671 935872264 981613848 481593757 902696688 964230019 549042546 306146327 333576890 682960707 448611896 151581325 985242575 232176316 292070178 471915482 378949120 785716158 449840887 862077359 375570006 123229170 419312854 103733857 538014909 669702661 125765264 174387803 271957397 239835303 966968485 344702526 681831584 339224448 540042306 544402219 862952875 360000079 220764642 843212456 869580246 497863805 44182286 92610914 124652341 772880250 573787497 134072019 663466554 503645223 698224408 480678775 912575824 45866593 46925396 436447093 666580111 649994568 613639246 515190085 196663583 587547650 151682040 432995776 483046381 132444919 801410287 496352384 758201023 446426854 274814235 226297823 772410482 920032967 554781157 641996992 189185725 841448992 893742057 100 210973791 229764491 513073411 208934932 582610748 811261177 767412706 946820863 700315055 234859402 707302217 58052094 740983754 55554869 653733540 352666620 189697656 8084085 873428409 220912415 480267841 36629975 548321372 827694148 245922544 579826455 247033119 156729505 522699596 205590371 443452847 183157997 447760367 441768960 282613392 565559461 638689742 922049027 148207968 908102344 722753323 262359729 454537197 775148531 3494986 293790528 340417880 345954269 603831282 589783432 439410797 293137157 948776717 270000508 768643640 898259029 242414361 825207281 704128663 360836590 816890427 264304572 163354367 263163041 111607807 196753634 141515689 159753062 646980456 504631029 606039743 405811341 994248826 624399653 932983271 745263963 726051628 55229013 807865767 820547033 941882348 235319207 706205273 952263185 687610448 299175219 647267527 288964897 94209193 47158055 414395178 108300238 109351562 674085828 240740619 205638987 442219254 186466119 408516487 183955775 100 723180427 524006975 12028455 988182689 370118835 929863231 423391158 42435058 976182055 406546771 909483894 42559282 358662037 432636331 981310260 347240458 602245259 409899232 771286841 293222754 41084551 172785252 760846230 576863301 501081097 207887329 868530237 367248235 680457071 449500376 765301528 339901105 886942609 420535609 123794979 771212335 578443382 676540560 989360886 948209086 808310485 937718747 305016812 496767902 336118550 549643657 527602106 132348250 658344403 459752752 114512368 30318228 281520088 872062843 596099185 373333412 112345412 241641142 517292233 300333127 526759338 698516945 358101118 945484390 983739888 140876543 143188348 968171220 878671984 539662654 873695429 860740155 243865089 390447593 995360716 544267629 644925040 995332888 32118691 209584004 687661772 728487604 297714390 46468152 610020717 46298423 213853886 837447244 636003659 993792710 81533574 728411300 812792300 826637303 266104352 158144583 327882169 540524264 433524090 745609307 100 694521602 652249222 124901291 571522060 925804204 349778446 523882107 486215553 546635560 437947413 420880806 948581124 218803796 67613187 649532242 466498882 429932554 816609781 927645781 445985601 450329490 803372292 722946274 366926743 179424662 732212042 395828026 355015640 996990732 845735436 203285719 64049986 888116876 24168135 644195504 204795745 647283368 760666534 125164568 602656129 48117990 806061745 814879903 117178126 588333528 516166962 593350376 827468581 264064343 682059906 992614139 34831444 798302831 239433331 162780383 89426974 784653132 211452365 759420254 949527875 398492013 49422773 608149133 696626814 265175867 677907552 77447995 694055864 595991686 673760867 683703602 687664755 32612916 10817556 983538845 841375435 521619679 875803924 76371208 584943925 599934639 695687187 307606810 190750549 876124699 162465447 328137 211705726 561317395 883506549 194037264 815081883 143254352 786601722 365557597 300794163 577672768 543601421 101513595 521002287 100 505082883 218254024 740638269 334080574 372975661 236736391 723349458 864329745 382998524 189856620 204014059 526069521 402255469 336456951 55780184 591219334 459848053 741967706 149152199 904438571 770137880 717018350 628127561 728370116 940310866 710895469 302632487 159024011 46330071 17944622 827443275 31941406 351196573 310447006 195513289 317708793 221357146 136016445 814289620 548068059 144726896 737642041 466717738 227490261 577966656 576420680 964615890 990745163 617061484 774830037 835442852 626150679 543114999 96577661 426781466 625510399 972502519 409516345 143956697 498322612 310778730 236378739 196056769 451622797 486753160 929076708 379555425 210039152 615811014 341177443 462576506 816711371 386621427 526012498 547613081 961621851 365412110 854242439 792094102 400142300 666114266 589447472 594774014 978529560 70712953 737237012 922304867 769514985 305945670 459216807 502320600 633551052 904557866 495309298 238221999 755842802 694418897 385098655 679643387 148628503 100 478802685 804270334 498144780 992031684 274054503 168000345 767631040 854458837 668320647 30710831 136953431 287066331 201677919 172366194 18820263 18956742 909334082 42133652 880654062 558012764 913239344 726061570 171216252 572595007 397304396 372810922 786276884 382482665 832088667 125858987 274366149 111818454 229745633 1774995 627353182 818313116 489137173 575679139 4940714 332712883 636612249 904579617 29035901 941942788 179839590 707611832 357076254 571562733 244744195 135528141 85681795 422571561 708464660 241862955 704824452 331879721 10761147 205660489 877338376 738857834 895402897 683754502 69784608 508633955 755032081 856336259 767105292 221814639 463379318 394955533 66969595 625720314 283298444 89185656 746659498 738162146 914221688 839719961 446012193 926782427 673111479 259735290 579847095 768901127 284612342 796652944 505249569 125098834 472246098 714280678 42458063 176197991 220310548 982629650 563738848 310681431 718857894 535358428 432781777 243640659 100 701844188 150737360 13266439 176166112 343295386 12321641 443029241 576489361 516234968 842554348 145975466 250899567 595992774 630402106 429809454 798474413 137382406 596727682 835579228 196633345 808115821 988352013 745585260 497154599 732293890 528269448 180685381 614658986 220135161 62828667 109372862 900775036 383170320 595819085 830240118 597933824 598166496 891697517 694211808 968001832 613732865 572367695 819303348 553185887 552589243 658286900 415838576 157090598 61344976 796482051 154188369 936278750 460023326 542828768 357731317 319889150 36103229 649454534 284595364 202048818 689580418 765450034 658789221 27710673 359370797 946504211 402923189 550177300 184877843 137763182 589081773 938155162 205228747 730609705 200127577 432987910 892532202 920738519 26929352 383362556 357813692 649553807 699905034 412190050 455272894 207204502 745731589 365542336 470792584 804345762 525004814 556200591 656976232 952990192 932076172 665728915 197157941 296988305 593788299 123603197 100 651219670 716294869 496218345 836019779 54896288 23866856 178245937 56822777 391269778 504409101 561646167 92088896 316413356 731005501 278597931 788495028 552059032 254035554 944482090 430405129 923412068 293803006 304801409 343680921 683143688 746149149 105602803 540977058 77176819 799214591 804900140 682324967 223715073 694417008 185790569 135634553 955222633 973660471 669956539 745385511 304935294 689899977 180489529 555728624 125782317 558713044 82821329 548202460 765993918 607033140 303319008 932638689 811567165 825254633 563965641 852152206 393078322 405089432 435185967 981532215 404379438 28051850 744577636 422849414 766300391 725994195 518424454 609569321 112084565 810810298 730427085 293360375 407781342 854067245 514947726 774844230 722765486 883622140 989525363 884912324 528921195 244116242 516891796 948241587 157006402 866948865 501724856 754890208 565893918 413134712 774958281 674445086 437907876 517189748 806933621 55213507 49320940 434143547 830135464 616051772 100 290594084 219157272 117150503 694488959 837127409 542661857 643906409 533653138 885093510 602507161 533226116 394726311 755415770 249954145 594951706 603453408 957061380 609824157 703201490 308729103 383899047 433265947 957501267 970177909 433946559 186285502 714508384 809837522 44811061 944425365 288627603 811663088 288416403 807519792 3470522 9619752 952749538 553578118 357068970 68402664 153068265 390010000 437884124 244910939 827431051 791552171 737663667 343735900 215097783 433091909 971733836 228538505 624025240 896029762 245029587 116288698 711881978 715126370 953143461 794631272 214044057 146670989 232349381 469163048 361470488 675115414 943832429 322418003 347943889 19053547 838594867 234148798 819377618 752424142 976857724 971889809 66131681 529411017 463169617 83708252 587027792 665210854 877939839 541316405 184075922 979001695 683730441 338603469 778180364 991867070 212386354 303631531 844758552 631837553 29763550 658738270 894048014 12718483 135539094 546746870 100 490821475 937295293 260276124 555865148 219122957 510494973 665335386 955628849 101343801 803055980 275401702 890463886 991478648 956831913 456017859 43550353 714715440 666771733 403699392 35407941 497308324 261625412 783285642 205035608 727466979 758747260 940204911 787736274 867283342 410843019 80182371 343613128 928755083 679507451 32719208 915068702 902427309 449097862 488580826 573496044 941809935 440225721 388213153 16641882 845588597 497686329 741689570 964023468 734629974 98245504 590987622 560940990 753225309 934290359 66538039 200877133 959257804 769148992 468108822 378804176 550281594 275030489 95915237 547794213 261244759 49035709 931306442 693267199 198901141 85295037 479069917 869201574 79585120 597802505 597748328 718936872 15895545 390980425 191832599 852300679 14362654 970475527 783209617 397709017 38169179 582945305 191086346 851993718 304803204 351879194 613538383 129741200 520735841 96414907 533981280 600247891 51215011 484929837 80148766 408959799 100 149963707 432776608 168781353 345612709 50614484 150269991 259670861 597153338 945449057 814615948 98293596 926798173 173920361 317883059 799914556 739912611 771172282 819603168 532890180 743128123 999914936 230123470 456577154 989753178 615465934 21490264 79129340 80177622 655800294 836473060 664245102 100995451 651908880 915701377 644820732 718609967 695826560 31884008 216205445 580576100 565484686 880604233 459713371 594126591 763214514 242519158 838123577 454118410 493454689 792162388 474559868 317547654 790638040 453078302 731105352 609716854 361472206 511794277 414595291 482895284 683757209 541453940 730589422 954871384 205090992 29433811 577363070 536321487 473195127 453215194 287646462 671108465 585094075 986121042 762598941 66184505 110162173 153193689 943002521 111691288 253388935 865343704 219128502 812449042 570280827 33069846 215536491 108116067 905326057 750547481 103870778 865836010 396296901 34056630 300636087 75972904 259643030 674246026 346571822 965239113 100 455062375 758218468 539275260 752385915 865550904 53860860 36612000 162970304 208377793 272254784 100464154 50737025 192777154 895136583 462003608 10917089 276970520 716782054 468286947 477666723 521823779 803855129 963556719 62440228 500293321 36312879 42522483 488210155 930920441 864934527 841555501 578836710 719523765 731589879 594042632 147600387 328909484 808347092 554575213 650370727 277487702 579282850 64284424 787811857 156254685 562468076 77686826 264623014 2112803 422736525 145309209 457658285 930673431 712422995 514349420 195760293 286132319 243005428 405037948 843081734 552495247 359400582 870175833 885460430 705710141 852851414 591815476 356926040 872594224 174374763 842782970 476987562 765318355 53018517 722231308 683199067 689444179 777198148 979096646 720612273 474232021 776207476 928793908 963123370 909371044 696631786 655053307 628471372 463166803 481188858 333887673 966626694 670888455 34049592 1751412 434860168 594217576 269335876 293788431 981145836 100 364697158 24625330 730287167 704366794 27492803 926000850 743275448 121182720 332162548 45551631 404684982 352045253 889369445 372459199 595042478 289363210 364500234 232743884 25727342 25993545 623884152 408822997 641881047 657931167 209056234 340631738 929601060 778171064 961435013 218731076 634147679 88339207 974940253 9578494 527531935 738406245 254857054 789047774 925869021 361807224 828629335 886310695 729493962 2102430 764779343 946412529 219719283 200184847 869027474 58353382 206249568 608043946 758522803 48535292 583609288 896866834 704392436 43200943 196827438 585233970 920656963 691093729 605266998 93870390 830392615 951443246 313282658 67142899 873599629 639708640 173630879 810098968 206412079 106199651 756468512 273601406 905187127 476628146 747981768 975799268 676836819 980809112 425478806 322700869 509843006 460235495 687857430 40879685 734150350 439791230 445504767 925239745 48698458 14795092 181206587 17582978 867120375 186773307 258153586 577585203 100 285302431 832681153 3761416 455192798 709405598 214539531 478031880 54635970 130375846 10871502 998166293 984786446 362997191 434457281 157822401 545924666 814779488 999034720 290169160 451934848 164757338 121355364 399684728 477710922 486369048 796736218 699432818 812048147 946936206 142350537 433318898 805120089 401357771 750382404 62947695 597119070 417063406 773875676 292093731 523388336 404419013 594302584 401393496 429165415 579842829 354289156 620648161 698876862 298644616 70652022 587210026 804547695 557083883 563552270 665914332 898268505 731172798 119349993 503652439 614706134 941092804 684659567 279532320 571148406 445734785 594168934 51359506 970003692 584957898 372007081 554613536 530551641 134193311 504738073 349222383 378149466 550357244 634203717 475793036 690907159 315359568 246102230 557194758 279790948 886081582 523728692 505351050 716728701 238419757 257928754 840617303 868740491 957167591 850857661 902987998 683315054 535361181 184748237 535180920 769279654 100 99201377 588911979 99465598 262878419 367936356 665047507 426659455 856722335 994128398 689193919 169129741 523818376 513573319 278659447 627801116 158339883 883112207 886606463 85442385 298201130 207668238 280346402 855602097 105333142 519809330 915978273 218725271 751639458 548070136 430165882 640298623 797853916 12922118 466148883 479056923 796453553 145874349 874125157 430139585 863193838 431787362 71276626 941711302 337515393 442836146 556668610 53123345 158834147 330086405 915903995 658919216 716368918 682247909 503851588 597459668 94722189 648239871 60713070 419063419 878715070 825620473 799214340 657370477 954928277 79141524 715026433 426977631 784518197 885589467 535534237 665138165 789281541 645444848 530946295 905137405 549576159 168150073 858747269 306274394 986345312 738576533 841347518 378761688 918891967 511571579 541435461 891952703 541261850 998629866 127560103 255561163 16744116 124866416 700036770 839353047 126777349 530900351 347895530 767631723 139878051 100 956280774 533944597 79274621 195911610 593121289 107994226 951405225 112813982 88656320 14115132 456857587 572107209 844050695 864660193 397845595 879110465 509315351 408283027 133602423 386747983 140304075 24906844 225376593 948794732 751463496 387474827 454900927 197862025 638521339 725950114 828329289 24643619 8709191 721558446 54515525 541996181 263740124 138196576 737720484 880566632 501126532 774935082 403500022 368149131 223709005 109934215 750443255 231296054 668007033 706331373 369190073 210259806 293665781 650754808 568180747 954717972 141191532 340419814 802814387 927319134 537158859 783146332 750305499 101659587 32564562 467175379 934431456 888367630 699937457 149695908 11525497 889202368 641137702 109433701 198003363 538218698 426597201 205844202 164418703 871910948 987240333 714116197 714307040 185208725 492181120 352879187 334380470 756431935 9927546 111448018 138868005 309637266 37206090 8302962 170600586 149107856 873485388 480524517 190862799 101517802 100 79180025 631622711 633227094 277850898 161347297 639659854 338788967 911361168 878431383 296874782 138396711 203759963 556471912 729058442 615039271 445984473 542766949 840472414 585517578 712198660 320239643 189660093 841353076 899030285 637000294 193266487 650158461 63075620 222021706 544702713 278260187 261742559 564790348 291624644 306908749 515059819 383827804 157935378 137253406 117476661 656931697 715752264 155692255 207550732 28019803 327293284 183930038 135838424 608905257 602190303 789800936 239740657 852222194 419267722 206978515 576367414 737017124 125683480 805727110 488453902 81455124 778658047 544796541 840475750 154463873 387414134 897125667 632610357 126825279 563491034 552248060 470851893 547774157 892202626 541521754 167450055 332906027 808053430 545390511 281071405 688252243 802869065 41745790 302008321 955642665 103238011 940919748 426962896 884783603 657612908 271840711 749149430 994585820 211046655 753785098 204147926 913675343 189839668 871300334 817934595 100 772248282 106661103 127493272 726566731 136707001 327927113 503174022 10054523 605374348 450999531 3041920 983107083 328335085 313867765 416672984 686540186 777647309 598390171 654349569 368156813 80087465 506517932 320933362 446487581 537604885 993748320 734333769 338989210 172045839 450072774 947254053 991008019 378145904 441849397 823649095 190788751 857096875 960462464 424814242 101014957 946698658 623463950 113220564 237436733 415296777 465810196 380836703 798141678 972120381 261308652 251115526 95513328 592696399 432332360 957147481 706555673 473549510 1016814 144055113 467246207 455493241 829299101 169077742 159561453 333065770 429516237 66895777 129789856 239722319 756310262 484745692 7816149 808485595 337013062 670333766 37644376 988778183 624867385 760422599 643008433 207747087 457624230 690825386 258060649 20385532 93030901 356850713 554103654 333095184 411803716 374559235 59706981 539466949 482635708 651947757 100311678 875842876 637958823 734175382 582235062 100 847370447 514779902 458653696 602304985 918888053 986074941 436364016 552933072 765783979 257304054 421960486 709568683 426708711 375232101 765948232 957327428 395493918 517415244 535457669 859973159 827061808 652053697 568647471 483006834 966842687 198068274 147895415 243301717 328044237 403758191 62192425 535267874 518005223 572224795 749438721 571300778 159939496 23880526 669780060 793451364 854323813 267476192 990768955 381511692 724221510 939213978 627074558 758201787 50323747 778225734 372335 669430328 638184190 334066694 872879671 468779438 434724891 793823758 646727390 76839888 295958888 551309374 8803578 95493968 865363116 244360218 711032917 533397825 762503582 451868355 829732426 381299711 15791837 579773090 428329698 603640789 92557403 275970003 334527038 913623416 469935942 820819418 839905247 996126108 727957090 693224472 308274678 837333102 496708691 150627999 853304110 965487548 721174663 221921221 674818667 31472286 430125971 844873289 854148984 611314320 100 224331991 687594886 861885103 67843279 243824173 44437801 249081077 750020652 441404793 225292982 203518408 482131995 264561592 338109377 50519426 420448331 878549971 904240289 122146492 144474646 11180956 929878450 388836213 659231541 674013347 155316375 688811404 309359627 801146703 184615163 266268509 986539068 813665839 656260880 990666557 773696383 227795981 808958543 703935563 504835886 298886534 52950479 804150133 972282140 665381422 686695792 366523068 653261236 145251116 938581242 660013787 836775068 994534657 924014385 972719160 440581773 974005295 139482871 316021120 902889405 896648540 62629539 431938400 69894129 418344761 950725592 455332346 504546473 801378126 367569406 176394011 654928728 733743452 962649753 681610715 193550572 332722247 323712204 285900483 578080409 62236196 469140991 707859252 195835040 811400697 821721811 46719654 892414831 476355661 624828233 688110554 430779503 892213464 871034748 393795163 211819455 445884028 97815111 180809899 961763217 100 594278061 713937302 24968863 413112860 683234429 690430738 447611152 51335557 25806407 929465324 300053498 468343202 465155147 83525001 786808677 499625926 297992942 209812355 544640815 772055794 763961093 59137045 439097310 216051864 951687228 530482457 419127981 789453502 826505933 199939084 790929173 915141003 45274369 723888399 151780525 784523822 826117803 79573066 521545477 529786462 176073254 398891816 368878101 649452703 954796671 644250720 538303397 811668768 980596190 467544164 586985611 131113949 536680684 564483306 3130422 414141836 87791645 714447107 210985469 638086712 165202498 784598155 497385086 136229558 271627250 750059680 274354247 212221347 157991962 642963585 70002396 614253304 292668927 132562699 394887178 717030754 167272992 307378383 619410402 550403385 435988058 495230545 927508686 542672731 126029679 295553604 721888406 497117720 785794797 294886805 725935993 174501335 241387591 929952694 217090724 532098242 36927686 312147887 640573907 435049290 100 225819992 459581200 157545496 11854329 626838619 873744368 746377030 887258872 636216980 46178471 905690636 656400419 39602687 300028171 621627149 5021588 975001349 362575758 57352175 152299919 139458261 865452448 72358307 89535316 543033425 491049165 125730210 255628164 360454938 241921573 778399862 417149195 681387625 556120649 465348920 176602271 613048142 480735354 377685375 722128390 577656559 701121128 683274726 570543243 14248612 725604099 740001257 474595214 598198657 65429543 609399863 347556812 582767824 365529149 7725091 434122239 59360131 404991699 281526752 493226931 4476229 631490576 311293653 789283235 581734317 85844947 954850529 421164240 458077985 748585746 666791124 955732306 422008772 927695646 648511934 113956328 904077703 349993050 893538844 197566472 810333443 899263506 787521836 819703350 260591568 752642562 459924181 362615763 829822988 391389436 481031596 380923565 850689096 487745464 82216228 770999534 711184938 106541292 29354917 360471966 100 80528623 193989951 760613301 699245403 48546614 457556452 426699826 464435428 424180984 758954177 182460684 85341896 555046405 588863322 262193405 70365589 799644486 344459316 968167799 266748055 931711058 905297248 275720146 847327454 643464695 537208426 757668305 363510056 457084970 550582339 982551314 583860386 701646192 224095190 95985168 162462753 889102510 592422830 718040203 516982035 145103125 982520058 427392829 881082786 828138764 818722041 616967935 766564272 162153643 760478336 658443693 922322879 68844948 290531431 517157319 328770208 422509372 705507625 296586761 337789509 232221287 566772751 11112556 372289274 72997353 559426073 111640380 163586172 338169476 747009633 972782951 250437955 579573781 741416784 614678604 852626306 955389075 962158932 79305424 284802881 970909179 895954767 214111593 721016875 241599761 75964125 493780559 145280195 250568265 863947625 906265502 364474343 750401252 49695293 482938934 817754818 965355665 358972763 504760165 985672602 100 218811007 99025666 806739688 314684654 774085976 264931504 772220081 374641856 265580872 546153551 116347718 189692574 790794141 196887036 61014513 297210320 101648995 152265527 952803572 421508213 453819870 949950936 219102396 719289732 441552822 789097608 332775977 494291444 536519458 721835892 745577846 905019169 568932297 940525918 984233521 175306533 720693078 837320683 617277430 538912474 772504344 607637626 444828504 478964479 783052884 163338982 598763515 647168855 604531321 697424057 142358414 685459622 87739383 64883511 60213640 331065710 772164833 380086685 131292746 644509076 494190065 790144995 675103193 870757984 525090317 772509606 235315444 50831919 248187657 753311674 506483870 913887104 913260372 284585726 880401506 703743600 165856170 307727520 968944222 666423636 766082955 993564830 572855961 963224583 925548073 821392412 487758241 608623469 403951932 720895795 69977079 897042358 936977462 272972760 168226670 473097917 740388200 819168907 864224330 221432094 100 682448932 98844014 281006528 958821877 29178014 855168116 928827926 833269459 627813743 115868978 761580037 116453220 56758165 430136325 291484558 477620284 297112219 670056570 672140624 340190750 414821352 377653180 440426433 112562044 943120766 39950424 939141776 885346487 784804012 891471426 107118975 141964191 612392589 182857374 68097586 41422249 971139035 250264799 190020420 771127460 529094702 710224573 74950366 732982845 622555180 207120205 162729966 613269569 257416800 490196214 27553065 781059797 83710423 472709739 919932442 911459206 140860698 564434800 811575913 499017293 222118470 513222902 9169377 745190140 310092796 957573092 435637394 977803076 715376870 723759978 459381329 199525955 482811624 448491034 850880673 8545311 407051004 258074727 140582430 351179380 979025794 88201377 205290422 273743618 999434520 725226961 527635788 246584266 404934206 252192638 966025645 37315905 799385668 45510927 294149239 716799837 164956279 402661071 624827130 355533182 100 647100205 566376329 290542370 41334383 202579094 422964192 480839259 469587878 802822221 128612906 794748016 185394603 423593564 982535520 459997841 842310535 796246949 320799189 123375650 406792019 711933121 564000183 748210969 271679175 577239045 541784224 885292379 416407202 303753749 509384788 867006082 156441085 316366732 399765928 375517827 631630914 166381542 617227876 591472984 908637024 189709601 920205823 191132858 249133536 651642797 806972036 381622928 110126206 147867183 245438808 788489490 235543351 64920279 211345817 531427769 79163335 279321998 24738942 629160674 896063645 424802819 578419022 494293208 866664877 685716896 236021250 660586406 193474723 57968672 520258497 131965178 902296107 23444071 901607107 492517603 267609007 354435719 859603506 240855473 14591535 822267161 862126135 875458846 13073700 195677687 193279588 83265579 796705319 447203505 785791044 915987404 236851533 185361595 302415498 938509612 73145106 999126518 897095037 377952251 753292921 100 495642162 33672304 339120451 68685369 547058588 538370580 618465025 77854743 545823598 646843072 731980874 72964874 279368647 700504101 277516436 878710672 566115000 463908425 970485884 702237804 114971043 534327109 963408075 770844076 572053098 940013447 377220886 552068514 878291061 383128902 532540543 607777968 607930773 98810780 702190508 286492230 920489074 39987415 172886014 409994538 63846285 98504847 490162081 869524920 908248444 79252078 141391101 282530507 785975862 705259018 389010896 391665095 226921957 100404588 895443584 294126271 177234011 307424242 743029344 351267010 854915344 39078842 217856578 304331030 129757491 588704450 495756758 427245588 302581342 570966288 1475253 459854689 806752479 756896028 879794814 251888069 40745231 762410895 850495062 554394315 690681854 284719791 104100352 280227562 417318907 67511168 905218137 433762857 438510238 883328342 188407880 142659258 217133669 482841298 502889652 588599710 877356464 963737288 526063325 758276042 100 388083775 493615353 579956606 638633619 911405186 586173376 78010072 129105248 213217140 577383568 362170989 918561042 607414607 550623736 384009014 357472010 698892596 334942069 642011696 220675224 480801950 672866066 922551465 381557673 126117920 882665827 990039468 251527275 662824153 657030091 417262729 313272950 641801497 135091335 758847140 789202322 38304017 806499898 661979002 350087269 622281398 548490329 922109350 328973251 51431829 696666204 863422996 701153273 58320637 899443920 243669584 70744570 719085699 891243738 217294786 592260370 26793324 379978937 851561791 510300815 824772842 774710234 323693734 601057208 116259735 666647137 232248095 20180872 417173735 531396039 919303925 716498865 395961749 300711085 808607019 674896946 110017729 578314809 264070053 757687549 524276496 402095743 422308478 280899895 379137262 463791245 39390597 248034379 806095568 701900389 821644529 681165119 781959174 640218164 798815767 862780104 932462829 198025513 112084921 956569639 100 524199394 624817142 211021629 786567393 807615216 683308915 284667463 247759527 464283720 222079182 117319595 455995410 10142941 729270754 900188967 504443175 686728730 755512962 416593082 405249550 730882088 341203339 614334790 496019357 119135198 274459456 186901753 354294214 135377988 454661973 234228789 475981149 326080717 295081337 70197451 492329263 373181648 305557652 754677153 797729709 643358850 935351347 523934199 82488260 793592773 437560644 80867849 430328599 932646909 890994346 731641876 410470816 277135259 991491399 334840441 699471873 123090864 809126366 262713614 895576755 747782065 25957156 390035173 599441073 71220701 344743011 341702309 954826112 325643357 342049767 27562587 794081518 128231312 111200057 330391701 774816964 90915133 229264856 52078872 755571106 790928528 236997526 661581893 431797198 540076088 273032246 493895138 71619583 667825643 627740000 267818878 775866968 352790440 818202880 201345558 341547781 602757996 91850302 56288629 797869474 100 763603042 254143926 247958931 688147242 627900826 567063975 628267311 610547066 704505770 836757400 602953332 526935394 398397644 98804285 918837337 864908458 746224131 810960973 347641915 647797837 611185396 700107919 266736883 355286533 331800138 680054778 964136696 400503358 446512947 712333118 221159248 355351519 309002187 844415713 815823737 585247509 722129195 949980410 844530164 459398575 927276059 70803748 311460239 750739804 803361155 249328814 898051113 642609051 358046653 522924051 213403860 275298723 279550000 15084093 809395858 290529829 275953690 739484961 499161059 663978828 167528683 755927576 257586622 135376000 890638063 819272330 526307292 913719830 210332050 985490839 833567820 146245456 195811536 111702315 579491294 665225424 913834259 534488625 659791639 50967079 182904184 346042975 278196784 236373702 812461147 33784165 755244115 393932780 256164104 754501052 342434568 228336920 692258860 695151011 170902967 743171079 816980387 955797712 389170486 841328385 100 341752571 819157491 287180473 672701297 946244467 584023661 468768407 37532914 242497895 13365731 953696849 379278276 234936969 803425 878856754 473214928 974369813 591741662 528918392 80016824 410132582 127924332 771092593 921395749 894036808 634491252 385572193 392471408 543528900 644454884 290741225 115921103 915144697 259494087 693213703 291406598 543229315 131027347 762305122 974499986 907409022 30426242 373616484 502110764 368641113 514202801 997495014 991390384 772185945 383007007 901906340 678817971 524171515 570383488 533112268 804143935 427188400 935542228 479779845 387705259 292595332 23059215 665358308 828693012 561903322 835321979 281500399 807484287 734743197 442666896 253208101 792163160 619878163 861732170 160421008 156497727 744209596 383787278 628755510 133144355 765280350 886716357 502347505 653428793 399694436 96037605 737893556 720158477 352769235 852070243 151306214 377339096 397267299 79776664 391797589 421875129 611589203 22621812 91120316 722915204 100 317145847 623491421 360756945 836256051 484729283 276606812 993564810 144192605 456558955 625156336 882332566 814619815 671637776 289354005 278673848 701599830 822370930 403734955 42096235 102841463 251538864 116495355 849363050 843989600 900522859 489052029 789949677 5845159 383742693 593456695 77135672 274900500 609027924 569904445 6741422 51065901 356697728 90440609 125155278 523362078 523340401 705026146 490593967 257552672 26664888 947153503 447343239 595527263 126674560 482977465 955651449 210520599 651748604 515362370 392145391 118415958 249376292 460732640 712546771 158092097 673855666 762437377 166644525 878093282 278858019 755991479 549434950 301700805 166116408 346267683 591598014 702283229 847616536 2524299 769345327 853329740 553433231 766306236 288378800 383503862 21700022 764243136 234027813 980962614 962628671 184748265 270164699 293186136 149323140 100904462 288733260 11697570 627370655 613928297 20595364 807204026 712024588 686474960 812346000 96064932 100 561800716 151884650 854605839 132137482 838107909 151839278 993477684 708927677 883284973 535051972 288608154 677193676 242825914 601894039 902143425 467534650 776961521 299892818 256126859 311325523 153058946 296090681 774459752 960186052 641285219 327512200 412657039 533328943 869777149 661899322 176406789 464904400 370994013 619121627 925008655 575471269 676828565 549194774 764346821 521282102 250794791 825504502 74182911 656465290 19724519 662321971 16489932 739826529 582159513 640217007 588703315 782821939 260356633 36549918 501318255 211068016 342116754 940114941 478100832 749064145 865274181 598740080 996469675 287645823 946817413 297973720 329061274 808453424 210410656 83710289 117040815 324664591 893725452 822593374 661940354 16689574 654173610 634811401 251095450 350420265 985396868 754307942 268704673 227717532 252239492 346675290 352258273 605176231 754058197 116895586 927820806 783226268 547856738 854846372 731486278 592665953 789260367 506040190 813471779 586938647 100 571524421 269645146 697474208 276343777 883216298 242241993 22422757 564403492 172137263 405514386 513650833 693753716 532663084 515610264 990837528 179923988 231435081 869918316 739851459 42516943 817698957 300584100 719604375 998214250 885803938 2576019 911305697 434630710 495878416 185391790 974645473 858337334 856789444 559068995 329120982 185934910 714619872 999146784 829478522 199039958 4576885 866129692 300208298 468396243 317910698 471245953 624339207 978986975 758650655 216764287 382042824 451665709 443601822 227555950 240860557 224168645 765779467 715169487 352352052 443665259 600428546 981687385 178045877 706073299 40140162 11165938 491504656 554389087 931407137 730837671 46349568 250270048 31978059 981817496 21970903 731647061 222665749 822194164 200480784 112839346 416647706 419918576 443261095 379202189 410400589 59149983 825150889 754399036 492007110 486218814 399606741 116493546 986762642 268744092 62905948 772661715 550319448 561965530 280579634 869478624 100 137814923 985291097 23723377 837098573 620592021 574422258 274400770 577118012 529892191 590896341 13730923 287977995 199576020 291293122 827209434 942878907 755981482 817778415 863018912 885941851 677206695 359185242 999816554 51072344 351573511 197134592 214659071 328715247 489015690 122327388 482233686 513989815 847201742 882935800 437606409 889830649 895235236 276556909 579878230 581033925 375444473 298892163 529333409 547402121 438753135 948046905 838490608 336603190 442709714 505863952 856177792 854341447 345938251 422736338 410161354 586439361 674662417 86255780 262231665 766190955 126441534 353664227 904270660 44200067 360020591 641368211 800297881 204965176 780177077 181455139 416790808 252181500 780186040 870258489 608155364 486352323 11239722 94264478 492596663 516136028 639440038 507609304 532192915 233441705 876844937 236464440 54222536 743627700 433684607 551114698 226447605 562311020 349474795 864360764 134470337 737267228 383560101 684318240 922327718 856730119 100 219364558 771374619 787922022 334490563 464261124 607115896 883727888 266519127 379564333 223445126 139865217 235804280 335937450 45954117 301164501 210976239 972072844 143049359 74074964 6907259 202999922 911896965 907259402 764044660 97529083 799013409 171820978 911592175 321831287 926597722 329782911 540211640 129782387 623637570 798068918 343538440 534038325 96478873 88496949 998327493 65877658 248522500 754853775 89278670 517742173 846998224 640287464 621680931 894702062 996365648 363213948 170496232 687728280 582337915 190534360 624137575 514419908 314167952 340230347 188402929 8319718 385292966 395966293 290802501 949085475 598243268 684139234 490075233 81015368 289704165 274224934 2390913 79008146 424886853 655415255 890287209 342437385 901173733 117131203 220016419 65950305 276760559 28771272 530655184 43415061 876114790 501491863 728608645 844436060 240964046 155101886 787482628 926018238 74234219 100258685 926041916 449445457 309992640 316666944 738564660 100 701108462 916347849 681778748 506482175 220911798 793480058 105115195 950640685 64413547 123717661 418027089 211774657 362515833 485190602 675857133 370114823 266787120 671622329 466067983 296497018 269406178 81371865 488025963 251517053 800444595 251051594 25254470 553254310 681183138 44572800 345294809 491669924 198871554 716685679 268332227 245612229 880169350 634318376 342461053 8230850 205056300 705949617 155091148 466741132 614105196 552072416 438386026 76552936 366449526 538214541 581096579 419282415 586723607 401384618 626934063 866771999 941005302 522302685 675163527 56489727 725497419 996193531 313485226 797525407 564470436 938661988 729817247 633963757 115437505 704847675 793150980 623971734 851781513 314975570 579403072 539288743 468242606 152288930 143221609 887180465 886960856 830752252 531750460 859094036 428537997 300033454 692902146 520137637 139603506 783630561 11389785 538736141 496306800 471487241 533156943 620190426 596921781 105929189 24773012 114036508 100 182144816 690456406 420612859 999200733 54149186 94827475 654402121 40273926 448288827 159881902 580704080 318886451 531714830 47322192 594590232 213761100 200041954 521526886 585314724 221843390 338085999 615920234 730810772 826142931 380444801 664380621 649189762 128422948 648536048 61274867 696534985 569428204 100966103 187195033 873843844 843255904 319016819 946627727 354301902 927282158 767666931 547664546 854844735 610720764 699146546 849305258 926705403 799375226 490175756 247436035 891391340 35703020 193365404 697444110 524665864 498738223 213001791 442038440 118237281 889765221 406266739 404797647 433195746 385484149 498777148 492755496 603592283 560998934 987477067 524911399 323497698 541665551 95394614 182485021 919820652 410708472 949845140 496360892 237009049 305522670 711511482 304897945 439094831 152539696 985845004 23367518 240389001 282247357 877938057 172973135 334870469 952604787 119064213 135614016 19073071 127272967 413821404 912687062 941176270 469080439 100 82496381 478258466 999675607 147581593 863925735 141617071 991203708 29071705 36831784 603798951 456830097 932693012 804385248 390964811 428828389 658626368 684222325 147437489 465896724 626759325 650057971 342764807 915924339 422847417 298552474 313794307 443431103 190128990 95874038 365338666 170765178 838194138 883039452 891376438 170262491 91527414 669291281 122474545 949784070 349297083 752753822 259434786 291371195 615720072 826507506 248785675 637528334 842035246 328055357 713437586 130550645 783626447 311035510 751120140 348436653 227219690 400750007 534107823 405738833 149717588 315213321 145597898 299135504 764130043 459517374 773522254 57454862 301243828 807440397 762601172 375299886 417164063 991710306 8215500 29681671 6663486 522128411 893061103 54091969 452624562 86062237 69440092 123204226 241225898 356270471 806702407 281872957 452047118 85070523 945591976 234041615 254325479 958702264 909841714 327940246 179416964 362979924 794297346 773719395 952427300 100 366936277 437987933 1675794 822017899 637073416 23874232 733301028 654143267 809212722 729199514 645085090 228447744 4721802 371145181 663135353 157042431 298847634 558802586 178305743 458073746 945012228 948489327 206525087 59321400 777442179 919238251 334767874 113634551 151439271 224577248 444658973 240439454 726074977 407900229 103872855 477564708 610905200 202464613 555248734 464748039 137417047 378261101 831714563 817059050 441089073 977843213 69370366 262170910 900488576 675160535 88469050 829971842 194825426 240525524 188206724 16788627 255283620 409333555 879961248 520342860 529950933 878404225 669647113 817045339 533933300 834479282 218556941 696922956 267392263 7561488 590672432 47387097 14382410 578487596 698979204 827406708 877502893 692640407 73870496 559537982 382822564 10711901 371787660 987609330 475915730 961756657 471584056 322588931 244611196 77979513 78096509 736676076 601023246 279365296 659078706 52460718 402737927 792630971 188214526 261059014 100 539269840 229862683 949047107 308359921 169066466 681930113 13772984 317531238 319546 106810341 27558240 691863777 939151128 800147845 436124639 837126552 946267074 859470659 368179757 577646881 574547330 608550781 957080723 234327391 124613479 503582123 976643083 637355671 181036730 436115968 368364501 692757178 571026872 461192073 416847698 667883266 7527839 381655273 515961954 389093871 765130550 283363872 601727 117536429 152247895 638651423 383233066 493086080 146775650 854502951 950168299 162676849 88309163 312369325 877591240 767439378 234681157 112908991 322965621 44772072 835717736 142428248 611236806 645042332 554475619 360789052 480801105 107997706 97824463 585610169 736225974 642531919 45447452 416380381 12871727 263641514 215872205 897297425 796562724 802198758 256349150 237215013 878484879 215501015 201612669 22663546 173175369 719300934 284102248 782380866 790363807 313823115 768684882 874001421 573221708 83911177 731978628 400974553 211699442 966554549 100 719365422 900378405 100646254 132140339 452228031 928298347 723053950 56632612 322355061 948896978 407068395 20524860 862285245 883273512 640352060 102771011 150114768 843795309 853477292 691125863 514250991 182184781 694668356 217069176 914497844 916738758 79476631 844079447 523676487 986798698 317819897 972761272 190033461 279548904 41060682 693635076 926117456 442154483 156427451 860444747 48966272 42451399 507319953 281502064 965452938 607586878 509559276 75029923 882969986 866085540 906509260 77377001 436317689 365701136 361817038 227254760 681998489 197198078 691242153 180127087 840291492 103095969 794862268 542387199 973443311 595343972 368396991 755094076 410556597 841718489 482348812 955164902 200112236 324009686 775775159 855773101 520267685 458343582 995381579 566465890 493080731 369537973 940455534 871744528 108451887 963187514 950617567 73684230 98085092 612292653 812377971 365921414 897223791 303162649 970485149 609576823 584140356 943830963 757898239 716656507 100 44905966 724154718 751140011 391682531 983849900 207467714 76029817 484629513 396754720 348775606 689138985 479670606 933936969 689405051 508887359 678448896 225308803 88804438 871129941 720000158 586753475 686424912 884384683 995727610 233588763 330446020 249304682 690984691 147574994 413368229 472157300 7290446 396448815 961357549 825151647 236957377 239074984 872894186 333160221 299989135 227278491 30380169 393327165 175095299 448588271 865991552 111316953 264889838 748044765 992704768 516402045 892853707 549628469 452595645 690045155 985290126 109562314 429218175 378371450 682897983 932708305 421947582 604753173 171371014 417869864 310445687 622522354 534825411 893641725 400630109 614942995 559828626 261328380 627191700 111109738 452691271 705333240 524619503 16168170 892081009 441824830 105759873 73259950 96642743 655388295 637069279 159652910 639290429 458683202 190623384 556404934 32129886 366315994 895520733 883537919 565226783 276343113 277379484 844098053 441640127 100 961428880 590730838 669943650 909074394 695521253 152214164 732805248 680835760 691908537 352886755 179566864 878821593 586274313 42777625 685225208 537287280 941742249 630052914 795638754 553481518 866897372 779005046 528609144 326708733 671550273 368439806 538731460 283031378 464730315 439185104 9262058 357303677 811622682 988497651 248799305 11190733 635752118 452103256 255682217 760955726 641094066 28988887 470638414 412410545 904526369 375220895 743574629 294535054 577929793 188418385 239540301 828790356 216600475 363927315 348171656 626705429 556502166 29662700 372932238 817032973 367911549 446360853 48013949 24056909 121589569 740237670 4950653 846782316 230094307 952364110 813093541 818967787 230342755 717324074 865272661 107844711 694480916 204490517 819798463 687797873 586445508 227393293 345570504 521692459 153726601 2162193 415774657 882284665 879720662 506138334 44224944 675827248 679802210 773885217 841071217 247589957 687648861 156886764 353081119 123945963 100 896418172 761845161 875437494 610033623 993535803 817461291 99287314 55204211 409920691 316688806 64729695 229024736 60636455 563040175 889349877 192198370 891891015 224690824 483282283 34584465 745890445 198742868 397033890 861426427 890968780 112703967 426977278 431600888 936342440 902568159 79325308 747390857 866704501 487730178 926119377 990721432 88535257 289850079 990665775 64237381 419168007 375323543 456975207 595428779 238160495 220041434 92596845 572931963 820118680 417231510 132809612 308291340 602046792 770808792 798498798 677432896 461513358 800988530 226272720 12272372 636442806 389043204 449722635 395026774 288268312 851608408 699556891 192988405 117655298 93271120 875894825 986985803 897162248 437607591 135226373 299064483 932997763 859865107 633219561 515753 37195394 900658980 751968775 591116740 879077678 504073516 464424084 936880243 855255472 139205656 836695064 406571438 273324163 776233752 48336269 288391007 409591489 439790927 666557260 250329136 100 205312257 241460171 612123490 774983997 234356252 321891247 32333924 186700751 654937161 673352877 509344004 985228278 69662887 741829853 478866662 325560765 324078139 569306264 422904729 664064699 44279942 942208218 244069738 361522458 538477820 530351734 501039295 154895990 388111727 337207563 492745926 512631396 375329510 210450023 166859304 112301882 827975062 43239358 751607847 152742415 315112041 345093470 391374374 760437811 381501098 752249397 324930893 145880465 423411452 267858981 912237290 533298720 775387958 431732896 573203444 876339385 601588326 155345535 87202841 203027189 187228765 155389958 581732240 481276538 668161147 891175513 618696974 446698916 728659489 911221239 379713240 553252309 52139042 949735129 672913902 256784559 182438668 919696105 629159603 443528590 954101334 540275760 434036699 256255121 601964423 880621732 421790937 750489165 463272214 92660142 181113435 800110742 209107004 847617338 620894012 391026577 780641777 587938484 417257082 773803432 100 241360310 289453792 475284081 933435475 454980521 155933311 298065551 74455972 981490326 379347159 694884266 816109896 252301358 231454189 193155322 853562931 396244989 90229230 819032690 433137585 141869416 766781652 617981670 537337730 48469786 118730512 3377608 759110850 420078303 376846219 682354886 925153011 778646933 773242854 52024995 240450353 923243702 730824219 708484877 584188203 800284599 332228531 178894943 334772219 957059120 141425905 619698215 989833926 539029970 611891339 918433613 149865391 267102104 954339923 990618596 476443997 656909795 388837794 770197309 359286773 297257005 102829561 608540668 141513751 129287560 693333198 481224882 680486272 854141866 481865486 206645854 273906862 574132661 548580029 344732388 182864717 183137676 818668164 229491495 761308124 116025527 971702879 597347332 342432504 290414205 794608792 890846035 717777960 764965330 664177333 251717973 693956489 368861100 459491266 148774181 254706364 636626231 123498537 151358278 155105619 100 665425766 273224497 954383425 203295994 883885576 359679179 560447855 714152508 288349657 634712582 271056282 171363589 845143121 416929319 628950101 554873096 808983634 166746486 556545170 899900944 477715668 936029985 367509004 284793407 17267910 655288353 712672518 679434775 588853470 926758636 935135257 279163382 251440628 711821079 178371312 493318995 621548483 828443376 679439921 37248577 853564854 491447149 519470580 304918381 537802254 714448875 738530080 155723330 395421860 89716388 428561356 230140317 497620174 440621096 965259299 272701887 766587054 437715788 70716855 865563553 632505509 548912568 446698912 171757070 497556416 686590772 169867473 886058482 298202913 177694128 830332888 437175124 501799134 337209739 260804212 859618907 742173017 274764812 338679555 671158456 393266689 616231641 121928217 636394712 994309198 464587779 201763087 361370762 229317971 585494513 270881526 363969916 946774264 911564832 191638170 660480235 195867647 196332991 928619225 533647808 100 936003664 372689921 144735390 638606695 106371773 105178485 316573799 831677151 314181195 267914143 738188294 308376738 17781691 920046652 230881727 860686826 639778300 217430649 444133260 569190728 404097635 379160835 530900067 317578441 200645537 718741594 893008421 805846377 100354599 369755685 420750555 178163546 876310323 555681685 606443602 400255154 865975819 785064403 986701229 199082896 766725112 860851575 444331806 545034260 969604292 55769980 559633196 636687370 876308864 86809360 608691524 50009627 112401181 313952463 51204575 9376536 331457830 394315881 739200801 332800790 247206394 447663531 432589738 992436689 672039557 109792575 47733711 501716065 258869746 927763748 154042394 268516526 184177792 778050903 607235194 702420054 722214248 249342256 508071108 34188371 6034450 846824136 732830203 754827010 687361842 366287375 492298297 356429797 81954116 299577829 743653374 755024472 509874126 447430146 388834015 516805329 416493298 55669458 92545134 485137270 100 490771022 609870587 525024145 506203250 256681440 251564634 262650279 165642658 96404919 677212027 214066280 751862207 10501570 768358522 650509266 127931281 704304411 786156643 955403055 15596126 108288622 808758876 56103699 634379463 845698828 532600781 451988389 36848907 219138641 224169129 621620595 460854169 731944941 960786876 853358682 175119644 549688460 445530971 912468471 979050726 769824647 57842389 488232483 33783591 41707365 314012804 733897729 148673903 655004608 131787836 826269423 549916561 348890171 21039943 179603688 759091434 110427014 98641879 868287093 660270927 232103543 726412359 438314544 234301005 388977917 674254817 230547905 433037010 212530468 770187020 205014321 211676423 789452622 510831539 499908289 335127603 206906816 59346951 364872506 406402980 762682397 767798094 11756085 915002534 940355817 867893117 372571003 429016767 619675043 234846313 888850730 722479397 768550368 576832806 760263775 152165236 164463696 50723268 107156236 859362131 100 282029520 306136530 780019999 20992439 635046070 800086294 583104342 620551525 832695992 575419758 866183818 943467671 602301201 393274672 792059524 635283365 377801588 423763956 575476931 51511114 734486736 428088114 293341977 464698761 83550287 868165168 495455020 32889050 644836006 841111969 38107094 677189733 468297595 638755235 650072475 98939640 943779618 132263361 58822033 926339233 312640695 174055584 475645899 755879678 227857001 513376036 958003390 367460881 822431129 556360728 983734139 569996899 752487254 834741296 263675106 59527099 462700731 933320220 25436966 416302379 93493740 126867141 874590586 520552247 111730295 583470105 166214138 330670772 911257697 347911793 606111960 696027595 926151964 128181488 913663826 912035717 232324897 429430880 478767657 807398784 216040073 994616648 668475015 566571284 555295407 454933958 517494519 25634013 720696740 734566684 821686037 160364741 687226255 2734357 504239094 65438416 830137403 950078809 898195724 122385843 100 146992088 883619869 880451441 921650497 33283764 691177193 140596849 628603332 928046936 614484139 196491008 181975243 267106171 506450618 868580717 133076077 401754265 63739799 538297984 81441835 757608352 100563187 695285169 337054666 95588426 667713709 243295610 7837076 531758590 397802282 170590073 958139833 883627339 159170240 195605009 195496655 583097935 177015282 781960850 383665197 849825549 28725308 940951053 566419233 795418033 76338357 311114801 527396884 849211628 754830600 703758388 372300957 404706592 186695874 338054006 67962560 345719973 247654214 115083866 160297532 963143789 299927414 10777407 337562706 836449609 246453160 300539982 519341721 194306675 36122305 629231896 341811383 853596346 347840721 780990309 599829112 479825221 687568755 639206336 211004551 631480438 999829872 460246939 913154307 124730547 230931868 42980527 303482871 305579436 311600588 672946119 473714395 201990902 303817759 976626945 434865656 582444126 536877312 208992208 432410890 100 161152199 130969371 761208465 64650933 333477374 526429028 630262507 676247154 53461011 986909378 729548967 949119736 780319499 581276080 51380795 607434896 364657900 722944412 168812745 974414774 965790568 367514417 228132071 461178844 54966959 555406176 204091814 299950332 72642974 91614445 51654580 720517116 342216930 315412341 972242084 670422073 277593202 365548538 306387378 886005041 368606767 506777870 875911599 438257004 624898083 140561653 211363883 431072982 361456325 810652114 501094961 352965747 731672020 937817993 213337452 746496366 151945808 664510251 493716244 693143644 75702417 55348942 516436936 223774711 649996022 731101808 252945911 218448192 325940608 561979777 544509568 200928307 101474049 385554307 790273165 69231407 21834178 699165231 433564108 81798085 955333446 188871749 607710258 927113437 270104647 586642 72625757 85044965 976420309 861840881 875093245 828335194 302897612 439047530 463179757 333309455 295200774 803043159 761918376 109150426 100 445965645 554975404 158565699 128568847 720847905 312509370 124936151 300597843 529246028 149449797 845473050 290618417 915316569 861346861 424845989 28698839 391520585 572264637 631235047 955300088 686163468 104990493 864025355 740351666 916145051 411420282 850927019 183630952 713852079 890412639 348749526 830790131 99199316 530636710 106037033 444462615 511622325 378888358 699620487 103417484 441224546 948464041 697639143 2812008 71470932 818742088 393263571 455330805 402166936 71557798 962377716 812999537 78477580 341776910 213323375 148727016 869720336 333659343 683895944 587576862 962291671 729394315 49250659 460574333 553957779 54985606 852001699 486550895 387589631 664325096 236327453 809369964 704090505 923963081 890142590 190084956 578726419 729000467 465487767 196678875 197211282 392992496 962870186 428986286 315862334 563336659 826487668 4426312 556342128 922870025 437462151 268295357 176678413 949880505 164381179 200288062 476812490 654938299 578095548 996962233 100 868838640 657258670 772621389 604212115 149429052 529558686 892825057 584662757 400369694 883279139 261930956 412499136 361312083 662269798 97070584 167218575 793733667 554009063 231626078 538879068 170467940 986538117 527411650 355758188 332964972 660785230 48110683 771789508 134285798 747199257 279417279 347261757 620197935 558048349 212399302 512937023 547202811 955598445 98480484 495963536 951598535 498897829 961618224 850957611 790625929 164910204 65695182 375714860 81759369 468300699 879582459 36233725 850479490 97396915 29590183 507637365 180390148 734240750 518770805 661531364 155170406 715829053 665362306 7522831 55609787 418811196 429079061 101287951 254496132 260751692 21743003 141556777 114797084 725994382 14138753 460868994 237073524 774783168 998069440 580338319 903869695 329514675 242710727 944593647 100646036 972738096 593472435 544089827 624096294 893872411 429925265 866637796 610240177 947939733 500764808 271119581 339462332 834126812 547751351 729411653 100 46776672 808838025 333829359 948011184 3555022 304909850 853802504 386520514 542977916 742513424 286528236 174420052 754319581 259391958 127104540 331828663 941761201 462345596 383924177 7304878 374636459 27409800 369319134 559064639 287521003 891469570 188337867 247943203 85231576 315139988 889238354 254451264 61103282 268386621 9476145 843668957 756298932 100714487 268407433 951586071 527038509 630719136 492204459 259613707 559581896 772163163 47457383 10702099 578681593 476839514 515857507 681234605 882705173 59559374 846939514 951200188 511854300 70722362 369496473 215586031 683783500 343626946 177823958 344155387 670981030 735872712 475319205 853318910 858668861 133480988 378387838 483483673 47636752 172370829 557318894 255602231 316679765 766224413 918437117 316108962 596402260 415336475 705916995 856428386 355890476 184842852 831956546 582674733 648503108 96140272 5555955 280597246 595707831 171068427 77521958 958113846 592907105 291748697 748250313 860279169 100 726387675 8798915 287777444 28646796 820254978 885672292 258561411 251470882 317668294 805397001 977032182 463062624 432737836 364495817 152927367 194919336 189444377 441703933 266650332 838126838 757430139 651240945 743652871 459965146 909856554 158283047 430052865 999179453 714260586 771178934 216292665 475500522 578563082 290889695 207116781 955499002 99152318 481524337 717494538 757772979 117914816 622377258 682695036 902747567 837783934 23143157 82870921 783905405 82523699 142483923 400344398 511122326 178712423 249732832 400073539 678706093 253554697 207024893 695791060 535263445 279756101 57785739 67889194 158549241 391823219 331466769 215988452 48034641 225627964 177312639 28230263 913715173 144214417 833325581 874544578 795691190 758220929 163854893 961790246 267204846 918720157 280608150 195037879 595977378 42813656 502926992 774949653 55026045 395724050 277042677 451900227 656658577 194511429 17418382 588341083 109031050 229216553 527480248 421617343 620665160 100 906357456 2253064 695094355 952224236 736298262 592642201 219868430 500886509 607816299 336014066 412662745 883604337 565743804 587331562 446733807 281585686 909435944 427607255 826063820 605628774 999862459 219541910 566292664 500610997 203319173 210353315 79574950 868862912 776735259 545099105 299391816 23050993 923628927 427499596 364091594 541230918 76437396 998418593 411688404 328837405 889046087 119704858 428232394 573838271 515641642 984362240 705758373 668760939 658088061 19855092 368120227 422960202 619274532 74412179 161830115 341201172 298215711 746970775 961049033 526949789 348259796 303584242 263245422 411678379 555701796 467918785 424543900 677577934 822722335 756862765 593749563 422017613 552744118 112943824 603341075 230078542 37193137 85533898 680944827 171035155 424397319 785703477 379320186 682706151 943284761 419224780 531757166 445541114 126151240 589267603 89405426 701744565 668709310 129580696 583249287 759041689 30119638 912879799 315870756 419731003 100 380177514 313863394 431504527 456608701 415101464 201263797 799810760 513084268 416901040 217810514 349604797 724826064 624705506 704444388 983759635 559181222 297959020 474034248 251366959 611454219 122131995 162910248 702540285 89593082 680951499 454151937 774828268 794251333 265220713 253650557 126982067 249720311 941703786 95548313 784405251 228267699 480124302 811036246 616106860 236005213 707367002 521728678 750962322 228715772 749240834 56509522 206476022 881839495 853925791 914791397 315225816 688905613 643523052 989171640 567317501 652794388 553520044 827350686 379679335 742600667 635869189 544496563 213322205 254986543 453133461 273414001 655854225 151572235 165333238 355972888 901999062 6083839 966214165 801894361 627735530 978570159 518304564 700518810 342004534 453923330 881537818 305399122 158260056 641866724 38199353 75209770 987496639 613891729 677978420 489315869 900145548 39732297 127240230 901516000 883698794 792522381 381577502 714193749 920924927 849628483 100 202029913 38621507 246927900 371665319 474873466 830593553 931620391 761673405 741507547 89464954 667841496 647455244 191026656 330616989 9888912 914294962 413111345 947099019 2033627 288110225 934492413 56210673 658598202 483379675 319122906 666131539 859032473 133791553 404803903 624668830 512620524 114715575 160856490 762195382 819250316 485891724 75288752 122780557 394958962 666069390 431241058 560718366 60472652 526874964 516121298 185995255 186061802 713701425 253431499 666190368 823607431 894342661 119413962 78933897 110495607 303895514 345847547 896909944 275917646 468350763 164470123 839965085 29559804 917307391 349834161 983000298 117374074 872728032 105866143 531567957 659832299 843920972 419137365 998641613 750464202 531896463 914654855 936212027 180054680 216139530 865170510 799347808 304107394 137294941 966013667 933685373 396136547 295790829 486603433 656088473 807516381 124384849 215759939 36010446 289673781 498877442 287825747 319878992 192985243 484784312 100 732126920 853871818 680176576 126762102 763023384 593667211 23652148 254149116 661627765 100647494 556451467 744669 338860655 421592571 668133388 745759341 82783067 14673974 732871708 438678972 298903968 737141968 102618748 17607155 336212127 875950424 633944628 422065834 212019841 525007164 48960901 804689044 762599422 176807865 304770372 1883588 207281578 185114805 551940005 814278267 827246832 939871883 641638835 825034685 137476408 455914180 386448943 616549355 819890395 993417382 446480189 851832412 930975096 587573517 589066634 494861526 208168764 5476134 689746578 708297967 367852831 593888174 520413964 723770206 135686557 632872537 234099794 643386346 500041304 882809585 595810155 407036816 964263989 674347375 676218754 101038851 840896661 902324133 808480578 244292983 434173483 22361912 859756899 922896617 318463082 493250885 455856942 377622808 618719253 747517597 369230326 532537017 118302327 627331678 457745951 981333114 547392765 600816153 763141278 553095318 100 9671772 742997259 251125150 608300266 944564279 330762843 373391583 733046135 451746663 290502232 877162483 465251765 818774328 134293506 848028770 945438319 26387737 93234782 424189934 777266432 951003002 938521272 270483270 9100992 285012450 836689522 46675375 910664692 154317137 747980444 880363004 352788022 455081647 467486904 925299505 363221429 387101143 810668685 647424408 571800965 301385009 124472392 938281981 415718503 391670079 768025585 788667814 238663500 784829662 97935513 249656466 376221107 6783197 929651120 887293688 787590326 423638909 36992247 340854414 506843990 923526434 333780313 573098796 195161918 826225720 366468857 526085667 895222304 247895305 51612814 4154839 600106996 936686403 75534485 167050002 573617353 144476043 595985884 564848901 89281630 689335779 673146378 118274090 23418811 577327920 48598648 60964914 838255961 578907003 798236057 399878168 581858345 975506197 235772930 593000990 303561050 714271835 797459798 304370324 43090954 100 59572923 352146507 797783631 882980393 298905406 54817533 433725632 221830986 768561728 106416572 80312520 319195414 407452090 73361368 274190803 6260844 828283671 320807481 428894214 421970937 276173423 475629187 569196310 994770171 417683307 688478692 500119360 548708493 424442693 461208115 431151362 140004792 228506607 730562045 410349590 789774356 579285699 479770176 759980958 384044996 246030962 17200308 135685282 241564 85345462 252059357 736331399 589001004 994235440 571589593 589773609 451871985 349002669 627999373 859905388 579405639 209420676 219079564 624295774 281147813 870098579 451639983 919162399 315090991 23708657 253677237 892712927 637978252 774517744 417658151 237581134 956605464 458025030 79205374 600056341 388478489 10043176 95226889 725151516 114704349 304599837 278916521 730904895 144716613 179070631 231291041 127322522 396684612 511256328 720909875 483843145 556799723 979522581 362775250 112241297 930697839 498428733 371320476 961470708 900594941 100 589480972 300537310 402242256 366549451 141086485 28497223 596432389 480002514 949190427 196397313 276083277 364023918 695113624 310759839 731058298 160674373 13468670 263944454 955207590 708277696 131678054 154176650 262981152 767811497 578566470 308692825 171689894 909701057 842328479 916155969 497171491 333582247 56688803 844017544 855391291 297023867 227912655 953379597 699986100 787077687 395132943 620666885 798527011 575043671 639406699 666407327 505285124 919848361 725231525 659645975 782778871 962063191 907071321 846602384 120715120 309656648 541999068 567594067 358306776 58709834 866168123 161057246 533204093 666450794 398490806 97093227 60337095 853399652 928870855 848361967 663132545 510145560 315907984 255317002 177726644 669611001 285955370 744513164 688918632 81559789 678720302 8646308 810594496 551440291 839879099 286929390 219641043 660560802 727020112 914169939 246388869 965102628 312944963 548516576 593414572 337194528 470149698 923429212 184845660 581304597 100 33964070 435430441 965040116 9849 907389764 801501720 782668274 233935870 533128543 469531477 520956672 462111577 844645758 282914087 726287054 34314638 657540415 845018743 556239441 593173522 820803209 464442574 278769693 167449304 744578548 145994705 118852145 223280759 472396535 676338952 494019265 90790093 646100102 159147562 628057759 229357208 850476803 56002342 924317864 303835039 714829954 87042550 791909534 573447377 442033750 628423713 151928250 132785309 290560390 501136529 873119441 812531004 874172877 646026696 244614778 965877868 635509635 75935521 717945526 154744521 116569396 437622014 343275523 758703568 629369308 548171951 675087199 544440162 894507903 676385936 237531294 377919628 524609340 581588282 538998263 267253218 739644832 203297990 449755245 50831336 843016426 52863931 899901872 438204791 583803655 883105644 723419407 665551954 988582887 73038915 443671783 636379883 810038338 283088785 881051836 968467041 495837257 441386156 674641365 234554859 100 223049139 690232880 215275252 34881199 957928958 711329959 326677964 197527029 294337709 354286833 394848114 284716827 370919243 175478765 129767021 120427279 807355611 544329666 760173369 407809683 434242344 988380130 580289989 350206385 741515967 195404825 690243404 470630888 246888029 496375314 651847539 158191932 972998400 971744936 569171452 760803011 552711391 331712340 760679231 83112636 332847272 677390101 132353852 290936114 926449166 996320337 642784824 120740673 217246938 953128055 441791590 285178349 939308908 19179116 691169712 336453340 946195833 480776399 638337813 728448659 442864187 364897863 197688027 562013055 62867945 58356028 855560423 857655852 666538917 400851677 376962148 523160074 232906439 258740521 860272650 582969115 100464759 594224438 340113139 344281247 680381499 974866895 755306360 26077057 225124088 31465723 79900848 23507743 770692974 569608023 928167043 214237950 429152573 370009370 365714748 281419363 82844498 87502261 500529598 525265031 100 542254920 203413595 420449146 149900731 611189881 390334552 559464602 470684124 226539138 660057791 980392428 55106129 562119593 312645037 945419478 839864883 968142603 426945588 274093792 768376018 143258778 589461132 26445804 163562945 490380280 765409783 60370376 16498980 955606152 430753739 447519955 918762657 399051909 965623247 896982067 846985537 17090622 959326199 516149454 281164859 847582951 958051588 176402753 555805035 692711428 144093232 595678114 200495768 493168532 955092603 504385276 932051289 219856001 743995528 236246046 588298478 433599673 329912557 805322141 394878451 711066364 439424601 277976850 581084740 227892957 405158188 991152575 961678518 939175755 605644441 402450003 589496032 516013397 847187128 965071039 65219873 684621070 737718089 786822570 246751300 813584037 569090433 128000366 496421937 688582541 299702282 83568448 915808949 832814404 607507497 163993767 879236356 312882170 632733463 944756047 896259846 263261828 332763083 234455751 182945967 100 962498239 524643394 840411646 382265715 498267071 303285593 759168263 763245856 220252411 440958557 490877616 722203171 616310894 129840558 422691633 208079729 158326670 558643995 49477883 403545539 937351482 849605638 302062235 133810608 733329754 371433791 472042499 321172811 532173637 115937344 185741185 409154548 804592214 192112333 803214214 985035205 680442205 854095630 719207012 481710945 174407261 644534322 724252269 750917691 171371591 391355374 386559175 311755349 738634830 39631202 716806280 831974808 473703065 370723189 604830995 877019223 291514403 143477228 794190074 755904501 651810033 991284324 212568799 678240902 137370737 94117175 221965351 236930050 155709485 91647195 438910335 609185940 145929748 703961485 546232394 700257064 757421344 132229999 73041041 940971768 549699799 229942086 68654217 72040341 541688152 144106195 25251085 899665964 104137028 901806313 911481996 210305278 215555936 361085737 342845752 549605208 572984460 840978147 79974829 345772027 100 819989075 272916761 342233886 980324162 739049839 816496887 158504155 282782201 565061013 571951723 555742227 778021792 783330189 599068105 200809176 936111359 588252542 354468021 614848483 486058687 847758211 855054880 223381876 435713156 753886251 404739174 322633092 136737708 999715368 750386876 141932576 2950505 919709377 613504957 513792055 759589627 503776137 226714653 524821790 846214315 108788630 381363707 569439581 353424895 705679316 979862006 280246528 955660466 867525714 877020475 766656683 376815759 285318515 434267337 110906787 5779304 177199419 754712927 927474575 197350841 516552084 921391741 132454898 305137404 422491430 968034564 172346752 156020143 258210495 426434279 299991327 724341978 982346275 360053406 101247472 768018027 860168211 543009384 815108330 429247584 586574640 106828092 345732132 845102929 763115345 252235839 910555845 125303128 503054550 470872497 459284374 979749650 626545900 283602993 415406861 517694280 578404643 221832225 758223988 323958004 100 700174537 244562795 96980657 989442891 657946502 248087849 538556600 726845992 547530737 261865466 944112032 632563360 141489140 438171397 927711667 579813764 329744932 198810840 905182066 703123582 20601629 794769875 694644660 647387468 202114415 232519469 478518465 464496190 185585935 979571662 208016270 983832042 432997730 791923497 746646361 762438230 495018084 365259650 301853810 528140106 515375097 193777183 804191486 989841147 561799790 758274523 927582489 224005385 496068758 612191135 549024969 643289058 362330237 563918347 425660519 742855726 870784400 864925658 396051025 224169841 58363469 193622980 394858476 567267450 573134786 615230431 366617829 714559117 640743246 73791632 444158364 234639189 57215011 165510074 458541508 945602125 8886350 518681651 656250116 833186164 810499099 606988367 827630870 373893772 137262906 238270396 694143103 373803506 853812619 415980168 909323946 468457577 97186489 797385626 735386866 140394902 129882717 746363296 756339495 509354306 100 740683609 431941892 15926886 47868398 310200711 732409738 875121288 306959889 5881390 10518010 927212884 608507944 820941632 554270517 128206989 814905074 544167938 391405920 618252732 525427227 936377701 640788322 51914312 780070345 198882145 142441401 689486021 683404617 54876415 651286714 684099533 55125173 588163035 256462623 222400113 806007593 694858120 181830266 458529711 104157743 511142211 727081247 473995052 468387977 8818588 225376368 691288684 133014468 288463358 335651286 255479999 535637755 551733935 705580879 636405759 402691115 683095561 205515991 328924795 112577258 740963139 672430276 508287852 641142053 521518676 255801652 134127949 256534621 221094131 554235731 673514800 351130855 199094980 942019480 197608570 982898865 729816916 637672453 767146138 695283830 440819865 367594984 545440030 533473766 855797257 808824468 360109556 73497583 946230908 38250086 424666236 442318495 855927229 763228566 834055618 631647474 170495017 589482581 899960820 834284519 100 918797150 854552117 141607495 768144669 646703800 751946502 643881820 941326418 285218102 861317497 45848102 572031911 550597446 559099999 175392377 764015908 726283850 551907380 478969921 998322117 473181847 480281558 511855152 515173243 415976191 781276126 638544659 52614583 827439659 420664099 970981677 812359831 292490912 536847263 223404630 158982587 475675039 827668518 214201441 319583278 247158349 511032560 692085950 556393567 617971595 624922294 67568329 510488229 787865559 657552399 509002104 684869135 456673839 529741911 390302022 487030125 631566350 779184966 911595424 778340971 827880961 828729334 638314982 719585137 490626786 892488934 168047321 937536813 75065827 484995789 26731461 907393697 758556551 615098129 1606850 902937699 91654048 93963818 183483324 203060975 305257840 965489356 401072856 687409378 988015690 788073616 414206695 771144386 930167007 232281992 434133960 726706642 231842206 830289393 664212365 531651598 582813196 86458629 262054693 524610243 100 94224163 814818044 60852483 747232967 149445719 882506418 173629794 994990028 128004959 544371890 911238205 803812680 357635941 48343029 285991167 211448728 608287870 854376799 871084455 104783881 775410518 585190663 191342621 475940808 802610216 123806644 670643957 563000797 614968573 614710585 30557984 651640394 729550512 239756326 868688531 466066208 312995454 488419191 912798747 257511020 411512901 530560700 918656905 4695010 306857585 799388871 337299401 621011304 440316954 850762661 849364678 447836620 899902384 794534598 159553327 783595177 988974449 368402598 190467816 327464824 445830408 779515885 392207034 721513890 817736293 969458566 698437815 132353812 288385210 913117909 250312671 909889323 629239630 343275551 723932201 557347696 548423851 644741860 952694101 84192470 350907117 648301920 378214902 843950292 833203392 946269910 978104058 725123545 156914510 767485386 332137581 154271344 695025191 363280040 285033082 158707036 102131802 858619647 326105410 395534748 100 46724156 191904993 555276484 126412126 515105344 53329775 39531197 39910670 191054526 253349119 965954929 56527089 566265390 448721400 30724740 929514973 236831916 643976775 921465280 570317733 461408386 492935524 524874754 333289049 901410755 557716038 511982957 244094091 748625802 477457008 837759558 328420220 404566458 695233071 150272789 538690654 851883671 252090654 532612472 721981791 767007724 188624235 528486272 468055625 107149419 70481534 369496530 685553589 731596464 298646280 347033115 577466520 168619331 254741310 227856593 41190727 759632243 424049176 372949919 769916191 192129864 123601431 448993491 709211678 264274963 676215817 303678555 132179559 417855354 766569945 215328135 577216308 354387351 630876019 349012270 949511042 935069300 699147233 745009828 512253718 767875237 306117892 737405553 548919504 920372103 282570437 800248591 825314078 211882077 884778490 469022836 498037770 929808800 887212217 383467446 995241502 296166730 498881322 243613740 528693642 100 42564203 646813773 651009004 148365821 458154771 39449038 324643941 32979863 479653057 164319025 425658205 322630822 710868070 665937458 218324028 2636510 422136031 829457699 25454074 956201664 643352481 730548362 197480159 992939349 575291645 38859017 741171632 658122548 762131039 566045504 167420578 379305821 649329182 787450903 790410939 469104900 178603340 453571412 269622802 647415091 846064722 116017928 508615884 682633537 455435064 649703175 838574772 704516546 210352461 653340585 233791172 865803 566452536 240937667 709692744 462972555 330556097 578520734 12080379 626943557 319101485 288273034 684514484 394948416 697911745 766432596 629708177 190069706 274031176 344274526 956252963 27301666 387507431 65326167 31220527 126899247 359847976 462870161 885060823 479702918 230258077 780622106 601168200 439208749 141652691 771607876 150376229 967835586 869261420 991756831 516007771 949290946 716674667 858803079 118137990 658241963 517094011 574463936 998293568 658957043 100 543304107 154377962 732259384 745640787 82016678 781045588 942491906 393902605 957973950 662525501 578752766 764085648 903331417 887203643 455111899 481721113 448337289 676783125 430338974 704704103 887330517 346081283 963374770 356091753 557370789 225504516 167556068 983009312 108778173 862814273 606899533 92699136 645764287 209180310 108859184 43941806 608518313 590555690 644388328 546185759 225678692 978519603 985061344 31746382 758404378 820801177 118299965 650301777 654022263 129238412 117661820 944437674 232987092 118749475 537488184 271036087 690547622 245863088 123931060 706383459 884181440 420854038 970582194 192670945 674197146 386408233 148844516 694025731 299460216 59784382 327016873 27461846 721180181 399152040 727810435 654418868 885757813 657187155 780781022 726037824 917107893 499637582 718370484 999633107 102144687 848371213 539493376 429318142 802654685 978031380 244654775 109691563 27979630 694403483 765871599 875212817 924885489 935694664 698338010 304980652 100 162067850 750888945 597784325 203891009 240028434 877506270 896093809 822205407 818430572 30643620 11727904 712355583 708682893 837100693 990696868 965546900 318102914 349324834 317735751 669687522 532381910 398107259 852552646 808541320 88400133 720041181 427960613 600595762 555154543 705578346 362910278 978805807 649587192 705596272 885741170 361534920 117928838 22479444 188528955 985193325 32272055 278880075 160442799 209610022 612107602 898914066 472928880 253669263 487255400 867369213 102229395 598119401 124622040 698949589 728721527 414164865 474534456 912344393 513860672 844655436 858684429 583953308 687973430 575844044 814205317 928522248 214231791 767455775 533038253 759128665 446890251 424954625 616832752 817099092 91908234 602329001 567176669 89369880 431322910 293374120 13814518 551224035 823793930 814518803 528089319 340282357 598026818 488866147 823184350 788886765 853195444 659565821 225647471 404788966 247275140 596137835 832301071 68076650 338181937 176993898 100 141879177 131755316 642269191 654931742 323781532 180708538 693996448 425799119 388586054 789404124 992731295 726427895 340992463 520680751 309900022 526292912 248275150 28839815 773560095 680460694 376805857 16639435 915810123 791932586 726829193 898170950 341710727 513502660 125374658 307254928 579408330 693674059 150006018 158016292 994997897 310830510 925798609 684874770 802347465 379486597 440032838 277124801 553521118 57542543 206534559 232054314 897453772 148207918 457217290 688872119 627152283 455427964 720189448 997260668 148468438 345741561 997308024 44115106 765209472 633333888 477129319 547441115 832695698 508781687 12964350 587047787 586960116 210230389 901281369 128827093 247435321 981278369 568773506 725031666 115605395 496938458 740229646 533574239 488468849 932135966 738218227 684036548 162743730 121276117 648258298 746113382 502103188 50508939 106508619 362366275 89145599 690589617 128564039 397743108 578595549 536664454 636448649 760338700 413860943 684922106 100 161685891 410112600 557123425 455406488 78706456 373434584 249369024 876772052 153105871 732899051 221653273 307417350 838564830 318671405 802769236 253868125 878768189 882010604 189829561 350327054 112979453 596219029 992387062 772194643 740275006 274165064 22548168 604858686 413151706 376099202 554919542 731526152 393167660 703563026 775175331 158806144 223801677 936485212 304577859 286443217 774360929 919145903 661504504 63500919 863412263 2300186 600066908 531028483 40275274 279207011 567261121 168003761 222696474 992613600 88198673 66313886 385605043 339067754 211858378 194770215 373297208 364289632 380912811 986449909 143625658 108298372 189654949 308804241 225772043 41801846 319763804 306632351 637772902 208653851 239868576 189180464 427522199 400083907 43053771 315853639 443686780 821396189 377064660 606845736 797510054 760889602 473985433 298379524 256845895 442296287 122549734 538294161 138856408 347156397 519614258 747687688 831735999 783257830 893255454 708603803 100 854564315 680558053 240553284 709689470 366665719 543517284 698610516 853410805 598750451 980351511 640096261 782782680 216630231 386730808 394888219 49331727 997476445 426003581 884076879 381698753 924754634 812533478 954819485 11615684 916192490 142778488 985510992 352408757 121997868 120178325 195046990 792219588 83331102 336013419 510194234 839641304 821416943 44914471 137945976 474018098 756269531 568247156 755020082 23413854 450303584 971690008 46735035 626002193 709718906 755876114 345946269 669740937 905209573 383352617 416452224 183370334 399770126 972867000 970598316 882352540 938160877 164992761 101741123 144575406 440387378 873075662 428458334 127631608 58143410 218887759 352822094 58884386 865386024 608770495 927153813 2880970 317252736 368444649 294874977 77017639 253518650 300115941 685529613 831848677 845694833 742329139 627588614 886862205 525482171 336972268 730677332 486754547 821612468 911303096 782752876 485749173 328279020 483806754 244949090 899568139 100 698594165 505507643 664093763 582742390 231440143 798239203 642795542 275056668 829294683 801334906 426875172 406325481 567252894 622071019 647464471 842097498 599663572 946724206 68215646 956701857 299435176 775650833 436419988 598271008 528260085 64258939 692268700 114909724 602487655 614880793 525202343 750599771 979552317 128644804 161655192 204587534 13326972 44256821 786122205 108183937 905249123 172124473 284104375 246408452 482451795 857765133 758629006 563745914 49318427 170141046 891183951 613307421 508650958 62628719 819683428 655880491 358833927 871184039 588594692 547438789 50078791 733872554 875975865 148575779 644035798 274146831 47748463 611826247 453510726 763649636 458399028 290170179 456895487 9443603 887514553 326270706 459309053 742919460 262829364 356611486 61371683 890024456 896978653 558274365 118642800 554884357 983700693 669535748 372493293 302878542 449154495 34542137 480878908 597374145 815800458 352969901 100353608 367034592 404929226 255721659 100 929496078 420058285 756522202 808653317 779342292 882178146 955686425 283964923 524341820 800977151 495545261 322162292 659943684 534875043 626275240 521637640 178801446 510567240 963891301 759922496 185909911 205126058 756808450 484518417 779314870 67866600 668958563 582338073 539070104 534784526 160347167 326569056 94774194 173989011 156975192 397958407 800037607 900229978 385280814 292965183 119075964 910869319 166647994 743575320 120442851 951831460 923513313 88392303 645177862 634446583 155959026 156193017 618576343 347270684 558730592 318157411 104921435 950700045 585261942 521653243 522118028 223763871 604949558 898094214 761944033 483357124 509084418 27545968 780286667 145863284 358844874 55116480 383727553 23526447 600295690 17473469 819477296 37758340 864165510 736359514 155293761 149094659 362325753 914161446 613878973 394451150 7164246 953286165 274711341 507297651 872231936 881953193 385514356 142053743 922384145 833695395 335766531 160279869 908534738 177148100 100 778187742 530261099 711951935 146427646 380297050 304495790 277302845 766466131 986172159 293551299 709005901 45560789 325353698 176618325 769962841 900406672 534878756 469362313 371042173 791155434 89544144 671435471 430080687 367697804 290084664 254175429 721578104 106826401 361219604 340873118 171220338 617676139 285063838 236119095 832760762 170967645 672507220 431744410 794594849 738349639 604397516 512698299 474430025 756969757 576226221 548449530 45327092 491574929 438601868 568204495 564761731 725951805 772870422 537369764 893227033 146443416 313046545 463957256 801949105 568623075 933109098 438730843 800756809 346516699 409504870 904456062 856596693 446107899 258489415 644710122 897793955 959360981 186273912 869794682 911771216 280704120 205542021 445453727 687590618 706954583 527475917 173726174 509593754 389336712 434138351 828995687 978701707 158953262 833383085 192577166 973597396 780863985 945522544 380066921 704321999 82121364 387270151 997459103 884308966 312854901 100 866113685 97932544 230126989 14639906 563004127 76130067 215173756 164342743 150059846 765939971 732171079 958242711 154754002 17859569 876626464 723634076 599733711 363996978 394396155 382484305 360254173 680582983 351416129 734948728 84774398 92110813 335912136 736793982 655412343 966337386 683436978 109921815 55553996 400224472 793243563 551550318 856770393 185759562 61911356 990763158 278155971 986161462 884300137 26135260 743489056 362127965 926375028 46459325 147368460 196170183 224585305 769980133 877067020 794447582 606325297 86194489 219153646 168280711 887661925 515796477 578537205 89811932 593533627 502280022 783365061 967699799 414935427 152059633 969259025 793509439 842775403 378277970 959341211 13098129 524034294 17774718 502121983 450617606 177608875 887484073 440000316 318731141 518074016 768769366 991455219 467177525 806116231 498609364 381969381 295149987 971960649 89538792 159805084 938121822 922715098 795527485 619138946 623374160 745788372 811544633 100 745202462 454556982 60760337 931878521 350190598 42400733 877207296 367858098 675003868 496089530 130633727 178028282 930931606 244481130 50415482 525314502 970580252 219124627 858436349 901967091 511020158 10640802 843895164 354730537 342742028 835739727 766115565 245044708 69650821 787283449 946484409 375110182 264881444 667880952 254383400 222219475 905382541 410666479 194463197 32336340 929386209 28873852 356743938 146519900 193285485 310776589 274138557 319305819 278580857 917366403 526470959 112809868 209483963 877856180 936265658 767075838 275677757 697910418 554758968 688196105 28504445 68081952 326685868 485111492 818148788 536266697 449652520 465610496 506895711 383817074 850997701 359133728 902867377 317772818 85555250 515674607 74574560 28708689 405330020 591277508 252187227 879018936 558010092 57218287 798641657 488324738 736879612 222687111 711286948 74684822 878370208 18524115 859831545 623245364 976995301 497598609 167605657 271504236 904206511 511364433 100 667135643 427412324 203201966 941276828 824821089 954276929 750441790 487149257 589070107 301083777 522060962 479080602 657580711 578425141 727854630 696343311 253410857 258228523 204549592 891088668 779290138 735823098 892721705 96027897 48113817 388403329 625699532 9901306 693564631 605412805 49952412 626187082 783159765 460685510 579872339 730545322 360913613 534186024 554205226 784821118 520819938 172891016 454786585 836365199 43384918 307453201 4324385 831549313 909793521 904665516 12276668 233674079 496878688 359604420 547770433 827366625 640404106 520521914 313773528 706162237 247891925 938060535 668914514 750874988 365291437 987071606 780146773 343798820 255632614 965065574 633377612 274683581 603273664 121272910 271304541 923923946 384396740 929006221 449381648 111788757 214393122 637005082 542709928 794067780 722852853 781937559 370632125 999178748 8425968 872684880 950360509 303874808 494781714 733409001 120684547 997462946 981442864 322294705 724924350 981331550 100 273698953 838336014 895871277 59174606 336081750 621545182 440082868 330417881 145863926 640237359 979687211 265619224 761806871 204093584 541617583 596997595 354865791 923026715 747201251 597769632 169768936 272885612 778086407 44669461 935277740 576536624 848441007 399113782 385976809 380534787 331766432 897013842 119195798 939548688 875215182 415676937 743353158 11219718 864954406 266439122 146255697 219614980 946542152 649161742 182233480 903379547 8147032 74072359 18984678 710510944 278411311 673390127 813142875 546648325 697691695 96672538 576782013 819182977 24806045 478338712 500658272 555848705 482920342 369471171 549967994 468712503 789006685 64667848 373401501 309874321 346705753 18688007 115680747 284549966 483659706 957733323 651121529 648156277 283836719 845809458 328129397 233784075 884416436 488139475 868269107 76955640 60703467 147302781 309791980 776223453 819639317 130716044 170486984 895883212 420900046 478942799 224603764 801174315 86478716 648439885 100 305484830 630224081 835411131 927972940 520875622 763002195 504498793 649861785 291760929 992047095 535717962 824474579 66597439 550775915 8689983 146406888 897902961 348400844 455915262 319629874 406054378 374457529 456004107 308688672 962553076 481546485 927575218 382618140 893397832 602543169 967666670 759426480 106504617 104278083 44694449 345827804 658793309 510101528 839392210 258319205 887057179 908202667 80551519 868073397 657734433 349153038 906467656 988806066 500978330 926544427 330544475 507451062 600221484 563438199 695234676 387012215 782053154 706507745 321101160 834514164 547606863 482720619 578907583 950568161 12095141 55185234 311866622 596131101 294136135 962980652 758694317 534992723 632219792 504602715 608132569 386310644 852350053 792489978 325682651 638065380 11499361 283738832 533563303 235963339 219899651 242163764 382685216 6755216 663445891 840156606 753692437 364709771 995530213 557293866 546485707 104049989 626124897 846487404 606872629 416969754 100 168376405 745793389 809681254 357789886 814768629 59342432 428076002 239396430 124892043 223284132 369006870 982091418 444954974 679428400 53904038 981237192 952887993 459043781 777675588 685618809 718573546 739738201 205659122 217081335 283027501 403799311 531890588 962449764 506196735 853507924 108955164 413291708 547813723 293489513 242384250 834688968 365729434 511499543 782560520 458982990 667840439 232051054 943405757 194694663 830089199 726052602 734441776 926916262 435555920 675154851 328354666 503435945 387912977 737722199 64206723 442772554 509412728 273252461 392221265 447940748 455435430 476075724 546448994 908766849 406591987 767771151 864582549 120895710 573529207 721923506 269425164 542112563 342727177 835510433 979082830 257900202 109746191 617967267 333492971 113090339 799801887 100655527 17284162 735018008 569586813 179760011 310576706 570569227 358869550 177706939 853517271 870270513 558326763 502881255 423642157 356742623 986637989 243096965 802110943 358879842 100 74497153 707129707 982894297 38941159 755060953 75604508 428897749 477060159 456670851 790843720 179432775 857122711 605504825 995240348 26466383 930518598 690627965 533174108 20655767 286657902 731127106 410235209 97825136 38622015 343514140 995112831 518405735 339734946 917341155 596405826 500612447 660665776 874350247 3598267 674419477 666832615 864462006 629570226 694753816 677359110 487541103 931757570 377687474 389080626 272789424 988618395 929175557 403526173 722741523 458635941 170989025 686987243 873164024 38772720 968353856 528500532 320960470 391735293 537890173 857238450 67295615 17231519 890604034 289470780 422437581 357967738 210356970 633147597 808578493 628362390 535828285 621600779 616753476 180787573 985317496 461763454 721373651 424780791 434861298 888266519 138381455 808195269 903545861 61800134 635156881 401291073 582707379 786016842 756916945 200709198 884735561 841501110 356327091 752620645 256587561 358111396 800510308 731951637 570128805 973402457