2712 2065 65097867 579827997 484343203 14161956 545336953 769691102 48937899 928513991 1065940524 102201652 401476614 150703950 1039445211 194489939 176388851 185953886 720279851 985127246 498682115 1026461425 244645193 867480481 29272222 282281947 271283111 807600244 1003524852 122969271 596723601 889591231 338336629 300413675 59601195 799704833 324289983 4004689 251176658 492999471 196387234 376995735 609895684 116803124 825372000 513636135 760652180 446337250 746658498 360363096 738622510 878244511 788926924 413598628 802847971 617156551 517853882 880037430 276190014 467279780 758018702 925340837 57128233 457494017 35395574 464173564 289083811 551711765 9675851 778047150 283853741 593928203 311300589 241628850 600003633 114123107 306152380 1013607811 989177141 896306829 218541146 86280892 517789660 199793482 152079076 295145972 22697537 202753995 753706228 637388396 541278636 660246564 1064168774 818899351 862680584 543867077 832188262 795826961 116512225 374909016 234948326 646682974 392106973 992866984 218688616 527800378 615680117 1037666837 498681341 743291537 303260386 596354245 860686621 942613725 1013301433 41067453 28093650 104480301 1060951226 676295041 85059022 473707738 952205772 313157077 914714153 394713950 1051406832 598191092 553211822 860571074 312436198 689262700 1043209618 509103869 734584189 1070224418 589591036 479418500 17933839 519616630 967744641 632041929 566577871 924283396 504433364 802342501 827514198 250104719 153564584 698133749 654252363 325642695 693696438 360336587 29747307 430526669 1002709636 450969420 257738705 341895351 16765033 1072140511 766389342 179073438 1035639214 531684004 322826763 691540454 172998582 63724282 755385433 353841881 808312128 1015185095 392470433 112345654 128443766 815691371 1031183906 359199971 635251704 856108942 525639704 833080456 654399326 197786667 1019250256 453470372 942801121 411250931 312306724 1005644789 129348562 763474960 404094618 892896670 301699916 104756860 56115349 414379080 310342105 403275591 325880474 897750719 288136858 699902892 864731823 59056868 975322816 460071087 97733984 251554097 29233589 111275675 493715126 1042596823 290194686 147216820 31597864 673273132 781135947 674015806 181881468 33208352 543100662 556734268 1046451457 896860386 946769154 323931149 438875865 383673735 1042420772 691614420 594698844 318720355 384660092 880091123 430641414 81543190 1064696750 511967202 454872535 149295403 9696832 1062259049 219781060 877996243 786817486 896974878 868079762 374449873 895968984 375898037 389959438 618267086 342911767 874924294 545816933 109149214 133738931 830347803 444840715 278857283 523324755 957732686 411409232 710070808 421072702 359430653 1022263167 252577426 508354555 614659294 887138577 619861656 604417991 982347278 337444019 43274228 797795155 726783914 31539265 183583356 997098940 113819278 158143526 359741353 185295653 332550193 44849950 381126157 997428501 163584964 980121713 77229688 289146952 824993447 804319887 809528774 1038146032 286166111 441335796 451906041 165569270 609600755 558016936 130484822 144501438 205922530 360196264 546566081 478373876 813360320 228750533 830280528 202925802 700865299 15524322 1047992490 996742755 970309550 172215311 1046260498 947049424 478996452 864288626 872137083 741996722 938050004 870272057 909598212 664930126 249533796 176138549 958429880 29115325 931248109 322080556 620587283 1032223532 767522639 28419287 814211127 506673977 582795186 424780331 856289797 605839157 881738515 851085202 179590735 778232085 1033612807 798588832 1049451420 349905361 149085191 572917899 644245786 775630101 145098170 286224921 465889633 643302657 94486011 702505987 656772739 977067615 751043249 567840292 855407889 330526049 465883304 967243643 1018038058 639203251 1069291681 516319569 990957006 433779115 816307608 690052406 591562254 7242239 468296037 737045281 410407918 454940551 769265288 11462054 437929950 947450101 139235637 887654220 363600686 616276835 152263733 663594318 521736782 652031591 148083022 1070955061 1015245022 652102716 589114032 356607115 448244806 1047369915 664281508 554542705 283890688 272072639 772651895 491815405 281916641 417418882 645894018 1068910126 1038512888 357454489 310570907 624613920 490931368 85364442 423214705 33566588 942495708 561511328 746456536 577597265 100404410 432408418 291370186 653749990 759573661 1049143494 407722672 237008786 17792441 893275240 772499020 1045480509 622216436 390717598 305096075 579220277 517054777 799687958 786541330 199084544 696377028 684634701 593978902 68719708 475886371 263897556 658973924 334333188 719592389 52151272 259784747 273200245 478151793 653265792 478587187 891559999 404748232 803068148 568897986 896061080 599843499 435077669 694603506 928907779 616198567 462172905 655816215 50519898 199338433 32456102 320885720 391188947 602230123 1028170984 399671579 4661141 226656858 218143244 338830126 939654171 498176591 101344167 922662576 730750657 103645353 457029554 1012678218 151495517 767484501 753681542 507629212 416633199 533231248 439296815 846341859 315491508 228307556 74594007 547041731 605437538 166604906 927425130 222442545 417483014 960288184 430551727 821301962 889723935 368127318 483409736 335062495 508521678 298807225 1014419502 165215162 875604614 762312893 557848380 862751608 863471420 1041724200 650104053 758429300 210802325 437087138 642286632 624020239 647163446 191740995 461075161 242341630 517910671 454907655 359977598 715209681 335880938 1052812903 389244896 43423064 225350052 657718154 952435292 57012416 722848575 443606993 197126013 216271909 719982439 745627379 634870556 985444262 387637193 1008750997 176943737 519232853 646098924 967284425 1060526339 782051787 428779148 792770618 118601665 909984742 94968459 30493211 15695486 736662705 109424893 530128804 907427540 163621036 190064664 625174682 7933188 655138468 186933971 687336337 156133489 1064837692 584643327 172584798 501718161 632416266 239053816 316309904 545148116 848712789 552556508 273463115 887279848 215292173 496275228 363523147 263914313 660167076 660254227 620254030 31875892 517038451 506459246 716062220 116404268 420827138 103744356 554513346 686101413 358270186 617277000 462719838 415571725 680656381 1017749815 243558003 849820926 595128606 844236196 247825199 1032978151 528587141 851954406 27896215 981683780 149611460 675176210 312510595 202596225 1043785971 230427818 265130245 407108390 20910277 455859528 225002608 626923223 546791605 195717282 370590646 723508842 878980569 743779948 161436101 1061938395 901958883 1056833583 843189385 876160542 518495872 654531927 182328798 892234204 355656478 365393939 287125666 452773804 271088600 263317927 948009609 544043098 1033689228 148350396 588617388 56667980 224356449 345934940 612705123 427733820 519471077 292751809 825600528 160226829 926633235 1004421522 228627344 404875795 195263313 532379814 431610128 88386233 529566561 36151429 328505116 504985492 529581552 676333689 823447888 734609074 1062989799 681189578 909494280 726911883 659261710 36391882 561967238 293756269 477022808 1028184156 173337989 354623226 436869309 565973283 939008027 606608537 658145411 678217990 632165121 21363120 849551292 438211088 439722575 800309516 843111074 276939639 6829435 1046681979 524623497 701981000 219930216 892001280 793477579 984063282 48492548 380459982 602025530 250295177 667505673 468855065 678566014 514511427 930155570 76920720 1010596679 233243006 927039911 734280896 448193447 214735199 652589451 481835193 827418956 48592586 443591138 481634553 390609280 124801719 1061819637 80862030 226881063 58699873 802012278 1054323564 945535472 251034229 573059164 505681522 373683873 990963854 1015047709 1030750942 1070852680 1071211370 549193023 432214623 752580201 578436437 417804529 124992057 975500484 1636837 824031245 884180464 22125448 136984916 230769863 989095743 271501912 863069234 366167317 64661556 753982 818107706 353168957 724927041 165966333 109241452 103860833 629489524 610469959 350877070 855346579 254289911 463786992 142671011 366111176 887940102 598217907 942324157 459458695 929418912 131756129 874221403 841452087 178553701 513742126 757430885 204886404 595738743 516727645 555989077 691996991 550742475 935211957 548415212 279023130 870581207 634091581 872697825 666777899 915564113 263194520 554692084 669595176 898297030 163910624 599706209 620767824 195432480 1010683014 630017523 152205285 821848691 691307544 519958555 677977026 915939111 643688701 486846291 879077516 432376772 200969076 491010257 867748528 30283082 169760462 645183624 385940999 96439133 593737691 935603943 79635894 1003891605 570749876 6522882 399417085 111832960 374998615 326538110 516789429 116390662 268686870 831423079 94631785 1020013334 207596599 927506410 276831918 945248823 586576864 17702526 803211742 223700807 482404828 94585336 399767293 76229901 539729670 4390075 1000080200 432831340 835689476 478340386 494015839 82249522 164036966 992578731 826549985 800429334 77770290 543473259 11333755 469770072 682948173 806709275 523043233 824656661 488258698 253871602 731769872 419435570 134398859 449134898 513712020 746836045 343960447 622806753 83430037 151994253 328010131 845434847 91972065 178960408 622297761 24307960 313015595 585025204 205102473 943449006 50683964 685029604 863440372 255798139 23208534 80065400 247026710 546559225 827380228 451562078 505289360 751217000 1016601778 946896731 510225904 639161198 97757189 502024663 725731648 736717427 911672336 69258845 330257850 692928768 136879807 748248322 361933894 640727533 460692663 166767404 1009307850 423705327 89968290 789075764 886795148 91813518 233948075 399788485 434939978 755030358 76306504 817820791 795392700 1049868253 542329354 666167027 822059805 861531389 149224110 565191047 266601683 126639465 228302470 90804657 940225280 1001999696 600761775 660602844 1052347713 494966590 532681296 877826793 271629704 146563611 219626012 494533932 165085038 334088236 450929812 969042255 339092247 117942532 199880297 640389697 730234740 1021171211 419692900 1016167821 691935322 231971438 871474387 804896505 1071728780 478859653 408685727 391496445 993494903 439099627 597836594 1005573164 99588333 375278442 809381092 736176151 794197285 22091717 863076535 256576897 88266716 452214232 578267552 449204122 898314558 458855778 576947621 194388417 402007714 797933065 315728032 839586858 974702806 553925985 41565961 508705814 737867047 495000743 944432229 995833822 646783587 500856972 723673338 620306514 416325144 627710712 579447026 240582753 197584607 667947763 812076377 921574434 339111582 837298583 1000306952 586596753 51311333 987763734 779439928 4453161 451897744 709224946 554721605 308574832 1024923404 581801274 20654563 641365576 1047992720 454970963 110614160 109912548 794058404 864475644 1004028330 131973466 500879492 280922258 908239229 678358930 1012662881 1025194954 327662320 936758170 272815297 201930820 821324303 929706126 854409051 408133428 1048490790 541268835 927661682 730961013 809721841 787017003 502567559 407821023 12944962 642912262 373602594 483213658 372715511 33395242 806304393 119467909 576132405 32193543 567774420 852815291 897544127 52148302 410745754 80297656 483754112 859412217 1036197084 662300063 220146222 484132372 204851843 266472418 364076106 1072237988 350233543 326128273 792718829 452528444 193879520 279249984 1020574516 640433296 310625398 134001431 734652989 1042316878 801480929 970940295 850393309 957035651 903245949 506773153 774115457 310794852 956145190 880445338 963695904 131497312 527280922 501020622 531803065 718763349 807309796 736661491 648663371 8728624 128151003 1043976016 209353605 1031469344 114581221 670038676 458482776 200945449 199290976 628851270 120119173 806120541 208281600 850693426 772844688 768253727 985580425 313721888 673070638 205152732 871850561 718669331 1032878893 216769103 960757994 49673479 954746432 706916270 721526987 444247072 758568607 906935333 391084895 52213488 58882942 53692465 875478003 634958617 876544927 610073732 505615902 1043857496 724699261 179324667 294692755 411890432 245948647 701415666 135208332 115105188 312193118 815548838 855605290 47108808 718156591 606562716 408926530 12865085 501128058 143448538 49402271 681772253 793937081 225173173 944895822 176683920 662212196 294234958 839083421 386296091 884115894 601429728 259035899 842387085 578382155 247419784 863339721 414469933 1040962277 911418792 76178379 394117512 800061073 144974353 1012277196 819181097 174983021 276242902 356368060 660757390 606518356 1040116423 470987993 17291656 1061694476 138737427 635501385 946741183 487314814 68887571 90143727 162953256 94525304 143471513 613928373 620233541 88823694 264960297 567508423 416295197 396802546 195291274 426313603 553869289 760734595 80352387 438507089 680294756 346811042 96898588 1033248019 259171164 45776926 836491112 483172015 603367039 646091868 448132132 967765736 170282027 958891299 601900860 734076627 1063875101 227430797 460017645 44622382 597674591 364256791 18335483 261211388 37470540 964408773 720200288 961021723 586469770 483819770 875671467 593156118 1067247620 966295889 480482682 326398483 275816533 370543280 471347079 317643355 811271419 931743539 346427411 563347726 891661363 5467372 562373807 243644176 347412437 577741627 153395189 892516812 135494199 799039543 583026159 264684282 910791463 879203334 16932900 995194656 610147999 174650967 320386875 406314346 741426582 670602550 559963332 308330441 264067421 895744958 799373211 1069641152 1021311016 293018900 571343134 695638786 430919428 1027061110 297591287 321814903 854882983 892490922 243450714 991798106 799450538 102128882 652377632 189048539 711016792 760600070 481777772 305653669 390035744 743036089 978532940 767698230 958632972 253759658 875351680 856570940 119144185 361321276 354492978 577844113 22173630 482885406 272788872 365174091 21268714 585524631 843587061 49171295 595003951 898634740 804212058 211421997 201303120 264577083 742173432 408922607 126725217 930209383 6741295 893617051 1065658345 826752830 609537970 188442733 717679887 707762841 650179320 221956455 519872944 401351932 627445490 790816521 1066076310 700875715 505977906 550874878 326558526 221707592 104430693 281875025 1016221144 569188788 874531564 644980910 151520106 29925764 364569121 539902119 235560141 1042592488 916377125 751968950 554687886 93083569 19751456 854850050 742753418 179054871 411570721 871768421 288276628 246687907 161835931 471680293 263888684 695741573 297892272 292986785 566407310 727678665 910254115 626547222 677615571 515993606 720473397 503394751 62231080 1070601344 91841558 180260301 468135306 1055051241 286964842 296550600 933512636 170086588 541034891 522363961 1044308996 303897103 489008782 313289682 382425375 554479184 567195854 869192893 550050232 241500611 268389089 382200311 137813559 323230329 949117620 1063507517 21394522 428529295 1011135550 544428648 824024072 376873746 302816401 72385034 1047315790 505306418 1070989829 135249636 156080136 486299844 427556003 651884758 1060726768 11093715 196818010 842897385 291068701 775578283 605835890 1038134029 15998988 503181331 281386121 439161489 286636205 106703457 640607348 1064599964 507471691 177568758 49617599 450123076 261237839 209183533 811356920 204265200 226136210 1038659836 450233910 1053874446 329297103 52000364 615309109 279955338 250915422 554912020 107740483 29435597 76978468 116348532 771742669 939724727 411210498 597515399 73125016 341728849 377841450 794638312 138346223 314714204 414926422 463981318 208859266 644783185 639717549 129349601 745046529 318488193 346005805 200877024 908748828 428932815 756997820 206493339 768111577 220057776 662164429 702996889 550766816 712320843 1012962534 841196959 1024394907 544844810 52823125 813158259 1055347067 122835354 105784425 408451955 800702232 987390037 569917556 270929823 913199295 917743927 668993811 486663229 271012729 644859573 794606240 482973805 171463497 127707822 308441494 332043142 752267470 816615845 1034793082 993155016 662049759 878234616 179664228 987501580 571708324 998040699 973024981 345593929 605579943 87093513 871230356 808658260 273679225 350098050 518689729 321306020 706174226 668970041 1040793745 177657259 393050256 682257660 941088674 29426450 909996788 884006432 767223704 30799583 1071379057 1029697896 112186896 674845607 67148763 472871284 542824414 764016240 880528932 241207875 828991916 704473836 910288201 947918013 611115022 376598190 259459151 759505365 201880813 217664494 183460875 924994425 799653517 445309488 81809686 847283380 871041503 204935944 715066017 887851779 106354929 762907755 150853709 896567956 662514185 914360675 497581476 945478225 370597825 479532590 596326274 879305907 119845719 2548525 81061898 819544245 222299906 524296882 224936953 913969940 829512846 868365609 281771630 378061559 909073976 1023929256 597769844 729166326 792509283 451591240 829801712 678741079 734554283 90819033 962364211 344560442 398166860 315492179 821683844 615642017 650556455 681934288 300091156 1018081205 122605633 724984169 838579376 838805131 419676532 548326548 225723679 275245375 833540314 1033987062 992923128 329472324 903209243 488454921 280134973 265062432 1058340623 471099277 251557637 424428119 67813552 745747547 524470659 933276273 930061165 239652822 503693075 26547386 530687665 431603810 19332035 542016058 587025516 557529727 647353423 1006060416 795394823 172714359 74486248 734727049 10877506 200487545 456819514 36442967 49193321 130173328 691453865 376865099 724149308 425635721 342740599 730629118 11346493 184842716 1062647776 521324149 692329850 53371922 874111486 690721502 1046666556 323856100 150954560 900979748 280592649 779563334 509374308 784834215 558948995 118061166 970407651 610611904 1051941278 127994425 625979846 646170410 235880076 226666845 1062574628 881962520 1014729923 1035236570 781341332 66796681 942180164 146297661 732532471 685849520 280862470 984949484 846984680 96254280 632673395 720028439 1021413083 483897817 58441547 776754412 863099815 589141878 1012553802 307434571 439849772 624054322 1056344864 487374645 204806282 24476678 433517972 1003724096 885342695 868466556 190554830 659256327 924648750 447253577 307125109 301774272 770354920 925716651 511697563 497993095 911980338 67990213 871557460 986974013 1014515445 747317744 700652151 764326451 335028603 907256385 214622402 439148111 96489338 444402677 864978189 853869154 1021768538 39574284 212012372 990315200 183174548 366590169 936982300 676249050 948739544 1045485827 53215760 1059720294 1041322719 935221198 723482725 447691402 286003319 914592959 701364614 1041187319 501991886 322724724 221142387 279077230 753730551 738711972 876502087 25964875 150135888 340594753 990436286 242465511 977849585 573611457 302838354 211131211 398261064 903392317 143097142 397334453 81245428 480562539 757292371 1068606131 215398812 760622106 275933622 456586445 559506762 100761322 505113467 743156270 557298398 564408985 491672604 626763297 905660931 320151324 81594343 912437235 525474191 81243570 397219669 744815588 152038356 667923093 425194811 423864680 339531881 256826023 226876505 559023466 1063376285 271220055 49759625 921487844 490255463 480710725 889368925 394948955 993939824 340283132 570104929 819993068 292804728 731802079 635026314 225460286 95475905 754111235 988811938 508290890 531565324 214138709 10580736 836171361 770194979 500825304 932413075 856868193 488486137 291737799 238278618 300826482 482816162 977431244 885322966 441395190 454232885 123639277 107468675 179889767 488978319 76061561 822721366 474498612 427340280 352692204 649129966 447020120 572769913 325908529 24130884 67912817 428198418 125972322 6937771 696388792 849037284 722374902 334603554 259593333 1007347895 795412455 906237308 761057628 306888774 495395855 123504654 950287851 596965182 105873977 519130950 769631370 310245785 561973022 848961300 901328334 995522318 390678369 906159809 919207498 609630909 189165246 44777572 637776808 98767023 867438219 713770700 409293684 688998626 907089411 54136388 980891574 768553069 342964688 721492078 70894441 310902552 336387534 52127928 879922539 802384223 443463195 219049314 716180394 486179497 62212166 768356202 55828186 989809095 954376572 902483385 279888122 709527747 834634627 989746002 820583 558881520 120003846 285218434 132934548 247892945 543001015 19519921 35212968 210539662 631441036 289436310 862588946 591881004 370958439 612766069 819670200 17878756 225325315 1050104376 35377588 295174390 633001377 419824035 847552014 362477611 6226547 300724788 703613618 135858556 808811755 806656676 763351108 1007530848 199480535 809117825 518912831 897180528 977516242 909662264 414834101 138291709 1040779770 802839030 254113722 339441463 145012795 387731209 521819991 736475549 895124544 1003048926 933992139 732932096 960642524 220947913 322598121 495937082 869430651 798935689 378260360 584206681 1038042162 255164471 148459623 774502564 936707333 522419783 739336775 338934160 930750878 511321561 451944363 177235900 172270046 725993623 993114566 261346827 195957082 433182911 820880464 461657472 223878393 763368860 645456327 890071809 133121157 1052043335 624361885 909886684 84678471 821760751 260959291 565030648 869416507 674114380 629030832 496954320 8999678 480046978 112400284 371074069 715186122 390073826 138157631 943097991 84268768 872557539 759089904 570330763 248332711 356751378 972275417 943872767 274715088 729084890 320822915 329401915 112337295 785669759 373734667 649198020 708049235 912454930 407446547 660903211 734988556 887570846 366356987 911354583 473398895 465291753 768620506 221672806 582060260 844553926 984331135 857162306 111424637 685301396 284133355 116461343 369244181 303077933 479373911 58769811 231513172 818437786 863367076 156701676 202320617 950945094 754029467 585284876 410129442 144147330 365696095 48193308 704270432 330959528 365127434 355133342 300933706 907680354 262839454 859983527 914781386 145541947 797560600 955382544 984636430 489814325 499391317 803278205 991679439 428703517 285573721 999372808 635484938 190298945 106142087 114027339 667791196 585844624 751957647 831076574 404648811 865747524 171208989 1040538655 189150947 84850667 562335856 119535451 1042815701 716926913 1004865185 974577747 915692864 109834519 371577529 843358048 397719553 105961964 240996955 814303367 441769163 907224450 165262230 243916386 405598367 1044680820 924487540 284705639 239542500 242993965 657080885 728165954 345415324 182525463 515174102 988013849 658830099 348710122 300562015 536006613 899941010 711345664 162456332 57919553 735203830 875117740 151640815 1010771513 674276063 600520461 690044416 481160076 123336388 305960454 1035350047 308324441 549151737 600344112 582976758 945182590 392315272 930175618 696622571 1049117291 498577974 804707587 84368448 639178121 484698793 558313501 227230141 873881380 339993022 609914079 723437054 49701094 135741953 695392016 419642512 980918331 335199656 55051080 750297776 463156144 727726944 1073358827 492116960 113496695 533608636 426681351 13888624 544789792 189247595 905633931 1005163426 165285399 653894104 211835811 594407836 753665730 276968000 157690633 1016151710 12330512 90930114 1058040208 348065246 208963522 604162865 96541165 927241795 645417115 75436206 45437352 757008118 554792566 340360879 867798890 818076380 451521262 976798797 602740716 673314325 901210820 428182250 45079940 407398159 598802522 732036421 903035896 120907199 520641454 506442298 523004009 194729851 692591513 50380915 587335051 1014152966 994672741 109532717 489614597 458786678 602849649 806254219 58090680 959407021 301308788 365988324 244871627 866382875 412014388 313035872 280256715 828239940 1064581096 841043380 177115221 229497092 320827182 927322819 207919828 858240941 800653184 133326686 373467202 624200201 863234753 211107792 520816993 550825149 998881579 865915565 184668881 718554188 337835443 141733163 580079527 342591208 645249561 202559278 754418353 475970076 229084315 24060340 706917276 29939887 751668869 175364337 236379274 701289608 936730057 395876534 770531546 481400503 1058586007 89075704 56450045 1039125437 845724859 177743044 738380223 567322336 169130087 983402013 422896662 845038214 311848399 711317674 710602051 449312839 962414798 339278608 366958750 111865846 879250880 652353776 692428250 1015775817 241810815 1006930018 132352579 399456151 1026865238 544836367 641389699 667880103 696227475 881735462 770816952 679631001 411933771 510837518 504668051 532993100 661657789 160182068 907027925 277649655 1018623518 729094126 650096903 335100902 251307216 36429647 719685980 707531572 141643653 1016254569 301886287 995096162 924994596 798690899 40312470 675408997 391243426 548325534 940380866 935440003 211090517 1057236940 395879857 1021738254 215626098 561510078 730531325 421626684 399005192 698105401 258209952 374378022 686897775 771670728 366510678 109231656 729956289 770814219 224077336 694787533 693772647 343621962 745181444 188402936 589351918 922749205 1073384682 658127406 884198353 370396873 439747307 304905925 164530793 258879598 384871360 357295259 813280673 48534744 384733382 342011295 301145277 166278863 521321726 44914942 256621591 444394812 334520054 1036150170 914850310 51563965 478340862 643366650 1072518324 522632106 163522537 828720364 716423614 1024828076 488970245 953781067 789891829 197832771 785885431 801170761 989028347 766792948 77985859 425310902 842495347 769210316 516123023 472680366 197863069 762064990 383099873 32501346 822780381 78618960 904520601 598110515 27931562 807797192 56147661 761497996 840162539 749085299 355972718 457778543 187281759 648890541 568785409 132855564 863675384 855587968 1011032916 205751661 309172599 844250409 497449688 794451793 704823412 121213566 817343098 370766874 535729696 467128114 144319917 473375246 655717055 393160818 697231763 795518578 1025010947 496667933 1049245248 6092873 93523027 568128538 233631018 868918563 395901653 365607767 130954770 764690914 974818018 202049657 1035204976 1068603206 977894072 260667308 217679512 886565770 1040492505 65704489 422936434 564053094 350220565 387925546 388313656 348150239 228999015 963062973 297287119 974724963 722422052 83715314 187826771 234006612 403055056 550850953 595961239 392562834 816126368 500610362 506494838 48798527 783371726 519012665 1029111344 211665858 336674012 928519274 987851719 860959945 87442373 972962595 326575453 943443042 1036979719 648296752 192010188 612252012 25713289 965606977 124883095 416252401 911593940 226962814 920462546 799798296 355791176 400146561 386943763 101702700 387269425 571460473 559752724 217464354 37013848 263110461 401727519 799086175 617141212 259413142 536237028 685264419 812748447 161994680 421184183 862517351 727793666 880813303 84955611 1071011410 403962480 5833935 191678393 503874060 458486249 50656527 494276117 195511115 1050783340 487727815 624555741 237071216 565162532 902499116 629201301 163834496 147388228 379439922 11618212 386620142 774248100 680420946 889444785 387497208 805029269 158067530 964001220 656665423 561789710 869622297 37162666 989249822 733583904 299608203 286186658 561827461 753461029 744702586 144 153 945555030 171 1685 166885584 100 498 886363650 13 977 149459606 284 1232 428688986 532 1537 296326865 1082 2337 465865709 600 2444 517072907 1079 2070 400896536 1359 2497 39724258 552 1925 1017398467 851 2009 156808421 388 461 214432220 965 1333 304026621 1134 2394 520968045 1289 1368 366240051 1108 1431 448790282 671 2659 715967440 1420 1804 53635668 1336 2203 864774177 1716 1870 66793120 1062 1443 847343950 1658 2651 91047528 328 381 970152591 673 865 852344706 1918 1999 341880856 870 949 413135653 1599 2115 400511444 85 260 219021207 495 2065 744917477 56 2074 244622814 1745 1811 527804035 634 1504 171938612 612 874 338823578 209 2312 849282334 1223 2012 320777478 718 984 760318221 205 768 244527842 1248 1483 749920128 1924 2294 551000629 37 1072 28240498 888 1840 565943953 1113 1440 430544729 1391 2135 638333013 164 1867 344635214 910 1306 59075293 126 870 678721314 1588 2027 2107111 919 1518 804089986 551 1977 346907492 724 2463 393395031 2337 2515 407234026 304 1597 908631753 285 584 777877036 936 2400 737262249 1175 1789 901626533 119 2604 380189455 1175 2168 510547692 33 1951 128582173 134 2556 955687021 2638 2675 558924514 1424 2647 869780870 716 2549 103121007 715 1398 444643526 766 1548 113797185 532 730 726910769 1067 2297 319361591 1198 1550 141121003 621 914 738626802 126 1333 695749566 352 516 229241978 1646 1886 598496202 950 1063 886674315 2142 2266 599388276 2350 2606 350888095 1594 1867 104982714 1891 2677 506525984 526 2531 342713376 293 1166 108319193 1902 2253 360354771 83 2131 641616891 482 1654 939135798 1447 2651 81994100 2295 2701 784959591 1145 2629 321925135 1220 1779 908352021 149 288 623383561 1586 1855 290555140 198 1230 822844209 2198 2679 384177000 1265 1756 670189717 1170 1195 600574023 108 1391 354138443 1059 2286 961208719 31 1006 858419621 406 440 45894683 1825 2552 471019411 2223 2640 564528763 344 2345 744662378 91 942 384921144 178 921 293582014 864 1130 180789195 226 1944 415237733 1003 1016 901502052 351 1071 378581593 1024 2244 429360036 591 2336 1046310020 2498 2538 166408663 434 2576 935056075 676 992 542253560 460 2302 109494284 328 1434 199266084 939 2042 499652003 771 913 10886841 1106 1748 1051211588 2416 2576 322681820 779 2272 504386750 73 1539 1071735019 1267 1422 423774208 1724 1809 358074137 491 1414 936977115 1471 1610 598127879 359 381 51517722 314 1189 825748420 1134 1961 91360562 1354 1590 903729473 681 2596 429185671 2314 2320 294505752 1767 2188 370774262 1849 2377 977941862 914 1499 364205970 3 1341 934362365 1379 1689 408702789 162 486 525618281 226 2281 249417409 1885 2347 935752692 3 1818 301260016 989 2141 88845176 2153 2295 512240609 1490 2198 924024241 1343 2555 85320403 966 2269 62975548 1782 2146 834222105 1408 1902 593773049 21 2161 239064889 890 1791 745986999 1710 2648 419872171 33 141 522331669 77 2070 625335451 790 2177 719909374 664 1181 143008520 710 875 885668078 185 786 894712318 220 2175 123142318 889 903 674008080 10 2674 666201503 2061 2200 936740289 541 798 720445210 2180 2356 234184161 212 564 273044519 1693 2015 776729503 660 2392 694281696 1670 2305 543427881 329 1290 1029345483 540 2351 513327311 510 2421 908603886 783 1693 225806633 1345 2226 586176400 1304 2280 530023653 264 960 576098358 323 333 1040958758 664 2096 619617139 1801 2118 317717620 2363 2511 279986733 276 1004 1006988978 1564 1823 433716824 1532 2490 934337610 1360 1982 302588448 1106 2283 923168955 611 653 153484508 390 2136 70790561 946 2525 276852034 1165 1728 431479856 340 1379 732402788 853 938 247103616 1631 1800 287262315 2279 2501 213192589 793 1354 817314507 914 1011 1048655277 137 1888 995462085 1704 2670 159655908 360 900 646633280 15 2063 660550334 979 1399 49735745 1504 1699 167486750 490 977 708759715 1581 2467 326696772 573 701 962379062 2252 2700 934458149 1333 1557 156945068 1600 2163 883159673 891 2515 264636112 1422 2177 563663970 683 1486 525795199 1162 2504 110123001 1891 2699 570082133 1001 1416 821514702 59 2111 756025534 801 1169 752711505 708 1656 709846517 1198 1920 938707671 1939 2696 228584074 1335 1629 246873935 1222 2612 506070540 266 1996 306483592 161 1849 65937639 1210 1661 924218408 112 1469 173737579 1394 1606 737953046 677 2166 89854447 1440 1739 831745095 899 2108 705568291 347 590 546666144 161 432 689000474 1737 2179 950797583 583 2385 581703892 159 1430 177791749 679 2197 289511517 1984 2144 944572279 1740 2090 645826643 1665 2650 1060287380 1098 2242 867685553 1547 2287 784986037 1328 2683 241507392 649 2027 811035675 1325 2557 585421054 9 381 1069983490 993 1283 478853526 480 2536 789057476 934 2521 423418115 1295 1934 1060323040 1241 1675 493367263 2336 2637 523810006 597 2413 803352555 758 855 237327459 330 2330 478315509 100 2473 995407291 1459 1721 484682569 482 2650 1069080625 1837 2034 458909796 687 893 42983654 545 1755 997605536 751 2646 224794492 1797 2425 475507901 197 2239 142985803 1419 2524 455019123 260 2104 1037465295 360 1774 193034706 9 267 548187254 247 1063 328053946 2135 2217 930407933 1283 2025 50928462 799 2504 328132539 2040 2657 169928785 206 1536 897664231 2348 2440 267370518 1640 2697 100385615 149 2510 570221037 209 1783 715230263 231 592 754898685 2055 2235 722766530 419 2687 541528266 1624 2194 206789298 520 797 957066330 1253 1662 501063429 28 644 218508084 1430 1612 546227241 1353 1815 44597278 1649 1689 546710218 142 768 389648046 1449 1523 7580301 1494 1655 146359196 119 2675 140247730 542 1140 254148928 633 1560 492915295 1755 2445 328850743 1613 2112 817071850 1149 1156 1055283818 1028 2674 94328007 177 1799 693883462 325 1950 400305718 82 741 1037873411 1697 1967 2820307 94 772 1055978268 1086 2155 125651767 102 1851 1003436067 1649 1911 656977666 503 2029 101051870 447 647 996437601 1702 1848 178203343 1521 2143 892900457 204 899 689486448 275 1081 964857700 254 1997 985873705 248 1644 99240366 431 1717 430290450 2157 2560 341755074 1230 2551 840839172 1302 1468 978783009 1526 2190 112460597 594 1197 599365169 484 2636 333463302 1030 2107 247680966 1662 2188 765403122 106 1784 561793722 2400 2563 608585966 1370 2110 1065537981 1082 1206 191102944 1120 2355 596551316 579 2404 895850920 725 2330 366408831 608 2177 279872717 145 1428 355810580 390 2452 694914872 562 1108 936789255 2351 2463 170662792 695 1068 742316925 189 1129 511183278 443 2335 359445181 1220 2276 549984824 922 1020 197846830 121 140 266281320 631 781 824502468 2546 2656 970383681 1275 1443 1055269905 2320 2669 281581531 173 970 584984606 1103 1480 981237328 1014 1217 60944988 1981 2625 1061084409 293 1325 1005016539 2313 2329 901104316 327 2364 109364095 476 1599 341910080 532 1443 440200340 787 1586 136035281 48 1041 611520082 598 1470 995376876 898 1329 824784958 1428 2447 340866354 102 390 870617273 15 2277 68475817 749 1636 28974698 438 2546 517986414 1151 1688 1029906151 1758 2195 992267586 1166 1624 189146209 1130 2294 962136283 34 842 572150369 77 166 39937823 372 1604 272335138 1420 1631 35897697 861 1717 517115890 393 2222 138848669 1475 2677 484853663 697 1656 206725507 809 933 55230570 47 570 741311833 44 91 614812227 955 2674 382492594 1457 1804 860445294 1465 2318 258624057 1029 1678 421450572 2001 2018 893379208 891 2357 627395411 2416 2438 718638690 1658 2475 569554303 2419 2509 1007451891 1773 2153 520257107 1801 2267 1047552825 949 2116 300553042 557 2514 297976250 933 1579 104932661 71 1194 59384986 366 1721 405246964 448 776 1027883271 119 801 302412001 102 2595 75977828 1165 1912 54167413 2101 2324 386304874 1684 2494 419225541 577 996 401303987 1459 1905 398921127 751 872 391588191 587 2648 46852585 1290 2668 805382974 354 1033 927763727 694 1089 164379672 1771 1823 1051831506 1059 1238 967187883 1607 2079 263830498 442 2166 323741813 107 582 21821000 423 1420 659946469 181 324 847206826 138 1069 24382888 103 1568 508873550 17 1841 1063039285 1715 2437 806350020 383 1929 161265795 1040 1100 686984671 292 2464 473331011 1367 2678 737494453 1079 1831 148399502 481 1679 1059885552 1977 2488 1024953903 959 2061 747942744 805 1567 404293892 979 1491 855759136 1191 1550 355944164 809 1407 334699443 1347 1607 900221569 1208 1512 294399825 1417 1624 228351776 80 1554 1069699420 1311 1460 1065284406 469 531 393494747 1726 2404 896431236 623 1664 928367628 72 1978 308836791 1255 2643 413392362 1836 2166 747354474 26 884 115575469 1828 2510 372756904 1312 1489 47210749 399 2534 1039044451 890 1153 45369858 2088 2293 817361737 71 1823 805594512 1191 1247 234868972 1266 1676 96337422 2162 2216 493334541 128 449 952669225 352 1268 1048189999 1536 2003 379567886 2174 2578 769109170 495 837 46350671 1567 2528 547367358 1790 2155 312519201 946 2232 419201331 150 2622 39722877 842 909 426338385 312 1221 52847528 212 2351 28464288 285 2156 336482915 1855 2155 49459544 546 2703 256182624 1235 1390 220372641 355 724 216819050 1204 2345 763674094 1701 2648 214970630 741 2678 7181368 529 2410 436329521 1296 2082 235642623 531 2174 306392447 113 781 122434924 708 1916 100858481 503 1834 518013867 914 2637 366645614 864 970 125269042 918 2349 62544785 544 595 402208490 681 1032 387537455 250 1241 987888954 813 835 338200227 144 1538 914480657 700 896 969514016 1231 2154 897455292 1062 1534 51211108 1298 2159 189328204 1221 1595 909501555 1119 1735 232614704 605 2568 906027795 1041 2341 812251115 485 1059 141873794 171 1727 829576229 1420 2226 775410582 2017 2471 217965575 2045 2651 670597101 468 1350 644591765 1160 2277 887336160 2602 2667 544140982 1075 1475 151455315 88 2504 905954657 704 1526 1009577250 331 2143 23342321 383 673 404650853 902 2521 161625983 307 473 981690118 761 1262 500614275 200 1117 273736268 657 767 47635366 1307 2058 785461750 708 1201 385260075 194 1663 435007457 76 599 482288431 1279 2334 393692659 1408 1558 479358523 784 1423 209221792 1429 2215 745803631 211 2344 238645004 1791 2570 901820237 1984 2361 691140156 299 831 630746707 1960 2101 756046817 1234 1255 103363569 1147 2407 973545884 131 219 1019547359 2563 2582 43572909 503 2532 663685875 1682 2656 790524920 273 2084 370748649 1844 2495 756399612 604 1929 438404616 915 1375 897589479 657 725 584191751 43 2674 286044957 454 2261 671477721 143 2338 133521294 1216 2366 469194 602 1486 41850756 309 558 817034322 1729 1854 960031884 371 1808 538694955 1597 1735 16581321 448 1558 957409216 165 1414 553842256 862 1189 286261714 221 772 757034698 1747 2200 648837220 1647 2544 824578863 367 1398 987441761 1052 2226 383538759 353 1141 1071930917 107 847 614991731 925 1359 789044432 1739 2414 786156478 488 816 587460307 1201 1504 539262947 2544 2568 14187325 1188 2016 302274975 58 684 325168763 903 1842 935256203 1609 1771 589908145 383 1844 893054660 1651 2575 896737856 783 1538 938995952 284 2110 76855150 33 2380 675223623 53 1050 1034595791 270 1390 879932174 2054 2216 692053883 936 2028 1027148245 225 1826 257741576 642 1633 608018840 203 1822 177309338 2164 2507 165402131 911 2303 441966830 395 829 363678007 1868 1932 978663650 263 767 437229626 1769 2359 497003966 742 2389 1055680323 802 1692 129003073 596 1263 35521477 1072 2223 809915634 1250 1992 408676632 2 1251 579578134 966 2383 362005896 602 845 298763849 1741 2131 962793877 1497 1811 922187021 1173 1525 258942340 972 1105 756194665 454 2590 639298307 738 1831 36154933 2407 2604 950993891 162 1480 590901921 1319 2103 1032181395 2443 2688 881716788 288 383 216808706 426 930 453157315 658 1842 905660795 490 1409 109339383 986 1831 566346946 581 1827 809365325 988 1021 848580692 831 1403 1006148384 1233 2441 234112819 2285 2415 908988914 985 1772 665941019 82 121 240162474 2119 2637 679486045 1300 1403 409020748 671 2041 747818116 151 2259 103668521 1361 1901 421880332 2276 2679 1018165317 1410 1492 159815761 2127 2332 952448831 830 1874 329683841 639 973 141861164 197 1908 557609782 1541 2462 594795995 1763 2334 603965404 798 937 735331742 400 1865 160135565 263 707 1052692264 685 1570 136293286 32 342 637399608 615 1321 223335546 1235 2260 570089899 1663 2476 239646427 995 2384 796908372 1002 1157 184196997 29 446 24798913 2056 2617 262280537 30 275 458794993 980 2649 91964468 1448 1653 145168078 1625 1925 96248378 40 1416 1022945802 698 2175 935175343 1058 2300 346069649 206 1778 933892989 967 1600 459773110 839 2421 123619771 1495 1898 89559401 209 2609 770206037 29 2531 670332792 790 1525 969394177 1540 1935 952941371 225 2068 562247117 516 685 173855866 184 738 553296659 371 1756 899524287 1054 2077 439666200 1187 1996 797017995 1247 1998 527473194 770 1005 696622649 1314 1755 825525512 143 1468 747664112 233 2153 449087114 200 582 733883958 748 1058 905114534 1995 2657 876295757 1599 2458 167375068 325 476 808698381 366 1616 89087460 1093 1470 484146521 1723 1841 801830629 969 1357 238447436 2284 2574 436549899 925 2013 900808042 846 1932 232504485 56 873 1017603826 11 2506 940157791 2024 2111 918232936 269 1974 164765698 671 947 959715997 888 2119 497688836 91 1565 523796284 49 1102 68249666 1680 1816 166440979 865 1309 127110847 292 2292 954522700 236 1844 39758074 2119 2232 126624585 1657 2018 36354212 834 1336 596989274 1832 2558 40516005 388 440 427035634 1698 1957 847801081 1462 1929 282515428 1495 1564 911834184 500 823 708130072 1698 2190 1036555597 307 2539 279830914 2284 2600 798977460 1073 1229 242223668 898 945 437477729 1706 1882 192967012 2086 2470 787721678 517 1396 535301692 767 2658 658635755 1904 2513 493234585 1079 2073 11663423 1109 1368 1002220877 194 2209 949931579 1983 2166 388800534 1094 1415 36431270 494 1738 326664013 1506 2121 879656535 1292 1971 730891553 250 1778 751088092 1001 1930 839793085 144 2012 415655967 348 1605 624908838 508 760 823493171 1358 2415 773373885 2231 2257 179875755 1327 1965 762382135 376 1098 210422323 115 1049 667163586 573 1113 709596984 2311 2453 516795726 875 1145 530079437 351 474 594383815 511 2464 209874863 1423 2156 536848337 339 1771 786566030 265 2140 736229609 1942 2432 343711616 1003 2443 692086358 1646 2706 179916866 1088 1365 975654033 1975 2578 345085999 669 1681 1024160358 1374 1787 89096985 1657 2404 857549688 803 2358 850773913 155 1102 791061748 1315 1931 689368163 644 1340 882550780 358 1407 132635787 1759 2582 977477573 550 2253 888916765 991 1373 448373957 839 1138 665680284 204 237 971715494 1678 2422 690850115 1272 1292 1028690689 898 2436 838916255 840 977 943352024 1019 1120 950605565 349 1918 483081706 109 693 614037563 1347 2272 913175528 408 1601 561627227 890 1460 821826007 1328 2405 70988834 436 666 745072944 866 1724 919982748 444 922 309631805 1380 1418 751943534 316 1185 410609364 1977 2019 1050821850 782 1684 923573167 1391 2030 974662643 281 624 520589976 1998 2143 468632570 1060 1998 928621345 358 724 351541575 1529 2671 460707920 421 837 579898206 1675 2062 735974407 854 1558 629379901 588 1407 553932048 1173 1423 89895268 1471 2233 716877471 342 1486 479600166 205 2580 943449802 728 1538 555846098 672 925 697115268 101 1989 421649843 261 265 219750980 726 1663 117727543 1670 2372 957362241 628 2288 1056240051 2245 2691 186503650 2049 2118 990344993 2634 2673 320084057 793 1639 732701283 760 2224 968145501 195 1918 535608040 587 1255 150063677 621 1852 1020506366 1518 1809 588534363 262 2152 219124219 136 1012 426725380 1362 2603 15504419 852 2217 452863564 1549 1582 752158164 334 2550 561448921 1335 2045 255584410 1429 2674 989518872 1874 2686 353466180 989 2648 837415930 760 1416 651948089 1520 1526 554673100 506 1276 802071589 1807 2413 829840476 433 2143 642702543 1646 2231 609134044 530 629 1005923279 394 1282 699026419 836 1555 844557019 2104 2310 29050060 1925 2227 691701723 198 1072 539150507 140 1845 855307534 606 1074 242329425 722 1711 397264172 1517 2540 652605430 2431 2593 570650279 995 2117 334589800 1286 2663 929091099 347 1884 153322679 1391 1690 896348951 1150 1469 895706698 504 2700 180637090 1236 2648 216938298 412 864 555439342 1962 2149 431873029 708 1849 786968559 225 1153 685863053 2258 2378 594395109 125 1850 489875840 1613 2419 933320824 186 678 817454210 1355 1614 607788637 1661 2255 1027899342 331 2122 433152499 1452 2268 74618621 269 316 346246113 2342 2646 640745120 333 1730 765409195 2324 2531 190001155 1299 2139 425871641 1024 1482 1051174149 377 902 446125354 967 2283 818880503 1256 2567 1035774139 1068 2181 830225980 2113 2396 463290643 1031 1915 762156305 480 2435 384620289 158 1746 774700661 432 2655 684850228 487 1453 101809088 1207 2213 814964282 888 922 153511453 320 2089 934844713 1290 1852 17121342 753 868 256671926 476 1398 1063641929 1125 2185 191737459 520 1361 276111734 1771 1917 1025888049 165 2168 945077778 1034 2541 1023560941 422 1302 775324148 552 606 412256116 1123 2544 567443814 455 2360 389350072 660 738 598176979 764 2699 430213049 1076 2406 736874697 201 665 380315438 729 2488 668491228 1237 2544 939120039 145 2581 816947414 832 894 246851306 1670 2220 589006664 1336 1353 604673107 729 1014 41313896 828 1157 317983293 8 2045 88680203 302 1212 262027741 381 2444 103549213 1064 1898 760863538 2031 2567 223662954 503 2386 1059594134 676 1937 285605823 995 1339 399899920 1617 2451 964972526 161 804 866950111 1558 2221 649395553 602 1631 52094905 77 339 708458111 433 924 952175157 659 1836 237722170 565 1071 1003335056 549 1097 113592061 115 1827 803269353 680 2568 338667759 1288 2626 216499098 191 1770 440900375 95 2176 71638702 518 876 564713238 409 2287 505416497 2352 2475 1034734572 1031 1890 109567174 1070 1949 376182494 34 1925 115491553 86 674 1061514429 655 2023 216309841 1571 1982 671087771 371 1252 1038329877 1646 2527 654702631 126 2218 263277772 525 662 730466452 315 2341 14001974 2086 2352 511659954 125 600 452568782 2163 2535 136071293 40 1968 354524699 1830 2039 602317294 371 1986 386187415 1053 1291 246027471 884 1636 565810223 2210 2407 672247564 570 2220 334456514 1136 1516 543525529 1172 2343 53424446 339 1116 167370980 745 926 1047206950 706 1273 207896553 1094 1109 102177468 674 1490 918396351 841 1066 706668394 1839 1881 219341740 1440 2046 252035795 1623 2601 640289566 1380 2440 325711975 602 673 448659337 344 539 789099085 456 2700 1017587719 943 2683 928217814 317 1835 371155564 129 299 442575584 336 2612 900925680 893 1700 449729166 359 2464 604518760 791 2070 119640431 288 496 533460211 433 1211 38137563 1555 2707 1043476020 136 194 947567618 530 2458 719207942 338 2573 703728038 1527 1538 267912529 435 1484 499389170 1971 2240 623471831 603 1924 716248443 1508 1519 675674088 436 831 903868086 550 1970 1005106325 2334 2619 847559830 393 1582 291896309 271 693 896787948 1071 1339 1002311972 76 686 599724814 59 1008 260278255 73 2582 934731893 755 1106 1020623581 543 950 168361851 337 1924 860451916 1805 2575 66749130 55 1440 14811514 297 2128 784538829 1255 1995 613125717 1193 2066 584343190 312 1787 630397640 1364 1766 362006013 1955 2451 945502370 1364 1829 880641873 712 1830 891045040 371 1078 1049538652 659 1450 478808693 418 565 962628230 1559 2237 824263301 655 1845 423724624 61 546 30897007 902 2542 768721430 416 1912 886174319 889 2350 670670556 1464 2621 621392067 1009 1889 731649867 661 2659 366576049 1808 2140 1058459195 198 1930 693148953 392 524 602542314 1480 2676 602580454 869 1333 69658263 867 927 479480001 89 2587 964791504 407 2469 172523681 571 769 926041666 2511 2562 471657627 1499 1706 735873101 640 1587 578946198 105 572 241394709 56 478 187221905 789 2121 156612188 949 2463 822880370 175 1327 1025997366 101 298 210242938 1753 2357 822955391 1423 2345 178015204 510 1165 306373762 182 1922 94954911 174 1262 527183537 782 2371 492489152 1007 1449 316137569 1390 2297 494278419 913 1896 952831481 1029 2241 887546330 2053 2269 194234719 747 1889 752894073 2363 2674 414869229 599 1190 872495611 776 1569 598211285 84 593 197902953 158 957 446519015 2247 2687 1473470 1742 2237 167614477 857 1795 665443144 215 650 454691666 261 1422 247665295 185 198 175443548 277 1936 512742451 1066 2044 273351703 1629 2649 193561640 380 2363 602329908 1668 1855 285193262 1490 2413 113363060 1472 1524 110300614 401 806 277907516 768 2656 300458616 237 2328 631710963 1281 1917 598707613 1728 2442 80722633 947 2366 564867860 1826 2052 606791270 67 2694 265350174 303 2155 86383958 1494 1778 461655869 150 1067 440615120 90 934 615769957 624 1520 1008765952 1965 2065 879245528 486 1743 356704487 124 966 1004727480 664 997 909607213 682 2425 816925515 145 1735 345276812 122 220 548521402 935 2428 235192490 1351 1733 449093201 1008 2386 669896925 2587 2605 851932384 2488 2641 229544957 1163 1766 403773835 201 1629 81628081 351 1193 550522797 86 2600 758394458 386 892 576878191 483 766 223847355 1034 2242 772474855 323 2399 119355876 1629 2215 491479766 573 1941 312873232 527 2166 607020354 1291 1539 889884732 827 2585 6322906 2543 2555 485678495 831 2562 470093663 487 2649 272706321 1916 2655 370419856 2400 2529 246649848 1609 2659 461028919 700 1022 273885649 953 1877 537295005 639 923 1004017076 446 2031 84061531 960 1382 976583507 738 2393 17378118 303 1341 768449169 178 876 685490632 231 2497 565139385 884 2617 1015335558 2443 2684 787904872 1290 2385 617400872 410 1970 317930882 492 1535 151827286 605 2165 323330177 243 1722 604465839 496 959 459980233 848 2341 273724080 949 1279 579168326 469 846 235247435 159 1973 446666616 742 2192 537549264 128 211 697842476 838 977 194013032 443 1273 293755016 568 1505 293142115 659 1336 722729051 427 434 217826294 2017 2587 680857482 834 2183 559887056 1709 2126 588006021 346 712 491639045 2332 2539 946932367 534 2218 797253111 2035 2253 385214198 1136 1192 276706718 987 2381 728402987 1283 1361 293822130 1326 1875 656016711 955 1278 267226805 119 2353 400001060 1729 1770 671851559 836 1862 204223936 806 1017 507811448 2344 2351 569804458 1173 2479 647740482 188 952 193053539 1252 2416 611141892 1490 2418 951542735 248 1316 402109224 1668 2006 724497860 1055 1555 749303421 1055 2455 866728664 1705 1965 1033840520 859 2597 145920218 923 2187 181774498 1529 2628 228787313 1847 2181 884749431 1699 2110 613959617 1656 2140 1020589163 17 580 644480583 595 1350 412396791 702 2124 914116051 184 1394 1061259447 800 1950 728191633 239 2707 917032937 142 1783 231015503 211 659 145859756 484 652 898595495 209 342 906153228 489 1551 297756917 1986 2578 293871342 736 1589 597704412 299 1984 496206690 1674 2098 240867469 1284 2398 900134897 1341 2081 232531416 645 1025 467454727 949 1507 349136732 133 1996 999225298 744 1038 1024041939 358 478 974192618 1017 2085 559760465 1297 1817 604561894 1920 2709 904363001 1166 1461 864256770 1761 2595 963587670 908 2024 360132594 1120 1927 840001156 740 1132 171676087 197 1252 987130200 480 1145 252366206 367 2105 950332584 1648 2617 782707873 1070 2605 636324214 1312 1650 10141387 737 1747 124005254 7 930 553435135 731 1082 568093934 1218 2186 46536050 2513 2712 1008470044 484 1394 715162106 1163 1925 637270764 1143 1816 279378046 130 2158 834806429 584 596 68868456 166 633 853750548 868 1114 954755635 1341 2702 866215528 939 1742 907091325 670 1835 29248532 1139 1647 132359975 621 705 72180341 1153 2295 535915481 119 818 89530184 297 2478 802843698 1441 1841 819704506 1526 2655 163890815 564 2157 31666636 718 985 402985127 497 1323 999371455 36 421 880374151 82 616 870586392 1228 1818 147347920 2382 2518 935809231 573 2419 921473958 2196 2702 354827919 869 1824 221883902 1025 2236 226701939 588 2274 530408054 1473 1973 60217655 644 1942 612897347 2246 2368 476629989 564 1218 378836978 90 2692 55015408 1397 1690 376884003 968 2465 171649319 2317 2365 782226389 487 685 194645561 310 1091 333463071 67 1377 275436797 613 2566 25501853 313 1174 147965746 1715 1727 613341473 334 2543 208558973 2182 2503 741165247 98 953 949048967 334 1107 218115176 755 2341 434162123 1929 2642 688174339 621 1249 64186113 1677 1823 411761436 352 1566 953015123 1023 1611 858321868 508 2354 706036613 327 332 121370593 2246 2503 82669494 1433 1456 103053439 1734 1985 430140104 641 1197 1007641944 439 893 612424628 962 2429 303823166 2012 2347 794247328 1309 1617 419675599 1094 2685 517302510 618 1061 390014275 210 1528 188223468 309 1417 900618688 1968 2701 202487842 571 638 516451133 2236 2272 45342995 823 2164 871498702 905 1581 105270348 913 1532 478335635 1393 2628 809006293 403 2161 792038038 780 1550 986987841 1697 2261 1039356942 1351 2648 299618212 301 2299 728418272 202 1931 863088195 1175 1578 599089722 1095 2690 709339965 571 2697 871988024 2421 2686 336095374 686 1249 127141630 937 2595 295105790 2216 2313 599779402 610 1737 380440865 1022 2672 447860535 1545 2474 409022446 1113 2205 1030709591 927 1018 174921217 2598 2700 786803398 1382 2077 12909831 142 2248 565176009 301 1716 428750121 126 2269 268673232 229 1351 87036494 1666 2290 172604561 1076 1879 556290888 271 2371 113945993 172 1407 868919873 331 1442 914034117 1322 1581 388350477 812 2196 194504005 602 2551 718403703 2387 2710 6731225 835 1850 189886461 1874 2063 144097489 1453 1517 535524582 55 1883 437716112 157 2543 958256141 1493 2223 202751221 9 1938 744545487 1730 2319 621814005 106 351 577687226 1882 2326 174082951 1599 2536 449750472 591 1907 1046219379 978 1554 541157107 154 668 358051842 1668 1795 491526794 371 463 546232963 2021 2368 445827765 416 2391 889385862 551 2499 391353042 758 2506 891064392 509 1274 201898666 672 1110 841909091 686 2148 32138454 530 2386 1070957980 1040 1191 859569509 1460 1801 80422302 171 1543 135970883 323 592 871035160 788 2076 818454582 844 1335 937361815 709 959 269844587 250 1642 329970725 1865 2298 12134883 966 992 899829795 2294 2306 425035690 1470 1483 154945691 252 1643 898224407 363 1247 546488504 168 2511 810571509 1103 1141 611167098 345 708 335855614 1381 1965 537887067 376 2409 15257562 1787 2308 695909123 507 1425 685279569 1617 2378 103485327 649 2432 143585784 746 2438 673378465 894 1545 254251060 663 938 1020092377 301 2392 811533111 940 1232 85417809 452 2354 374198153 1507 1571 411301150 792 1249 798047718 1274 1805 591205725 51 521 822673810 790 1937 819202216 1499 2589 411140491 476 2325 1047257109 367 731 651642141 447 523 949092182 225 1012 959265405 165 1875 758583656 72 2113 294267693 673 1087 325659311 265 1652 334637224 592 2403 298690498 816 1606 55040446 767 825 742582544 902 1766 842346872 835 2624 93581592 994 1970 584108872 708 852 147760321 1148 2567 46409164 167 236 487015595 1481 2500 848843819 1192 2303 276984800 884 2187 563649647 1195 2207 743683224 2079 2605 92846719 487 607 1049784884 588 1646 30064067 546 698 525580674 476 2499 202749021 520 1208 1025186714 23 2071 657010710 803 1766 579473016 460 1761 950952175 694 1867 810058420 940 1618 254484418 1664 2356 763399133 1515 1651 12517206 188 319 745681271 298 618 663229733 1336 1676 825915673 1447 2290 222103380 511 2660 910278702 2125 2433 1039502297 7 2463 549311931 1783 2345 457025164 187 546 278317548 982 2280 349569564 239 2329 940811567 2108 2622 739754086 119 126 1065882780 1862 2516 301089829 336 445 602665575 1471 2026 488881645 1175 1468 308425268 1735 2008 276139336 1375 1921 756442152 349 2617 566728912 122 790 687504047 946 1499 374843062 371 1762 609447593 1775 2622 273741108 1150 2351 692149300 231 1385 736282471 784 2375 1042786087 890 2663 93949860 276 1642 658956507 949 1055 853963648 361 2610 119709716 387 2271 796193516 1453 1548 166337142 432 1739 808468736 681 1304 90767347 587 2097 1067512590 210 843 998072342 1806 2393 1020107821 648 1473 470537652 666 992 75144449 869 1598 384444259 140 673 262916419 95 584 839986599 1583 2537 541861654 1522 2616 438995071 1799 1908 25040990 982 1746 510163010 435 1633 303082797 979 2042 133630935 1911 2005 235937197 906 2508 845893834 644 1391 934117265 875 2465 1015074506 198 2116 714241340 1267 1286 51454901 775 2256 708462983 604 674 734807696 663 1597 705373847 1235 1571 239677920 743 2358 673964545 565 1004 403222124 425 2183 426719643 153 2216 951786920 781 2246 885917099 1330 2258 344340378 522 1073 757613497 961 2037 317827592 1985 2517 375817378 917 1406 350902119 394 2424 1063655903 558 685 1029015380 64 1183 380215569 1921 2287 939285893 606 908 564048698 1292 1652 397662044 326 1957 56203662 569 814 1026440229 1046 2094 375339168 313 534 680015211 890 1522 26984835 797 1963 714933209 1020 1203 486570046 270 1448 107286582 586 1591 227681509 2190 2463 334088902 549 2540 163473451 1241 2429 1030205777 1665 2132 1068081904 426 1238 496212311 53 2250 433981031 500 1881 790363275 797 2212 890518548 1750 2681 807269213 2210 2637 398557467 223 2365 913866110 381 2352 834394462 1045 2646 911437011 1385 1483 185585972 298 1914 234847940 1643 1757 138066450 490 1115 566867052 2568 2676 732487969 704 1662 671046467 162 302 470715737 79 1375 449144635 266 700 537597157 295 1181 48483219 433 1423 153889657 2197 2594 102055425 84 1940 290282068 1647 2294 1043591948 2448 2563 760947628 1919 1985 761395152 1612 2335 66338471 646 1678 103024653 204 595 1051528955 2378 2621 1002585743 542 691 813354000 103 2195 709027186 656 1948 1010622650 66 1342 785214256 709 1789 344003482 401 2484 433092227 2036 2325 97703560 1409 1932 550679932 896 1654 808805159 435 2637 876622770 211 555 360620578 49 2297 1034004290 440 718 235981224 1541 2474 95159168 1276 2313 9748827 1185 1989 427072908 820 2680 394094150 524 2499 652035297 199 1401 905188036 523 1918 82371269 116 2311 300550841 1001 1470 263048892 84 626 76206093 484 1561 535256662 25 911 418132174 253 417 368593351 780 1921 80326672 787 1752 92735014 301 2393 878815744 1338 2230 240211127 592 2472 533344256 642 1921 741920970 808 1514 964931411 607 2409 359617433 326 1019 555823466 1340 1578 527755062 1431 2295 997952035 2142 2624 447235252 1231 1652 466309889 580 749 1071199838 51 949 1072203289 792 951 6372420 722 895 996699908 938 1907 70405997 769 1203 7652765 182 2692 700185746 444 2678 178598873 863 2363 688862538 2284 2398 239195774 1966 2442 913486008 10 288 1037888038 1413 2709 915780140 985 1167 795331966 791 1903 927144369 2177 2443 414622441 385 518 47143801 526 1850 864942240 1651 2424 759373931 888 2168 1051307125 2013 2175 37301725 1404 2489 186162808 561 1330 319081045 476 2138 307975774 780 2227 566522812 2071 2630 134907355 1799 2219 89421531 1221 2461 847530447 1128 2638 579697952 262 1070 775319449 43 2288 682435662 720 2481 984370603 277 2150 630669374 31 1065 95964680 596 1024 452823103 1455 2595 58939185 1687 2522 255773811 1324 1538 412900221 233 1846 875346351 2243 2623 274038624 1833 1889 736817037 733 1591 667290313 884 1930 746867222 109 369 455878879 1721 2463 724506180 509 1651 566961936 210 2198 958162865 1055 2396 921317245 1152 1165 529679474 1891 2635 107700206 388 965 392389775 830 1776 422528993 610 1446 687247498 490 2182 266576896 1043 1064 11228850 722 1167 741371933 676 2251 743560839 516 1422 1073109174 367 1659 430223464 1419 1657 193356161 1089 1831 837690940 1526 2667 565295701 1692 2519 204076405 649 1562 812650786 642 2354 630214048 698 1499 201394209 1264 2518 691133278 1734 2490 931803668 930 1267 752840200 1619 2329 387372936 1618 2700 835966439 1841 1870 448434737 1083 2030 173649123 998 1787 182071516 410 1543 732706700 1145 2685 30886020 1423 2212 861434720 565 2423 274347374 867 2569 567846608 603 775 717954661 593 1002 822991120 1850 2430 218868866 592 2454 121194617 21 2249 524374401 1529 2622 892388296 831 2241 354499272 278 2353 48373096 1615 2669 685224142 582 1504 536327056 1267 1896 178466699 1875 2306 1049240242 858 2038 219930249 439 2033 608981800 274 1621 857388078 1327 1349 132955130 425 2025 92980891 406 855 485703836 215 619 56992329 1464 2208 57352292 1919 2221 470594879 615 1066 752177521 215 912 516912250 360 401 175921156 425 1804 177047057 76 288 507774007 600 2293 137996945 389 583 441604032 1477 2281 679046195 767 2450 475280387 354 767 906932777 850 1982 430362562 586 1972 518854237 1513 2395 184262394 773 1869 727722289 159 1199 538324300 217 283 971098339 364 772 952529433 992 2283 883901068 320 1712 536734765 1591 2420 782958101 79 1483 295861027 138 1262 194736853 407 639 560794056 11 795 312827641 130 1758 466583301 2542 2642 989798015 526 2261 509462772 497 1673 492151412 2683 2702 567819779 1224 1828 710099551 1984 2482 518672647 1131 2375 1010885075 670 2089 267940681 1404 2517 344389434 1395 2638 1021739791 1497 1950 552349052 851 1316 951377590 814 1612 167585101 750 2429 946765802 874 1462 525802600 1177 2238 980073650 714 1096 184171264 593 1583 1052285371 442 1221 591221126 668 2249 173103062 1314 2295 78008659 725 2344 933512293 671 1816 97448224 394 1261 211256416 412 846 143671140 174 2391 697888468 88 793 29559163 1927 1979 771862124 49 942 380872764 1233 2174 250433466 1900 2110 427333771 1487 2397 946117789 451 2055 115075798 609 2008 886861414 30 1196 48708474 1149 1154 10244181 326 2467 363656350 2285 2621 1071852050 710 1502 785727520 249 685 839721728 1526 1534 903619769 480 824 450366615 792 1457 504453440 966 1004 168989516 1580 2084 465923163 1053 2337 819891371 1385 2429 963185472 147 2487 425728694 145 1848 59490568 504 1834 542221173 1780 1985 57479224 933 2098 979588696 611 1258 372610795 1075 2583 760621255 800 1690 460784623 529 2444 626163520 1639 1810 611018943 1172 2234 710249904 25 1348 650394552 2027 2603 215279278 1099 2218 762541314 704 2305 674453912 384 2105 203051074 1125 2258 165739032 545 1208 1032913403 725 1817 609212425 377 1576 617498134 1043 1341 220921756 1131 2194 890314105 1315 1375 997636324 2018 2289 200834647 803 2680 103340873 977 1148 362252934 1878 2605 84636592 546 2677 1072064622 1410 2665 564182720 81 485 583764369 85 2293 1056690805 478 830 551065638 982 2162 511765324 645 2190 30129337 1955 2642 436844138 623 1590 280281159 339 1873 283516417 418 1964 567748594 1028 2338 310938082 74 1468 903609056 1222 2483 420524402 2575 2650 79810290 1536 2703 746205000 430 799 856556996 586 1631 64828319 195 2084 1031603713 622 889 177828864 2359 2407 790220585 385 1204 396367877 281 919 1021105223 1241 2628 851758591 2 1592 826303765 1763 2036 149604089 325 2683 897946727 1109 2707 979542073 904 1458 744940275 475 1225 1045057923 2272 2426 918887369 376 2127 150465522 2147 2377 860363262 1095 1827 430030992 318 1749 803293596 1525 2462 716964981 1286 1647 556348747 885 1797 294182504 1917 2438 1006918162 1063 2479 100722794 1347 2206 722882770 1330 1968 950193699 144 1262 252573015 551 614 384537609 1220 2705 364278591 1159 1792 28670160 2591 2602 501026555 170 2708 229994142 2405 2484 548175952 1155 1707 576386203 1071 1401 448159180 244 1794 675352421 1335 2236 628388326 361 800 665587047 1772 2225 927158255 299 2039 512746338 1975 2230 564921886 2515 2694 959465629 1700 2471 386107305 1220 2391 1002685021 640 1228 902368725 684 1175 159083228 518 2081 756574946 958 999 945354229 1498 2451 109604929 825 2419 479268227 385 965 719676711 852 1583 589766274 2075 2364 21803452 127 1830 408595226 2390 2424 618003940 1881 2136 505790021 2321 2359 736446331 530 1377 770409357 130 2040 640351991 323 2406 771799260 496 1247 852250493 1345 1658 911289093 380 2561 781757869 141 2042 35147353 1076 2219 12633139 1004 1286 360157947 1634 2149 645498087 56 297 143029659 96 1440 487586830 1512 2201 568876564 1135 2504 709168662 488 514 72210580 112 1063 302240858 1321 1328 432736254 36 1378 269987746 1465 1855 915007130 786 2264 632364844 692 1905 228232805 976 1685 645785578 438 745 724773251 2047 2254 68460134 978 1950 661895394 1261 1900 1054479233 60 1826 859063203 1646 2410 174365996 426 687 126266768 626 2448 1050055400 1144 2401 1025917263 2347 2573 476575766 1324 2083 697726661 536 2126 944118203 1623 1919 704966502 1178 1420 253598086 35 431 707533269 1188 2161 368502148 361 1649 274184685 1476 1885 670925202 429 2383 25966447 395 1076 162058307 758 1739 746475954 1758 1964 791549750 899 2614 383463842 515 2482 631704329 931 1943 349326166 1590 2598 595287406 941 2005 521325020 759 2203 162237002 650 1556 1019008457 2361 2457 737228273 1642 1730 259210062 956 2341 420358242 433 1425 99194533 198 1550 127983926 790 1967 689809983 1592 1625 537056071 205 585 804699919 409 1726 935177198 1432 2312 1005622363 1344 1878 599346271 1584 1888 603266707 258 2105 929973943 1106 2184 873249300 1275 1364 467552475 963 1438 108741150 981 1655 168608222 864 1325 458298649 383 575 861770305 678 1252 144964658 768 868 831356072 885 2080 681714050 1151 1326 1008286825 403 753 791412878 973 1191 249355218 375 847 380473625 64 1700 204459734 1638 2106 391707890 141 1425 39402613 1255 1600 602082846 226 1156 937315570 368 1896 279660506 1831 2387 86347465 1337 1775 813871948 1196 2430 327848381 1072 2391 1031143502 1801 2308 1052357207 4 792 246777998 165 1792 922747290 1769 2602 850556544 36 2462 693068473 1216 1751 372423049 265 1792 680799675 664 1865 907659193 645 930 42843187 42 2346 316438320 2256 2323 668654176 1626 1947 166267087 1078 2638 587152705 1697 1732 1069422365 1478 2630 1061524499 740 2627 591231097 305 1784 397611704 130 978 760424029 1158 2610 233374480 945 2078 821275030 1682 2228 771387367 423 2221 621715449 2292 2334 411102411 799 2330 535732290 167 2448 714552684 282 1700 251385124 1111 1138 258543429 939 1095 225305704 1032 1601 749680823 144 1087 906746831 1460 2208 453790387 1538 2011 421404964 182 1020 824214458 423 886 831293530 573 2264 581211275 483 2158 316485785 636 1692 1043529500 93 1704 706558188 1606 2128 779152124 1805 1874 959792815 615 1878 21111863 1097 1256 980977955 79 445 572734888 90 506 60783943 1955 2645 263919934 1656 1768 995218229 226 241 1028599379 1483 2593 1048729269 124 2055 94790134 332 1113 595919390 1731 2493 955686135 334 2567 409837514 1334 1745 216957043 1027 1081 552876213 1149 1808 34625178 648 2461 795012219 86 1692 939148449 2191 2279 784674356 975 2202 455936914 2221 2676 738666673 66 2662 492558733 608 1160 363257018 1027 2318 496717644 782 1027 709534120 1081 1842 139141168 1009 2006 64961129 866 1804 328139343 1391 2446 482545263 1616 1677 100059183 642 746 1051191037 2051 2643 665072452 194 1834 787708153 1597 2283 422133743 395 1891 558705411 645 2185 943404859 204 2413 463560840 32 2697 701451649 2304 2448 356119347 1101 1249 504999096 1804 1949 603005835 1078 1158 358978051 253 2516 219447494 943 2124 287698825 1481 2387 285757976 1174 2554 1071678156 742 2684 459501915 145 269 863990823 502 2186 236223245 757 2476 574656628 517 1468 247110096 64 672 992950334 1368 2433 255279380 2311 2367 1037190859 810 1102 753783731 1196 2460 993527567 122 1798 141384072 1565 2400 716636333 1089 1198 47452335 938 1302 332440308 660 1818 925427523 1412 2613 603895124 468 968 821353365 2080 2106 473767493 1408 2517 778912697 1031 2152 925168617 1502 1586 407954232 441 1915 838606672 1078 1243 842533265 414 1117 856991787 316 376 707357539 431 1892 856037213 407 793 756024353 25 167 292894159 1053 1095 652183740 1759 2407 75860384 524 1789 35891373 599 1480 566685866 1263 1941 671536817 256 1364 931321259 1113 1575 148452054 651 914 67647045 1711 2201 96744235 1312 1463 389227573 72 1538 983445364 197 1990 513345660 888 1409 935573732 41 2163 262086597 446 2308 685972085 415 2050 648998601 1144 2678 1062691713 1819 2665 404070421 2059 2194 632844486 211 1743 272158518 420 2201 844591940 1296 1688 942942905 108 2111 377862454 643 1999 10221755 572 2408 525910597 1792 2342 180414571 749 1657 70600942 446 2132 954576643 1979 2514 106776513 234 662 875335065 1172 1891 521397807 137 1767 1034965462 1825 1838 610274164 585 1445 174280484 960 1783 871348123 959 2580 903709185 1186 1736 70593007 1488 2314 804218985 1879 2689 572199387 1149 2062 79665699 529 1809 103870577 152 2051 682081848 2214 2226 53133449 39 167 470533858 1294 2710 435629179 1158 1777 104466114 1536 1703 681025475 1704 1884 246482470 776 980 145463190 1369 1418 16481413 311 1205 418035865 1526 1961 381643351 526 697 229446696 567 848 608625914