2286 3818 979946209 337613631 312894294 283023717 568768696 187097939 177824928 18519587 783491816 851005098 522161682 654406814 246781391 20704698 977506136 138958260 818155964 823407709 469179100 42244651 93280108 589087497 156857136 619193714 988193892 274171796 520188783 181949405 817169852 278019642 135040197 816379108 7729394 971597543 396768042 259185668 90154840 306518644 903378687 650079680 867265066 74394487 376423287 611726031 858832581 854343873 732108567 517126682 330668681 823116791 785247981 927479221 549093968 630319115 102614736 726675486 131562350 706781582 871245087 850063777 988572481 661490484 857415743 251922738 91903602 947207932 526559064 212458911 304529713 675048754 906816708 204787133 310932999 168767820 988540486 260339632 459137147 728378255 43613770 231939902 354239675 405108537 197403038 783255319 902409637 9575687 730291128 706262205 22070276 465245648 493026618 107924761 546598051 718896189 280491539 921009146 658286248 237043019 241436745 575218423 211250939 698106006 508556161 340528719 722221399 330564026 650682057 334862524 834370624 274742032 207895817 703221095 588600104 384464215 80624862 202575243 135170233 428927283 87185992 793830832 468108056 144755122 492660631 357549175 867890967 345672807 903270627 703214205 195518307 565652221 795736172 480707935 607072668 697173126 658040077 66380332 691891306 319698876 17272740 183082971 381171780 372234464 634615890 682895758 498980069 590994869 129732795 478488049 88201719 119305246 540066904 87644549 669118630 360681632 809229737 913276224 367421410 797662238 696231765 718149349 809340961 309866575 997785617 213352377 777739009 74033720 148559941 290005425 858196657 940501255 686857880 714437582 3654476 962511631 908517158 76680374 766832837 460728895 468168300 750813979 327892105 724546621 760721753 165020531 284640650 496674521 231056018 713709218 495316273 155091602 180157735 956169948 238517056 613567947 912766067 849080686 575858737 315130165 427492221 304561602 922670581 314606259 54125256 359054061 283865048 881198408 565531312 842224430 604835323 818605518 305802857 884597580 606979018 906698191 643184603 102454239 885769062 614434364 378721004 853506083 405293538 984721411 100407731 25095194 652342057 37628689 78594008 961387025 765589712 838591304 370946716 405825449 743244931 952571933 869818749 401780423 365221612 508802602 260693683 132223552 416201284 647220613 817609736 350295705 290975750 42663670 305080684 168909904 835511659 344473173 949307310 566730854 89236608 919851468 706043483 635098553 669313861 804131611 321601507 494509873 645818038 272378677 61139419 957172011 12002221 51945388 433880377 644562344 241158569 581135080 703913953 880328494 506534143 632636271 282067700 667496122 681688992 958780302 910632496 496312308 510157707 606704188 616901368 273208911 561773497 500101209 307093324 40704050 42300001 923893849 955006204 41202076 858267226 852100844 799181474 508235352 52255490 98916366 6569166 831580859 406221686 766975085 170027091 639251552 722003527 22219028 605547447 674088677 124554885 725569487 704146157 849050264 223177495 951569944 210930854 276972502 506554600 980961010 35413179 375987689 254626658 65244220 108365948 994041620 801375272 301413255 979529924 323741370 766054564 22033317 704831277 579332935 684878270 556058389 719577593 783124716 669624178 273120788 664744894 634463231 549110308 931195228 524444309 698637008 757616100 321226562 917001095 562330027 567582112 327120466 206592069 293820610 166772329 282774814 105907769 419931305 28988564 243706374 188614533 421874772 419171831 708915401 372764360 593265014 77984238 360936493 940945548 451596825 146821484 936929789 287475265 235396492 286023181 994524941 569916983 40266517 48679578 113174058 824569860 50960313 497745739 247257170 137615644 658809917 604797132 210205531 854129264 706684662 104766596 274882379 693341733 972663264 870535373 202865755 632527684 393233433 883834064 965693193 926140794 437035602 786051867 945286818 890949542 807238750 198134392 889701363 886836941 427596603 680959631 872407465 249388948 294019589 758559174 665907614 750938899 88062641 160063258 379677566 211033093 230996104 508783052 177674407 818102941 479519676 323561885 31133405 94308535 528509219 879726734 615020524 709120312 585418783 394033936 49514461 86521206 869266589 313485024 547207880 660889371 833821685 242636875 752878313 855816758 995916709 860468761 455961158 954160598 13378279 488352768 149631962 95771561 980651372 749910469 465206117 599417521 170634837 219938969 935863106 207860872 392426604 900924126 16484934 612136019 263073765 595547359 36023297 314783305 445891463 100967923 205494815 417372166 444213107 21494282 867262975 778699581 778402896 753046914 626465325 528886976 77267042 886551457 242042960 9008406 82019967 434666536 701793603 188263369 341814538 800560884 965597216 853143033 886678773 936262922 345092897 960663586 658008941 942364396 705830258 253314372 370231287 514581399 645900411 115626864 29147531 147747088 866006006 502083999 818694602 594302937 373534227 420444870 817975124 260244314 178145348 515927088 928890222 125981463 360022833 369743395 239576626 556961486 28751513 344020660 160817286 135371164 774664092 108850993 893223066 762724533 945937866 244010082 405517503 74535228 881620634 776244716 643442329 757534235 121040224 185909150 799834598 719825342 10554423 613202775 66088549 536439424 437175051 488210041 832188913 135898879 173920942 344622611 179782542 976049156 582710403 377237150 968471560 962615613 740436587 85214289 476489224 305495071 46923001 760694171 310255198 347943206 881495019 579405365 48960546 299107933 905643450 567223271 190106249 238003171 405075683 847950911 278239859 52846610 901838694 339041102 667133040 636525304 354369220 481684949 756115136 152519733 773746086 233962139 508844207 195902188 915423670 344211959 255832404 333945833 401721420 976509666 36795159 571487670 38712931 560567656 884417704 882974558 632739646 516447778 535098150 48549187 996737628 302122437 939623457 777630208 151451068 733230333 580171736 328739984 197081912 155075250 914603821 881396156 114797884 279504534 598923298 423983955 544538014 89752817 998345348 781264237 414684038 145266394 530035525 908127191 500952488 114815845 753810773 604936631 816585449 881594136 209849508 456834577 179168348 218159377 655251826 862343841 410123569 109987247 261606677 126859590 427790080 545402962 56176011 77398878 694165420 958286076 232639730 21687235 701574006 871765018 906730020 636151435 254449717 886731329 323972872 25395188 137630904 175158195 856997312 707273045 505852586 204420999 183471077 858289867 120641143 176368819 333378819 47717319 541824168 881292098 941995247 854528431 827656030 911635579 432878255 271760682 414923920 156972723 308555010 639393794 493529303 570511887 479404044 770760167 161331386 187999933 320512040 733371383 19917611 626973164 37356396 451395069 402090249 178796556 754204369 366645221 116783295 555223358 719327406 581604386 556702039 770442211 695084518 126118503 912388103 375238031 319632677 57627150 673996863 417396332 25225002 860319761 737203341 750924321 411059084 110759344 243587206 32129089 801672366 154575879 752441538 32093660 643126956 483953055 841880592 369642637 629128531 482049968 488525963 70579875 654446028 242734210 258111009 781139030 892093670 119293352 840729640 712649120 624745390 780787110 785839748 481530910 756804419 263096785 516751170 594184454 723942659 672696041 101178363 898730540 356896541 325194822 428074174 966545529 669776060 130237164 738785607 403609868 157523436 579673873 89786830 940774117 968284284 86733935 676146688 726316671 745129339 959539294 585315729 278510162 962977260 708249718 463227795 32203539 423262114 83115952 958000867 702801971 263693385 107754023 42932266 403080157 555812062 796573451 216474562 371842986 957315293 988569768 573702178 991153864 581431652 25570690 460270479 634915491 437873405 251332558 307260323 661772189 746570707 448358046 966889768 794976482 926813873 191774862 610293190 83819639 756143632 79096113 566965481 658885951 161558824 460846540 234217014 9026506 3533690 599136947 751165007 310178486 409329169 818670682 618506143 440450832 7500335 451398093 296112999 374306872 590639752 98590955 920421804 123305060 551302064 921228762 67516510 110214746 957820724 960140865 865131124 602957468 857124789 761038952 13421471 970875212 312709514 584214679 112556565 293026023 392980816 862424649 913303382 696905649 892728546 382314019 835601402 187796579 977504233 93113508 605868646 937728547 656780784 765083175 108842785 316694862 170442714 547539553 427506991 755310335 903428571 778731491 505237522 957634899 431200687 229537715 551815055 122185987 81394605 159809441 363065589 714230092 493925688 859607857 813873902 302325669 560607092 418028857 150186885 494231723 678953711 856559818 886950800 760766198 766236453 638871556 579381864 452195032 559978017 328020373 355340873 42679219 959574948 511186839 51171298 2868662 582628895 710783405 623435680 949304129 723529053 481229494 33062020 869786292 129279729 686020963 75546122 731009017 815206635 519675543 192910789 75367602 902626226 738451583 866224350 848319152 606705287 483433946 206801284 461721838 481323999 299440425 199108036 43643237 670283673 67640475 894900878 215303363 28120272 709771245 641364188 591385917 274496336 77385792 344946360 549547314 304449345 172950893 418921491 388333457 153344444 274851146 903661686 920552091 236193904 646718342 522251762 733888453 514953428 799319394 363774860 246077475 8875805 34135140 640138492 424916193 738622284 846790434 3283316 692984428 820575552 782647748 640638407 38145936 629856778 877054430 730482002 873911238 928398299 439469897 899315832 61763999 192747842 947857966 631131291 400114624 786562004 429278814 386915583 104758171 912316310 249451134 661371119 647386969 255811602 31412767 566985634 560511995 251749296 708020789 255383492 663879224 387610414 414783431 438331974 223726011 119359937 539694153 819289752 969240594 984543272 730880731 727202756 749445151 672152891 605047337 695105264 263487235 170552523 476014807 810459042 944643461 779610489 402662064 36576036 539213577 704526230 649599200 466450131 490402678 790147852 46324314 328605243 695853329 260869374 808002169 625609347 581949691 110899316 148659926 504294051 485904526 147133942 551055175 216551176 713301604 330440814 662793999 195649608 890932185 103922413 633383984 235785292 973787748 893621952 960926493 608699453 90828322 285214144 365110599 35019335 96021932 702456020 836789907 711981111 653643343 369663046 991251960 354235457 234183380 278343541 5598364 802677933 849044456 275727869 787817044 271311689 387086662 79218475 751438716 496540438 896884965 276269334 683996808 372369641 927503468 300197278 107822656 382650765 803413726 529509613 445289867 394832583 871573006 256146905 153074091 715606872 726421186 401504841 616042303 244085113 22464913 881961230 289171865 190513456 68798943 672819071 754202086 489705988 136626667 356677195 535548275 984066006 513399539 634759525 694323218 670593591 757121399 683526631 866425060 318489216 904640546 519541579 410984152 642513206 529695021 624807450 858563367 472351521 537515289 79967026 717485838 684482931 617005365 942243004 772138510 94554034 106221770 322789120 939890303 546815770 252573057 697208520 892558909 719485202 129108137 386985091 990412191 469492586 545832708 401781188 66834796 762830786 933128770 615605417 224587804 743305251 919206501 497296224 167916690 833987800 544809000 313112676 656696060 723974625 359396519 480792585 390071554 321315560 692088289 254181930 830707016 961025891 421834595 799527499 524247588 40491243 27003367 417165646 404193028 731350973 373152384 660489300 633760341 934570330 34378290 298772226 400006913 175391195 385682589 369003725 353815080 494435394 314296847 733714947 397979604 646044088 75929094 111819754 640191999 554412672 8553525 56296605 401358004 817567832 83013176 408434865 195455654 121547649 141052222 828595380 185273856 177106469 316542161 838282181 936198702 909175853 542460588 891439149 69679223 719266823 346232054 590682582 787478862 932635345 78700851 845261747 26487110 707401593 267694457 880493440 212688377 698077597 715025901 692191995 377257882 592136823 29151629 968215136 952056525 73953777 717941756 354926133 434974211 329648269 910504993 667275527 500918008 30502942 833179991 677811481 823651161 840264540 315820453 86782700 757006329 9634922 403621114 251444618 691670058 443676235 415459075 479222539 581897354 999368932 549057623 394426796 433077015 977400858 467360266 498050096 353349647 248246215 872708980 934494578 359114548 479777019 889856937 193639147 706202865 350209831 18348935 452128815 136364210 257987882 769678536 702805639 73489039 669927762 163834047 68749177 618330169 481482236 819272131 909701322 414061185 696781192 576467443 421346556 174137261 240654432 697497086 47612128 530338796 823934527 928912252 500494541 833442886 485582116 465560964 764120088 925828028 15175084 58100860 864770324 358157262 49091207 91160632 829540021 626743806 780759271 924008124 894847506 377651217 649818907 577810630 595182085 57992802 950847938 560184611 45040987 755328645 848881378 362839731 926096944 836379118 92582492 224864070 919083690 143733436 98939883 246564596 120380612 924899258 823227256 793718073 498144165 652496913 623389679 393017563 603821487 920807224 473657111 209737863 584309562 645008744 286785619 939493775 418935049 522926097 573818698 504036772 42486476 662265931 594253053 883626378 59494448 8944050 355977656 986839984 840048167 155888648 180722442 234364020 379408017 669890354 724961501 379328210 485877716 42949020 899234909 624676360 103022897 532603182 113409782 914320139 7838089 417048452 696555113 193253058 389635699 356686008 62044800 168743651 887792887 454328473 221831247 15541628 973327375 81002945 838434619 481143012 679957012 835158621 939563692 584053129 314996420 175865309 814036349 819434739 67651561 485134712 514906751 447472288 554973244 184873282 553400452 101801256 942977255 134077584 895960404 265305115 664148612 741299257 182993332 205904476 418191218 120523108 471381178 486418 465424962 978884961 746050741 60432892 538318946 756563802 788186232 475344940 39862451 93789750 767163435 234131235 32484674 420438476 551395603 321763742 53047591 543643332 290798208 603881060 804341199 873381879 860034149 748394038 88467887 876414546 38178812 893969943 429398532 996631581 852145116 864522386 914094499 13503920 392116659 807946753 3830375 168911621 973361354 588688487 948799698 418879991 916534232 517217939 464804127 201521613 448123066 444067560 637744361 130529385 377845680 285248362 732309048 840019584 48273434 223386025 604793225 178717991 687395691 311895151 486118228 237920656 32169794 730016597 344453298 232815961 11111596 442081039 694465659 559543029 921707454 210099663 289726550 469241037 380210845 369863483 649376892 4190303 610184043 640062805 426544932 690089739 926122720 895193384 662195300 28257367 319558146 587558683 437157465 797769774 528360091 487900685 121424007 956084798 580891415 186685563 759166334 708990362 814518706 762930335 835463284 831056527 29824806 726804971 600516441 729629892 289900651 226318471 83430054 722797796 202632035 302090441 143116401 319521865 386200055 708682377 507415222 72412066 491146241 47979022 979025008 153477894 404442454 625348858 567185494 240223714 527149487 391029455 725999453 98682950 654379938 140068609 924819131 190832982 435277171 966470215 245503656 538020868 960988740 423307387 143566444 354974813 798244436 754540960 887092373 547273279 750259733 307037615 973706359 844107283 993407943 801328769 457248189 348291674 620595566 461793172 730320160 905993613 254397598 868116496 704276688 453666743 316817560 795084924 254555503 25144185 928499508 317546934 155140903 502556473 198648832 908873392 167345062 401320245 768099377 792466108 71659048 352116989 521363895 691752152 624797993 760698975 906486551 379661644 364577998 131315862 486519808 935363541 702816727 728315286 289392659 503713607 443193498 480834364 371899275 954678091 456337308 916964943 944809627 361677417 407125131 340259024 656072677 667430298 92069672 350217376 723560877 37741481 515476988 143651534 508972357 433681282 385780324 369365876 623324804 11267802 527925773 858658408 115288064 267940917 781837946 669139680 585833163 262970685 87579211 809173971 921239630 272455918 520535993 118511763 212429541 180552192 897636884 467255069 398658850 185999479 114603459 487720008 853674817 169130231 272178787 629031311 632618030 48203275 915598263 125257243 24430829 684100606 879671885 657867677 951291783 424369031 639492586 374840846 589124392 765079241 22055221 343367236 542434091 607686944 938832106 857028268 536418305 643442593 590481239 171773480 923587660 926885447 179589169 636790049 682877800 316149956 996787247 572015937 774027989 869834503 239752980 183374714 37533193 409747846 803820134 17168263 74022514 764698074 215329619 107342948 787863943 445199898 293426583 988450806 710547975 733029643 214082700 286485162 888996511 122338214 328515782 277919613 114262807 290508397 731561723 765224090 163487670 808121532 575680304 454994526 383431999 876816768 605647122 956818070 878585389 982410262 528085919 565723626 451047823 243258403 420083623 635250927 958407985 960564580 909212098 660862844 342153268 843814689 191026887 284030279 502785003 219456467 83075929 986325086 987599496 566323258 550927389 685452198 690913943 451808797 700300306 809936526 321330614 266388093 134285955 384350820 325792815 503161694 208570961 314256978 40877232 986262761 547931427 443475418 916459978 380645883 702920631 725985955 936442135 875835115 152178643 868117963 206636367 714332335 902592727 786334378 274558129 39026810 940593729 760497608 158374443 267989413 562892985 930001372 78104637 984780372 422240504 453886118 148144114 777528902 935488307 626535467 535213779 345603248 628470580 357030168 510594788 483391990 385439170 431406504 599421704 505714542 583003720 91335687 756499591 985943338 309787440 549301659 942678197 77525159 514361064 939166638 945914776 725523169 357498030 612585022 713490674 687527653 813861342 230018320 207475164 164606834 725162917 215681440 299719236 406661574 356176856 50084119 380027924 333187417 78710254 15900301 780229488 536361645 904984745 861280711 153477347 890894117 55353560 965621158 490247574 598495390 906657878 978930235 399394916 190969303 312567831 711773583 517209820 237403460 775378086 786339635 17109049 250943985 703147904 127806436 498471851 163356615 44083023 33959102 753659770 119760807 318027201 765628045 103311754 352007188 809374736 80561670 527364078 134901282 752803982 720857691 962779074 953295428 622920157 475974733 325039830 437396086 999673523 521561211 775393162 501243036 557785462 526785234 338042308 430656003 233265756 487104273 124874148 960395213 739627655 82629225 920922214 290984237 40588596 535265519 249138429 915736486 93616806 49840538 783079972 758781574 499922752 178824912 879042133 451559072 419735260 527485587 481096899 157535124 570003774 321577940 278686844 98122698 540599970 437752769 551641363 27360008 791356560 624437683 759247540 192598681 96467379 178537538 60755720 584512512 155680641 105706832 591984727 808800659 776250633 487081174 391666405 126527560 658239706 392517046 693237818 841668561 6809573 18549276 334869993 523365490 646039593 933473219 520273216 467486321 685753763 314259152 171434510 969815468 536734280 93956513 142460803 864168089 302922159 430200108 950027976 541554149 763184919 403136629 350545097 935004556 536952031 571553070 449987283 808458345 64665795 573906814 739577357 503791473 213786049 781133778 308935815 987939865 829888652 65165508 941526853 950709055 186080136 838745612 15800070 671873536 902750053 31254494 698183698 311336206 233179866 479432266 318767297 531360566 698481749 423792684 167350120 702729370 966379153 267974726 262177691 375062873 449616155 177412984 574696148 87619298 283863618 274451543 956613248 977498708 46039208 508902327 335583685 696404510 717798200 963490446 627390185 890001476 884576591 391684890 672446953 868969985 841799162 996721633 183770985 445257470 8619331 679200789 123447078 957670203 466548791 970742257 684954216 730533777 865578913 185632857 282343737 468808393 781100751 422011265 113793167 847634812 63852527 954446060 622828433 465832533 979333870 423739682 975627633 707278846 539756020 462339122 413026964 672994875 184141182 133745384 935944846 427949422 27567937 627164157 938296687 24128016 767374190 959956538 327779144 704015366 710550393 706833505 492006386 347550134 227793517 839930590 698773540 110926826 199888350 723850459 463379553 878317975 44700342 113813035 901318798 543036790 482389860 901545563 696765869 912270167 812968631 749282087 241010240 574572705 352631880 655527876 605945488 618778199 683459886 813103507 231466850 793826767 937380812 591819737 60149289 886337847 921750469 172488688 620231216 288367562 895988973 489013046 443083401 924061643 178886821 322818496 611925140 227098463 289379837 435273293 697124609 446000277 617924363 2306310 685318759 415797397 557206096 105989720 615148431 98880219 876420597 287129815 520794006 12333291 990951250 938514649 985203630 636686523 443025688 579769156 378716795 646452278 811411455 942039818 341129506 45621647 216036418 234754733 473632736 874688520 23687059 679297396 82140768 40207553 870646674 438513519 995965909 931656763 837437600 677087614 585114527 71086392 31500319 125317641 472889981 698779462 569608313 94869213 786575654 244246795 388606763 173516105 743665502 860648968 336734521 307385520 609384701 74950828 734341965 346630466 117923748 244242149 800741497 644503531 657959664 213784273 953679123 169928915 520840366 305100260 928170482 459900814 156942343 904269004 424553840 579248164 417136616 926870594 967687165 816366908 541857134 96233017 894787680 922809766 134927876 973715728 20122600 432550722 651616144 918576424 430097641 767365277 803305091 390973584 964938960 888343636 114641270 429313803 673285612 314014606 799261389 667094872 571900262 150267890 388998095 947478 19682873 513167161 337231700 660791393 539693105 573613516 244853040 542782064 725862257 484789339 661986770 19003543 181376880 936646751 925198133 434224185 894654353 600787813 994581713 827490223 354283332 29835126 284620252 30406815 866484467 962424157 857549529 561176657 596652520 942895220 867183209 971826804 687834714 772544377 601673118 458515787 648138745 629945234 829957177 530209458 974779252 151513901 782831755 349408846 403089620 415744427 871926048 553937178 889263041 24791864 816826571 206718852 539649933 309294883 221263524 312379250 629795475 840458193 648010098 210114356 18042383 371595427 379506261 688516811 115096888 357414334 219442059 149780365 365569023 824239007 670387980 213027076 923716814 135547957 50102835 357526272 997783120 367710760 933395267 291146308 603775290 856137394 633327142 723675254 375797085 557892749 948991266 190728266 29461027 653206589 22696667 536972098 756227083 67018335 828465157 74945575 424957932 301583251 390106212 803479917 241027828 453638429 366433741 166908439 362163513 338500325 476065649 883154477 617121152 716959434 805282340 688695814 201838382 249621515 413461586 112787226 939421371 882243834 158829879 552641400 871377354 129059268 553393288 640561623 922851693 338874513 785252684 855823664 928125217 3150471 993563129 470342748 112196438 393121858 898669191 649688067 244751061 28783348 455215705 454924180 141138742 818962033 164986090 596504938 111092503 113251380 818447454 333322391 326328022 439938934 565635867 731260420 703883301 509029439 520701805 301844741 845682050 824000062 523598282 578207490 230982702 967502332 812658657 651474803 960023358 608753225 653027467 658523495 8976995 736133922 927020619 318347622 28167385 813923300 896098022 372446616 604767906 203615295 866573455 732548756 623863319 208099525 894044295 874694851 426977154 985076637 354332877 702895482 578271197 541600657 115907646 482669630 771911390 20480193 626704975 473068922 841207116 357912102 470430074 408950 982619476 490604887 435352615 500819349 488363047 316584963 475554783 168669769 721616008 199101829 625517519 23406238 860353796 502918804 976041117 538719175 699447076 755267265 368563621 453305077 160263368 116089978 333677783 948590766 136942435 195288497 210011537 420471553 159925788 313168489 313715731 187310803 893489942 298456515 459928365 83285868 919735783 436737001 779158378 389881359 290400546 279335131 162370295 353145188 467810644 709194240 362905211 80841319 394929765 67685536 392229913 92462264 11549317 474148921 840392388 296493972 72813197 855122523 52301014 731853389 132405219 65220629 154116350 250991259 422984783 326248327 469358728 229850993 830399854 376786843 519623723 179782730 549643899 729343818 125526339 797679336 673817926 486584114 949046411 263021946 702336821 247193415 62135243 53121252 463572970 357494806 342192612 19280732 991129879 25366173 523093879 592735417 161965813 526877522 118287090 757345693 746385567 634792010 819041796 703263040 765577816 425633348 583587497 777811334 487577197 161578431 930553257 561621967 920091211 393284952 694729452 545822145 176587430 90176412 74109568 645406985 643043834 653573069 707864297 285374401 465290833 386100163 932679368 994235413 638196325 706907787 742992976 636268877 990410322 237983829 72782190 921910172 325918159 819722757 449907552 282351762 584318062 76122612 524887316 58461210 302678388 854027676 81185194 498243047 822573750 807064657 188134290 903752131 300650925 968758491 832196370 460624746 846132993 968908309 9052884 904822992 295089066 391813258 678361137 453675669 896204345 219313097 270245800 105774573 26880847 946642232 873060788 144166445 614501503 501313768 449282974 789162743 975176762 104982863 675219296 678687792 32237806 457512653 948640948 525333468 524819335 472249072 954564320 594563359 658197246 455474080 767988825 498258595 916550133 164465712 308343122 116275761 825027407 526204180 701604631 804319785 834275705 981136505 847411340 130407605 208725642 269604892 714898954 767469954 776682893 155345293 983375075 457759184 26550487 105182546 760599229 299070239 944330127 493351004 58190738 542728481 572498162 438479710 802263378 119592413 907983442 667145496 393052186 934116458 248799716 792395176 118512809 777947264 229504335 709637961 390185174 419926399 163420507 616243356 836718456 16167071 187847839 850644956 701574555 269914910 584510705 884006016 129287185 75063957 309098923 168499000 656528699 117856881 325140492 524991425 545308807 983232668 839670230 327110730 792405899 179805681 139562232 867304145 557398028 590322389 25429686 299892382 381173035 579034725 789657891 579463487 98255431 202587858 546810283 53883867 386631229 1499520 775696408 567303659 645885578 500774615 545892179 378242807 667816812 140403486 614169649 83556464 34866002 465549431 558878396 814016175 794987912 365423635 364009049 462653075 700215773 197324172 173837412 577284424 994224143 262962877 160728991 370983092 263430439 322723259 481222409 551208321 98517137 213542692 319242086 452343534 780582642 413039815 509930750 886842500 351114220 580069105 11418645 626637225 755835562 677797712 939122664 801508008 188265122 754348703 257123823 320938924 84329236 533483278 778624082 495830946 210257495 306926240 356667210 8956949 414523241 615690369 869485460 195845865 255926198 477316468 559759214 26315771 861608989 498448992 596883463 699862433 939749314 443232478 130966059 255657551 217013079 605198850 680602583 226014315 925393365 415684642 484727247 128778785 480309117 878413364 846291394 212625353 458814020 68100 233372363 183841923 648617789 449234589 856570369 258922471 549579284 353331603 798197771 215188078 669498282 898088825 737644238 665007990 539018915 777179788 534994758 798659811 361279541 241863854 885507868 697370784 518835432 113871055 895497988 725823088 590735208 821921166 72915616 426934897 658175787 766548997 790417887 851253314 786102682 444375514 91927478 167186057 99919657 331547285 681676532 914400573 536696487 853373990 285222075 932821197 256018758 820796259 625910479 510751959 526639604 540994758 62824651 978562911 999164531 636116491 566156480 747112987 138014877 270859402 717706653 54229096 192067002 98155904 187879849 657932812 328585893 861027127 703785352 1019398 864344916 448149905 359848689 688760611 617115805 6906463 512220666 401910766 826539500 689046946 753279869 517855252 220635733 920567141 494254394 526696686 801239053 46372699 203021723 600034693 614954887 148847009 603490331 739570620 279950251 156231281 474684667 487751225 881517531 721910333 362693210 138036006 839491358 27829490 192242062 928310003 223871671 679795798 586419429 190056277 287234288 811125724 406970745 46323162 754727074 270950350 490953314 489433006 961751520 245027469 219571827 540647771 956034553 548076183 169293215 244038987 680899160 813189422 834860158 169563908 371489099 949221644 559978172 792153423 185035880 15528344 636984127 264797214 877177128 555962331 350305370 23805433 496965719 411985935 404228249 704468237 100690370 511250518 370851803 52985076 867931881 932454749 166996226 538248730 124072898 971599505 271846474 772335387 865559761 486375714 431590835 700356279 39233293 720925957 333135589 765464207 178084441 607434258 141910449 36188438 655323302 349601691 304875161 776170199 611597201 18709298 692634799 387224339 306088294 952063377 400243349 891763056 326081348 274196974 379899469 151513939 538876908 476992663 226418275 499884727 866907097 42225754 7755996 84309620 568874991 137173659 935595690 765595561 768957082 89027166 560452306 701341308 616651768 651787745 101263144 519963049 507763862 732033547 937494239 116216395 769895388 218702052 8165826 56873812 831038927 124071694 708105365 852846598 229142615 844255649 745139820 898779770 818883266 637799398 400162585 165842995 962885247 527030364 738895440 429023266 189615534 643528800 977829784 552606698 16175558 68780579 581799512 362306511 239832267 868084190 872581275 130194449 24429548 147289604 234074647 33137896 309677316 168819437 598699340 316191920 263943920 861219272 186015221 899073607 54589482 180756457 613190218 262253432 809152231 534400279 356877355 554404298 309211380 436847867 89514655 233442965 936655367 688226912 263520325 537413661 101084094 264254922 565196207 828868164 546414134 40547319 56164627 153089711 771037410 42292161 222012508 367447164 103078909 753042839 484708962 204161040 287411873 15193431 583988593 690918448 802587096 366104389 394326902 30084265 225513591 618676582 66450950 349853148 802399185 890318510 149315733 795971876 653517938 829456682 180612215 37616047 464553482 652661786 837041255 351296925 454865638 881563101 881324075 568800788 587335387 469416984 940543731 348970708 800381751 110659815 986011826 466539245 339922002 703044197 804723559 647162102 679208446 660642285 739782745 531174136 778317312 704751093 185270506 305700503 331003312 880646276 795483231 623821877 194047137 655037035 888224033 924202368 838032082 966022605 778106429 321682508 256008977 12804144 709863194 362196519 970228330 25617718 165191941 256707847 293918960 985362379 592840184 765056767 788297757 783744795 949340180 631361436 578432943 195455118 831204803 500903082 980784319 320394793 925956479 419537648 795684155 983578649 623664149 799481275 200996568 835977791 274083354 930863910 346992114 684450442 208597041 62687254 80014114 954232527 146043175 247658713 414768271 95283702 985015041 814871447 979028348 978371906 864602053 231814595 416425477 983596304 447218207 221709238 806900625 708083663 368990881 219944853 666450790 794159590 600460885 434463863 702720182 451661843 711432871 282274944 423095518 815545952 365908848 479832321 792557398 221689839 973234878 719341474 977600453 368058884 918861986 178218278 894328251 688945875 148801613 177436177 411279346 30793374 376390237 9020294 665260323 888384225 428888262 389879135 180427283 574868792 615989933 673102053 424718028 321833981 181288473 623364103 287801105 241668254 473718344 220606401 331628984 244666563 147110736 505265184 919422641 329400778 142439201 810005415 511006874 889458083 720503532 954746033 3733573 752111365 507439001 219938852 922117201 927902053 451686212 746526820 539612423 732507121 142086007 423216666 148499314 520944256 505781371 113332581 210575739 904030245 490563289 752730775 565657015 987717065 672589458 867745569 155155179 659973508 441205921 841400014 875617554 317416537 87195638 485752242 515338985 591366494 811226656 764131351 682424774 856090421 918750210 95711428 24886884 235696169 842273283 988795343 858137774 382690787 634370114 670223939 375203137 754243512 96802615 620312017 301130451 511896984 292389933 825399420 371924881 386216391 747445516 926329230 183470998 298786273 363069707 595904996 839015414 498877951 706981957 340847173 785427865 432322713 321115009 440944161 747417140 336634637 806808880 610609400 869781559 676775045 609551842 204245763 93572223 155306562 909267569 725187111 31757113 639893188 899582997 583154916 371788934 829266182 194595242 667544939 695919909 276215310 744057331 219027165 889269300 720273969 472532828 411369582 246633158 452898462 696554807 102966407 301822344 125014974 202569208 560549060 713409133 611352378 550859627 406764430 214808404 715593083 669184556 939296533 414744102 40787915 666063612 1849973 228040191 123412507 851154922 963463223 308797608 967696030 632502049 132563279 237344916 852580039 5604520 868626555 252072745 632126256 240931146 944521226 20735157 971519568 347862980 390437035 455782328 912443314 461393578 398755635 250750713 432280610 246057207 566630340 72430115 805286209 537761079 436995496 661221502 832544511 315960333 463293148 132428164 238169273 800108397 448069107 766579562 669373519 997031670 432477383 185030660 513304816 560647690 552673028 277434160 220079489 515686797 87755766 864048855 418959215 771033130 43230810 805113066 848546247 2650836 910773702 972926191 880302104 414508616 404521619 557495562 254767335 468318894 503735426 500367479 62889535 981454657 257080497 584392360 600828965 254301030 491700526 962862019 726502970 50896652 186231067 542521741 810411161 967237024 46253353 652014078 718541036 104204252 970752170 406773931 964556469 607787433 985615990 812619511 413077325 978512867 711544852 218430780 647649005 943862726 313400845 607784169 746807740 935991371 101726186 380088467 831735339 823194564 499063424 479939820 60596286 654117766 875466011 33235504 14532906 978445124 735832254 990516435 856170352 380603907 52482640 914762723 355350629 661049207 725273913 71768718 493074861 899069183 139976513 545440522 128942158 733715741 384846402 834329476 348479280 231369005 25228488 934411145 893597575 407652232 658806592 594307487 760363530 829508970 287765864 710889280 45043562 369881955 811766523 714691025 620899434 748363168 53421041 860505598 236603287 670909713 155358926 849022206 990481392 744289231 817979038 861003511 302193963 894154910 9653715 29626264 259207657 717615119 304214594 306964190 242609963 593398006 438506016 421405209 449219461 730703025 309614934 817999503 220900982 825223073 579616837 388128418 319308609 493310480 650547410 673635565 438096661 701669803 574500986 202758610 838915722 257227551 374159600 232086095 356641804 360312588 854285996 53917016 241484877 768610754 548801901 672143981 526123549 773209824 974234214 389446238 327674111 70739500 820986834 430639246 997008217 525330980 219045142 799908840 322809234 418305173 661692854 869269161 649190604 357104231 443497269 351643583 609542771 442889403 981248226 41922160 70879652 364081482 198318576 841505158 616536362 159683939 591111233 258985905 249741070 28824393 396825357 658251091 35414007 343478570 994320727 7437541 470619817 390842948 403261265 121689646 641331323 880127968 36528850 341171534 212875851 477462724 111525661 519610525 561203959 555006441 884293381 564359282 723934225 981112633 69084781 341857703 273060236 287852356 535328528 844191931 525147960 496441370 384733221 555240739 459284196 452232324 708530282 66763547 781918025 109337537 896864315 489353639 634895069 415693231 413465803 698040445 743613681 95035740 938551081 957612447 644690594 981508379 954898027 674837744 151118565 153199517 764024079 868723786 598629758 367868293 501342019 969693098 110296517 229141210 355094106 434824556 68518547 862979509 984313880 108239702 636334915 101416828 880451926 181500884 883788860 813244390 252379922 763816168 82813791 648759650 212565850 208314382 878523160 924543813 213805656 979009153 258259128 599784197 19078070 636441829 424046451 716859252 884485648 858517555 169319065 396391707 41606406 113085558 331352075 730983627 722308236 400572082 649717045 993076200 656445371 664316165 760001721 24266917 645849410 253414178 696966215 152711870 811754508 479519049 344117306 104486778 531465048 392338765 228204996 765503833 327652499 580275790 392878419 221323983 227639132 280159597 302300784 584717578 341115241 279922432 655948927 91400631 546984256 439389698 971001428 628807308 593741188 425025227 9436930 329176672 230777792 683223055 854155043 302593678 311778982 29033199 598605030 326271754 956061894 866123227 387931427 47614024 383778315 377625875 683466376 703515984 336737183 104707658 251513851 643486761 276217131 418294106 462379343 277764342 958378246 377205999 33359971 666814846 79532492 829254842 572226196 634353744 433229009 381682686 52616546 673506561 604858929 392346499 40100916 374192516 323642479 229964941 621553244 896284922 503414359 679812162 196932623 868928873 918163172 552658945 908632905 164555465 636582580 722630882 372188165 946685211 418140340 508611134 656808761 213852495 358014012 288831433 338812386 529855836 372744712 37520404 851269304 873230958 31487924 133665707 889145172 672550827 116981165 472892409 710252264 388520593 223726663 970579092 198300748 267081701 516691046 947326247 807541942 723574520 372454731 752157800 251727461 342082404 265350619 657229639 709481048 957778716 124048510 551183480 812180816 725435067 506953450 794640801 445135640 884723853 542628858 536559544 506423328 661100928 471805324 95472243 161604768 773752191 814463901 4914848 180506279 496550647 332308665 232956986 328943753 266385269 31299281 312800848 452274951 857784565 115724366 468082178 497044437 632219934 209688543 60463348 303644519 107360928 781313457 29411039 628069721 459965023 646409528 885100809 250904883 47179465 397166154 644857153 433240717 285776211 777920204 863800874 31725833 256519388 460036354 625116932 48216964 591011801 381700258 805820414 554066476 359756129 28402997 120908356 917387971 510397535 538848579 477609568 57856071 892233791 826334909 330643385 431000785 349456498 129689105 842614094 346278297 940426777 633090311 815493452 114411673 794642978 366145894 635247801 925367184 148406083 887267779 999550637 246701983 475837589 633110312 806157095 511774160 18959913 79559330 857962682 336073122 630993380 587243077 721325283 630593498 939571817 600840586 335097380 65514112 519496913 476982352 697076111 420830584 51654968 429505217 248334998 631873580 519711557 964439703 4126561 350694123 446994211 221447240 532212394 926877386 537107578 557165451 859907471 603123458 569629687 747097253 273502503 838172319 518646472 408552232 603560930 779327529 191516516 588825665 649112079 949969792 503598142 314033561 578726792 680996526 591847407 66498740 533032126 926305610 448622372 570960650 381155270 545071227 565892030 862633583 985423404 511926575 154096668 301969248 660886120 642887429 569964706 112915111 937611984 252374778 875128460 751055307 780091527 88437323 715382713 576844442 268179499 843336223 435441540 383313157 831821761 513665077 58805115 216382049 632456250 177550750 539125776 339384499 876593226 77916291 134780947 695978753 171464528 963784172 159178491 568213750 75793009 615894826 795429321 124760416 693184270 525187344 548235015 241751184 566404082 724397079 559791240 403552242 41009834 528598106 455625394 479153354 963792827 668507895 974050610 606414285 164585581 668444827 517207526 4640380 357985113 154105099 331782749 275491492 699493090 245703323 224996001 168800117 630378116 819119356 203325370 973701129 336453549 702733789 521002194 698539423 26949932 518042748 89696963 583859290 366537750 708650054 45093661 132650722 130438988 460948522 762463669 613656471 948577358 279441115 341293789 364748464 389115513 809152751 619968597 797598572 18268576 498086892 203048128 635094290 676527627 491550367 76491870 372072258 167194161 354019873 930692384 917107962 877747523 496516644 670173852 501167827 605568493 500103181 571657058 25748747 314887379 534624611 887731440 540710858 130474086 549994355 721938946 310610323 468081272 511685929 315228999 883617928 768049845 377377925 352644259 178238652 94985986 398384013 912764455 864618979 969287903 964432228 584350515 383283469 940707360 579580855 969674945 17543440 64843142 189171099 189799461 432650705 876361787 284310945 629385032 948911610 979864628 732468580 385485706 764726120 786485138 506454230 643316743 478725456 226471555 906144919 373794443 810647995 48536107 569931345 451551602 137672436 590162819 95098452 754765028 418455202 189347514 644617235 1660257 188279044 632077721 12516091 14348652 969786106 968187362 413603980 195017703 830116718 127141076 697715703 728342451 556133085 540926019 471965255 106106730 630749831 931873790 604066594 211926088 116833521 791372574 81236544 12685705 943220522 34489956 940634418 90147231 747850215 248866429 120521900 593976209 634274253 521943141 71783312 611562290 206110399 213720980 289608066 249226218 50664532 294671311 174287945 196865086 770281762 278753435 251140931 488785976 755546669 534973530 280091420 499956904 665331871 236958668 966377118 61242636 582368593 133288143 895744745 942991789 949036354 408185024 39218583 491400143 694868675 347323913 575287328 973151658 936370169 224382224 504940179 185170748 503533427 911736288 545125445 135228190 972039816 968648899 398257476 332097164 9286400 7821209 492157205 692391494 132993900 771970398 405769493 548098382 738572306 797463331 43447960 591048930 352095404 434720949 327928418 713784258 475187016 899878415 984556851 331567928 829348310 646275020 83111982 568664345 104782417 738045988 8936223 381759262 315181934 182541293 460974411 878779436 834308391 148385687 723529865 738773289 930207157 436927184 291787952 211141023 159697030 951877737 7499717 133743188 421786095 587274298 113578816 449406383 947997402 354611066 981531154 426209957 640506719 801546581 289410501 421831619 548699958 790131444 737532791 920383847 68966565 795549596 97600475 643599743 556212505 888504404 21387296 509851068 258974585 126791129 539425644 385330889 655696960 569837130 716149571 309896964 995823737 627460806 208474552 29971403 374723912 389105105 230379055 608907193 890566281 74732583 525776381 408485770 455669539 415575602 928036717 965990052 330571701 816195927 976033509 632995994 429739233 704428348 542723837 181895852 268826890 680719398 61410765 961308579 64455497 61404556 839154053 941075205 644500229 879561747 974656985 831215043 800765755 401144835 727254434 185895363 687861502 932156046 924848977 929339331 475508624 259672204 378848896 262822393 918462180 996262890 208342763 152200690 976981904 243978347 81900891 371968547 395314881 817856816 763596824 333676852 790654894 543307317 407435414 766627622 114956853 649433007 705569553 156122165 337891785 282955965 901175654 466906806 102255660 48472312 320912644 64253977 679089605 44701686 489756337 791453067 515820528 1001532 744195160 513039738 63831330 791396946 959268696 769479048 900989809 765414760 296940052 695767949 21983166 95471402 704837473 935640948 606433472 949996540 862556341 655291323 250097329 246173735 289925371 449340536 908733172 723836253 752085658 584484586 589587760 849542740 33916543 164582253 672884617 486347196 99506002 522322125 301921117 306451416 894057819 604756643 263635853 17592613 121814955 331331968 498626566 20189941 448100181 244597540 327153152 638502159 416502971 990279518 577836276 393970439 251809688 75376725 732789591 393238730 495720623 54564852 334352179 902319834 196887887 52176286 636011428 484217537 123869400 900484826 654523634 32867398 415542060 275579855 173992538 844199293 830846223 789268887 186658004 450132416 508222553 539336188 490797599 605599665 669248644 917012802 873159458 900608109 864648902 258097135 554906617 610429201 737457372 533545563 791421504 208263294 654577432 687543463 719427843 5851545 83334523 589387941 427129453 859123680 620295616 223267656 452981418 977367719 876080026 409905791 859693291 113338266 901586724 386373949 977262221 283983586 375958619 680211323 99862402 877237148 364853264 350861440 418390497 792272304 712311895 489835561 631894345 792378912 484217917 455762407 829632360 832940226 279790670 109197689 367002628 473010489 973900192 202827827 438600291 129529024 556544502 95664436 535812728 409176182 949502769 482498703 868090466 643441305 653589719 52999335 169982100 441190382 497836800 361724369 179466503 486349081 742871871 316875680 476912990 82235360 312276833 372722213 327575916 823588742 504146110 54222132 937963364 495121146 809343262 994667214 908152684 517158272 918221422 175430107 472273 694498607 256051961 724036463 15358570 839106468 546996687 544504608 849347849 190115846 841295608 321831152 324714905 407681024 942890263 883984146 67546438 65565732 741053889 714712194 752506456 127372728 442957353 804484161 596918319 494808917 917741683 522279382 389029970 124766360 505814788 686985346 99625155 739460217 971007441 844395623 164531490 887382100 487638161 823642058 134723602 690595473 392572868 700164119 694061546 629850383 490114697 518795858 842730951 917085704 31060364 800690576 677553932 283880548 316559124 577575969 627931573 426538607 795915996 624228948 7831753 837078081 913548204 367058179 455293514 608671458 467326442 582597836 971675300 793091218 315940525 57981427 144077364 353566067 155538423 283285331 83271855 865949495 226587486 361307607 615080691 742189747 552534664 165719308 928178238 152968038 964387256 434880144 464452681 886233713 343747834 415453854 236734436 445015080 168009306 805478856 137503831 873034176 591620076 973562091 57762253 588784830 674661825 72222956 741064957 404171267 870929774 826077668 393764224 675055810 582062242 494342469 918064517 900910247 589591825 718527700 731979570 438575869 167185297 66921008 59369435 178559692 433280021 606928697 748323715 682899244 446170014 449923319 685842805 333624243 840347481 737756512 334671177 383624629 25183434 322247592 390149421 611214061 253639550 27359613 28687257 839206701 691587951 819900138 245981136 252536819 589970055 704283829 389400344 539134616 422872320 933468433 842783266 647203720 472497375 612222383 227703977 395519833 117673262 729799626 483131715 374319968 369212270 281499119 200168485 556711716 496194661 435206357 129468255 15300898 424873891 394568222 509794474 963208854 501209624 406476361 533034303 179042637 675463951 665857599 460309200 699974564 669205610 229078218 3743768 222247967 819228375 19478916 706564975 958445902 162663251 629773085 896028896 660861705 244721203 944411088 409156445 332385842 364553851 814755745 767836629 650459586 855199466 840252120 61992803 562046238 562769518 327692751 281532157 259188050 807823641 804953394 873944117 275613873 435082777 522544744 453971469 557123608 725277980 309686698 41140978 695762771 195478210 744237883 754261561 222441452 421740396 229847671 23514397 731648656 12860801 672927023 804251700 949464820 906715453 515733213 996245987 91057259 514120918 470984088 893300801 898788132 346343289 831821775 17558299 804564468 433315415 319065958 724382135 844659247 545981611 108349761 653851940 699698572 540575474 799075560 212147325 55206102 884236148 817230054 595308527 837004915 925696964 158761269 372798330 458078699 44719951 696695847 216317785 497896421 521242841 672964728 608980630 558020851 457566714 179324027 731779975 481108794 665792742 30941367 361673193 357540647 739588327 41254961 480063741 643974787 425260368 210095710 452338388 361437788 733476185 587604447 231558740 670453143 638918090 54012558 726397261 743367686 709052480 606433782 274518628 429999280 892401678 859313999 693626691 267304013 949116119 573364925 455791773 728551199 212292123 592606932 474351474 438905628 998206710 105559495 492800486 508379455 896046152 748259784 193831499 950242866 377444387 73728663 770140114 953567348 227804882 60146978 622787875 947102770 603581901 185997921 402311451 174678536 662342974 146837993 878674422 216813360 982450740 870993866 801703730 594737646 716629702 797921240 532943037 704023721 228501760 154753543 188633266 2625629 21536138 978062672 647360012 114222723 681609483 723298832 690445319 368657207 552732354 491632530 105414533 173387484 926281543 323630418 72060935 694336780 998861027 203477660 493348642 212461611 561280396 61490626 179190762 451209920 491597582 314554370 791745906 545846954 388119101 847864748 765482919 186092341 191035744 476986044 610420244 439780424 484849878 926840041 859996103 40319604 114731126 867911074 914060254 34564057 786122345 934040025 581238365 630553566 11788690 125486713 280752948 809813735 172923238 269747382 920299573 496109040 982851570 762456848 962584085 530371351 903698857 213751208 246183847 381836753 176058509 657966401 630556168 764359496 952584754 484557192 715872368 78603543 487806350 279020871 37729687 442294222 808272754 447628029 211643814 569558180 536528176 902846526 4285253 381799515 569331702 603236862 167364312 575865098 133723918 421999470 554107047 946656148 227428279 644396372 971704758 40788806 667076192 974416375 768307516 861283573 702876856 297005209 900606077 589951634 938177028 977704129 811992804 551316087 209450864 30445649 439926500 427633287 751420350 513498127 146310042 31495197 174612594 297584778 917278480 484488753 201483229 408282025 745565142 374964895 543099923 964551487 687976921 782100318 852190136 590788272 84212637 416080494 891367392 766460600 139971365 415096375 110100906 393772088 273592105 175438997 348249117 482707022 536178066 149449713 925786279 205467493 467883873 344111120 841076400 506920729 103625081 818674447 432035479 861058104 450504234 179287732 806552469 610622641 600512713 558767807 223059360 143748951 528108036 894636287 761125798 561019140 398752960 790323931 916105659 687523994 971840889 194377973 234047090 246061797 345410790 517170884 105312518 657275212 188630322 525788475 372372974 894842753 363986138 278754549 236210667 313813319 351569166 22437536 664330390 276320507 369376876 32688975 837565393 465473217 984370936 73859205 357885091 465314597 833218053 135295083 305530116 764629799 383596866 138402120 232903142 306067203 731350285 940136275 789673985 645980306 351873081 488446560 703541949 479990991 591023269 132964387 555029164 790804508 397136736 666286740 452064406 659037581 143483562 810050686 491102368 111023790 485224272 71593539 641941316 46787097 134631464 198881106 212015133 526186915 533372908 19550051 465946717 885624489 382928815 723598009 602010148 185985353 646497120 938466449 311371816 586418222 434160587 740826702 373778957 30348276 512634006 177311455 941607020 116554453 277886876 433631587 515872808 780898898 937374518 618946291 971650417 155383111 782213185 738493317 674758822 49113604 910463511 220574484 575604732 570390566 863343614 8786667 147387913 29732033 282324251 108623710 579027246 838026079 142302125 198298799 810629416 532701564 60618129 693343835 929475082 491079977 293108167 50693015 532567518 581835620 714222795 820956456 356331615 27834385 201971844 205702098 423197039 751624868 908812630 36005406 143237514 531090839 339577252 159436723 768927002 590854311 592829412 198974509 133134783 407873369 574563774 187249891 4599673 998211454 503511673 705662122 746321132 100041390 537403921 517531396 523946804 998797536 177236845 624712141 843102012 132113996 54068341 975397859 705879996 968819154 724861953 149384094 510053697 931670125 590314236 133611112 992632906 297896162 786549245 456800769 313566523 131783077 344703414 641296062 541775408 263585239 554564504 930290556 434644554 264340228 424027034 244870368 627293515 771777213 896886513 507829315 367109842 944860624 398923118 491200669 877554573 517315124 66408491 950802897 422959590 744512321 934724206 245370395 332398220 348898128 165185439 138096623 272655776 969381228 764754413 790545193 662983485 868676530 289109194 385589405 484096848 86746168 845876489 82030500 425023101 536032107 41771604 36304124 14292282 663217690 707002658 335037266 101966215 863434210 59770600 894377989 884104666 438310 150956156 835048821 415939040 337566606 938193944 118300193 974588609 332476968 674256150 86157782 442209490 826766236 667216581 311809699 278485219 937124860 209636374 150360458 9917284 472635358 106856726 262102985 993860925 143459561 821301766 735023363 693872484 253376311 198006709 228850868 616512560 272732547 349123173 770094980 831041073 609617608 756096426 741986309 172872256 978522164 472696193 140506566 48590058 267299244 133932498 771919490 979877954 600550733 676785163 832775116 431651617 273876590 177282681 820663639 747604335 712756950 131548984 121563826 591155002 967595704 969487555 302014137 839251382 334592592 999313761 265920794 471713438 687052246 217415088 523514688 819994428 383114944 529027766 19455993 257747140 398175764 50250155 85595914 820013870 546423392 166807770 561702531 136930964 345797369 581785425 341964630 257382498 805748111 355927621 826250275 428159952 235033372 214820572 407148704 56530361 684798516 498208578 421847128 712407566 456365834 399113562 939585996 6320206 317436816 948264296 402449082 180982401 439272294 435394261 654810609 173414111 112855385 2941420 402813659 696688590 761666578 250757846 826264911 976579267 59134306 657438061 108649408 254976394 110314348 916718192 228750777 784316593 195017881 82425338 569211423 763721681 495293092 245574423 770854026 162984597 627862688 61412262 804455748 999742711 214645865 26674824 90325696 814611619 128212738 561827020 892862962 909665975 442269492 366276285 530922228 292207225 394265682 790818848 789989666 811901212 605795237 724892371 145505256 385780672 968566908 296904787 616760756 856947073 945765315 376583146 52986819 986082924 543941972 319703040 460490900 827608391 283573466 473266925 720705133 683603819 812059919 351136589 84080266 24692625 511146751 330597693 730990209 841804488 33918061 784524876 203138792 711065496 580478941 809280530 793126910 911280446 286749685 273560371 682046936 489955937 166628952 637166149 280207454 771790292 869063460 581633805 844764600 220035782 417362620 942356735 328895452 504167913 844284251 296642407 739780430 546653705 304192715 133223380 342793070 380663214 171642161 549721372 368309057 378288300 436055814 657900876 817803854 126413377 507619417 250190146 915198773 386762207 939818808 939478856 655641486 177419274 485019406 378603681 173600413 741492716 105508268 64043086 59870257 556472258 916345246 77341017 318240661 67079666 147752953 265479907 768066195 886230284 966275059 101994389 471435261 491516189 317191715 338904129 906671849 644774712 745522402 342538116 492373483 198961377 87459321 849686521 477268074 359600038 562823781 877518823 415422287 204281272 698728976 219712650 260951784 70299302 42751836 824077823 502666442 314713201 390624391 459623503 708728576 36401876 112486688 531041873 405514473 81397261 402953255 759117874 443391937 399070805 450841029 339950384 429962342 127235295 322096262 996844516 522738210 366576194 121538998 953967125 838990422 467225111 453272847 582203575 258485857 730600176 204660390 149181463 376967794 253375453 161444128 898087647 960710168 752344014 489373219 561465119 370966559 907440061 965432507 261011458 884862787 238069910 378230008 817588581 689030020 681143044 934589912 737278335 847560873 356152143 59098612 465121412 599435954 276207159 125459835 531522038 640595660 640599432 805277970 901491114 129804790 915541931 11164681 607454750 268605280 270563245 232814625 948781457 106253306 782112646 703832050 591758399 780013681 419169238 610556667 342515579 650384876 797482105 952371606 247745312 799339845 70789196 924906930 206635198 929658334 281817573 708146434 491772947 149208059 505150711 67681297 689033573 381111730 910328329 945302383 679405740 93452095 945822239 693781669 358514803 890550920 324191351 486375014 995473322 576749577 595323665 423493535 804345941 793418797 861777507 596006716 526666142 649184867 483769723 178926561 647971126 651585174 574730627 107806952 327191166 112919285 858525693 457256107 736900626 869624031 512774872 174823316 654336893 602282622 90544423 863307320 598183745 789391815 265316899 114708080 299572627 250287483 978283052 864395742 482524751 467544770 991576852 457686211 505571919 84472075 884320824 609934156 676697281 189023889 896153773 303826941 323823675 368019182 231488837 659736943 698715488 612886525 683042248 705224754 131118063 321090754 731972514 348514133 855364570 722124141 502731699 982225928 129931463 867506806 940629387 648128615 477638163 425400429 319959211 652078997 227546903 352428220 879966481 415124768 175045762 921446017 768418407 830904098 422417694 636774684 900336896 402169051 394982829 785911134 649178983 766220194 113890280 457459013 181561045 756420015 718748187 219004804 500766366 292359985 58247103 608756397 203193596 980857174 560438979 689860653 448098775 488595648 453269753 153327048 312699858 531102520 947496359 109092553 43608395 613964748 658820383 447358948 147972393 364713278 348891046 673625918 443660377 274805997 626699761 865555135 141605588 363626674 751816423 784408399 794011242 362194326 769528892 357748525 830159604 600342639 101814838 695702708 35106925 771662361 886516230 173558975 47966258 67859126 712111898 714236225 103033127 230786154 685160127 719342607 386048042 664547374 776218105 787391228 833472953 212682680 25151090 628671118 717183348 272167243 631695090 324040328 783062222 903071297 648898318 299469556 492075163 982486613 834243893 417871923 86629245 348691654 683008988 219148397 318418257 441024558 733783051 211344404 810583351 348811061 596698904 463711876 44843921 420900926 739191656 238270897 474567422 150342342 117199812 372378163 710676465 425163864 978686670 386739971 374861155 212215326 365010678 710583021 874967501 684017040 197802105 831954489 811347005 879139892 130590620 671924945 42179839 232341800 879415582 566453971 206925430 894963193 66999495 231995649 993376947 954412220 768022481 364217886 543668643 884349655 456020205 13298218 930215436 481616711 218493785 348773697 18231412 693310448 297150011 822397659 230637618 36282340 361439646 246728526 758007889 966096823 307819985 729357827 747006142 961291525 547495218 238555681 980165015 912455534 322162706 510754776 83883097 142669627 423153846 794686788 994370230 111377225 206001524 359467650 140613222 13609747 539147889 308333461 174253099 224259669 530493107 946947735 705532772 989099454 927466348 579562780 565423385 920036436 694095071 253366977 449220403 663583620 904510624 851782804 867325376 965868142 597578826 325595342 613977466 656562384 137149823 523099758 188030586 721153641 870764512 683520016 791433419 103738106 498182657 612016737 310637525 69564849 867120148 658054770 237286026 390221149 155588676 650128915 204366150 116705659 941526859 334229435 662854531 471971356 267499300 995835653 448695864 110263456 111036844 541223654 182813774 679059035 72774445 672367487 405154296 302420384 130283327 860952615 653068280 589530653 464981294 328308955 983992669 578608658 954791523 468659939 899456059 725598962 210028766 724334809 29986694 600192392 99339706 576910853 909593914 836418775 80081833 884517002 123998830 221606930 911621643 197400511 837692275 296867827 698991792 145404767 948933340 502377419 912158694 476250375 894601898 338859322 283036769 763853097 700377274 37841675 120062965 303824023 691229244 602868888 187533122 436597377 166530454 116804296 493880915 278750429 763534562 175502294 990201419 887202135 184614691 346411531 857660823 774228575 249060332 677045890 533896573 467532596 542746985 262586469 846618151 810985599 175268563 66277316 870239473 790271921 483158520 552255444 144194734 635054990 494928127 800825722 65597764 581132875 160195291 393966255 529106543 612629284 813606430 949112422 760704460 365497419 821363485 807129376 14673460 267833804 855039719 219350202 543410025 567109839 142151927 407166189 488954391 716846564 547086743 451268035 793091004 277566744 992386503 566924534 372737104 555072955 389728358 837298709 242045028 337587142 559249141 879358294 188352041 625605999 422538015 161924118 467810462 753841477 723810304 998842272 469593493 491234418 593579027 608700259 118574226 153550285 150045546 756492063 446101412 886591234 881865174 425721709 479206148 806851540 663080678 717945765 839204231 744739539 570277014 812270413 474624002 794576252 136123210 331386005 171407495 656110271 231999285 371658595 599829739 656493515 800132476 709838965 42887122 252476612 459229975 536732948 949349224 419481297 633515560 666380675 513857271 561974724 56780034 345673209 195281686 811219080 823622176 702200749 850739460 394984279 226712462 772526755 778570879 320783013 407179990 559603238 519623615 824849018 143713783 842006741 727961398 308077739 553660538 412521255 875264831 699263723 687299036 290008136 83499400 780508694 536331593 856112511 438783550 345928663 267895580 531533241 412851841 115005816 822718926 404469976 445383726 650724604 905794051 466428018 357735020 545643267 754311049 528380279 926537354 319926202 113593770 470829771 559176660 230400665 411668002 949141857 397575498 689327180 376192594 28503089 914320772 335290034 331115439 234731495 153575036 149975810 717577339 43745782 453774201 451580864 773225752 298693347 787252695 716257837 92645531 214291738 449191623 33006668 441579157 800658521 909093286 908138825 321584331 464333444 517308752 119541624 879932901 426474725 666927506 218518257 836366802 154000344 27125477 777434059 15140388 370495976 913293622 235624298 721553285 11642562 636488750 164754923 96861858 689727198 873448088 883226761 370554447 290956366 743544154 405341655 112343478 499485210 899552875 725643235 492429796 755392253 560996003 621408005 236570292 140586574 684490899 861499985 850053041 296391802 355505150 785070049 768113428 458734390 631824110 626136099 774443061 142580780 781661039 224288221 784451220 211196343 453754801 500436539 233749679 484381454 806595240 142931293 651906994 79482944 891690317 217412790 239707847 861848742 279160975 71942598 594990819 691780130 793383116 140713615 430002727 492400326 755444216 160215550 670099044 756616513 318053483 257943831 989332020 495485832 634052284 209204356 842681455 508301561 439337407 269145836 24282877 289871937 114327577 908881261 636727139 43711162 316360917 239233439 161852096 244589743 601698 689411869 108262617 500252141 103436215 789046328 699379687 405413407 722889672 572064925 641871330 764350488 534771037 265122779 295978294 719413580 442914802 601218450 947792514 874093087 89625027 108701087 840547778 94215403 633855648 574322122 638391089 308497088 20624103 552123723 77876393 337513688 498590638 521962756 649528713 952472259 388995035 650319352 975099692 919291503 391611423 224674412 784475604 544651335 969009358 397056004 218932505 529841626 486979261 690403703 285688530 315359664 498948925 52538542 749252534 368483857 925949629 228322896 763427236 471903530 978551907 571314405 198229416 160523734 989233012 442710712 757836344 950303070 308885114 109619257 96857274 34537452 509051344 850126685 681562521 490905529 140538852 800726369 654614126 863527984 132263539 277630324 334674452 241535391 575397916 209842744 679447737 58873644 818701396 519891795 715129598 439636781 968917291 819004239 258387660 175852054 408887084 423660349 184579132 164314558 200394174 359712256 378943484 225996086 202510768 861883122 512261287 9476434 937325136 971875446 689106006 620448303 900946625 943355586 621067442 807588125 705138521 687550990 520683337 537518640 986656512 752134028 721067492 888851978 736273787 139522505 267172185 25219740 265661137 502192794 756841343 84138398 448753575 960061199 603942707 231298521 30105788 217643544 392014041 969496615 169105780 397650028 428015423 631908936 926108907 349451928 331944514 479925428 225447268 262800483 805312861 594161511 977749689 908537350 736076458 197455409 520828769 677090731 511357051 194043576 551332768 94449520 846318307 739669051 747726398 511584275 784028842 302558783 233518470 570423238 387947288 394451242 705141471 868937252 332139986 351066958 279222047 53974914 108179659 950221954 882753396 524984859 875750659 739228037 401981980 483132456 111677333 404234374 606930660 124267510 547109662 778084478 489949780 302613735 504164731 262756629 854502277 766109961 290485429 898347407 18147339 189522160 969426352 753569598 649746390 684184325 865846955 651344369 606399229 221815259 613522139 280377820 934922687 709142985 982643626 800704991 992472819 905812661 724992228 498355053 843236105 855580756 11197161 234566558 261378975 508143574 762500665 870116542 867207163 476928583 560150254 428475039 954560849 92879919 846580294 553454171 795008736 722357607 469042026 144254971 173008405 453486192 92474860 390787571 986103090 98002344 671834454 385176275 978200397 66602461 469305243 557802352 942940137 358819492 418019640 381817559 4841920 576680407 899525927 866618640 565737652 624199366 502652371 796754659 236292371 733381978 640060016 575729440 273394667 175052994 725916734 187099018 35498973 263740044 212618533 112813121 145773468 166212365 929341343 804230479 105888629 475720969 907880117 811822536 953710444 766522489 989130439 461341229 527045082 603938394 178539946 311197578 939093118 209083146 566193021 209575637 277060500 349293337 672689570 335997841 955587576 91055095 224387435 28421292 143790958 85060147 608247693 238316214 536515694 251899947 612976431 978200184 11089842 742154241 333866403 457030298 702246988 367355911 5270669 614948898 825407633 177431126 58434984 259200998 606801504 113372371 432335 896367250 79179820 825942784 912838218 474436173 502189601 217139865 599438415 748259435 20046612 852695018 297323548 204346776 254500266 182665415 586341258 968376883 519947391 249901103 536161930 262141271 894584515 108066991 837209247 748533280 334950670 694035050 737794864 948203117 347387012 74148770 884858399 373891239 639035948 4944138 622653881 359263062 960405667 207134078 323679447 702410381 721191730 492814110 801787238 507010097 187001976 521921115 187137965 640640625 860986780 273993704 566733790 345816821 102057031 137406810 685210925 308461215 709748173 154213540 535213475 977846924 575854727 783172819 445811427 182502279 59715954 39485808 535918943 334252628 12743009 984910362 72744137 241378188 36518737 980068567 902322719 45589846 947466214 160907177 740186661 705169672 840986583 947991863 309741941 121987209 237254874 18704597 372313565 130345946 203214661 473647757 782030140 428999506 534123248 327162056 263074061 479681740 133678541 274379025 595338140 145596707 420934884 949610394 947380432 207835935 179657215 498847773 71706802 79534508 556492144 854186281 535487965 697936257 43943627 888278164 316588162 315467515 514715484 455207343 802576776 171081244 992075159 833348064 607057121 556761878 890072384 657851732 632509043 626196839 256003614 534297142 701896765 948992191 689770579 427718146 571381432 797540944 331721951 180807559 278737943 248686200 276499245 577693224 165380531 311603169 234259641 109476253 934388304 78075833 584740448 226416066 969021442 206559140 687022178 24396325 622117355 373984179 304454494 120075204 366058031 679290556 401993675 685131992 591983951 266610925 219526864 31837876 298608032 592603427 237386359 512986942 796768844 402441410 413505794 431063786 98009555 712330328 206425887 104508826 648278318 669647369 658123832 888868543 403141486 617613866 173682136 582886373 266393326 579930344 245799835 312219677 182175256 979970295 854601189 751896382 717865775 321358700 922403052 413576548 466254350 199110749 132070435 538008863 869594748 40751354 9730185 293965917 426610070 735893988 87831345 885414061 532455485 532480187 320751816 34840132 93123979 672997669 404579856 765040968 483813954 234286373 436745807 216533502 751076238 481359326 556652894 676435796 622315810 384963372 417456449 518117237 740348919 812119215 68194444 384771028 925637624 371072543 611508198 231747228 15285935 340749390 875075088 828414101 351652370 694498254 908669505 945623754 825295580 657188639 397015678 388618076 711253417 371873599 97757754 940283046 573221727 368797826 856008062 895706740 328726682 150063146 235962258 999733397 38844095 256689189 759810318 656158183 895196825 404528511 199048506 836642718 287216973 22028671 779705533 555911167 485403980 886281270 586637582 506487845 447549585 422607555 922800669 97863313 283051315 591710571 981696552 895720116 495574439 224657386 762791675 143937013 402879931 242814572 496835358 417446174 890779566 862044060 96550831 972188149 644053993 499647800 134893736 961816115 93884758 984968422 214653525 112363975 918700541 983850096 566213591 710631686 223016274 551234770 999792277 771738721 912021628 352705967 292355027 211567059 956285372 507380946 610714769 337182937 501876006 712357632 416167483 608569148 136986130 214258302 60833621 267115427 323787505 347121264 920533607 719217667 450630724 142544482 123448969 778419122 72786308 42124397 278255019 549693715 403827055 469629572 794085051 794324768 191309570 496794703 338151444 608071555 460465467 77830003 327167223 934206905 340828761 339384113 857400077 91606537 502231059 885165574 69075194 879111264 550941147 203406970 975867093 295409255 225359250 88131227 223736626 706294128 153136272 828722899 245003948 512347911 137515843 109865231 188572550 918280373 467618719 510782799 310846236 193345705 710881951 757606203 809561180 800820097 167654930 392553932 924942427 461082459 254961747 431439000 28516928 601839573 385172680 910635757 907067341 8734817 601063966 41865011 738148361 456837374 935258649 133452498 40224609 365582771 712598557 261821759 32194091 749450651 598430861 860108537 712496633 163874370 393818860 538582072 94059168 822399476 829056358 631048232 590268319 755678377 543704130 412509217 97103149 575709215 71598752 359228194 873587905 635449159 497964630 184387563 166473338 354888431 824188460 513473005 371899080 21595664 454887013 874786010 204853232 217202701 600790843 277111623 488576227 417721710 995955117 912624383 658557339 905182543 855424677 132905233 646894330 79102244 87295362 829678256 200883127 476614758 341350973 181256952 311147913 842363916 573356714 94941455 884818039 53607585 121447206 686118741 192322905 242359997 86146857 352870578 230097123 359774303 866061684 566196550 967298128 734808982 220675624 80688731 105689591 117068983 175629848 403280225 690799401 379769451 673036668 599058691 910711253 155187310 480659404 477954170 385425079 346286943 96463641 596495776 668093502 842159155 49114093 312170137 280973326 472183114 547216452 856162806 921802238 242776986 917827245 843566581 625471603 241536369 34992453 349257256 809231156 859114588 579452727 877470066 7873576 69129258 816340692 629912538 895748279 849491304 232979339 145034020 430228820 485909747 138540642 565116294 429676371 301434170 926311174 97464581 188012426 125660710 358856950 679728653 685502490 519190555 838247721 820057259 832646807 553279488 47718626 555374375 660642790 52011471 987364526 492526163 37096575 982476230 576177690 709300603 911130147 227919862 942458119 184051754 616249594 827472677 11616849 302068382 100355915 385162816 278187330 44195002 120172454 905127346 502464031 71782555 915536216 958324693 212324562 661175214 885602468 420331394 880182290 831413436 297105919 77587076 962303948 836664339 729980416 40503008 288577689 585531481 691149107 553760550 135087588 882742548 534577354 902712023 153902510 343994310 444518595 475522200 449886372 109203161 395581355 643187989 266517161 604238221 205309015 497471454 247462598 999471209 831047448 810466099 607853151 15961988 513793352 816737073 578462154 548931990 932897898 65429954 591250504 123265550 467236492 73179389 340671528 438794615 496085204 141005032 166437200 20170719 852623758 519481489 381811117 493147333 948829196 308732552 476692766 799738697 983916925 210747614 939335074 482033599 682192893 59363637 705045158 727604555 707003514 662255016 538218335 63318993 962221582 725041911 286076795 579749364 53634156 977966708 589379371 624785546 323197411 303000380 767171582 83114631 369442608 730357610 564535911 184141838 129096436 553125578 442708797 556391073 838299608 576527232 666412928 856483319 224750685 545552817 984711774 772937015 16696577 81207336 657690207 718571207 102334550 694124124 571780499 332810754 614978109 863641297 705931345 753532676 4476460 843570209 980283371 938272995 396917246 455212864 751092133 642209213 390795478 261798436 198162258 586001439 105353676 580052623 141067988 491637570 355364649 288958293 934370039 752365644 971374352 508766662 465125860 858481882 702771156 909682962 903682541 123445 407110884 998281611 757672468 8815560 440019226 1321781 430252870 80923708 509820645 329975702 637040636 504881994 263636023 466479513 362618282 635565862 963165427 857771275 150675432 520503374 500028295 749839895 529832017 96347367 695869156 816787228 526941347 968852457 11646516 181141522 668502679 609391920 191865636 746196271 173066626 303572602 43576514 730447055 877311513 947421940 928236980 362063789 873429253 395834636 275770775 207428375 390885634 55090519 496165527 86670314 605705946 922358442 94110701 354297045 823145755 521097804 967407609 658987782 760270878 542940371 536636930 733309306 171539327 935657807 336556433 119551361 577365230 621763900 882646584 205648453 128358836 27019774 542161522 400507832 827539684 998140924 74178614 494477669 176230775 496533629 377235471 367548072 119437592 64394312 57021483 924656502 227244280 290599229 864027529 418202544 198496027 690462460 796102092 178049280 985620806 757003991 752826123 517901797 491581336 102982573 728300463 404308996 828878164 257609752 536282724 365956103 655132129 779202900 848247953 813710605 60708831 579372203 678222288 625173144 92590443 367963291 276485620 703670733 888425802 908917029 266995254 748508822 710601892 392975068 863629886 176234237 347755941 316458616 764235205 886319476 148739250 355103406 191630168 219865452 699596244 497736838 575200255 166850367 663148132 948421496 732446977 901061298 154597373 759062707 422482636 664641574 606171063 234300572 333073945 247648095 683497778 316861989 224453164 222132536 468043004 558839609 582147852 475717553 758529355 323465632 129146262 402393438 625987028 636142545 546271879 481593474 448579221 651060436 203302707 701071194 31095135 707742078 836402197 19472040 433025673 477365016 262250859 540776750 265630232 593003970 316048039 262992029 305364207 749326689 878830334 41895447 380458046 581085585 105098995 171448196 622733630 190970300 139140187 371480697 513943979 326186711 936818988 967344350 599502619 935790579 855032313 724916609 685373444 425491407 954494898 197246178 89106548 215729659 303604510 77150676 106852690 543446977 3220921 812069739 911538465 626035643 625302071 475155751 285986382 904926600 299064334 515590013 716437048 32006961 383839281 706629024 242041397 476382268 436850014 282248705 18386731 528631822 266271692 223064021 233248773 449104512 43652042 316654468 434327582 63382083 777226810 488814099 922969569 61295436 593934223