6988 127880830 907044985 974588844 995347623 636471486 656903680 602998833 633272896 91964707 451850305 829566456 991311149 540692607 566034890 45983309 833440293 387030688 546735614 666442239 702496631 529719807 905044171 89854625 275850767 860309277 901598119 222083351 630848501 14123755 280358932 173748743 997187512 150623976 735848615 4468885 997272460 852217454 976793535 594049571 656741913 940303706 961639888 809427746 897901975 173370289 493110315 93764268 475433917 599601600 835334271 481219381 517504945 213611979 240655188 585104775 728912449 323505647 642608906 672047831 719773922 828732916 882400361 44028115 89825909 393665628 502794867 185160854 916779927 901199829 934083550 327910635 543561529 380344769 404905266 638906269 969968732 886202530 957704776 251978382 974292048 586085559 925862317 945314584 960580533 758005600 778411142 903254026 925374021 871607303 952784231 712206821 891668571 557549108 593392434 519458040 602250961 713563772 724879010 751982500 898741410 934620789 973507838 225067927 823395820 857029130 945734849 466483234 697262087 889936865 911926701 143186662 883431626 542365380 700282598 686795845 701300192 1 742837078 61754023 556390169 543382492 587917878 555249017 889187621 886862338 958887281 223020454 889797230 794317834 882770097 271468266 573168732 884383293 920541164 891846482 983740713 655599590 708185157 981873679 999591819 155112833 597841660 553467066 580094361 104904711 170995926 690192895 928856945 317450700 465495934 669845176 934088529 1 251679489 17574663 453318451 755682960 772090625 435937079 894057337 355584612 621064120 562416724 782337337 37579628 562383729 837454112 940839387 292687023 987422881 856283834 974989059 847677359 923329190 260847596 959141268 762820331 969081744 30664623 99173948 872308958 907765858 472420999 639651510 55382720 929271293 242661212 715189294 562867235 857635581 908168964 994009433 52031043 353215708 698337532 754312911 453014010 960015938 252717311 812343832 816318395 831713440 102562264 924582206 318127630 995076735 9869845 925056114 779743023 985682745 114320054 807558764 454178983 799991952 696896459 867373533 951318827 977354251 122133272 195324520 883109604 973283507 13171751 205130887 500285527 575911156 324608475 454787972 553160382 883597090 3182441 619119396 55768439 868310464 454725155 547586029 566683225 686186448 66756129 994856738 317734812 999005185 278317641 611827845 896283747 898780943 434084610 482310690 678690234 798131412 953804921 987828102 695711110 989394235 380730942 635323300 520452704 730183189 619414826 851490930 179285217 588747594 987084118 998927036 684654001 690848839 767647025 886703191 523829705 874718465 436159242 892219092 975341401 991151002 820248824 854092935 571483990 879858275 340088352 972826111 620288057 631731967 581182758 835395754 708357370 937298394 891229352 995071951 206638766 742462328 373603704 478493921 341296214 907194184 402198962 896862281 172831192 797206183 621871393 672853712 855003195 855982173 477557801 876027260 12860004 603061137 756114809 768928551 1 622221264 34353074 216871676 972297495 998960279 441049011 468742629 469136320 722907383 394476703 467720121 366039800 376628106 654019055 770088178 492472201 512053599 70225525 902861326 155922039 890009074 597062626 634844708 20943961 941333170 61477489 458345850 788857605 815622998 571295991 688817392 639943301 995419704 948683330 951467749 572745404 705572027 1 981657842 468778757 855567718 490280095 632598908 924165698 996423467 943468537 974043254 489576868 675174682 144291379 826282044 587731241 672122519 653939647 968206530 115624260 624716704 687304196 755484245 511639050 975481912 343249099 412568741 517282355 900056459 875577823 996869001 285330517 421330939 942510439 944281489 492705449 654878168 210242325 752894589 997631570 998448565 466529994 541734124 599066110 704551812 34582513 568781332 687777782 715852627 463487934 856557752 774231043 922307789 75307077 637265060 567131489 668102922 456299784 531920615 711502467 950295507 75938893 865955932 562656018 905774321 648834303 923919249 193199491 466628671 719656787 978562958 797127234 817930003 991402775 998016586 748014222 851893308 505459059 708400814 795471960 903830665 535792012 631852106 538920010 915404651 941575190 947772742 957313409 983517770 771232029 949217709 240016664 374876590 837969427 979469666 856267797 914101430 218419935 717884644 287805745 525177434 159282771 458146565 539662771 661775340 739872868 882651505 401512481 489304247 684800870 761234759 665471059 872315633 280556586 998932095 974348060 994297771 148106737 746910328 565627651 877415521 309418299 406052653 764048296 796113480 647483786 882907805 657716684 782222141 942995965 992623846 227979876 915158525 213180546 337068291 189812636 580739299 732878301 912103156 776440839 887220310 613179206 667707111 215131724 283026686 73746373 536138086 788383467 987688275 172480981 701761766 70046271 734048151 551475389 556187193 153746480 472803800 827003530 957890853 621230413 767241848 976249087 994396088 813041095 888419767 81334048 761699764 995963125 997582912 206812782 278273179 15831580 857617269 954328968 973340539 582205396 938014083 396250311 754442259 827209188 896141035 37846479 306355675 348055475 509005757 431476675 739973500 170659003 534038900 425749534 782107110 580990177 848641716 640576152 838480964 874303034 881741175 628928026 795546413 201971961 631802300 371442677 519896926 261692104 876795758 782681980 844957212 137695272 382405719 501692245 820297019 495240721 524237207 971520330 999889263 453816987 946851500 539028168 877701605 545795704 817577043 852438491 853404806 205324334 315223880 137810432 766337754 158039934 261556436 834027538 903822384 498255397 832243155 808501327 851117714 180772493 879922166 117440312 254571147 1 810889801 88263575 421137837 302324237 354397705 289261734 571184047 401686655 662146451 465358419 479688408 104494960 114885457 753042445 779818375 36603489 532610499 213324223 308476178 966877169 993901460 915196828 999535219 822214670 840529461 418462453 952887630 194832535 986188291 464014394 803081918 979278736 990407738 629105534 654191206 796840617 868635903 411828922 966308347 859373734 885990104 862162246 969307311 923796159 941684107 871218668 889868681 443485625 479576649 483750971 620849670 963737316 973126633 777248093 878397656 220775513 826607209 170116178 640544064 312776854 467800966 248539328 906287012 444022673 790432906 341658995 746258228 883301301 961739032 1 53115114 313524883 460321111 587960233 940333088 996799415 997419571 373540202 513422715 246912055 746637925 504699630 929970888 762418437 993319613 190911804 860063630 445878916 870314920 261982111 860302355 726641487 842585635 496341974 600382834 351599339 434623966 990115071 993635355 456973759 675489881 88633800 848999400 369244618 804192021 361394862 724433118 965664442 996059428 423119297 670794260 402078219 494270569 918491898 967423399 912116094 962277023 13310989 785625898 196373883 564848041 943257109 966934078 407112087 722912245 865655867 987277409 878037138 925735833 351952760 737936039 975132071 998481204 437194782 978540961 419626787 880744111 49763811 849978066 621987948 983531784 951294906 980800808 342940201 591550068 454690114 931503469 143631799 603059854 378487368 567585849 66901397 941307893 829763701 893780117 878924785 952467976 145785224 174910644 335274542 352728305 269654986 497631411 842370985 904637349 725193980 998201415 988854641 998076673 483528921 747192491 898562659 984511663 528835927 774963351 567542686 888241331 721165602 808148577 663326924 951148482 769103144 903474878 182856828 549196880 217849654 321688516 186441658 811839802 447012568 454220446 644334803 682892304 369384644 728844295 57710576 212179410 334992047 572060350 494539532 747322827 681564280 914692768 952658980 957274732 369836767 414187186 9686434 474889863 761356288 960213117 960112617 998970574 142657822 755700980 944486448 966835502 645759498 949853384 830144107 937230104 962545297 994831438 318989013 925534571 815690730 924269969 863342327 991733970 789717378 860869628 269135908 484569691 691575776 918069246 918445148 979529499 97902115 370965849 467841374 930457625 1940037 31476458 376439742 934079523 103964918 975678251 259782903 754345859 142727662 255475387 762428247 891766050 243417761 703402173 94917268 388733190 604220966 762660127 970278090 973318377 359333060 960822420 37101067 671515075 553011703 813124375 758481089 868160945 4659215 826638374 356158901 380433938 868235454 996986869 932888892 941301394 193386820 812536197 195200316 937538668 206082055 472531270 471830097 519024384 444706553 825134836 96290176 573219401 579440564 708352441 858110540 889740744 159013682 728479811 124095002 639231467 626123422 992239968 886590541 942028802 735300539 943513516 987800692 997430095 630656993 933271464 448974135 659654094 97643193 654430846 108874811 436510094 961694682 984406374 655094303 889644539 899283703 975777525 905615635 929380515 127399394 563527995 940922659 953197998 760114305 854814706 813651872 876103205 679926589 802820370 379990159 474222652 725385020 864355211 587606081 928128552 43386421 630881522 419773197 684366048 245081241 658833147 705834925 914072462 141763575 462624786 432781096 615945546 179763069 635950287 850761435 954287602 744498671 868875945 179956791 420847481 188653060 638106532 334110886 343491646 323503298 337205411 170597663 507079141 330958825 908784980 450212435 482650905 398689771 465817763 725423743 745079448 395276336 588740910 367188913 424331739 916281598 941395260 94997523 802050357 675171757 946996273 1 621538288 772803962 999084007 84195973 361676006 647882668 873143324 464375500 493977544 769575261 787402084 399399509 859568971 229622137 483396009 673555266 805990026 945247337 961676723 780692063 906247175 774468488 849886095 991642878 998154556 661742189 878324708 60093782 442036936 664798817 926433620 896199055 984541513 399065200 684896828 593367564 672501570 406780759 850111435 277113457 983504329 481497799 973831555 199479341 293990041 152244464 441091255 772068890 932326003 521879871 782166673 208116388 646875394 403524206 665510780 531218474 727588503 913981231 999057238 178992970 537731041 426994919 471908019 323073048 802128766 53054789 572998071 621142743 828156510 493167467 511204071 528394232 599234589 778432534 854795446 452939083 640392845 957340229 999008222 648922581 736111731 842601047 942157824 104910135 165597885 509583119 805062154 287677200 407647901 414129802 609908752 992963021 997700725 613090022 838859388 938732172 982114890 315015293 631931292 135371602 857792320 691418908 709485178 970897359 986429485 888812606 902984230 591136807 973159605 838968614 990621995 26895298 117065272 671432434 689926079 661999997 666396478 182402003 934404746 860240517 987243954 120023914 131879698 557630038 633882674 433473796 565968625 104968872 571471345 936042357 979072815 753708767 786789283 75429185 112859077 870695435 897282442 666307825 842327115 189143028 258861557 921405123 935630466 393842367 636119232 117559732 309194726 981018513 998576814 502542540 812074014 741855900 974408948 659421033 999367890 870258841 890469171 786202068 936487952 711192690 873395427 215619011 823376142 486841678 681112742 640540113 715107503 701931460 857259418 779219501 816440929 683861317 776041259 235922960 976876527 506555704 728921791 222133214 996086683 329427675 378366511 231985592 363656632 281934492 547914737 304738329 840356146 459410336 878210266 379398091 396273151 895032438 974492211 842081199 893713474 14154791 327643125 362714865 899277656 843034621 920309233 752658269 762745468 994007088 995024651 633311923 787003960 236315619 335028883 339308664 726985147 184939191 905336406 695566616 951069549 473963888 672164655 440050548 856272133 872350320 992213289 894542181 961002015 816885441 876136121 230990028 257857219 741194505 988086178 1140115 680860900 428889887 459119037 600532770 911377730 318083771 336786325 315423537 792830138 279273793 699885254 427367034 697049766 500780999 876359851 782156649 818449579 826461704 942954067 540886414 776913709 262504190 731335689 750723957 789415248 687197259 772962451 22493653 94951741 883637372 918060945 294511864 920795644 133819766 764682202 154108510 749484896 433445151 861664262 318048656 799386071 336603046 428601103 286989383 513905332 853652553 998161545 968501672 993032306 821045950 837272025 821007776 945098443 939981177 940424306 463692816 642039897 897693518 985621231 1038793 860098703 195715559 949139825 331655441 739738685 298685078 309811941 237309470 341441130 671216738 837414380 214597402 713584848 362164936 413721882 465446402 525799901 907505935 939738257 782473326 792443659 802493795 972841685 186586286 535248509 380880619 791056583 242518524 289468836 773523884 980059761 1 255599113 616701119 841204042 457150020 754000686 381905517 972318998 158743049 639501150 1 507062122 142862083 226540040 590234720 637324831 220566536 512674480 67871329 421569953 316866136 611214116 868153250 898692369 310071935 782195865 218152575 693010039 229594801 334983786 748656610 886229329 750492248 808730648 456441118 817289996 295899900 667823491 379010930 991923655 773555030 822360957 630019593 765623919 708474805 780551881 470657933 497866333 859476482 877916695 940088172 988807886 592389398 926387413 676938740 685845650 28518004 638515974 169015930 965206857 195529753 812431958 393855581 898673594 261141131 755017333 48607061 782936782 507784127 754182317 432491886 735856222 387055857 754304506 86056675 836582049 435176780 951807124 830002555 934787729 358296079 814142390 294054724 970474651 336835008 445031178 543280533 874623853 801051783 826460303 162991217 586893916 559754188 649813454 702694932 925477495 16717822 623317365 864331379 950424683 569730277 932631595 610124502 748717316 154424051 814576194 250920202 272480689 119964479 850460831 401268731 490523110 427973140 722853884 821195864 940064504 85505907 583928211 980756166 991603423 884368709 981507376 737569255 944964654 443223051 581893483 587275098 746496366 431691045 942278877 604174896 957910213 451292182 812096878 786156844 959300544 654350536 797917730 416828764 834087815 816012103 935239554 622374848 761228162 330059591 903033661 356222331 982183570 15969898 909468216 557116795 863651713 952817837 984587737 277752762 751637500 788157156 834556153 629508479 999477219 413364096 526129236 52716842 701678948 296754422 301082889 370947711 899481275 136419647 816486134 210020894 858284129 552323352 726599206 915697510 986969672 453610137 675121882 990577933 992901849 994786848 999145034 498578889 894523531 561752919 587544423 106229478 335991234 981092215 999415586 959644508 961828578 907929254 979513619 721224186 963539026 909812192 951618174 865807388 879470875 697714813 699774597 571727335 862405227 747277211 938699168 843170416 889802476 817009446 883919876 921173747 936459401 139617631 635448493 647933905 815665656 447149132 980088448 656371072 770155218 263233287 790708265 961756645 977159157 819508999 870354296 475876840 858231711 107448087 800388695 787849716 966974696 377467232 640122381 241634186 822035528 922361689 932462585 618887591 672772879 247330529 561717338 999369994 999469757 929724297 955769868 953256384 992941950 952518127 959083984 935309478 981593776 771679400 857604651 907071828 930097807 299351813 464007554 781877722 994936209 5053573 211393864 315585852 941300207 292903969 676032183 800747900 946730777 391893996 791158784 476718522 891894598 233691240 883024261 602564005 895431609 427342094 789999185 993205213 993609376 12980927 596574007 937189634 986403882 372449280 557271042 768529757 889709359 942153987 997480768 145549512 160326335 888970964 918569585 719917107 792601645 534493030 873846650 768422968 976164067 930027086 970453192 363368934 658424436 211819612 950233138 37599607 911333119 578719969 995260647 790691372 830197039 484911413 867683889 702680544 924027507 927110939 985641757 195933989 833957152 874480132 932676636 303736745 691040831 323301389 933010980 913355789 969508519 687814322 732740612 656625719 737665735 633988660 965679662 29887289 383132945 18134174 471800238 817770252 826329265 714355469 999698202 246883282 389831078 480359565 849594120 737329273 786798066 675420424 996731028 924575230 929273084 879593787 904544032 976364865 978736073 82080867 291290899 8133004 336531297 155649448 399906955 588318010 827362581 122824374 652680423 545526338 758659576 23543962 891159300 921486300 927041649 897370266 925964290 812076295 932149028 124817675 443100515 438215570 646722657 195726908 984649571 614704609 782314886 401961432 722294084 819834698 865816610 111731000 838284166 30398217 989163539 691833670 751603848 197111008 702665710 680882183 704201032 368977989 478081097 65219878 171666520 112006612 435169203 192767266 603532753 12988191 410326177 917587679 982392444 581830617 673210366 874340460 954465439 172209493 375246181 172809730 334939098 186254099 979822226 480708276 732112604 680078784 926931670 777060972 891317435 691504516 778686085 333193596 430675507 648148899 879373307 26605354 463982856 219884507 481743605 320831829 343541951 409656852 511463511 660763283 918507304 547591745 837988707 995155790 999742766 43872599 683783169 114668129 214163223 341782389 427359325 666446745 770978049 773017749 789951309 535074321 624167544 912056559 962654531 248292161 607485651 749303167 887271331 905972653 949975036 627612873 900831281 300950769 462147993 508435891 728103194 579185492 878728387 115063417 543614153 674624834 678709125 325446664 467828704 778976786 792417388 346281129 370493658 769629451 824202572 940462849 957965852 483571741 966643817 107948372 659837490 407258053 609102374 36273944 366299399 40271385 223736697 888747967 993529004 566083478 707594329 351537050 657444727 216875854 218818678 113122399 493782765 344774279 435409592 119052706 832414622 62461387 314511363 125604646 315552680 700251708 918705045 636731556 791352225 34366124 936441856 305594008 668083341 118611846 880979984 44283029 967223244 255035182 538464931 18168138 356254447 548467212 955805770 682821700 988226486 739097019 773673288 562933534 628811230 393355351 403501756 585196559 889893383 549996305 973269186 580884326 969748402 754761345 903914670 898325963 961981784 475422873 552148277 779310814 973162963 997339361 997999804 212543777 486164359 108628369 308109174 69203803 911899735 808156281 863114688 582827010 637284573 902707757 966295810 569530442 757478860 237129338 652795087 391481849 992308796 229712334 969339962 19307498 801864828 204772552 775251668 767113562 794704912 213076519 512728095 370185131 463138886 915129957 988033031 805644315 884069868 28342528 281120440 516862060 957628757 104132706 482566545 137719287 746296628 494568754 944800449 879219884 982340031 438706096 526280249 734330935 896200159 328537268 957351583 234714418 300669964 998025046 999814195 841416890 971583471 127872445 889625301 862175920 867242656 667467470 941929885 580342695 946070154 154164324 880889915 291176107 337690661 963195060 964248881 486224609 619570208 103180745 951219818 447361575 538375005 815206539 878479068 729439469 871542412 103009323 646090870 558731565 843465935 645825633 975449308 857975042 958572927 217261125 570526165 815632445 878591043 283146518 606118066 592598972 601250876 151247786 584567257 714002073 723952437 966976995 984257269 518678505 647169541 311145371 678367170 920496596 946964613 116353627 357561355 171410525 736749768 547094112 551631010 982918453 984914262 342895584 558030461 813121495 919473634 618661200 885316750 711076585 886456171 246163646 793636640 462147848 699253282 586002153 685570466 282607300 834251046 95520610 351060118 188575252 881774532 607527885 968817769 27396391 421720470 563466434 770360502 608307873 871151774 10621825 238129177 445554983 985770037 886181365 934494311 1 357318796 203420145 753139355 699286649 819329025 648454863 842797978 133854484 268578988 851709080 992445455 194151352 209478806 642678050 796107771 673497404 704934775 939364568 997533105 174668691 313533163 10762909 796085169 765558666 783027162 660672350 817901914 819659813 974509128 258002589 988621285 260096086 826197838 461607225 762430626 217238395 906328071 358916684 565499730 879504437 936828193 638812420 999981944 405583485 631506058 280721538 355602590 461560773 856151276 407592096 471282651 549560579 607565298 165999333 224210115 945285742 951911877 315138430 447310551 551283581 871077112 459254438 870471122 202372460 483593238 747259914 807426364 633070977 725160374 294906802 755830206 853346503 862209656 124469750 317762464 464824159 997508401 290880253 700669037 562512611 966680959 66224532 999638932 174118962 392973135 996007851 999112618 761445764 861962134 91370972 292467596 819123259 883411748 13858302 876770244 412235711 630787613 308718115 933374905 200147853 310569958 888747665 958993152 11462119 56764330 932920514 966139838 892605626 989929429 7343734 489391575 493385938 664640035 560825497 635866956 613063529 972160292 658931858 735844757 603060285 758487149 942521682 995203537 477519085 932833853 312853370 815137698 873424462 993810889 819297860 943483294 199048345 538618500 181286961 780452793 477534889 872391803 82890582 169721905 809271914 919004411 313400188 421108911 336619645 541464163 170236782 597609549 297481631 658235518 195197681 921264492 541286803 643632830 468621955 753184083 466002100 815140800 859791387 901414885 595117721 646709532 289034491 661857225 81346429 586026296 343231039 828382844 512724954 691700643 66508840 940214909 695484587 923255553 712630495 744586589 72682639 849144745 538101318 997032005 224368023 859684161 421370281 662746884 486525112 862557119 774262759 812466615 988596362 991178692 770762664 918369883 697151591 866109832 732256381 967446431 747038939 769169236 98324530 187538433 985366806 997225953 225582418 573327729 140497850 859244265 244170706 791468895 98726185 316365937 914705048 946700219 232066804 799287159 712070881 936100631 262262703 871469797 194505727 512333860 784750093 953032736 74644008 239021267 825203738 830686802 576442285 705861501 144015234 758644282 404799873 609205113 460939170 686764476 851548754 875615738 353879574 672437183 102107507 522019441 677678032 994262068 472347359 597827025 429948317 985561413 200220728 380104777 229828739 952325102 456656771 527036171 37792134 946225801 415111030 847595196 753660369 902654371 874561399 876422196 68036575 532621293 9982034 822536970 357407390 621065845 880163089 904390791 97669389 971877566 804069530 923728233 588484751 615938730 389514882 982877943 52938698 155505935 117589141 315210088 426229417 429840438 495671331 622223645 879551776 890276472 950341782 968446192 837056989 988660948 964823715 981699536 629264018 650338790 558334708 913010909 1 185751827 439546225 903008434 783765516 854630954 870693826 991881024 747000298 773795200 880939327 970898259 613067315 685298038 169059741 312868584 58437700 685589754 97081038 459780316 604689120 691868086 555390485 682492383 346770448 985334273 920972484 929397200 943528699 998314205 32601865 971351319 123726564 183320768 165496292 787703274 161020601 816509528 877451111 938062344 951150732 953144758 281511459 721368924 239083225 622923986 610719517 935213712 824664771 868383539 116360758 667743232 844358388 863106663 509014809 626087080 563725041 762826799 280797519 966798839 655096274 750734675 345436146 893533376 100058213 416124098 941565200 958756397 936646090 964953414 793854354 934903318 245959762 735310461 128284267 264529878 340308926 420579515 561092031 693804076 168041978 608888558 149292053 573807509 789772125 959624725 574062774 812366329 524590163 792349008 283770356 576908832 489640665 570346517 220975946 941632754 982506152 982969787 724394130 804213161 877742627 926805191 1 573875385 514892501 957691997 629861023 882895521 284891722 734347360 567789128 989749891 797653220 872991152 683863656 770599670 758737202 934592511 352159329 626491767 308166233 827535934 581726009 860035750 896909175 958106990 626693796 837581038 250226540 929232631 316255541 960621764 988117490 998654746 138861950 223242679 88485694 822305625 753457082 953350631 670530860 671287209 899892810 909305956 610278021 829914397 93923275 338334260 799235127 932130126 814879286 883995707 76744827 563030627 467588827 714934613 751359419 790373494 597436721 776307386 296432809 592611503 124099916 362992176 636447563 836917173 44757526 869476702 591965429 865869529 455897399 930974295 1 897706796 820700765 845139530 576081906 847745293 569015397 665320419 308114072 452401522 962436812 974285298 153223026 303005339 885736744 978905357 858735859 928027857 206179195 465924866 862852636 958850852 575281236 918899416 630991277 706472469 750265971 830541999 719152316 985410336 51986855 311700765 575397930 744583525 721857335 931875520 829327638 892759985 757067568 861809915 682367763 724692154 10324306 557037633 599052317 817807649 49986877 573113033 140489113 476581835 114564435 732402812 294422216 628498158 415361601 828956553 436637655 856632119 716674258 952672377 357703862 836498952 15167 90155717 378849356 890970304 145788643 323495577 777374945 930054154 292660513 835250529 288683618 793991207 961261622 974700430 142142343 854711672 275444171 412055414 207118995 386590954 934890862 987224993 546708997 771700906 867247379 976765637 1 896285312 672267816 959046476 382934787 791454289 522698323 767097247 943876905 967721782 159551817 693628436 630974744 787670106 94280619 659902823 285066328 288347619 209898810 485097327 990368250 992577942 818211016 945026985 895051808 922070614 399607606 826915547 833050693 907539688 253237307 943096793 710981288 862293250 478585615 704017379 893040881 919317897 427319651 478296528 803227335 977512670 219074899 966213256 949689465 985504744 33068869 71846942 694989993 918020141 512401102 793775708 526832383 874296057 227322949 402432232 797898555 883188610 651393888 785684236 851361948 932830461 368423466 560411107 998122313 998790266 244685624 634421866 862614556 972408300 851741263 943965946 683388692 783924014 970001643 979823563 578229887 784964500 247858490 997053465 215272855 489585188 871187245 873320219 968813942 987796103 191559066 619581761 731926223 874210680 262546374 763194098 347343476 708506493 933224122 989598454 446921167 794103547 654304404 717353431 299861209 678867734 749032686 790538819 660735669 693560991 807301785 980247784 672912812 978431473 6273691 584648690 683627472 859201362 386177896 743320599 742346742 830514874 330270840 562618994 701815623 867226647 286138531 672236828 537177108 541383532 380059149 911789943 229297570 453387870 959767714 985376632 103045704 276666952 898181276 977959682 512724198 676246109 377692119 533778820 44622943 79910294 179189543 626227281 231748750 399357958 73041910 174394639 470961369 641382703 192487433 819473800 50174506 694620751 185739407 475492743 282174633 642379522 92641183 339851056 776656785 866784768 845817373 994347157 744447965 990881938 252455229 358408706 641187477 762057518 897931223 981440888 803688372 818136195 731117782 748758716 391712433 396237966 462988200 595750845 806367345 893557310 630990253 744161015 798701567 989775171 125226465 965515449 987201940 989504166 169570444 800156202 872353414 992665184 173930244 360038867 345462242 580276534 289368336 612823561 779511563 872086559 76511658 564829289 565373039 602807649 981681376 999011313 704909317 749920721 278240073 485600336 596751413 881243800 786804735 980533808 505302297 834656779 848209623 872023616 773247872 832775788 92246940 911506492 801151231 999925027 191378943 898520016 815542879 978985384 774547972 856330802 175041716 441041106 557210889 680971191 63124133 771232569 492487778 547408074 905057170 913611556 370234766 970197538 834151081 856425140 806757594 947621438 857592390 874480983 28609634 951537242 380515286 470499110 981355296 999545317 549050801 912313379 253025731 886128998 553325458 690359686 439269260 554582069 230055227 594342264 273456127 361464491 542132080 553277637 536249332 970357467 1 607259329 913891900 939582090 548738602 778258882 682760891 786954917 310054918 753692107 305912061 772501327 475470707 628519645 166973136 950868127 365638500 403727037 521556576 602271465 217755248 803470788 250834664 459822277 818420346 966085429 858421587 983486215 212734714 404450702 945414182 947516163 288240708 558412340 688885861 793172737 944580895 954437814 156780352 853010224 777516599 838337162 877813703 894949882 759296152 794528956 665937857 815655831 110035739 963889584 651251080 752183720 523308198 959214763 713239477 726633394 391925420 755472911 482503131 599091086 922904078 974983949 699894863 758411503 65822495 512380643 138937067 552359284 982067147 984196874 481272362 763447855 743144400 945150821 152555644 317980929 613906544 909257539 434549840 947347267 262830101 419066397 163612941 837945447 11554982 676943848 881749665 997193060 685334867 797583287 529233318 985251836 583630458 819130372 995776479 999187664 133059063 439486819 77813816 994095742 449645178 646513587 113081509 267498969 127703994 354172452 767097051 919767650 233716405 328647384 355154732 488037349 518312943 646332633 852495223 919917930 278939353 978407381 137864425 512761789 87398177 627080819 654430579 706500381 314524611 930789139 463364064 463955443 542448654 935199980 739886698 905254716 657950939 685398895 662894736 893666047 332710730 612287697 105883404 511838292 662677947 867107735 411343904 800009670 739211988 872892413 128720405 529785347 286910329 590884303 569136567 719455914 66005445 608452049 944938554 991710308 671408236 679423538 354186330 731428721 520136240 699255823 439443825 785912637 341066450 713197282 926125792 999332515 397484094 658652078 156539076 655671574 403053981 559124033 685829798 762495426 646245541 949422917 117502920 996874347 18083677 848681790 653038522 970834925 729991446 848848934 613655449 832384387 441739458 584614612 903206154 937984756 278667735 992371091 854822484 887337983 724889496 945934541 822480005 974302023 734553330 951556581 877027756 995010372 130651137 415184126 382117632 551788161 392935677 993732170 302554779 696186796 383792245 599625752 430506999 570852221 813458173 859520805 143859231 830308653 926350391 998240062 738437123 988201888 135548920 426966031 935888174 969113690 265920365 403251036 815238427 968252825 490533657 875833067 644354010 945375810 217154286 759397313 845180329 951908497 777783739 934745686 436601843 874383850 880441754 924236124 575864621 620856024 365225713 656361617 922131254 982482927 964663005 965184985 273175521 744280580 889678077 931132509 442198688 513725879 148678181 818390825 738857391 924079679 316830695 712984707 299333236 607641011 927745072 929459082 928824622 994592792 134726682 824867325 590122177 822472317 714764133 795738028 829944832 880379246 680032156 766414795 492689817 805001396 583325637 802008800 140800061 158963211 10207276 894218695 490199396 918195098 735960659 873476465 326519233 646103696 408729457 428131577 17433994 384617860 339716245 999210637 737736364 754389617 864034376 967372367 921600936 973724968 551399962 799540430 304102393 740215943 778881009 918176840 125163324 304551955 580733838 684824005 581494433 828720107 345826706 869038652 552506717 697830869 311137198 462678219 442455770 679284284 86009706 851549973 730229264 750672475 736654444 964688806 528063507 964772135 86444488 488454063 464038331 494823268 705821982 854095162 980683930 984831455 961865925 973766991 941821335 993969549 875581472 981746503 613382669 618888689 690523456 692146496 941553004 975785127 714520265 968417812 411557663 490974479 352993211 759812166 156013691 353938223 988138265 994788316 660253850 871441944 932211050 955190326 905889196 985692787 436482644 802754252 235972102 697560233 1 485372094 726525761 798941275 976135876 987990542 302053154 433723289 252393917 468198798 721471474 726078838 140467005 465763667 517985590 679196115 640158114 664136200 660242439 692302902 101534907 797231240 794352622 885057510 712304859 726792885 567397575 635802111 980389391 997774389 944438386 980536428 762351610 835295979 802602559 882159341 570919973 852962489 40216443 70160504 911734634 921329046 700588066 955301503 972853725 992679434 289020884 909956156 544709207 687411563 383312160 910668302 56474533 97615641 185469523 941118170 162472758 876237967 436586173 602856676 661147962 803689161 373478081 561940024 280900891 617191979 444776815 554963306 318908973 945856893 196471557 668508579 340321546 387328615 759029630 835463364 571869303 618201012 758828743 833861854 414517099 811860655 701005596 979676766 133503180 937622569 838681836 931048767 556845398 661529570 443152136 955178323 581709800 789304122 559309823 911977359 899271722 918959391 884362668 891945700 343703775 456652622 298227801 786278627 987337865 996940522 769255761 899577121 85389440 680938293 442659355 946333472 928413244 980634151 140635101 548477440 768125446 828464264 360071121 639062417 92190918 499268276 339090552 729694380 828913685 833562593 773010704 868355152 164218096 915688339 795053860 812421358 95524757 161987726 1 283980319 918435742 970489684 510308241 889054472 746797334 881607265 788472708 993823235 860411267 895950787 653977715 691650932 679365107 863203211 669393153 880165945 457110366 755730017 14527928 316953464 106440207 107895498 13109094 576642707 233482098 455877215 1 952065297 170164834 896646097 235049130 844143227 281549443 857626928 355721990 357292022 348237761 978497231 483537142 539578400 505893444 563173720 555893435 785614484 10736188 747131506 752932586 773626614 703351089 803857311 455596787 624072001 296067558 326606323 825521422 937692769 605272771 980895210 117767497 290029199 373011531 890760488 695059813 928892376 228544929 421456094 819777832 962194576 695815747 765810402 824067906 849205044 194108162 723185556 397872708 858371862 27523556 503399182 761961124 888001888 996367292 997364903 494544787 624925422 604690175 695233121 787174817 967179890 307808539 598516419 291804592 743595252 11482639 104444122 94071162 303042510 303365933 635133526 815913055 919883220 425442349 477509211 217134562 748077019 23853858 244932214 923346030 943418596 923146864 948672634 82314097 996002661 778908818 866723075 778424450 854885381 368268073 633815308 950242049 958029697 361492273 828865409 74781503 119912477 799623661 932041340 780729381 908969666 111409296 508269415 679805412 830257815 307543297 587673636 430410622 682599151 470986519 565698803 568276279 860189887 548089088 741504918 425765129 986255939 205845535 346116752 967126950 992152496 704862806 982031018 252797999 552567045 869556180 993886531 444783221 557439359 803651141 847825733 959880305 979278641 1 4441947 225938182 513305273 729057926 841480736 165348682 209393617 829846413 961568769 709692023 721951325 957441217 978478254 741753178 813098154 793328969 887889114 471427606 674693971 587345455 717548172 428035532 868501290 118404414 326746276 676596565 905399092 137161247 308599763 225744782 738650835 397945815 549808615 57371723 961410119 756722906 951196951 26281557 793810300 715769661 940060716 616095439 816961407 802572454 887916689 543489756 628037285 285307513 639885544 862376561 917020045 758443516 786733921 36219076 97921498 100245811 189784561 400809200 589042233 798775701 845858091 195606220 604308525 102126353 261736760 444253529 692666242 813408236 896945676 769652424 925102005 954817932 986289055 287934108 951436519 730074031 848419162 17189680 40491408 875344504 999732893 479429383 933533222 309790323 958982245 828750876 901370776 20825490 710084346 870270780 891086409 123757108 619291429 258419510 266039768 790448271 843686876 771835302 797204809 232004810 867159406 125465595 421635286 875001646 986323561 640925982 691746862 630216341 634704710 786819381 943033203 27893215 980981325 158395944 651724979 472739239 953164785 126181618 424052670 722958306 864749329 398462334 406685925 477615863 800478082 75240641 170182664 452347717 601364040 312421785 941240937 782790427 792782766 128970332 994170440 998269771 998279457 686865092 713433951 824779047 855143210 767964199 807278572 284133195 876806056 637602249 968067109 233295842 712135042 920199925 983421542 431532952 535350623 860122062 942097368 527651175 837260502 441808080 891165353 584636665 660131445 566199355 954338969 466962559 543885240 1 546262572 565866562 775362824 726022657 822671168 35243224 665172220 135163426 903387476 759333713 998933383 324731024 929833524 1 470206069 518162691 846191788 586420007 724144801 313107147 330057605 64979925 335062396 347914954 493829468 958787020 995406971 625744019 896737446 46342263 53246403 333211331 915495221 918509391 984698851 222093840 251472591 966154183 978402115 966220459 975255879 819680768 906886534 738083590 772154859 467635531 892580948 491188143 636889644 318318181 959592828 601626648 980609163 601021364 903991682 862213076 996035504 852307972 951585313 236143864 940371208 257055896 914632145 370301384 816699380 58098867 225542794 100779079 879032336 587591498 630278011 169977287 961684211 794900742 975801357 335019392 336304339 654671450 823679205 649368755 802063619 593335742 864579185 845836927 913663011 987916278 996499207 641444079 905635909 314743781 665063693 721273758 993596633 469380344 901884443 996232009 997257673 884634340 903335445 548343133 599494856 64714065 72084315 382057963 578765570 170415490 401788427 870211540 873430004 247723983 293913639 731900715 975445453 153900049 826678169 1 183364399 783673301 803415794 79981945 607508197 571728662 686147028 860039991 982185271 212994697 817846247 446619461 719544647 990460658 992576149 987681452 992121117 273418268 843395369 300644590 569788050 690377995 836165764 482413431 555057170 834053809 947783044 299854368 464762443 4099221 199656817 188595765 809321757 872533895 936163060 382244800 968497220 733944605 940045453 964912043 977448711 752400083 877564655 56725030 927790140 347524808 803391591 62704706 752778759 146987508 513241872 233430417 947008083 34044202 853872467 567975200 681557978 771069887 908013025 707918641 967563812 954931044 996169978 16688121 462316409 843260145 946521238 775156120 905040051 743785203 962683177 592847703 850791143 374133837 959578222 785741216 989903586 86938802 88998091 855042645 928233671 263579740 329472483 662242553 947826892 410377373 854373734 14841620 773008050 830643915 930744192 332053921 783567569 464164565 992125398 129632292 508993364 812815106 961544590 670093875 804826498 818305521 969133399 373981870 479311604 186821781 574198438 439074816 743431522 337425223 503858554 182902654 355220992 972843172 988059282 71931198 540735048 538252577 681488934 919402650 945822960 295621071 878599107 949792631 991968832 635829368 853846966 245719590 489798518 196101624 937602648 182966628 320707831 912309388 962449449 61288715 975007902 98586445 229885612 733182657 778813861 438784476 747375296 279501182 807177496 90345521 968975287 1 247773536 841138573 986806297 993193110 994854390 511433963 685317319 22670877 452399665 771300104 926116432 746350265 996368940 481625229 917173281 578230850 992977505 736289787 845632483 782010523 855285378 437644535 747634809 87070393 964425234 278433446 953605646 408567498 570013105 873723838 911723391 526041219 894081540 990767019 994647199 179456303 955398851 287253810 694071803 265194856 284636928 303371853 316399703 698877494 955748499 94297610 215899564 474740594 598938103 115078618 167283322 155656407 927665383 23608139 550167621 903689484 961348799 86106184 739537669 230603499 272708633 128503287 363719395 187172371 978535301 964181842 998547314 785292613 818500464 165296335 709365967 71879591 927471577 53389453 156743996 556995795 937656391 848153533 865625474 108694198 417732277 538080622 551785737 224937620 931083621 1 281024987 381663689 934041162 812708286 860214103 245088055 377665282 971758406 972043033 309455452 891973460 200947425 446780864 196113377 734029861 511462104 626574237 92322204 893683944 988478674 989198068 86709737 981741456 553838563 799798439 973868515 983977692 845984421 963993216 346875674 502232152 523720002 873023104 895225336 997040640 657886865 815430396 949661864 987628476 434833983 574708998 839469941 989883832 116020580 469843631 347069727 715233656 174509969 822293416 598205005 803268746 93779298 776971365 335722673 944689105 83189801 928446006 684189216 826051125 36300734 660286657 201029893 202043227 262862791 694259133 817804360 920705550 675527349 809070808 64516969 761008180 950020163 983867379 488260072 590713833 497185787 959917387 918004049 952349474 378631209 852813986 630499448 709401275 25948383 181841809 693531119 892225879 470643132 973143081 703875287 874594335 679452383 880878693 605104075 935559961 193368796 881814520 578769810 918018946 385805927 689643176 627388417 975667291 425683628 837292759 63728006 878195843 66162697 95002446 130893710 817584795 741570549 876621725 151698226 356366813 826772155 927642647 459553753 542052180 557803749 715717582 214589808 663172545 730943553 760854610 466770777 531173476 986159082 996555948 263961375 345060280 850004279 979695786 510380642 935141325 247786586 782971959 287362269 696473365 606773971 880292723 289893828 509138580 852136818 996428874 450433368 462427212 13080049 49511426 864626749 977906011 938068078 990818056 994280681 999768888 269110304 750330350 474906241 743956634 821536938 852714588 451227953 751332138 311581438 997487277 142493090 552468291 255213157 444444026 672687856 708129283 138289844 881696119 974566601 983879955 526246703 658350643 555996285 601151832 567714936 904118254 66272155 790092103 536797088 717703209 577874637 802750132 316939179 394194248 467227579 753205273 943354627 954274832 259796361 415043709 315793747 880183918 22429416 928464947 492328314 905040119 459947433 812545012 261657134 344156946 161267837 585380682 933248068 944924725 502309846 851293400 567120112 919141924 838714608 997868395 875978408 935020983 14198991 108911590 908816592 961470632 572500970 802611581 559703035 629904942 600068787 656739200 743125868 862927216 725510581 774119294 898700506 915974604 1 93251170 907190116 949423078 495143250 922465715 902069072 965344693 487630276 928973481 175348304 880298183 280761416 413974132 327443344 904673767 535401882 542838107 151350438 571724372 271447113 315676791 358936266 755161216 435571156 715360090 86542337 594074116 77338002 723033261 394239488 772711913 887670107 907448827 433109813 589800020 428078033 627607661 57459669 467336556 272774438 395777586 220713788 865802794 758061159 764294392 793811202 834718221 220929143 930205844 522417558 732067433 968288583 972408245 290842224 818549757 810805361 885793072 845740000 904572183 789015410 917656175 236624455 381847083 263932060 870669201 404044477 582814745 211349047 797838287 740412611 881567790 828981992 964661252 340378720 455145577 856149491 981986627 185204525 846979523 441719058 865828952 150484343 984229966 694946186 853820387 731236742 735616032 508762976 954821661 57839360 197336126 696557753 896756538 786176625 925891480 892055233 935399646 354800380 543801076 379308433 881611734 51568759 725450752 319005942 715452669 176525490 632886200 33790950 505693124 956185196 979292502 641042402 680971443 707422513 906615935 544353377 779541458 97150445 823853502 121463278 669126662 202509466 908717394 49669113 274463388 479090374 850437362 608000522 804030439 160408259 698143089 576684831 870769544 815051187 938821537 112494719 888636138 867801730 993443697 27864550 264338717 646701145 708214560 982542285 989010867 146740555 797520101 396253267 798942376 331026529 852866712 749072470 895818660 973221531 992551550 8168089 929556008 1 263354078 272987371 992200412 1 540711171 887880152 920874815 915400053 930298752 653503172 882617746 312169450 720439967 316571442 614360324 848219298 953037555 415788560 866495907 596233312 702365280 822542182 911360247 367060616 995856471 144140195 338064193 596362118 754854908 471171922 946808767 959751518 996961348 783654776 960856130 155175180 639624066 692264769 896555690 401160077 957518095 701293393 785572371 594638755 903420144 584968194 800389494 617205035 764683285 94371244 893588905 87215422 151475914 90331276 862740662 197019789 342555174 20132894 731208186 699905291 832667417 462612216 946565296 560940915 847467733 182774349 746398727 518948649 576564887 439798507 539773683 782247970 979905164 12249610 185831750 920615705 956214348 993216509 996820334 910028731 940592759 151357328 194404532 847597352 863746708 347141334 727478297 112620516 717495888 950589235 964161316 234706997 929658567 240999096 290907547 606824608 711771801 720237942 909573165 740359619 749250696 10223378 515248029 322937027 803304204 290375225 677630541 882366608 948373813 803667524 850076554 444934773 567234472 217199632 737423297 33611437 856816883 544076531 728784253 460268017 633295091 122541187 434551368 979679931 997215500 662514647 862936912 853269796 977006235 319827070 883587825 779343298 988876966 490799625 928547839 667315533 742492603 543688223 887510598 441668643 836797402 295177089 498868082 655618082 775336096 650557800 848230564 46336722 241704560 964608769 966483264 224482949 520238127 260982778 916029476 818044425 913434983 779612835 789141567 101131156 554881485 760980588 851963586 57580515 969459914 450653856 966260691 343831035 711738885 161842595 966419767 884535575 888396102 482226500 831167399 360744242 958066003 134614330 155926377 357306107 476191438 675466734 884007430 275300324 946911028 732530977 821019265 435029696 773047205 369097580 942427242 810518965 875997292 107057612 465992081 506062677 942797836 490146227 544504825 87581869 137020998 419896801 894349298 773387827 876812975 381443309 959498327 826134004 881661010 211474563 690799643 198201102 624193724 623618074 754613810 825332620 837288274 892864749 960950116 643332300 663813007 911518208 912076883 48503084 997547465 705683463 838472863 668643326 827688824 818483667 892815977 741449049 927644430 656626026 738730215 531503069 754748320 721108285 762863564 909170964 995940258 165496029 858833894 1 400419025 536143198 735886989 426764765 587990995 474621911 641414100 569173913 985796626 283122360 760933892 585396829 995866530 872997753 900153302 532279941 702039464 230572190 728155501 945192351 979920344 116430680 244481958 524365268 747721760 462307407 915246859 952090669 990629047 509224220 612110171 802796705 892465377 813634501 933253448 189806745 469563338 989553967 992611427 84463142 609317074 268533672 723964189 11251820 65619859 606278754 731263978 576731747 764271661 399821171 692848292 243956211 594904101 138009784 782831020 710955512 855081115 441787043 539906309 483555439 993812811 928694768 936272153 692163905 788916668 638698989 716298168 722232986 842357080 103195547 307097098 554714231 606573479 596714637 823507271 816114324 936316906 35770863 294484032 646051583 795962372 23343549 383322489 391810620 863011224 399538815 478540564 859765329 874306325 907912183 955742231 188658262 862254466 498850422 584827253 160177419 637683702 253404158 553980868 146863534 843079058 292807215 692225315 618163248 845656469 953084939 993670139 467243782 919368522 513537125 866145022 697447281 973125578 713491649 829817969 894328817 931567871 187725343 526558311 618931269 940387466 587439381 805374899 832283324 846645824 472808446 963875343 341858648 444790765 747771273 901411593 670400356 705198938 406238183 544940543 159739987 621071143 56964469 360130556 638119570 728345386 27233846 622264545 725110162 820790038 789813879 954649058 165886308 440548198 770828706 967233455 407149920 703703691 994970629 999924076 395685526 915111314 657457145 866700270 37320257 415004597 42381 368205035 312043918 322661578 74853445 648445657 994269976 994651604 512918782 759570918 817424945 949462305 796362539 942358410 281051052 795870150 525658724 559910727 999367809 999796182 998449467 999300361 54064626 915079443 187815076 274016633 56324787 791854080 504775741 738265199 546027632 915199785 903368768 999016064 537932717 891036431 544429450 544975263 893350288 933263720 364355784 801907759 263146222 656276514 380726553 859518491 980552502 985412411 890184163 994909897 991915518 996496993 56613929 841076334 237122424 940681560 51609296 744790332 155348087 709011162 819090947 980766113 477285842 982242719 808513723 845603434 166480641 636752711 487234823 821148345 610927274 746119157 661299438 851650887 699541212 844498050 698376472 990618689 671619305 997548568 422919665 637112138 221722179 518309991 480406568 719602028 463130102 905550731 475174154 951076442 4623213 432109428 921409303 921555107 199969326 813185283 883142202 908791957 794116646 827016396 796598160 834768619 809576804 972563625 866207449 921019530 319726156 767276256 667109949 942014212 122321457 608646455 40453953 615333787 365879122 377621379 430240725 833575771 701503642 808265441 490396649 888545698 913050576 916145953 219485351 388571731 234626370 468695885 1 41048984 727459447 931622409 418579598 585495961 212448351 320568774 468600631 534974113 95346983 151926662 845768110 963938543 343656682 643087273 476308720 765219721 393300521 930171099 549326750 618428645 144093857 932658413 537620797 798315646 760413054 800648036 390237865 396637798 617459350 982722512 510433905 858451113 666216843 744840764 304953818 780794047 478328662 574329922 273977795 386763133 619769024 847493270 395812903 607695452 35961971 907215575 773184338 977992782 505913862 872816923 876927970 909317051 546066305 873011733 780711673 808252169 806518548 942850092 137493889 526423606 44294912 974884030 738313118 895273383 32644771 869937378 388261546 929612884 804525470 970546012 992718008 995913104 46274101 984479122 421433496 469201311 828218294 967979000 60955152 542843018 702901703 865982359 581801241 827269896 144922522 435385062 520564750 543573695 676560056 951215051 110726359 568477927 80075267 932866584 293589534 678731090 565978593 640594883 146796178 342627785 167854552 335084990 462539651 845053569 457786193 632619153 424096352 597081885 714093823 770678234 453934841 522407160 647982708 713315299 862727440 914448776 61886577 377231176 15942050 403316050 1 616286271 554096081 970602862 14531187 504841777 409215931 803484626 748145021 798069317 317226906 966146789 376062036 879981956 274667044 665783644 769894104 866458978 199657680 800337301 829729549 905711863 390684662 510440462 785553248 813512133 226374434 271437085 633925488 888367256 393965025 957295102 242312679 446718600 7583525 744494552 342892455 913555826 144316429 258578593 282496524 633980622 761440686 785279013 855186185 979703645 369935862 789300924 491403374 711675898 389974658 576780639 957055218 966272836 437282013 889175470 177265365 612149257 171348073 659844961 386367266 728824463 357090241 598160447 525981906 847110242 935025408 946884776 80271184 150960184 201264497 838385336 918380029 937789392 596187755 617172565 496546836 646495020 682120176 810896854 72746463 913537831 869552565 901236300 561600241 879682541 585169313 686495706 644011952 788119649 286972278 421939304 483645572 825853447 906058175 957098673 420311634 555860184 201442509 630145442 180052799 824540390 949230015 974136231 231799997 724179435 546495901 845751142 871756236 992827341 768509372 952414213 257593650 802866938 682554548 876441378 797566457 887256919 676069310 748651767 899033336 935979905 848733456 997233835 421619926 636661264 921485582 984391974 297983365 704910759 390891210 856913103 84587345 804745331 263092088 864111943 418399425 843630299 163527934 976283236 506792422 636493219 165509878 798044669 311161001 760036037 73476549 309353572 446231126 903026444 108449735 807705091 970842007 998068216 14147400 754985650 713771497 908154820 176451422 509464555 403376562 884707676 696568461 819440773 947923179 998112163 718908851 956920455 479031756 847945265 65185853 402228428 630295876 662767840 831499944 872894564 569588056 898958444 417006686 819938059 266147303 580552677 51290161 901008788 924421355 924864436 422259115 894323233 411719890 920091652 896752367 970063313 279615393 682165666 291737009 873437181 646179099 832112911 171736315 714745774 336013877 915158863 329702185 552267171 272630791 681023796 118966849 538257137 109919121 524569251 305764786 627157776 781574843 970622695 654916367 922668192 949123265 960640152 991608075 998305286 299291470 793119224 949613034 962819495 865031307 865988080 460565002 964269377 577006365 906063707 930024253 962365849 358792222 498186941 251290150 682743881 884700254 934555763 1 304040713 45403395 625483126 874915858 893079908 861310094 959451633 734662882 865287587 99127506 830835727 187020785 694325632 458726873 910533038 190550000 837959284 806053637 897013283 872090968 957828654 117398095 170346871 449494405 525353569 244438082 905171701 295826805 702036042 804530730 980244937 26631876 46522622 44020318 776613455 287700573 856170007 951842127 957026933 367056261 832311233 820602198 954702003 151848526 577736759 822486186 954352233 785008937 849442039 164568517 276436540 652150935 892989954 97862146 889837615 313609376 996750498 63141138 708545263 717913884 872307876 587590840 775603557 926819873 971298508 813046016 843184199 307012247 687519071 193287062 956443742 451742445 859497996 598463554 917231474 689581033 960580630 947420627 993509712 911969526 968813743 665615331 791861747 378822635 412309096 78552752 857900874 440339660 468001927 513085184 642869119 96924821 732125015 692905502 896394853 897308213 967938219 595231179 607589585 726570408 910850049 814487772 829577858 281650017 784328660 270214601 563320822 694333547 776083602 718848275 819487633 606816432 683268352 201151563 601582299 961564638 984559912 277824568 860997988 1 289879297 951433010 987294000 578307642 690078386 977776924 999832503 205798924 819306098 606783599 629449627 323052824 982798632 709854731 887438629 454092537 694143414 427415448 479803924 218419643 779576524 627798528 674581429 511551842 552600410 67876720 434164910 744873654 881609626 439271650 661918056 378164206 917514348 704351857 975768180 120860885 663362421 311040063 324410572 726568615 776538328 482157768 514616625 417397809 575135080 551240960 847216606 954928372 994050128 833571879 992748728 385286025 733960481 837245938 845175655 664135567 872820753 438559758 842122987 516088107 743376235 687396208 902044608 618914404 745568728 713854270 962665203 636850864 880124020 703004924 779479746 259125180 979205172 31647951 856453427 387832486 614045023 381903466 866280104 197594892 226399731 299760974 390870442 118873316 290137589 933475236 994460650 68983910 138145033 235147800 823346100 459564152 574905002 452220110 819723471 723483381 973584976 137132055 304671460 101991501 270971059 949516128 975840035 714820844 823928190 174224324 682331946 68205663 294145877 861135517 863355241 668374020 832946366 419653659 685541435 6008113 621158451 273154003 858008391 93379636 866741556 659660292 823538080 201488197 279323151 933481465 975244091 110151713 591261833 357015572 484803896 6547749 912389795 345780568 661857323 44526352 671507981 760349584 775999429 482938242 813158896 736468933 821057805 272788251 511775448 784690142 975268899 638599559 694742472 60205131 709931680 53560675 637023663 2003257 144911569 312762453 945352254 386853522 820166990 173386095 826155907 961082032 966939856 840783888 855265602 568940664 656173756 28627446 529873346 422045823 510469458 501007104 950435041 956638746 989143762 351946716 651335523 10596184 566458425 38760956 258369524 134822367 606399898 633257962 668414654 568130167 860570655 515953691 725558197 258499650 918738746 270730526 746867980 968092632 996925733 242507212 925593983 42238111 682423625 389552182 795169669 368599385 629665889 919917805 970565016 468036903 626621984 975284507 986628689 81648690 386519070 338820156 895291796 389327660 710099632 919916361 924266622 34684603 230058337 133024373 332905149 97774558 818990154 845022232 904488498 566558601 985248361 229290631 944407386 310917724 571669147 386436221 604007273 974927429 999998718 325123608 976429113 896433539 904563444 419289151 911481338 848107846 871149608 82326554 731908724 752727412 938945347 951766766 958930093 643326946 967885968 672606742 770452794 699656874 905717657 408755856 556976448 978968593 982540565 228706630 616816278 257157476 753460177 510283996 727991813 996254110 997003416 68588089 804819529 889962836 916805398 663171985 897946746 386450023 440633766 280977886 610945814 967002817 974272752 773948473 859091237 907007711 970853908 912123085 956491672 257383861 537509120 965746517 982757529 697215595 921965251 996541682 998060519 926729333 970491880 434578312 852751524 689557016 789424278 544593369 614953647 909213708 945990427 708511264 993739624 656163273 941832688 651710069 967733202 806347332 965616847 345407132 902742576 770083398 839948532 240745189 966679474 281407168 627855508 154812818 754842599 981896517 995682588 362584102 443227310 880693469 951311282 303392908 756457432 576755424 688302107 800449872 901891776 454494556 723238868 824148510 858116411 220845039 233532529 105870244 783174805 644417651 705076782 952710306 991362628 760799290 790571288 954507137 959975212 110546587 674507847 705313044 956525457 777764086 823140164 879310882 974645328 284053340 799611327 581344347 716851995 70583788 509668796 446181239 477027901 686253624 804978893 49959367 991424378 460775020 744208757 729385462 779389675 21349061 879112728 905110431 916407516 839335004 912951676 433060825 546031195 85713979 231945035 472677592 479020919 12443958 365512262 773246918 803885903 231822320 912167094 44299198 445803461 274529622 593395840 620131274 724359703 812170925 985372622 958439205 990710770 722385982 900575350 614107014 682465512 943988661 958431882 200560640 529695368 371509021 768404694 975470661 996941200 890490481 963188894 503326812 641940400 856743652 874236807 21381984 984559112 738186542 829326335 514210969 853470289 964646546 974323913 671444046 995920200 485090133 994638409 928373815 947581968 695702679 842179667 23170072 917799392 262315552 484724355 12092471 106159204 558256083 801122601 432989485 675000683 851992070 921724193 173804414 687025895 329475123 898220536 316129186 452450586 856333411 867575726 1 119920838 212740467 356995818 509376114 910617686 747006692 949013562 360486578 560708442 969812369 979111023 142527525 372770836 70625960 524087668 712446030 735591512 301862505 932842199 971957268 997100120 950075526 987818386 811798138 983081427 282105350 531526683 276255585 561303956 230566473 554261682 127977654 315975428 715344588 842963626 621517847 824613099 352073964 721616459 586434510 614253094 781782023 854192031 696974321 948295059 801152864 961622204 948179522 981981035 963831408 982780854 15860646 748421995 516687594 606486333 33860822 470962123 379252975 871277837 135215625 189607015 238619834 397356133 556342887 875591252 198803538 220857291 140889997 796627667 596634609 845399105 991402518 996336858 876395019 895072240 922391569 997164753 303159537 589391340 275026341 309475582 291968465 351545184 43945850 280169400 571504495 705489257 237999860 890559913 807693442 992705774 441742867 934202312 473526624 946060317 83887093 219959440 433119878 597658573 198260264 936881337 717287909 974191791 153123013 733939609 473278805 764961597 99301511 141501956 664851735 811709070 544904386 746003007 357396094 918983159 397247234 624838158 698897227 805401788 947472296 967611400 259048752 841918129 732663689 893999257 969941900 985021790 931844224 958095785 418265178 572669247 179787481 636797799 336485529 756029956 600207697 865088457 878088520 899459771 778722974 901980761 535117421 567051936 243996330 697794249 878447189 890944466 153178544 332766502 410292854 947020739 252355234 896510564 142351233 738362838 387317517 501129110 541693966 896825218 879676746 917895007 362038982 724339415 505615084 607514706 410067983 491642151 90197884 227564952 27964567 391593710 165381475 272829971 555146744 568219724 848646774 959443923 421593922 492106160 882174396 967930974 549312076 694361331 834167186 844461354 758043716 885586776 724526453 971239160 105839638 607796184 118566249 547867593 632094243 903146524 367127736 373776332 792886339 849799166 239021082 980423674 827995987 846059430 951586914 954885734 154951242 437491198 88699819 475622448 333652266 449321450 434449299 975747634 14682473 984275998 536348969 570060880 107073810 407413266 15783386 810338820 147810868 637474264 727749567 807685018 123950289 176349589 108803403 555844389 12839973 348899654 588284542 969267947 612066965 910252093 584921192 659058102 665392777 932645587 830689897 952543119 937179250 938094041 199975532 518345634 828705427 966719808 196880667 289732154 904349956 981948279 633655591 813947577 970689196 988003134 1 382738829 41483449 568193777 828606098 941042257 692648330 928905629 749604860 886383451 133622186 490684976 209041752 399106240 489182689 872668674 905809393 996134847 886390860 995582449 81044187 745303767 462459449 811456506 454470582 754419518 840769979 965008086 552537028 693522572 478630130 666856539 762815062 982743884 5718557 715920584 418624527 782597713 168698404 568241784 496544901 839545983 726404667 812510165 434541124 741882454 289288565 490366769 114560658 182353624 862763952 966520003 550647132 660673018 825009565 931255007 131407641 563681925 478057090 668665294 935140292 953202089 192699784 219066067 854358013 902289930 74093039 579687940 513163360 828133040 373470921 474336751 960304296 971772569 400869453 640042264 230269585 738245394 82136150 434758427 530833822 983610411 603607735 974796002 987263575 993800522 1 474333032 776594096 782595506 291448144 686095377 394133551 922539337 328823028 852802519 751548499 992091657 910151007 937839995 793292940 970673953 449966320 598836222 307845661 478417673 308326751 923926658 423555976 509665265 193433184 743169833 966192626 988281478 472516823 976799871 207874693 967923174 892547106 931600731 925896016 966464598 878775288 972035148 469090135 745731063 936892790 949699623 885591702 914940637 936625484 942679229 960883134 966911076 267977736 462275844 300782583 666322125 633355255 646453643 711744130 930260477 556191037 696225606 553515260 747101490 500733320 931839363 94093293 159751975 757488350 919423629 403284737 695495516 107692033 528552626 491465551 555999525 26692349 76187299 83914575 331357874 882535729 990284346 135624200 264395724 902090348 972067381 945236389 977037784 94206087 669771464 303108397 960527675 152253792 759977663 949695396 953942484 878245487 986368279 334158871 983747754 842567934 892165543 799751122 805123289 126716268 661176947 101209930 266258868 767286671 821562764 583289898 787115398 464323472 611654640 296766833 931090613 21577208 191038304 810419100 851742354 109736985 876019305 376341025 468647813 619937868 682869771 656560310 881812682 674025304 783337919 442782179 552204195 326932967 630198020 857043441 995187733 399281047 453961904 651721848 672532704 387840646 577225868 603112182 661708019 301973300 351745084 114294028 805237585 949037159 982517806 710391953 718846984 320782770 735095492 744618075 873990646 801013592 901943446 926293675 999376956 411292168 566397514 937849059 995683820 368594024 701430610 279909922 367738831 896100887 953910522 605310677 722841462 146070642 758924324 115381752 996136102 135793244 681349610 274180455 419620567 95480875 557263261 46866394 296343004 556046139 894007806 352212890 953252176 427514258 942682182 55926490 621069453 677730057 886009876 810286759 836501096 185166053 871292614 752454839 851500770 757637468 892010109 933164792 963672425 669363211 697455704 362437386 406755010 218673705 391040839 84752790 127509250 581002387 957509747 4608598 169288197 912511951 955700633 777230811 805665712 370890285 849576063 1 507326358 275940174 297953854 698720602 704696994 92319110 900120335 897410622 920443610 926203544 962907514 92228960 131058758 304003213 872821889 68370411 675546408 143421389 610722433 466985429 523907446 472008188 562197261 44743674 876003456 620122755 739999646 208885084 493861164 494564126 714291231 868373712 971108629 983243050 983798758 714186623 872346706 909673661 953636308 603398822 862471139 828466845 940796540 215802134 261310175 805677158 992982836 501596243 780533193 718225498 870445248 756854581 771959573 372674351 424659878 96893828 797991880 752041183 806323771 75286497 627319243 470847765 784613289 754191842 756276397 28703928 963869434 658483469 883715479 417797384 911262415 343836689 754404919 362319653 458475427 291461894 322340182 892278925 937902821 532169366 551875048 304554192 863823444 860660530 929379659 707610673 866773786 545192341 893437672 503835604 852986369 471335627 503756576 716836346 871806557 735552002 947753198 198880183 793802299 887465500 972271592 792631368 838942777 123397868 583861561 925333523 930009059 819824436 907559555 845554892 891874149 990288121 995915174 24219402 332889890 962867344 971027762 316454226 968671444 125179934 542401176 362534255 822551363 770572420 950142356 19615448 270470452 762552910 809801007 784926197 914288158 478264177 980065108 856324174 968541590 375758040 635572428 430701867 654593973 363035476 965647504 821025562 852446152 826295032 971563329 347958252 786806771 514797400 974566533 5391704 867303680 685746236 776383814 726402907 931220813 547984219 651054588 223738574 348388990 142728177 491268198 70435351 641960934 569532334 620651016 747084088 811235643 545894763 869244042 628910499 999482079 73378279 876687681 1 556081195 709184646 825029621 651296940 937226107 11985915 80357305 61500330 911368854 348480502 650057420 695083436 744906870 182149752 705924147 243753103 509730944 512915120 746318421 410819552 428380971 448951638 963194931 547341879 733590171 900429293 981886873 819692056 836117701 761343470 866618971 398264568 756563691 764026511 979087943 460964163 736323014 578543844 755504494 73938787 989601219 524487629 945199008 75710610 398758273 532224319 935271363 703689488 872543838 445406557 528416287 952594967 957048706 352196111 454643035 156932696 386582758 155251743 164469811 656122635 679524154 852499755 945903624 831292963 914099968 256930844 795241791 692371622 821237230 901456377 936431042 509109289 552432968 70847403 578180852 821148125 900703690 164119457 366418730 523237678 754722734 103658682 204236755 533750663 820745296 66178644 703220890 576765310 587861706 655681790 997003591 407897959 857803204 138639201 149065514 468419516 791256433 995184200 996928296 867696804 893877729 913974893 996090534 165666933 866407568 899882153 948324343 324934246 805825121 377205781 452704345 212978585 898567458 925719166 989086451 298411862 458444134 482189928 825164322 149152748 414084491 767918 836176850 473756443 740866445 641927860 840204769 492438335 534844575 29258857 691103266 992370740 995975349 734057274 836328938 35504888 377095606 211741111 639789038 256978460 899593623 398403314 969717982 60925426 138842210 664104184 815698030 601558450 805176504 230568119 351331125 847659574 979337638 510980354 867802978 820802730 895096747 549549249 646639950 256830602 492610613 200968490 694123593 943352569 993112592 15939875 631536349 922917246 984702878 406407472 833476216 572891176 747841679 333356525 969335826 199279334 312883197 357482299 869100058 193513118 276116138 864768143 906022710 751401758 975117081 1 176640749 48264255 743954190 270091626 814856117 535735902 634617551 120026106 524363222 366958670 574602264 673540997 915773338 166004860 825953772 626464428 826831834 794215280 896043642 328001778 497367027 669878269 854310952 524951117 728728270 345145050 497388471 735820856 847344437 264836142 989097615 841963091 894672746 884692293 933189296 84045873 193139532 91670670 505348136 287412846 435976557 293610243 911001118 167869054 392250999 7172948 689656787 276695632 369915019 315822556 337895878 36167828 926465322 980034914 981254791 464889105 628969212 657888826 859170722 186325604 561158578 774882674 901881789 687347755 750972335 868085440 904201663 732459712 883292471 900165704 985411759 227925940 302700319 912718440 991157137 35812645 104585294 739508252 827417053 657484076 933729615 733017720 877841217 558668663 872365601 932837043 963442395 7981483 441671113 431594375 995434128 254191125 731351113 272677571 927186288 532987232 907565544 268844804 794805388 952450849 984080341 992608018 995571182 422698436 759792869 385835830 858777981 844171335 903367311 495045551 831146760 547705526 879850103 511524928 771126666 882468572 940553001 744220142 859177711 643801320 693732438 75560759 270661141 659263738 770161460 545270945 911568464 34706089 548944140 759926730 827208607 607230988 713562425 908275060 968703021 894274044 912916628 227102966 235878234 314530625 472333133 244915236 791477798 923976211 990568982 963863063 995385934 833881439 882056360 437960735 996488411 912775577 926679791 783140440 941551106 506078916 595696034 330777257 980079461 345157345 886374454 626173639 972131356 225819463 226764892 980800666 988249812 715379502 956476542 1 303983658 773583297 961801799 750012049 786542378 165989161 716031254 236320662 604091157 942790450 986064440 168937083 956214224 860337249 975604428 167303435 578805240 130875076 227370119 192531328 607393776 911968736 980594857 418881924 438923490 674661385 751696805 891491764 940311270 987911921 996938173 911704807 920877922 460237828 786141765 367263712 870875284 501895636 879011155 414124253 622550158 96020642 295123956 323900308 976534859 142174598 870521439 158805270 268520515 537102818 902094658 395740441 484282241 571585169 912765559 880398925 956605927 591246328 802504628 421073217 706252516 563583245 915789250 83460268 926929634 377042537 697041835 681988714 873463015 806112190 991050375 779725071 816645864 896912393 967791561 626886000 644372675 794288828 884648788 135554298 363329009 364611634 890098640 702064367 901439094 491074250 506634887 8923758 364282918 547142549 884355424 618700760 632185179 858364739 894641493 643771028 978137044 893195700 915186462 943447912 980739568 966558871 999811161 970474706 996769072 805909553 980031488 14548037 529487326 325829016 634001482 557049966 901685236 339960954 569141036 888754035 980537751 199560094 569708589 32382286 390438782 408913008 842358071 362216257 731774165 240969306 684716418 949663219 997947679 701479347 875770166 929290058 940881028 338460011 563128221 52896834 268437476 461988173 828699912 80992365 959859637 1 119553586 486152418 499537987 511865517 926729501 977972659 978593846 551470750 587031193 580385051 672000740 448778156 554859316 927893353 960130699 751677111 859217075 549569895 654600226 676267929 869912321 197217301 554719286 129437570 240046984 522226156 848952451 39554212 454884344 614036559 727420549 205982671 788981189 968416912 973175174 497543552 681270061 816885330 895318378 455266943 505661742 861561259 971515290 230106824 937376075 85477342 99777919 552537543 669119759 445430252 838815314 524588895 895860544 364143944 786900356 390053948 609447300 170018796 386752918 583049940 628844965 651531765 915873600 889442368 978756672 60356042 851749860 647307505 961856538 456532472 956431268 198978989 521025955 249110855 619489619 406526534 545454713 440119638 796740906 719637323 879072512 477223077 975880234 689710748 765951316 853209597 983697526 693425261 886930633 1 59186264 644592177 736208010 581616517 919188101 315085623 796956393 980332058 984019779 795789946 941228568 969179879 976368798 679692513 932396136 545695320 753730430 726755650 915761619 318060307 879268499 878670643 898891132 853334606 977009946 50727095 825688254 206266701 621985819 116787033 470127212 6191105 147688098 44579206 318910508 90219360 269941580 179164197 760259811 554890302 648806407 487608735 572187518 819462273 939258533 561299278 984531516 282686416 860893503 793413367 935780571 857681411 873838213 206029641 975643867 61929373 954567181 363117872 843498777 871901424 943740428 391031514 613199411 773256378 812143784 533757435 544130353 1 318432044 283619554 965055592 46833283 591474451 612423063 866556957 42431667 592997050 910040866 942636418 429346885 947167811 393208759 841513346 885292774 955481304 454234171 752073986 118869574 319146168 15800617 951961220 273210866 484588126 796972826 980486923 594155270 685627079 387488768 563049020 51875835 566662733 913177816 982241541 605539836 758947045 430524980 749985991 57492402 691733900 985685259 995649086 704767033 744888483 876935025 880092181 735943554 986008596 230888157 425760974 986720876 995896690 805337635 951456149 675886256 685405502 959523594 981830968 400465703 568421848 400553116 749095658 835830605 919136361 913904765 943488851 630961578 837783220 475329560 624692005 743070550 920052728 187289071 640846697 217436119 494642509 471844332 829591260 808661593 897887104 889308522 950191262 14173733 899309360 339210914 913898756 438040558 717899196 465985781 785357070 342751051 619050889 264961629 312735248 58248447 458072979 595738378 795903336 84188246 573067340 8188009 819752420 57650877 920036078 44179235 893586226 57635529 576890935 807583894 862809930 548579013 719400152 360139436 718503267 561190102 854201986 717212707 914206304 60790033 428550026 918607799 936154264 174961881 225006574 456966033 559371615 658575525 772067361 716866198 989837485 603134922 860814144 787887207 964955377 316309147 722893169 588940902 738447867 343813817 818033713 741363805 922982331 228037538 611740667 883343337 918787210 91318336 332953903 753619721 932055544 920992429 934674616 980735031 994150854 614792448 890305551 729204919 923622145 431748371 961001357 118397540 869276796 836296074 914164921 615039751 750009058 309781756 874346529 523732125 595029199 41882096 957140621 237198303 522717103 494025605 876686431 623115975 853132121 56392108 892099670 29169931 816266172 936934684 952871722 618571009 858075770 868765583 911592784 971967279 984422824 264478855 390363552 498914095 751757747 855784056 978974256 682482658 754298973 305910258 755631888 629274897 714572459 163995277 644815532 332656038 579915897 490775198 985253475 215692661 472478603 51464643 149707158 790766773 840529356 949991772 968880007 333124148 523752164 435041136 673205050 701189434 881155376 201660379 461197893 521380935 723170464 79846067 225754814 842509440 916637367 100582274 787320514 664779902 987689982 378863460 584415984 636765119 942887550 457594397 777180525 445033696 505963608 188868346 391716395 21277165 626762100 318422495 512125893 809799490 838604341 194245876 904572199 596703158 881091133 651172831 852428146 910426067 922797673 432470822 706751416 860797814 891758499 798665882 945653889 309809973 329412210 553533871 605746657 990631417 992858931 764634018 986892678 409838596 770109775 972255304 987169627 432397134 748119162 603703733 775158858 477699727 504608690 923051130 930850703 496239798 532970699 789011330 879062486 975858113 999883047 54644682 663085257 371309055 739031927 994373586 997565842 885163384 950621082 743502402 862182380 560204279 847948704 238342267 759872066 131813440 509729095 95510664 589480556 538995692 554400036 258883792 674760690 557126016 632782940 591119421 999235994 96177181 556333199 918185279 919102144 494379093 788957129 660141552 732388149 925864576 968906857 1 428347448 904048073 953702892 332433954 402339648 291489988 940581930 312559648 543397094 624085521 858110032 211718847 240200362 432490949 563447242 454688520 708184655 31663351 976867293 662748885 885153199 841787513 985154214 548267265 932577537 71615191 109769824 132188548 661929068 328825307 342352151 21520771 167016813 196397157 451425136 791314785 912623804 233815534 441075249 770382353 878245991 74203625 517924637 767347179 942304942 308049711 585312107 430013592 656608843 635075814 644744210 334958383 749840364 546381773 649517401 219928800 420263440 587071674 735959222 2564076 365328073 165421748 936912932 214225972 932216998 1 605315510 940219564 971576147 363211001 498488738 437847806 722719791 663928689 926974905 449452608 636094558 260385611 787695192 520246023 616665056 411585432 528000140 401202218 584780553 466168014 715743650 713007203 956180087 9494905 10605918 503186019 627935138 655419656 753182385 318551293 995732828 811368131 900357088 294572897 509800016 960339758 974285845 251061804 644905480 48162937 141516089 696622795 748007462 247222603 790307744 816361558 936542935 650036588 758846941 251038139 655552269 630072767 828336760 358200115 371527550 304606523 906605552 600094301 826949117 530752955 994295339 182200787 706722370 402034336 674396471 137872296 441500835 424273432 738741599 549881340 642535792 876511897 935612467 598537100 821252173 156300685 526806606 408250088 806742250 338478845 670983469 48341260 893493942 896119107 984981203 522581266 933760147 724255010 805923614 677808002 956247029 608233834 893586387 986458285 993844632 815401575 961703640 681287352 782164149 444202950 610138134 901749239 916787091 867259567 880774336 510876912 912064429 117226408 297628731 940522084 974004618 615187145 877958098 835496556 973618190 759576925 940906984 911757620 998117357 310420329 611605037 637303156 734148760 619824431 943654843 703156211 948177113 445105078 487429545 76146515 965016215 459203981 819929507 947429673 973071286 121871216 828235994 278278561 540676367 765209714 839506821 693186939 760401655 146861672 836307706 463316394 899307615 869578567 892894995 577236368 773839577 520737417 608271657 831332230 897732007 528232657 818513985 178977734 623755107 795874226 810539367 636460306 732528796 933979124 964130686 500394962 737817442 283351954 821595041 108559062 779257929 785891132 903402502 987830074 994808539 969008659 983191963 591788282 700472384 516915263 552186307 504645934 578363611 108721246 559354010 262799527 961030793 187275539 682335634 316913243 627276992 761284188 890006014 797191533 882618052 157514955 298545442 119495516 405832299 735306889 850375266 881132703 986067728 284656983 482208635 364629062 787541201 806866368 926181241 603271634 712538287 345252997 849146600 120052687 590134310 854955922 876400824 843251631 865618898 106511284 737636524 174876772 906239030 1 244935432 827276838 901429830 233743471 721127773 657939661 912266355 288788367 580392392 565453702 737187597 256615255 898020418 741422427 860872966 824231005 902314427 959039480 959719246 768328975 770811572 294837636 527586511 591887232 891093818 624053698 692553430 537473551 634481033 213708141 904570337 626062847 644829200 475240646 981928020 396157489 675388753 300848966 325149239 574383382 669484045 770974543 892239363 103836018 275281897 981084072 984900489 378829825 636034885 538032153 932030975 233018266 855921514 334945000 544609786 276942617 975609489 402209770 738181418 441822612 933891469 160721179 631588737 248440794 863447200 795321856 847601071 417746204 742926511 227910636 743528960 763319776 913902016 56097291 170923666 841015335 950058014 157896663 402523671 861839791 982245852 952722337 979882963 516590831 638120122 683036708 925476335 41317505 607181225 461278234 808396714 137709980 598914848 642393455 836084792 806813074 995006589 423529575 974867993 368615267 674782244 589308170 861221884 760758220 766465645 670485229 791211623 385885685 993604495 754483644 990116738 518155409 844689086 995773952 997154101 988576489 995907547 551411944 589279743 112355041 769779113 834653068 911867473 66536018 460269687 867839085 934455432 788032365 965734745 161946819 891402408 609742279 929258451 217191353 502539212 957833070 986497966 807166556 863917602 116985579 998657115 593515913 839998751 242283232 658385613 452299183 491423052 8968797 132079059 320576815 403195829 574589608 888692761 747880905 879333317 618161573 986471307 851711497 939379405 345404646 437632543 948892595 965545118 707201775 952312955 296170954 589020374 211412530 630296564 964978847 991434379 836458080 904993773 159255569 323303579 934708994 972936031 937658220 982426297 53932810 109984459 814111329 965328357 926273227 980213612 149177985 711592316 95939736 796757904 65666545 272909521 449092512 553310849 488146344 903406790 857214580 911092213 773111257 808711245 746370038 964797084 274667761 516332445 707917706 909481588 524890774 780260282 367479961 532334388 163361613 795024783 764651922 859628976 677505704 941484928 140412379 259635469 282021950 325150231 511626625 821974430 528570961 542860574 98590047 237574377 864829659 900218338 24339826 297156880 173853734 958590389 337612264 341612050 530348342 979426115 148565481 763677852 394140475 585653717 704586811 868806615 956046394 980651891 519018951 634451274 231765624 799467481 512325332 734814517 1 139521413 222729007 763299584 49870522 210138543 477913601 890080594 684825262 945520840 378069169 824439293 431231161 739715498 166435020 231705725 840250665 884814769 330445878 423152530 2809430 872971482 357810269 945901170 130870734 885688051 138145621 220423852 511070263 667675995 441698414 641573527 792799282 830668872 424205150 819063772 524127170 834260566 301290672 504022786 435673488 812864912 259559729 806988285 168730555 241686484 927296156 937634703 105399927 477629522 416006927 540947642 872624722 967465252 54779863 351135545 220906991 899766573 738586328 818540179 304371559 804534411 298772646 456256018 163920375 269596556 887540540 976057101 670891443 748204832 133732639 936157290 242704871 611059834 1 749957221 15537720 433039986 952375595 998543668 335766534 748999358 775598606 953398435 51513931 746072034 485074859 924420851 832968510 909762907 303759313 395111497 425615091 865311006 131869523 406135760 789036993 916140602 210970340 732727266 621870722 790377029 755214836 775742050 223046535 310920397 66789668 325177790 692271152 834284959 157090270 754834758 728544038 884919031 603512812 957111772 198199561 319817607 4784505 520884351 193332703 518727609 678632266 851922302 943903904 947195649 935460677 982707019 725647497 771395595 200641965 625014287 916444370 941875063 918114412 997760856 1 406071020 61223060 315784376 984948295 995150499 338895549 725404980 259505808 698236924 552865113 860827883 8545448 28167887 160667824 507561178 522212255 629722442 574685336 759007468 711538160 905776543 831991145 988116175 866337226 884808074 514018599 682476128 699651388 794384102 656081750 664604261 278486775 290684047 352186574 812713551 948188105 961456033 417468225 988386787 730049516 811276482 848216412 999842452 671315865 679642192 42845343 669463804 720884741 945554771 243010073 276090650 876204897 970393166 507645318 757385981 675249104 759774743 539218375 792753920 210030195 279203918 427297153 612812354 926935812 989137260 85398353 637354649 38303595 46389910 241350096 543685921 626464295 643268833 608451429 772458488 253782259 791554050 102969880 739164845 780137481 786100214 899969790 971073754 139936602 923007003 1 51826598 689344366 977724609 544892852 875517243 486305407 991177061 971285324 987703313 189863001 864149361 348039469 520199256 568083465 783864097 636996083 960252625 212213297 616485260 988254785 992501822 730913814 848473425 270542041 882352834 881034356 896022019 887428941 919510637 175283077 888952299 258099065 919979729 617364412 720859245 323679373 884283183 570275385 583975506 328678332 762015333 390933531 650190010 108863752 167226712 175164533 751843552 909922048 924290841 2250804 729810470 752973768 924982701 871224646 960673225 90682964 445238754 998196903 999913821 737370350 742751481 864260496 894477420 148010574 528794302 206015445 490396716 646305754 804632548 86440659 866568491 189448128 889566056 470657002 944909839 153498065 826543841 735970002 781949947 969316482 993823205 204862453 535332264 221482921 290865359 451952683 493120414 588978940 592911808 754270154 828274255 556790405 562251749 286668130 764979773 957184451 999733707 820964927 832815164 911366842 927851604 466285061 844633796 635710320 686791060 601603186 688969158 838202134 873310555 285612952 642306915 398930589 957562894 942675985 949681501 801332583 965859992 888325327 952278849 860496011 903435814 89221022 459360640 985566654 997442252 503158645 948856414 480312046 704136978 831078290 873920463 446650883 534960754 30398402 492558761 666847690 938428299 570509889 724121278 957787606 980182726 939475991 967612630 435343467 741564749 962918477 972477578 558921537 973305941 52195381 975531694 699952543 986670589 862697117 874050055 952398025 976646417 311679510 772833747 485736879 512028569 671213832 704020522 20019358 800255203 521017804 584973080 116663508 381825274 227216148 568724458 765661639 994757956 490187896 620501769 821369715 976690215 556204165 843438314 927942168 941385159 620463461 796508542 661693085 688254049 622263126 864765314 908915359 934102146 182650094 285502550 193386566 996624604 322169775 442802542 772029341 959562378 500282410 510283230 731202488 748578339 984465233 995887112 88085926 613728742 914849529 932409324 568291655 580248523 172187527 811418590 308585712 910073060 566014663 765083121 236299518 571222304 112958203 166523615 398869554 752699376 8828863 371875858 707500381 934906380 558861552 719844485 85297418 415962816 269729552 498868582 440007409 587171458 665547607 744466497 960070540 985530234 121029774 150695958 51323143 838527511 897544026 934649051 838492278 970014455 258434214 711557905 543515174 912720748 351028306 829487299 344231598 885786657 463493211 488691702 222716956 741352647 298518944 697828961 256601540 697255675 472872021 683297859 457382205 581252278 912646540 960089897 178762067 312295416 609092240 839024475 253460922 865024862 709997798 961715854 67707529 896906756 175372724 200269959 712370096 914285851 304530122 740782875 885240931 957844703 630914813 651127102 606672341 717060533 898808785 996724204 731974436 882009963 622983804 779922551 284850006 576052327 618776943 904687254 897448302 928701776 155050054 970625265 51116455 447017370 855533439 882509272 409520255 540401786 118458217 724334811 126259456 742750891 15835939 702735498 99326448 396708911 542425445 886405001 569235068 661897934 451846907 632454471 198526938 523651284 280353033 992203779 47904050 460760046 992014591 996635934 862297723 955196942 37174057 762616456 923510437 929707100 408624443 450871942 132683632 966786461 264772485 734386131 873562950 949410844 975357987 975590761 929710192 961521479 743113136 769491505 902268550 960135901 862660166 898903366 811913550 942951163 336029464 442112858 460641322 620135244 979850046 994407131 871927571 924011849 781491724 789828338 93098818 175036773 20579496 813790023 501690195 860378627 28645740 269290515 886451244 905757348 759716301 797376839 424589335 884497963 669384522 752235659 511912359 662407843 277248165 599423301 299096499 592936392 510835109 835591227 994326202 999737925 852228113 971584914 831999655 870323538 14864406 251193544 233332305 896940485 545276414 883458293 290410505 604490349 627834761 809391545 84143312 797332377 710193551 857702997 889039964 929158627 265912387 771325774 255148304 800285772 46707743 181877860 104331338 801050711 20185521 288585404 753995422 957019030 195112639 974695627 602836974 861625963 642556916 920191016 357842017 597896843 873442739 978218236 376917545 705160281 724638591 952866505 152846202 270020292 244874214 489966734 836639378 952036767 998032022 998982263 678745155 943631789 925905211 993938239 520411800 569535837 129835638 783683090 322266582 789282130 742193594 943478445 199686922 483892818 667098114 831199544 226280714 246482597 203594640 262830772 7166899 186063583 844441827 856383509 555436481 805469515 694782006 735890179 411939291 526601662 918383148 921041515 383701197 846329022 157739181 265987500 576548149 774020314 261263535 623318955 711882582 794484465 952502544 963649056 199908382 953740780 960038508 998301665 539736404 764076418 171546883 351577579 878122535 990386890 664558803 821805532 296578728 552303376 421870686 939862692 830892522 871636264 361201150 690641718 962684759 966075585 523789341 529549722 571707010 885296048 458302694 610510602 316216739 454509986 460372895 636784419 199972231 533622802 264122392 535396217 815848267 840639831 637099807 899625754 983500217 994692466 901851736 970915427 670699007 977178497 1 973252639 548453702 800395038 190090459 259368798 709937145 751701161 958839742 973385944 829346104 875391145 139222446 690415481 766883760 955152351 842827367 869693725 634258680 860485881 1 873018538 326342973 664313757 295171943 577555691 321245978 764499781 23624877 251239550 436392030 529078018 884221064 965420035 419269605 590954193 233904616 972463023 306465040 476340434 736478403 754427648 664837793 806839201 949500526 962676184 484663720 960997408 237728208 899396449 61070490 788402040 99990802 632303774 619457153 859927546 424835909 698572463 841495844 896517699 551781659 567257478 910771203 961011787 168962509 752674349 68537953 619724410 277769878 862547104 354940081 390102244 100803179 123075557 570568726 891221922 371875846 796855813 900190322 973575403 242401566 803796182 557074096 970481140 851416405 988211216 957355934 995157595 808671190 864305842 523934880 609421857 31387425 334934967 72555017 360839911 372556036 823314179 270936739 676558436 151152705 478998341 933375089 997437743 561985529 873984653 43439526 918170935 357687947 560170218 733090722 842195128 915329955 944452712 898716876 970048478 950185193 990450579 340515043 493650173 154843292 885283914 570236400 668601364 526534770 941876557 943460406 983784394 921134707 929954248 504998836 815114273 668275577 783708944 409163522 634029885 652209480 911503736 690815342 965276203 125288036 719223328 207202534 805942160 989516570 999313875 436179329 709992234 599223127 658164060 119839125 530793397 488258170 956204016 250321287 808017230 894910782 972905517 765018531 835505588 456252391 493903618 198162582 876651607 916516607 972228705 199722166 813480124 818067493 886369303 268063079 538728826 250610720 463796840 150033600 251004817 260509448 839791658 439098137 497510401 275632159 611158097 183222541 929939094 1 421025223 808151076 965198563 462811104 639541171 30140049 733530895 477470255 759862502 750369091 986933350 775668068 919094933 867988585 888045451 40504516 454040389 725354077 796404541 568682164 793286527 347461887 416812726 620774422 991990946 552440993 691975600 913650015 917812744 968302319 979888864 832855875 838702909 306885473 371865274 703398420 784422722 972312264 976576192 771697707 939461080 953061748 966902902 991138497 995741530 434315939 920540506 924495826 951339425 799977734 999073024 996443466 998249749 50813162 198419398 358560254 781759085 235257090 237786913 530084620 801628977 197029492 323161539 200291348 467262178 82411905 411019041 988051060 995235963 964702480 995381764 226031035 861254712 777916449 941222493 590752902 808701950 200822459 364884854 310475332 983444148 379426511 766189033 884360283 915120904 53633334 922907122 947835315 971686545 505335779 593728736 324274322 617421152 995946950 999790421 991958447 995714813 382245911 963218042 603542216 637465960 384235253 818662789 990000436 996357462 557522511 699911940 614332332 959599227 23280261 53002986 707860919 864967924 780564362 801814147 506136649 543415493 539069804 581332093 662714157 982952529 56467002 842809469 827926881 901332779 453327923 879416727 498880072 624467930 728548914 963210093 253970376 943522553 940419234 971323930 433731522 434728917 185084892 473539702 37845409 356414032 805455849 963699675 503648571 971902799 553617718 824464862 142506886 449948919 531226027 790077526 739856834 991446658 352702819 803133953 554799435 888421627 615762889 661496996 111314128 823239107 315325805 633838057 413071309 715154738 318373019 543133604 569766805 579885188 871901254 892058552 62398330 816526272 508100626 655745800 795104515 950491818 12231209 783748693 706290730 725600289 954890083 995104659 199559179 930238983 996255540 999985288 408513793 982049385 690046479 713440021 63933116 322773143 358492229 944111296 204933602 668654968 715017246 732707487 587674358 719172489 21170397 737370405 453088534 520873038 937387125 949280844 20390410 585987150 464832551 747543440 650516944 774245663 596969193 962609637 152026494 401062616 521305410 946091765 449710946 915562841 870336617 874647198 218542364 775451163 37486549 113795659 514631848 590080664 311039972 466369519 663239128 723684340 677976372 878066881 742395844 905126826 8592350 323553093 880872338 941706726 575214764 681763298 753052243 834137022 957446971 988697784 235341508 884504734 972222422 994787426 727479364 857054802 429312660 556693483 989183664 989713563 451604463 895314105 529571077 711071976 749656793 930039014 910272551 913524513 205593160 555958801 901891419 952679053 170978482 668814130 63973368 738764538 28129139 718612192 28708919 321567591 217534800 507220753 1086609 111192684 131472223 674171031 944628828 979573554 152100123 760355130 651271417 694235548 439472380 593189262 409580095 455744603 722553619 729078469 170197383 446123942 251472464 487650198 185227983 362024147 652020517 668888430 361911887 859302395 145091622 848872453 81957686 284032419 114418668 155520739 529788437 846003182 257530668 713327454 98560038 960440742 667925202 861137904 686251914 845182086 915877820 978040025 657734392 873290325 622787359 796404215 566494840 568623800 156633656 652798937 818694508 964001147 772230023 952998048 176114530 708669344 384034490 480378170 242043367 924659883 493303120 504196738 15785295 969567735 839093918 996948156 555426252 811606748 83945951 984425109 15015567 315409859 93871906 426217882 8311928 743177589 638745674 723602344 495023947 980493796 412203727 859402035 149553320 974334400 756348727 891293800 140172850 615823930 555533320 589622249 460650924 505758313 760529210 898791973 858960769 944825800 130036882 387886037 809137970 847087366 940453845 968497916 486401619 508095551 485646654 587768311 861109935 975063223 285338101 372195363 108937232 544528286 269395383 369239576 5342284 261910324 795971073 928586751 1 589672551 436923669 903897114 266185574 477797071 526952328 899559205 293703541 973385732 891785454 987172510 664355089 956556177 721801723 944610937 286224351 981956177 438200126 961537823 430669316 758396632 138551155 435108109 381562453 677736679 516348231 691136993 105663817 266270368 264836511 599126030 671043691 796935592 869888998 944951479 550221129 551559075 621030532 709229040 798701396 824803502 398977952 939959208 877844899 976791936 88305829 698777680 226841802 556161883 910032143 974581644 221211815 504541273 325097596 372678570 717530525 791746291 981650157 998757905 421827763 813322552 409331086 780482301 190112098 365977160 786258116 792959939 987695145 994908300 895490221 959026749 435969871 503939948 695907582 841354206 255399013 919304613 309018024 860257166 469419695 888958117 732899237 957314894 278593311 873298160 755930644 858694539 399786583 624988261 951298029 980590678 446616861 448982472 796098192 992277426 787847239 915411825 740020711 859302887 719406831 882288608 740556193 917587861 537892825 614585266 131363529 490430873 23736442 323399464 666896659 831246604 728019906 762007498 61789247 358787073 132258811 479605476 741332742 988145487 346615597 640806546 891502656 973115170 920329873 939580696 895270289 925483688 131824637 158616829 917434488 937934871 508850116 812827082 144883061 423231766 245967498 409923269 886031233 998169886 132775614 565070922 230638487 493486262 461890081 756845257 340380262 512760386 14673796 232933369 351016650 847408471 71627020 740468195 768833324 837045819 742473405 952104049 884511422 946129901 297462772 628495708 378821452 951622856 689934336 717112206 304113294 400344107 545870263 965345067 273852584 686797097 779883897 970132116 31259456 591452754 705421827 877817531 46685595 567005240 502055432 629187549 308469389 541573643 926755860 927523203 896297546 910188388 72302175 485028845 479317567 873599613 135124202 976729443 873835745 940640033 950602855 983365322 22289410 735976040 185268214 346041496 636686874 724629920 44148703 512886337 349289284 691728338 959008908 992342196 107020456 436419629 565490311 779237195 383283242 742094776 512191706 598094208 301465436 990818608 245228249 748802874 10424628 46229887 580337681 854190934 764086255 998075892 761327295 960768212 536589731 909885257 1 158065913 908089751 916062381 572529399 634736425 212929554 465927414 456027115 779431356 267007929 694887809 778008104 778440068 109750308 361129173 618903635 835659162 868887879 938471871 501507561 901393311 525684208 907641616 675652954 792862818 203743790 835145323 936675600 957625504 984611866 986934327 103679560 215986002 438604247 747368350 879711967 985171130 529269361 865172258 116407973 830298004 809076339 868269481 745047213 812781804 806804721 960863730 948294294 993115118 358913759 939548205 675452827 930833459 92875682 428165168 262029480 534439146 319404335 771900429 323163047 785836522 768775361 981007175 931079676 977931558 844656199 845479463 997829341 997887426 241432704 700468097 504344362 951718718 888865548 909166183 311126484 617298088 58467465 286507376 17021067 603787835 417622073 945735040 797225420 935681479 656834081 769632224 135635663 227095915 951449051 967428021 125902641 506349091 326914082 730082051 750133806 775297185 509949207 794401957 905046466 937800491 23241615 335212127 945365108 954703808 884408261 950897591 98481188 419360360 523986041 650299975 303310644 471231768 785940232 985931815 352012171 520993585 794834492 858309755 1 443633508 796506466 959296276 586713886 724524456 999170185 999554855 869363615 961988702 52159 6129801 678461507 861584128 112446566 401494148 598563208 702440070 140924917 665509062 870767088 915562690 984845099 989289330 12655063 465196591 662721913 832497311 66312909 299772001 23571254 550654009 255670359 673000524 943023281 953667193 184182409 904281307 682241057 887154741 699559186 871755827 898583292 983868626 790901166 794495897 475094987 708009823 572894907 937937230 720608178 761146565 363960540 987914769 969805653 986126804 834151351 852835281 157379945 660891761 93955339 376959292 244043177 917647232 722324238 886709648 100199718 975150174 774694716 946551136 542487505 889742486 635980337 746375393 708120916 751709045 190365619 993725020 4263901 123270870 12602535 677090194 74085841 301146514 363773041 630732374 738071303 868222350 219526429 385064894 459387421 911272730 570628459 941974259 329998303 508398477 141822561 602182901 338229820 560223837 454143175 873369422 890690214 949666932 751509117 824666768 508121193 621692869 517078006 944505577 602490728 792540989 867349811 998853485 255558740 551171788 524883894 669899235 336679266 780436519 483645947 504954294 488623943 692951289 283123258 936528441 984037340 995315445 763496418 886512504 982039332 991841904 91973195 837128033 284617089 753796450 493808327 533406623 817108277 861351800 792106761 970500950 419944208 513241203 718201316 863956123 517617769 879038697 56625710 332965109 2458103 477905988 632273710 908262503 445994478 665177964 400458757 888742436 950658563 992264043 813881792 860148300 925285252 993742246 957975542 984350721 457469911 488265805 405732124 456875937 502618936 807496456 198368460 637519680 484864985 768586354 762399549 936880064 921690056 957767017 307170567 528914563 850337402 992997079 968759296 989791183 976805813 989453653 51770755 947233797 533647548 764048058 59824016 474805201 694443523 788460174 385499903 811841564 529821697 745548914 986277643 999549605 788721983 877373710 1 999153499 49064503 530167348 770664798 951180481 548855414 876920663 954974856 966232585 548785754 644200888 849564136 949723198 632465492 672645487 244220251 849533024 712064972 748608868 344955485 947162491 25487429 499402141 726347587 913599984 241632209 561143629 573690150 594131930 174859696 975538730 25999444 659420579 45915854 553380364 765302327 937921620 555250437 756675338 198483203 359416416 111275770 223210306 390455897 589351331 231783609 676639573 605394116 773236582 73300212 652974517 83082543 336293877 159300170 334188220 4776331 670839811 85661767 328356586 311114521 706562139 118350222 297179871 21058800 297244468 767363338 934186100 468543915 826941961 280181191 883467837 563585788 579227923 103656622 601633855 952722109 959638506 793537933 890748571 112931618 596993865 876312730 924261628 387300978 902826923 77835832 832296699 628190086 809561132 583020592 620457144 411410541 712803800 748383419 995546428 56745526 362417844 278077993 492886754 356838029 495661758 659836728 909391303 725764794 839747922 950557328 951733898 87839537 565627299 671087807 818988264 741102882 805726369 580495744 730515466 324931797 806525755 152046447 317536395 429621517 629074682 219779891 598619615 244824778 393392822 151117773 818219909 1 800012315 592583763 729522161 579660938 700312155 765684465 768444810 981392101 991144423 170977870 764379978 317146668 758339642 480820272 562301474 301546502 955161556 632851668 857946172 70226776 917353999 681062250 765801971 662656907 710543097 931810896 994513649 609195704 642626983 802648541 959482124 159654882 196313963 356788495 567545725 727870527 759250721 433067646 935276015 825511917 929162821 54072230 230100456 894353851 911226284 312069964 896143637 707540568 858421727 86305244 250185051 245817121 529012468 283509183 749509743 648692021 650736788 2113278 527137422 713690014 931110341 230735601 720422549 201488692 566257179 631475615 767240288 228273608 776459175 325833660 374536294 527940534 782908918 958204562 995729235 452459222 753171275 922338674 951125466 629573142 959097010 897548625 916250127 296395743 656452474 769544469 810194718 408512265 955838443 974925447 993630900 684367751 828186691 236153610 478029839 835602322 930641742 410601402 467073181 78974658 530886253 512267486 719067824 430060586 777812859 719173276 791206121 206068036 953887510 74532022 296214140 16913228 139270868 411534317 608448821 42653532 182275020 199782144 729424288 886804858 931388968 751423513 951340945 100480814 403417363 305085074 951559438 508556649 715533069 712293504 835483015 460396987 537418848 467808981 979708072 542484921 995761313 700225108 909058041 473246231 483956307 39455036 966685227 133103148 685026822 978768353 991119592 302219324 798071981 85292638 989375474 910272865 966437186 844812230 977926983 400981995 735578400 232956256 924623539 218653099 928054316 201414708 873439200 539214063 622687122 190711734 656562543 559209787 830930978 56118797 96394674 42701947 894033413 285206488 310059724 98016924 840926307 462758013 731225701 927340599 956027191 530013902 874190691 33758322 282412731 665573793 798187674 958919703 986213424 747671015 966807327 584769471 776460681 163233366 894242435 518788952 687045874 393433474 873654139 549428636 706752734 650855074 768209373 490710617 720925316 793433207 860132338 893326378 971834957 603489185 657358563 579392515 935995557 4118671 187635138 963258374 975116339 796963494 895595677 847838129 851724088 36408877 631137347 903500770 981656946 353808605 944856947 162265688 331808519 707355008 787460381 417611313 948103630 970144282 990004275 603745069 621609071 184484827 567700093 608826459 651200040 748764514 817136394 925509876 987324349 93801200 554820676 90417040 587077529 247603236 895272169 989974729 997379529 389264461 944394199 182699751 362110579 488779288 773827933 891651939 986971756 992453326 999745943 200176196 799694508 330172740 449047636 812981383 854676038 633585132 801147081 309630329 941015736 606497484 904722921 672921225 803626466 758827972 827675149 180016675 828283327 643834027 939929621 596342371 689770888 417798556 449368088 588096140 906720914 86614119 723175105 700666420 720956617 696053557 918760789 632206977 666992381 32332062 339273047 818234047 939351460 749094318 935696760 715406397 807448078 934767959 991508494 816236990 988902404 590435950 675475733 531756364 636777343 40669310 240195982 491577151 569181529 168350976 352791864 609228755 693463849 619591934 635726036 715808868 807237863 460528433 766236711 302089233 514439113 888857836 922727320 977987845 987302321 594214352 749220719 647591117 848464950 190612040 790440970 149738955 844033351 612668993 927044828 389203397 766947075 504337528 855998718 964469948 971912231 844235011 875121186 57282832 249090119 348881369 622268027 252795985 700019541 377340398 925080020 291912856 568134761 963098020 989451624 825108012 834788570 641890541 999193530 629215173 763666119 927688878 940806390 386469605 846309151 137780856 829987533 163379806 214983075 175935940 668929339 149623949 223279948 908185672 993544010 15369462 618496362 469235891 902093750 917559782 984055445 963517227 983967979 530435744 710710239 55832000 69216716 11385649 489999767 587257473 928576686 478203860 966118428 399607862 952580751 351489385 869891416 326702189 819914877 221417795 852917373 607331429 833517859 311395186 812694032 462598285 808639376 795265875 927769316 584038609 754502499 890434323 950056914 600616673 961703538 776960254 999662201 544012183 575540229 370168157 744087797 684025152 828740718 448226939 606879123 382750867 383954332 426276956 432910740 442144151 755782653 706104222 919744834 772583691 896916949 634966782 924335932 356279538 811459669 913121048 924180514 190582041 966242532 492348903 941549250 651708538 947782415 401902617 704206352 762319618 827372862 649176366 695479032 508485692 784954072 877970130 940911898 804645253 861276199 440710779 988957829 469989198 901001869 836880885 913297460 781001578 822653973 624896009 752587487 100822834 997808564 712131627 998302003 554448250 896514883 194223075 684464769 314510445 391163045 699536737 784577535 421348046 465151863 409166065 561983929 1 921484643 201461087 532841016 784875378 999231948 608211580 744077264 605945245 747205107 285002238 616713629 726298476 999734855 919891674 941621277 963190123 986921807 959417111 969624661 390539109 767570625 976362490 982851807 144829569 431998975 362011915 793154755 495944328 566638106 529451625 780474618 326016883 750279906 293677380 751357309 744650563 797361438 314546076 347034323 505288826 688317483 236370047 419154595 336561139 593455022 146437800 154395416 891116664 941223849 258806034 487072214 319512617 598902070 140576235 968773374 765636605 987445738 771182042 808677208 871368629 939612481 14527182 639209861 909137324 932686376 844857990 920378302 169120620 421475496 378672993 938414498 109431900 841451381 198656227 256570479 446283978 634235285 224602614 685899545 813999262 909608805 631081301 714569526 102508166 445263757 364259210 667387497 72468382 613417474 12531495 988725250 83847193 867948873 954929501 977934334 851329972 901008344 702014268 941021828 410836452 450423554 191352673 938091121 575289924 857726581 868520747 985559973 995410666 996225229 215482766 857681394 187543265 830355175 500824558 798152862 525589793 975897891 354585037 528335638 796881170 977847538 769320771 807187576 1 267194209 242903023 912170786 160595038 668586907 990119948 990421454 371307720 966740947 380169683 871190106 439581018 829350319 230962168 674953733 807047569 807618213 986843338 990896495 501817272 877620717 806603221 949384010 227312682 606850773 399645861 826006278 588374748 777112064 679195272 964002906 873290234 972235503 902293908 978908487 955049381 966837856 791663785 928513324 62572015 85049556 1 620201661 755295486 962191119 165082217 767477810 815948713 904799684 196536492 861616621 10771347 454959890 624740121 860299123 585433487 813760293 611883975 969124995 228630187 250638697 271087887 910731678 584383198 610216364 16681908 209563380 486293011 941097633 136956508 494333018 680100005 718448540 922904130 967263956 855028823 970391430 340540762 539248439 200692162 976827208 518290443 743559631 252719414 316522013 756908440 898744335 969363902 999263574 665806498 786149814 791212165 934378262 296936442 642564928 1 857327994 76716577 270876918 895925074 923158736 854165658 958823288 243926414 633695284 768881406 834217435 441507270 775457043 431215369 897122078 232563653 399048185 304418191 886899426 833491168 839189412 636204800 754006743 605360882 890640519 978197366 994606723 898605493 916312938 410383133 756366471 363089494 937158456 591737546 983707684 724653553 893762429 402572893 681528910 874664217 922147290 215026620 467902474 221576717 489892747 650110876 969584208 810092060 846958715 730280935 951333960 913731501 958566354 137486933 561955064 327560668 927393174 251146343 583552582 666481584 751165131 254622379 762365284 20128340 614592173 316873700 557985682 378802073 751284377 710687390 962184377 443069479 455574678 172600778 873836541 127227513 199915932 316439501 476228621 111723417 978542497 490430348 684234869 549402262 632444822 730564084 826744513 533285761 559986219 733766590 900801268 422428275 444954325 825071527 870726438 832631650 907312615 685254771 995983350 731488753 960336276 967537702 997886670 965721659 974872231 432710337 869014337 586169203 829444588 666928531 913396036 430368188 620585848 215558656 694056256 579035497 987459861 406324498 593524771 575528858 626092003 673125093 972585010 371940716 757460689 85644869 722182213 512758230 662332505 714963495 878610933 631579117 716928864 502193139 698877593 96152453 607724946 909028059 983734063 136240921 362120048 973965049 978276225 459652633 671212533 998909452 999799389 716213273 770233204 578695419 999427787 690275281 836293869 800720024 803869882 151634156 654746364 397388646 597465710 820807666 955562459 232330986 296683909 954273163 966644391 916136714 959025858 927286306 959458167 610415398 825799200 761823550 918182471 105759023 260149554 208755530 851164595 912208946 931644427 37266535 919555987 185794757 333919656 950560856 993606461 637591282 975573376 983651934 991698613 316175819 436064816 956150722 986385939 35866774 927646047 575680265 585391823 165202642 841832693 885695031 944369923 954088331 967989164 180459337 822860384 882255591 939759914 190507470 954546746 198984808 574147944 776480458 985143864 951306843 981188642 932088772 980821902 821643752 928488210 945257357 982045833 377428122 659698775 870867940 951479085 661769209 835298935 778359177 844526993 376037842 990040797 450507462 810283749 279087488 502404165 482119867 953768912 730990879 802219147 584847059 922237666 182063628 616307149 825624191 846989957 1 399280837 935698848 959387595 583707649 966675191 848772465 957091891 266565303 327853419 49274763 837471337 849937229 934038514 370348405 624066394 785345556 851548536 218575326 442207843 56738207 779327568 779744772 918360678 72748971 983174222 94504362 835597234 798102992 947488091 303453230 912188189 490230192 520194071 917265579 922826006 58752560 823756990 617264404 916936545 964755131 975937249 2663558 581804356 403274925 555127603 155266110 362556108 3056413 398402628 214162615 869342529 100057710 108032987 332658364 714356342 212102989 618670791 493250635 850266518 548999590 967704232 609569064 820498066 75184133 843770623 800118422 902223798 168710418 488614255 750083434 905470898 40387198 913877257 974039069 984770448 899918970 974186484 540939693 945905062 99258785 875704803 372772329 492939918 594047100 614149631 204502340 702718963 236833088 643299609 277091690 300994892 894216276 980238381 498858213 711481796 286232939 564776257 454880505 487647724 462537967 961839229 840557552 910196763 636174552 733420970 738756313 861365451 415301398 678941660 716939615 753805814 919386490 983147192 284778494 886643215 185307727 609436580 934012084 994242376 150568328 569799867 995614674 996168146 827334686 884537891 95285796 991908718 414590211 525004456 419284068 745882437 441108517 570499886 421077508 939574965 703983565 988277248 288728933 427902041 298523070 722064436 357692162 819981895 54687549 614526324 729955651 883501800 716029956 763473381 260341238 703490911 309857464 979023563 905325697 954515594 835829711 988369517 762206913 996370458 2587403 14075225 249196725 674839167 152917595 256331164 718316144 921465157 723532213 975812225 743958317 779322905 430668025 563120694 863217375 938268596 486932093 785306782 668567439 768846034 394181485 761825709 128138762 800060989 74109000 632374103 823238951 868020202 699103708 774291137 994768435 997034143 511302223 882090677 1 712183104 254623742 875322493 863001304 962212865 432070758 758973250 708884994 917349000 471917664 899442822 582350248 582979387 348388886 945342611 470867699 989397221 270110567 386831314 840065853 896323290 576886180 841049163 536777009 946073019 2967537 528128804 501313213 603130180 692032022 786786059 354446517 435496355 871073981 972206030 12274424 332599548 573805234 762039976 449230734 995778425 285117598 437539128 563920552 774499473 159763933 166001252 767762894 805471812 643538080 809928368 183703992 395871263 363834677 854248407 476402931 537179066 572941414 950793787 551174652 868387442 378165288 859654333 273324706 307653162 724946208 971576128 742873078 957591720 791767065 888443329 306214617 644735288 952125413 962482694 777090674 922175743 612345914 983222248 20154453 533894647 448084163 719426560 123332207 311767458 43033411 930324491 765643578 973084497 986051910 993934064 333864143 407270041 444720970 596234087 244412741 693662003 322936054 615456911 323171283 437860090 199832919 478791133 649006863 999654178 190517368 753059805 2527775 394779333 739026954 993466206 97922060 888008973 270408349 806620385 318540995 742257881 776676400 829968965 288769906 510983876 783246603 809722051 17584305 684579169 419509391 660033821 161848034 709269947 916205391 991510169 405383430 803030710 252969623 956461593 64350651 688368931 6547297 843259182 824193106 917251705 702129661 993828904 491958510 523210161 785091131 934298387 165495358 548610317 116783850 986590752 296982335 713743418 537665860 791891915 77760123 779749374 625204274 633716960 500203677 957682953 901634420 995045357 781376053 980511983 468264715 473447673 4998040 866455425 660203920 796649258 775842431 786738277 41838813 315402875 107313974 485509073 154813437 920914733 717801358 956080125 364069757 881036372 365076029 492684698 166415486 301640812 718975219 949542189 653378087 967633716 730129538 741527144 679653568 734609409 946145977 963918706 556655369 900005063 223320029 239289727 719907336 819931114 504815177 723198483 807435283 822794517 540995375 752166840 779343523 799613669 623815301 658689657 263326349 394603144 72691414 608483233 1 989500054 239189473 814645230 765280551 771445028 630967537 871209503 934963958 942056889 575007141 820540188 401559346 888447336 312279757 638218193 897108868 956931421 896407382 975615529 840912673 880881797 709088008 841806792 85658881 284241525 686465024 690044437 90796449 330128455 51954624 678736389 295966856 520979820 771226836 962423290 353441991 804677847 835997958 865588868 104212832 929550175 516469105 923043089 216499305 793418359 654121861 747603658 615414407 626427017 836812442 898897880 754524338 807434614 398736556 901963519 301207445 653329664 702291740 936613224 951602036 962223605 190912027 689820649 347349764 701138819 170777599 363366656 527135408 772300127 726756288 940585937 263903974 609395908 856121516 944392252 156942734 630907103 846779679 978171725 463060612 588035783 914334189 916071818 12064661 947973891 631923023 651090353 192671661 590065717 845991328 879962746 301203403 688367151 253822142 842689763 967358053 997583661 970366651 999743503 295552430 704986472 355956876 823421273 140786228 632663035 194552516 814821909 38572422 42814365 387418824 536927722 559440378 905995858 915503632 937141633 36157669 733602774 612491430 741415016 63197609 409336447 293883485 416959364 318854930 722758244 996046484 999924515 948322016 990464637 32260634 757464786 394880591 623316312 270932715 647368855 945233913 960363496 108079047 372145284 372848963 940669136 866261214 961391191 500022372 779403232 353557186 926625365 484122613 842916384 163259005 535272012 594978890 834350871 554316778 622504401 1 418986222 113915800 870643353 719733720 920500394 312528665 852569547 1 206957888 335696031 972017749 452260421 471000606 236452801 430008711 474494713 802428098 410805099 426474247 403297243 480856797 567881625 918370982 548666894 636964561 552962239 640023206 961223474 999565533 76671486 834100026 269952088 698411620 976619153 999897412 863264095 876672324 833717598 939785495 890891467 901854148 80728771 115315764 733105343 829452440 180146800 249700794 955393168 986576303 40308533 268486017 657664869 697818747 312958637 582289720 857764070 905167711 26653984 933351567 83140542 696001354 933196636 952556030 107405929 873691305 587455036 887474170 783129981 792169505 246954477 986393526 183593154 987698624 941975694 980190608 803130424 821846749 294131726 606733715 273837370 690210408 348658704 351389063 618864854 845966387 137900632 545660082 530710973 987570554 525962925 755290795 111882749 797960840 595249666 984090931 460111080 631943743 217540848 596616449 482505726 826800600 935033175 956945713 826550459 956375771 676577930 757411389 438926186 640932585 658042259 722610402 584121993 723775037 682689406 711444319 787407570 828165136 603574390 676563175 142955280 951783723 949413004 985150202 296368297 843694476 543632017 981251392 823181070 861040631 586490937 666336601 368686579 464241116 434659423 709878732 736134457 973435902 844940696 882301304 449909258 818639739 401487902 897607791 350434111 678844056 12103738 143440165 804784976 881226880 735668263 948880030 588266399 732035804 843146509 897587434 665983285 674356632 1 956152876 313715105 373574207 908638146 916449355 861957617 932030874 293074232 322220382 109249437 416663741 774919266 776965407 805551729 959628429 447448576 451291652 123144778 517520612 749100509 928511562 745472130 777469249 468766808 801578590 364633311 797107754 436549190 949685538 972042399 981009601 605666720 789599639 450906784 530015392 611679508 883347303 260330057 972746473 960648795 994313058 44724021 348805781 5290943 775117658 324864956 947252822 784656287 899180059 783003185 955572409 788706898 994952603 544542167 844199791 765281372 951147455 606360316 674833524 663517659 930644806 711771287 974473717 476265244 621216706 318672675 807754694 537349965 999210014 988793470 989947563 189024108 803871195 403606274 457002359 211719850 932090449 567420090 936939296 795801475 868893408 251091257 552366252 559704321 918811745 706100424 787389360 209360576 365347785 678311457 797486112 911517468 952839106 216750916 531805676 67161393 399031680 848041921 959107013 546882445 585203655 740099797 756486929 530788336 726502428 748430809 866913309 93143341 965805097 28064520 724285701 555803112 685182919 11719981 924740261 895790865 902978669 465596019 961551535 581576282 709550413 579144297 971948719 811684652 889947321 644563047 865931357 623534892 777105131 656064893 809094473 254077473 472099367 332336443 934847632 772044956 957668376 413667980 666475591 82759765 759467987 787161012 958975661 636049532 816704217 384856595 506258635 257956712 602005828 142779451 715913152 126172947 973998984 880369369 900456671 263656654 541775712 799222707 887214560 724630641 754159618 218012246 302223222 475479844 538833261 183849258 437714124 482396747 783338939 927440769 950817796 106035320 513647349 723039149 857412138 142850198 534182632 145032663 316365521 818231295 862259828 252524038 660791485 872094570 998399568 343972795 582928494 514993126 823697554 468114514 902159496 104182050 766647883 971220103 988994088 326127544 390553990 966250338 987685747 755754477 821964419 233320 107481034 547672400 554738491 386637460 917261621 794833196 896658109 463474409 937098133 974923411 978915266 485675491 882692664 90811241 465710267 943382555 998981278 100623758 439157309 222196151 564057668 917357888 917429437 528540172 621830518 949107623 989139165 370893994 593282090 491463644 828879816 926709820 995452429 144755343 872236796 664857663 694015735 174086687 531239129 153079994 754731471 437882855 656922066 95217820 142728685 694988223 861793547 808251380 848143157 674597602 841986795 852737820 893008411 178413718 233171083 922471910 951648312 898836773 990829655 174380248 208792573 384675169 554025743 14173104 835933507 29320940 418624463 340320923 816559748 992097040 992305485 407488622 788611451 230793825 744059936 220187842 863666004 159218862 358778734 668826854 952407298 619541220 831819626 494071233 557990977 847514914 941675383 128173771 199124996 146854900 188591320 44628002 768964725 61426756 633370437 574648541 824603844 885037592 910418419 87394236 713888786 331412194 617574546 135272013 374795111 698783575 934017779 407883082 885303179 413959132 960059147 489038594 942005412 755360437 923201403 766160353 901235361 443515517 764955721 154912450 396053268 359318660 373487222 339270157 719753985 623032130 857070322 361573892 566255677 9905105 342972247 890116556 951361063 529163249 603995379 363553156 456736337 550918731 934190267 606990260 732091214 1 638112833 554879046 764090599 734460957 751889645 743467343 972349137 794324390 798260159 353377713 553209982 314707754 924036751 866712314 953858958 262997044 791136770 606675967 933797359 362976024 675191085 118922436 492860578 672166009 717950136 909369740 926096535 357836912 959289765 986996384 997543438 476624072 484017780 703077274 971922377 334680093 820593209 782630673 939945497 661878092 815842191 641535898 845594216 921507511 932812205 957248368 967469025 25174844 367070540 894813932 899393682 693071349 716274878 654181895 837428015 944197772 997728277 591095751 650452180 853211814 965199662 104100939 253557327 155331791 579561369 198833872 618552319 160966790 819480918 93724493 448460456 608925171 832270802 849620766 868789896 80683209 921601310 584931654 661586819 162189435 664119442 410637894 504905572 447990045 753126126 476378070 940871914 387337208 951678358 964074347 978869942 242734595 673607192 837027657 918842348 437633817 738434232 131526859 200155542 169419086 215012671 179302257 362191133 126221558 879272094 611934959 686147951 987260435 994118370 660313814 704687047 452283334 860779595 400487502 779884571 984816704 994747573 929357086 956255755 96587684 366566583 263694437 320334687 803728065 849418733 927391242 970606892 412640124 978401795 27443905 663876960 823511120 983185775 726770619 851358542 374461269 433131048 697398833 721344361 972265307 978963115 588214391 741419347 247575710 964101425 459860696 669371636 77553494 805968261 19903547 610563618 36747275 78338902 763575041 835053025 375720336 420358780 929836813 967990047 114162526 941023703 484665642 618707556 795158195 811501547 810111131 902846676 836112235 922102399 318137476 848832191 644577125 787168588 943623106 996652948 720405883 821041322 429211187 763804055 831670976 926235237 531773094 556802650 878191965 936441904 136207968 913045905 673109104 862869306 953528909 958159411 384687883 418158756 266109062 290294479 441654810 572125813 558226914 811109241 189417148 699919036 699510137 977069528 187526885 667608846 601506737 747879372 402298563 603310828 273732334 971995987 982726820 987081289 283630797 640560754 725316131 822595703 704775093 964371338 396528501 436128032 361093611 399040306 245628120 777153149 522045133 763052778 807552282 828456634 344108604 911531361 575408305 704845009 910478743 943774035 372705440 651595492 314353033 368649124 59484949 325836940 24675679 392341779 996869312 997525949 281089690 299302208 179044991 318150481 216446145 587519783 310765201 908043917 674252691 745985015 442872065 956733085 117804841 643125662 726399171 950748354 303540781 929359749 271859129 527026985 835617006 942327196 692793981 713463855 766447026 937638809 368279309 737544594 125282115 687265512 518359470 592394168 998513968 998898474 802188210 988350456 504718161 756404263 574634506 645469410 47785062 231215981 670693099 897581308 754047939 996856044 110270580 510099413 338979494 545901412 514310782 934094818 507122129 774082516 345105023 963281255 947647237 961138776 800825864 849523420 871974714 907182847 511859906 978124348 620014672 747057642 917255235 965654032 115015564 815414187 344145303 680267276 295707588 454816206 847377657 941090352 754949761 792867641 444162746 860343961 172963914 798385030 598058419 929156470 329533241 972274324 527813699 901958947 964611867 978216370 765720593 947879396 932776467 955887808 265941171 672770420 707664104 781875328 756826351 971372275 164088929 833188082 873008739 920375497 586045412 718196153 417855002 539529725 907147139 958008758 403636853 452513424 482755031 815009338 36058687 128465876 742285194 826501849 882955844 980831382 5336394 965858643 308384248 315012724 598715968 886183795 319066348 741963869 591134575 763562459 601141830 842702646 606165047 827319132 59474191 245623040 85465449 508048081 620828804 839002472 790303397 976338065 856702600 989703359 351196402 425058593 33710687 72254554 555609522 610111645 672091830 709221627 191801554 391322755 601494673 856438171 546874614 902245011 4835674 12607450 663225422 783914501 734962727 763021889 244195643 986252928 971357890 985612238 855686610 878543775 534788573 925938442 619082358 707360621 380233332 921784417 129385383 519626531 462070736 678686880 377253617 829073020 162994401 971489062 202053462 782335022 658862208 971644399 579580965 691726204 140411263 571305037 156149637 263656705 332323148 609548465 192604232 966778098 987875825 999824804 780023805 926687033 621001966 824797124 340245880 523901910 629591858 929407005 75057626 252291253 937597592 961211648 982083506 996144081 684110315 701720170 532873376 875292953 266573534 513753937 343303742 351299452 383008902 514099752 458948678 660753427 576622424 700710792 331463072 973948374 3396752 672266660 741351252 980262982 309731135 478196051 142772167 338659965 403566198 509721931 991268450 991553044 596920231 818476840 216477929 322940029 354540146 496232815 682570654 784345764 83133671 463199773 437416762 579861901 234576969 715761719 78638896 726015985 133604549 426295906 923262263 953516568 103088917 612081937 168894988 814437948 748207024 950126496 58974362 995619859 257883166 812550269 413419369 637081296 503115771 703064268 515260694 842533966 720311191 772821351 122620002 919479856 734201726 866412856 340756983 481200515 400834347 584094702 463033450 691548075 817179351 982673685 181954931 640016581 247983732 804745392 686603941 791530947 121709732 510120100 402493873 603431443 398438168 421985732 874021385 930515757 210667994 570575318 950757327 983949935 624664552 721115804 472159857 873570231 545795763 644911839 163955409 308002373 604123540 807868671 353655064 514231622 7550085 85844295 176854908 290405672 200806072 837094225 967986747 981319118 3026839 377791875 733576426 768366449 619915220 808962097 264426907 783083887 55597654 660463061 125116241 367185532 450651464 477791927 845758452 921142511 972797957 990723051 465864693 919970314 271862343 782169015 700417259 957704927 163216118 657168707 417353719 967592512 982878489 994818175 173337379 882632617 823863088 968756632 61626176 888298493 830378043 912438804 316931339 875030087 371399959 702286447 575713411 670407924 704405483 988275735 124312008 124384666 426734017 515729444 290620718 463443275 637746682 913191004 299979601 669999802 999423841 999883861 426992072 998687478 792952584 990587712 855988535 956424747 227056164 962822329 74485161 802255675 645752435 951608329 943930438 961902260 878469937 972608805 528160527 741727173 951046523 976047345 349450426 918201107 512314862 826975169 724146666 897908664 377391316 998521369 226756941 821717518 794007718 982228630 525797435 711545242 549331791 597404581 947021862 952568243 314129073 465574732 241869663 401863426 761377054 769902662 739561582 818873586 267807587 768118643 608300412 636657686 334390479 548577428 579256537 867029943 107198984 812576156 238360175 542244263 443597532 449472694 256705558 417345858 377062738 909647253 276067589 360572398 8028339 336013267 370786100 483681431 582221981 616269161 516509740 621368781 906676219 935480999 227944396 471012207 380450189 581131552 293918832 909536287 624127862 861635220 30917435 837565587 286009422 654771156 819400915 910707129 399007450 642359137 493010765 568470264 944770028 977808892 510886876 967557410 267121018 707349881 271963899 591961947 756654378 885712758 297219402 439001503 217373281 418396076 485253071 489476310 1 981096269 245715955 900261675 790769144 947699505 561437987 681455573 286033167 616073053 376400401 566447581 159249118 594076966 708824107 792205255 256745833 863966652 69684753 107301998 353643024 813913972 87648186 525997601 917946304 978068277 31191244 361389198 47408110 684517671 990451329 994957080 296341030 904133241 634087139 769160872 605135541 746276151 418174612 902353728 171095827 202287686 302137231 505011760 100208018 116502651 303003256 333174081 272616272 854423077 585970574 785660266 874834560 974466582 957082415 980970899 172656566 872992529 228491017 335208461 86704404 622344233 423336777 978635652 884663613 891608612 453266221 675949639 626076934 751157940 905885112 982510957 132655212 295633947 810489204 992494183 723779776 821420576 978321281 993115541 739437875 920185985 680311222 929465364 256335980 764645671 364200232 494019942 198575176 483511320 259761536 673433945 448622049 713799855 902918753 988263399 686866267 752562271 581568775 669538903 575924615 615609264 18163217 263799481 324432742 549929734 311339194 881758436 476495701 704118951 80305592 902717133 180448421 946823494 228112942 534748358 9462036 205502966 135528580 621113675 342284936 458117227 1 505751041 421356344 890571170 994019285 997689202 247947993 480439342 853943702 970190914 887837617 918736285 803603611 933566640 508004757 704027915 622212727 689051744 423176167 979889375 370910876 796933029 741041200 978214000 224019876 543180125 531551809 922379386 358245148 664978943 821022305 998436313 1 291732824 68249130 432623952 288616783 507681946 924873228 951603902 498497468 977798890 813027708 937039539 275682644 563595898 24949034 243600165 317655255 985615298 481811862 623607302 683998824 961757983 433756497 605752115 241580407 987103582 209373078 876984286 169092048 358440075 100985236 546172050 667486043 957889970 857042606 893103440 551182647 660766795 203270452 920867407 140748013 933515945 745414294 785041551 521563861 549608209 814356001 886650998 792407623 886323855 245721365 599361600 180381318 221215383 400627753 471999050 94224530 306850975 13315521 848145287 53038927 829302896 656010902 976136907 286963319 586792899 885835327 992676670 113413871 655365791 932475629 939281356 871144270 888961567 800539580 801517014 668716788 765994740 685956103 847828131 858851148 863612875 438333685 919531889 356236129 830833160 125188949 895709218 563954053 585463998 592486121 744251640 504225868 646730177 11192343 902931101 727305103 915834385 237989450 654267484 283186709 986758624 356095218 411512797 635403154 994359158 339036642 734117940 333075305 477613263 410256776 694030926 777572464 831175074 797285828 865783429 506914623 847699812 705649501 884133746 470829239 770911882 977398030 994021623 210398801 886619988 371973372 907034118 911858542 984591196 3571760 317096165 864333958 877547944 139453409 953896908 729651267 923042881 174568624 647597796 862618165 867724482 79950917 862923651 827272664 879200265 943225110 989247809 805714913 989982175 40895147 802651008 509310392 651579911 819675765 943886867 81137162 928810093 222056364 919431259 568800520 620922369 690636174 740305570 201665628 700660583 959494644 973833490 420005980 995997114 624774129 751634836 890954897 959424100 577216632 704319615 627158765 970022203 465908485 811728841 769992864 847407992 485342671 696527099 96274909 308863393 515693708 918328129 771350967 876134955 947404061 950885826 222687922 407289574 392259194 578846893 998403242 999390583 715234003 786243754 563196800 961349623 199038254 327898452 596825860 649573616 872215222 995932446 435994148 545619895 50661502 939403987 386434360 797200377 518797745 679291518 867233001 960762647 800337712 898064411 968444661 969579521 352500652 976790622 815874328 841322624 639625397 999362762 893702691 948065635 272382050 397623702 345186680 610292768 574387142 698498142 64030650 303658116 547481538 772016267 207809949 274558037 533516813 875186098 185796734 254004782 808244017 881264884 177669441 897953147 667714338 731316567 676916442 981574775 88158530 579233182 589226330 647441334 49249633 571122779 950516313 984895069 873498510 874376733 903265615 979643137 271878625 402149299 625043022 696315839 646680807 711966754 715628321 987375842 628419759 637654553 486268797 997930720 24340621 702196858 297380346 617872791 595909407 910852407 851601137 934417838 450189848 481634363 820478427 837714507 170480340 659986606 579252870 998888639 283561255 748034019 785856968 894470993 692016694 712333719 384877625 699673308 260730760 946083005 256716992 637249082 155767004 185027637 41476063 953875883 608634204 844131379 247948418 845426137 754433204 791278879 542056950 749012096 341457383 827175390 524181205 615120350 111724017 997232412 155136963 677552957 366352022 389289499 750544048 817959632 307096200 638936661 13500261 597615363 372068936 674192361 172023054 376120008 645710031 663989597 875904729 892375833 294577177 984291494 568290048 904207231 975643654 992163607 160340073 285128746 682582690 929454666 948590502 989572502 291129275 970455936 741123777 816620489 972003089 993691172 870490711 953232064 403468551 664845009 265504691 855028244 81059577 786607680 253085756 745855476 817158756 977045816 977560004 988168187 557577865 585519918 952142983 955753648 320850702 933433414 506115451 795986157 573051446 772900426 109414878 867819451 601900845 661507799 420721102 804170999 74281417 495677756 116388326 393117785 796373101 826934334 537761010 952189133 337420216 948316502 237315016 295112631 756955460 787876075 242900511 454335761 814760896 975199108 159213466 238014314 981410450 994473271 153639234 446537238 162207204 377570396 656342593 809818258 993962086 999838334 642123674 743869108 99735913 683402981 47537683 288845082 10653572 718315077 318210714 959380136 749759008 946581322 405548055 536464940 607687550 891140172 40797131 779076233 446202313 994161007 113409249 625796572 768646191 967625161 822565682 900084043 842079639 853676138 376599840 512001279 845750402 900020253 298435013 853907288 340630827 997010051 711738737 816904799 7536741 845395361 235909474 349538679 951281296 988690897 821344059 997107055 39884693 580499635 849743612 942342211 421717410 609794904 575076207 968917208 732847791 893211253 830235405 853811619 75299826 455910839 196793503 455336232 593848608 789901608 181114940 388943645 934835726 964780038 834970367 940968985 35366428 806728301 597686435 942256930 174090824 380430977 150214628 775330885 250143840 265773694 885172769 965756816 894400058 982202832 8175143 988755873 499792319 940792863 237781210 399836511 35965481 880752456 327907546 532781557 750211878 895414111 59376811 397286476 722592395 774361675 68701831 149390514 855664439 880312663 1 693156221 927039138 997985893 620888260 999994515 490756835 890345726 191142154 891182681 959853573 977441683 556156853 993327372 879549434 921435869 394271126 828346765 346515394 579531724 443181196 921176182 256972882 473151576 210966443 331889764 437067937 713275310 679038636 832831156 540021432 638135998 131005722 957570153 748651533 924360770 612945011 716002568 981026690 986778355 279137914 960442787 496331458 747076098 502464752 888881276 512211460 701324664 995256406 996256415 324819237 641426941 370817968 964476406 996757983 998681431 1 865048236 187863459 402309905 37385362 506580792 988928814 992917951 329468700 446364420 966596259 974163651 697866086 701903466 958044487 983738675 647148673 876785226 921004678 938072204 894717823 997133335 142438551 560957556 787721820 959931351 309240281 783698000 785424118 882758683 584746564 710136612 409066849 788515445 348958811 683552163 45133635 381151599 398948733 813443842 72068980 298468160 514677965 582334269 621011340 901716515 39868392 910707795 980857266 997636801 465448459 478811886 787848668 911071097 512236272 801585896 177752563 479891531 85519998 821571694 76715916 94865450 809776649 941628268 67152992 299486848 584928034 864559842 89497420 242062616 924953023 931972122 1 786069356 632030477 832576041 593046161 788208259 32025206 495421676 756823547 882702433 566069664 856705015 901925053 976466512 229634274 880255963 405922204 818010437 978400081 981609252 666968179 830766439 146845807 910136534 771937751 954770201 806175077 815466477 639925229 887197734 376864680 460407591 480384220 899945216 670490725 699492503 219956238 394656951 969320572 994942993 632669647 651228950 43864742 523578349 820817441 869536892 3955642 894509229 40173504 796396194 164940215 237922977 721757499 773610666 948013754 949985870 552268251 785357073 386816477 423194087 1 856401705 781659737 886365635 930739045 950190978 368128880 549951519 629107714 635706627 184995353 370826146 969741845 997554895 701371487 951720784 367804677 911798163 105414210 916329200 327780865 902207532 298766317 828046169 555162350 965639373 126735648 726932643 459131974 803998962 286780777 537204838 772763487 896720989 626152929 799538744 321428299 421238037 795978523 897225615 611767974 881507935 811506275 959102639 823755545 943275557 86409121 915259282 966798852 978527181 970952044 988060038 684511760 875402469 364782979 604246770 135724535 638670063 821035312 981765287 610256668 721689669 986439440 986996816 713052981 808531171 594195915 670353085 357639344 375053401 257409153 721096150 586042308 937016049 320219818 902674364 902319398 986004980 227286028 971377559 531407811 801373847 587432196 785420135 271721286 732446921 1 176107722 92408280 438769901 447509731 659235949 998358312 998611216 239701215 715515050 396715043 601723940 181656774 582853907 62197867 97194469 189728197 341419952 392618500 819425783 89509024 704813152 559982229 954046644 961765073 996986429 201960076 679178687 501022988 629540611 646922802 702838118 239013189 669318269 225634479 753391787 339380460 826901267 247037365 344103657 713436714 801921790 986099566 988841615 574655331 961662550 886768506 947607659 76104705 220742322 56991830 513229301 37858589 365673895 381898799 502866648 230907438 862446812 577227676 676946145 785690921 813978268 807234841 965938073 795261826 932236420 912414610 973687769 217542800 409588564 202214925 579240113 268016119 864172631 730061860 748928109 651015007 820155449 689923405 892872141 327940885 449637300 895669862 931132569 278917532 776991560