2087 814399377 708264783 41359014 831042937 159244959 942865422 889458964 443215498 239765122 70962709 985417829 989269411 627703782 865522230 161436724 834625215 840581032 924193402 703631653 758901437 861859413 173955301 394326015 280403329 333432090 769133242 527602189 310323276 83401195 241113968 167451193 739837555 998566763 762341387 16484964 568084160 220986077 941240750 131024960 178937551 563869053 383904160 423080122 801655377 392223160 18938698 490834705 446864676 795248025 906694258 734918863 539084078 85895350 115040826 245050248 215660413 801114337 612224698 471974641 469752857 635973482 58275002 861998362 273016480 575449261 584715266 710748349 62978048 18984212 443667672 203774378 232948164 415232518 219117834 439104187 368764042 209797772 716373117 956443196 981893307 353901484 985506651 314451204 752405709 988321810 899595411 804984999 941367493 26592942 577115266 542479760 249589961 978106782 589930859 801269528 906538427 65646298 325032179 640466456 698556103 701069308 456542328 32438434 372399315 199342841 516709781 655245921 574839944 833005737 547653743 816998590 581040392 439780202 555456348 77468401 756773657 405785843 152963373 279211700 118945856 680295991 187675561 207096624 313774139 672449931 59651354 884595462 465980520 420527970 667509987 466959946 46820825 795619674 57730985 345155909 6437981 187595988 651956666 489873164 582841199 129705513 95678530 906736444 366046753 506652732 769583887 838829962 189931496 984390533 77597449 128863936 796110906 712920966 485348161 39289073 834818374 626158358 523450622 201055123 283103915 931855844 405462919 367406712 731265771 739423657 390276942 784099744 498013724 836681144 125015603 379053045 424668204 933618520 15542027 614024532 671129748 586781927 757495273 578556173 52435315 461478792 892261756 71598460 333962605 835420410 938566758 727903832 210395934 655621628 771367980 528383372 501206026 565019111 732846635 386252691 430087797 65668926 161447018 461597216 744734708 169470325 131530009 958187191 135923851 28271334 813655582 13366023 717859393 791884838 689225421 979933109 904783774 202533371 388382606 73732704 999645730 981926954 567217764 16604926 395502715 999039467 536032533 824378177 724953674 947889766 933396488 387074222 446350943 492782364 82738641 477380678 848195079 775495181 397647411 748960761 449406301 788119682 964725169 315638245 547786450 663861210 729233982 664259383 235263537 188845813 237116267 99797714 736477794 477232250 702580511 898480024 414420103 207404395 506492683 712074678 789502082 498221663 593059144 949354293 970330480 117248979 843595643 594217579 923807964 53666942 417106681 507071715 409632919 948312182 280525070 636036365 367053012 261441205 463693576 516729191 615361668 593480363 436942134 762137305 530077292 12174055 102038593 314739554 397985422 173686891 782415331 987282653 326340157 534057577 365941878 535240582 330067280 54079499 278275637 385251888 623681861 296721909 569262142 33823903 629612624 253211968 434849019 772290698 342239724 67426526 141659339 469195680 723189161 329784005 273537075 387522547 786837829 864391099 396826255 898954149 374377190 471971913 887692456 870861633 675968277 682564873 864819862 551930948 144770273 596559479 547737210 303304041 468468081 11363967 424737012 45820107 881954160 475948848 205457915 27718530 228309875 782247049 52653611 801382570 449246961 776070361 886567422 297969750 606732672 860732347 437962159 700779065 432661573 170668192 701814329 304980777 351349105 967137702 266177905 204353845 496825492 925210924 213896228 183337419 143450286 47000640 280279782 461000569 114868620 254373959 718131393 657360318 570466401 736684814 279165437 438615942 547579529 470462286 470275609 601978706 863739090 195782233 211983481 544545192 964813439 77500170 52965493 777123945 850892695 936626624 584588062 666715327 15617745 459763084 655513957 72081160 710322311 830381164 507587198 3558292 99415333 960095358 144331389 448301665 126569551 895388324 876173964 788417202 193818348 811826184 925770367 227938738 581133229 746544418 190243598 857547344 467180663 889002648 293170595 337801864 237767858 661364410 858597297 600257437 436230474 710499397 342114906 858376938 480528869 111422295 214976998 128739902 821698612 398792722 580871740 601869129 765302061 778172552 908938449 687584385 555571323 533509567 606341064 58175240 369224665 691280612 32695194 93981068 692131191 30080662 643539084 292464860 660227539 380442545 367157474 131884932 217650169 882445216 647388196 812904193 727465716 220121753 907575066 530671455 818590714 40617696 962767380 20202765 549175462 544396153 431498919 189714182 962740763 827886928 939735864 88005228 359466787 104403025 864486053 288652481 504488219 350782544 728363783 777388045 540610562 318071623 712764740 506650483 741793099 866889690 50524984 210117744 596942641 647158828 77712377 190484900 664934291 967555957 987254076 478110776 177727663 7940778 920607610 299508661 687313571 700405173 755825609 877695508 637532119 402674855 869515861 621170293 100612048 764859814 237248519 344036321 814255113 28205498 259334119 465327096 885391585 292237981 814905986 949870161 825272026 426190736 724129160 325565822 310658946 514825393 855885041 809557415 77297456 849628159 78418090 252589472 579607036 315668682 958843601 377867851 168099487 588206519 93725352 918857823 103038902 544487912 100192134 830825350 708685736 650231838 105941353 202382529 422503923 98502723 688009140 2702997 863276480 699926365 455411761 831972721 961949630 680811537 266992416 587636421 586961589 441914384 161523329 351360933 843800507 508655951 797629592 11487651 295153797 184936674 974729492 678730249 147861685 451012133 467524476 23051043 461336428 541185397 372109077 456550076 857023294 621839197 44021224 686884779 612689999 156744832 472881000 876158019 246455176 78338700 619209923 635479260 45008504 75750288 441182928 41792542 120101840 763651685 533491619 933774079 94187085 134990012 940556376 539894283 249687120 681320134 754016038 694008596 474535214 364584348 117542403 56267245 742446539 833422150 2492244 180563348 88119890 943435873 24157593 256145323 104334280 36598540 69897774 69154272 581571895 466377915 974658942 456286601 824238407 349121961 303195134 65601804 270421294 858685549 75410550 635512532 679649392 276634464 330777081 817609022 901664408 253442789 919889465 672967446 699350601 716383559 217842869 499378477 956877540 781148145 793409121 456604682 751706126 920645253 334471123 325309903 650330151 549327600 420498632 821533495 998403360 428799227 257663666 52101463 37947129 295161479 470770494 615674102 337176759 365639128 149225412 595760715 369073716 305526682 125309278 156952382 507709737 405941549 170842959 996997447 242514312 70666158 12864382 522956182 113413515 484433429 808602294 405770132 133642207 939875923 227747799 622260689 965376259 125494319 921062955 115089379 869664302 54000786 700616236 758595170 585434406 749642491 827437139 78833817 746305584 42512107 72805638 59035580 937071166 904853671 883259485 980206426 848588212 80619395 633508705 945829792 472997753 310106717 314610278 841259430 626016020 735372942 686624607 657027496 182854602 163999325 156442933 829927434 220038056 287709322 513944539 945414529 598148404 908642929 405364573 742664599 541429857 720159114 502617967 966909937 449890527 902606755 972096585 194290740 624729996 654022828 788480603 248807190 886843124 718204426 852149375 266185753 464804241 503618717 260096088 607686209 12904729 466297366 124432359 675197309 409582648 740959657 714830016 161020357 775422039 235369351 921184796 734090404 364707470 618001093 837888987 11027541 140659381 598645018 258530514 764540126 28909681 143385656 661088125 894965135 386469747 629151060 216449803 668971089 741316254 130617646 635411262 337380577 221309580 533923357 498026033 392799823 166804077 125179178 846662513 890001451 855315732 306899427 214637963 614840838 39319767 947927785 792247155 29502592 533775323 969278372 290246783 436662615 666845488 912120310 876968245 264153961 478348810 104027534 460844599 144799984 638640646 199287420 335042365 276462704 528366554 964165829 206143203 748875577 217474979 144124924 605777411 908374190 262018694 608539344 59316887 943422787 590981002 989638614 690913252 997095546 739349880 271271005 993221754 270067299 480938629 904299822 97948979 215750607 699965449 833299790 251105044 533416542 154349023 852817176 319029190 670758149 890237255 457286139 731371265 337939890 410764891 360540080 816757386 860957653 398052726 877467941 948996872 261606643 300488496 678950342 107499764 810738700 855217090 752857404 260631687 939274598 676235609 378327315 939544137 775969190 113110076 90448264 421415400 45903538 511754464 604317848 860443780 974277415 604730840 41406836 953501814 975385082 743672515 907147207 57108497 604908365 955685712 852407770 509899410 776404370 895904185 8437353 888519729 915167678 954720993 33895001 516688400 596768503 54135116 706868463 812530242 209695568 321151236 59362683 122365371 250632843 990014307 125758489 489858420 913493920 72895714 564235514 590277559 99286842 640438932 830766748 468688135 771490754 351769001 487845604 590741445 719979139 335808283 551180708 544856089 112462789 457019948 171075325 22504806 422043524 939123496 389580344 362335817 801220577 347397036 174739280 159734368 102487145 426300886 431580474 116422904 179257105 146557629 921859587 130714499 970507122 169604760 589871791 891785711 489499805 923975397 369440210 713636020 997404630 467226961 948329100 415080079 71451224 100886714 368026233 204709961 550967335 265486063 592327570 474115165 748621928 176406710 65565860 68431946 915058504 674766418 666715968 996531719 740445826 10063398 497690629 712923117 703435005 113030028 241444355 687161207 838341649 738802139 404474075 546448611 925322062 149506064 614867458 76415114 27816643 586961505 445826703 135771712 524604009 137533245 589719961 133372482 525348906 236263434 980751840 653869047 44597607 230204875 904679209 169949821 755415146 104660313 921320243 622008000 993451282 371163497 597823737 275097044 775204754 390641389 970122593 227625952 617289253 271576776 766026537 565880090 185577661 976765688 246628149 222705032 470582402 461058242 762924111 753795546 264378653 326200662 636530216 863799280 84873222 857204106 322226945 137245594 867511080 199540782 899399517 673318221 677395058 176323173 180320743 370507881 644657423 225146022 907828577 293774401 282466480 505955132 92891171 315700049 442645825 151679341 992181854 297907578 143173514 910906512 936960812 683631359 791457490 439873836 488053963 454299588 832478533 326103707 621950078 811072289 102163494 626189263 645946125 261586450 720741634 125219166 869237355 280076096 165863601 223722825 593270228 718658198 965110783 894208739 719382297 867593981 149656925 359271607 135098505 596389144 335193701 87162831 76116959 136163474 882528653 656105767 950847850 821219064 807181976 888673453 794013712 49172712 233300548 327124351 955229926 82907448 286249700 131217268 269203963 488815720 219785436 507493898 799949685 769389177 306211768 929054345 169689154 292996702 238032820 435530098 190789829 489844039 138779343 335850745 525482503 149950982 333057067 717992585 805617462 220698995 862109240 850102502 131905193 164591306 411046328 60852988 320146074 585704837 372050563 359857165 963110147 325043255 885041462 938171895 874395096 71673885 811118663 781118376 672740638 662653862 893056762 189276520 79997194 384164570 162819231 671583235 44224138 603335451 832862112 204345667 964300572 367842913 614199612 92224456 507993187 439169638 990454457 594251696 635256696 266917168 29054201 784996517 860066839 596870995 267069153 874917571 605527036 171209038 144578551 606909657 495553357 78547545 434980450 652572989 271088115 401538435 554525021 443812241 503275049 230391963 673081361 144479414 924919441 27185324 444329183 944926999 402895671 655968952 736897149 658586485 596763982 449962043 314218617 550795591 850608127 783381464 973869884 972678098 33459789 163788517 498005943 168619859 894870589 53184097 657055245 372540364 222218181 275875383 287823442 682021563 999581423 754173703 936698085 178718068 303902631 400432830 918597009 255730549 253299536 374515637 979796579 874719637 108132749 561931748 573837668 969762688 530463946 33785622 78968603 800646302 273247991 503707877 874360173 204960652 981939177 752067546 174838908 900394689 858822781 927933053 933658312 877633427 847752918 947826739 242943679 754674004 696942526 965492610 984068883 323218678 255001634 752551137 120788305 764252220 795724425 786693850 714050470 84712204 545270396 694458900 3682927 864488414 57239430 582499904 929217494 216494922 775298224 197059801 223119779 149436889 220714269 720328838 415980584 536603474 624378775 950459124 759285056 763157838 351148797 609864558 91496834 416621478 330796572 222726710 909888683 204115000 458026822 835757694 808883990 375527474 100707875 459411803 410051873 886386489 760295818 84388309 402174804 501315969 889680599 760772185 560412296 848422025 735289977 633529129 105406980 148926966 277842042 877857458 758541700 571436990 654305154 415273727 818613909 670103403 937431600 996419294 497637651 504588784 427361091 736954307 448293240 898839995 639454480 100441568 385043585 924424276 568363016 779810054 458025239 121409253 831420538 716116720 492878190 562174813 294383651 576028275 520455802 636113860 836966720 692950702 816868714 501108201 726611103 579730208 317438488 473121654 467032746 681384313 419437651 615838879 427244192 465933870 805033141 666982487 110997318 584126340 139796340 390546229 472002656 677087473 818338309 196885918 600815437 398347171 572573422 871217129 795845705 121283832 876949119 679811122 364026277 170078285 182022274 902871400 457206365 191003574 751736984 325517041 173821498 766660937 66354817 830897557 787246374 47595415 959934736 211010811 653684583 885467677 2206882 928239285 610385812 65268831 282248079 431337439 689757254 808882055 100793259 464426198 263423680 72807604 925289934 376116130 72721118 893872616 830451854 691082572 406260797 84211882 599441732 553629031 414662777 17898271 126230381 61147138 123663211 499911367 366329884 940251105 384301287 320063414 364518323 715033505 264979875 657424363 809256145 939627378 839097320 249298347 553981882 725473891 410481984 772782722 966914173 334847197 901065572 760600392 402478219 6359805 124949192 873869406 263059932 529289378 703768437 406451506 992703378 577947977 400385833 815481740 739096161 271962415 901553268 20099125 366733957 473912087 684563509 929645805 140257608 587295519 554540021 780523830 421492125 63867732 466883336 927031580 72129329 211020588 893719210 610219025 313863595 306563766 332106593 62000822 790653703 452232722 767407930 370654429 798735727 76343388 856089028 941174126 279850201 801910101 746704597 856436090 27898808 741628872 961482265 327635703 723501680 491961717 877864465 125591820 260721000 304681959 437059328 675414183 205099849 262784458 439807111 555602340 233553833 640415859 168518486 924114043 111815242 759370353 476494492 304689113 904841732 995266774 578903232 912683843 548743562 352750599 25857744 983623224 947396141 412285326 58011149 12405771 562957686 300823339 335033214 407462232 834565698 648902113 125635064 166421584 931763211 63008505 88005131 391509617 460237313 967929175 431116971 208416007 1358174 302618180 160867458 815616288 2651297 264590367 114507783 27064148 807293741 954455982 176017688 41224652 512625674 537063451 44930082 115183793 456045888 374747626 431244561 843050724 406879376 915573364 923973501 143365198 409626915 563580350 92671542 319772573 824295052 6940401 188544055 533460579 765766959 766356671 90968977 265133974 637807777 990964341 293735460 975637712 41271110 39007217 263634223 173502110 869396350 32534145 304164253 799289296 519998844 907873205 342419364 292547154 112526836 619975700 335064607 426071067 984789772 777780777 498853824 661346848 743273553 804953679 623436607 470727433 863409761 432908979 367638143 594018463 304681070 428033550 899954310 759036798 360977718 68222704 618338821 212514866 629527549 130308773 746311878 967889470 113274964 302975199 413533941 725078219 31546219 138105491 777076833 5183445 152933888 185129353 408178455 778535350 69232262 359524691 950541478 967879127 233376602 906096387 839678135 895254286 885653577 25970499 91969352 646506465 80556100 709918605 349815285 534203994 751109650 86817473 624109067 120400683 612162316 680750262 970253519 952854287 917997753 375453826 533455578 106781549 500743575 206422558 85429765 702790837 636297322 413303789 993330106 274638429 780682593 879098205 580098176 732581532 282936479 622862030 791669141 406309957 274072555 223299029 193421557 453772515 49534177 294037876 400952895 726476753 936207905 439257996 254468055 220885151 313982445 325395071 9906520 227913251 444561979 827409157 424433962 428534976 920176288 929003145 993858318 641727429 289632190 138940572 399216698 948850159 553048319 193706606 540570517 342128533 362122018 934895716 858624488 521127070 765276563 72844309 752588537 300287622 178614070 519839212 817283645 542309992 425375820 714785733 374757445 927700660 731413959 901238173 364423578 849271079 309055780 512333291 842618432 275699985 284166867 445843675 401024129 730918154 824923935 561091235 761487240 949441745 698190479 22890255 86719725 117439737 126503700 226918119 77736264 867121089 246260183 220336464 540176296 121147844 731708099 867301389 684352801 380230544 477116561 117908446 722983145 719168692 60924271 123340955 915806849 905949690 815957766 973156144 450425590 708208867 29370569 138387311 596085594 713040034 926088532 990189911 67890118 812546370 578538106 23391505 456274537 664392560 804626287 410464503 582737566 20262482 393590786 212799225 665004811 430001681 679584054 375013901 7179448 334481362 772314192 109605195 272784827 864892845 395891051 597656430 464764081 364736553 385628974 946345161 271615517 515193389 473333534 392313054 966959937 693920845 877859720 139409265 286471856 249254415 649832198 776449594 600712473 965779029 257851886 474560042 343411554 375631301 708657139 527061899 550644828 276600024 455645669 424934542 451777251 917990574 457600530 113605811 68603061 926046783 258496313 692929520 261445286 35341644 519868293 80353580 14473141 429444163 839493766 753255673 654914468 522708478 310152223 646073732 397404459 569866147 490777434 286269002 720540361 154085826 172790988 986250960 875874390 47695175 15366726 607667035 267134982 947788215 233385969 841447489 947008789 66587762 766865516 3107423 866010337 543353214 303331922 81012365 429646040 337466396 152631366 450796010 496299168 653050849 981279005 30029451 873714699 774663146 214101189 382937621 729002154 476111444 578355728 570317682 283358369 180151144 210400528 899282668 19060243 481316230 179045638 435987790 970019872 900225125 412651102 902511070 449536022 450475670 90373120 972969197 731577148 744193116 703543714 268828510 742971254 3721650 706662222 140086476 672122277 521095205 411626770 823990412 999725365 81166296 88976131 456017867 795113494 473701924 90657161 777012653 306932528 680848804 705050179 780562205 719431360 892343788 702984305 181326612 13472300 815596553 329514986 594123087 30407316 947301457 627060830 355103836 811424185 172279210 999180322 857776447 862640334 781090739 76046180 557457680 307197445 317412299 958974992 694287569 917878683 745232962 778796168 754203793 782516105 193152427 681515563 373107364 491966527 324848200 829265766 495272860 934846585 641960877 956099437 965580249 256338907 334316074 2506691 306098562 526712572 627772701 717497787 368255475 932812042 65564877 427476044 155571736 299282330 460725415 178232752 233116719 405156378 253171483 473773994 690615490 985888072 867725307 808584976 756121736 251843895 532959636 611843566 909347883 745026080 727143072 468000499 384601646 909893532 919487928 581449479 145882381 146578393 990730002 659314865 695269620 563825444 9567304 860576973 896546777 527647437 97714207 204185435 370374426 288905592 283631122 591321118 161571773 925466415 810092032 414520960 527969147 786586613 474670336 106891222 171498161 113016083 377711520 418172203 60224555 147887819 370679544 496418527 660057437 576870985 920202448 451782928 618246287 401113999 600888608 808737963 527035305 190071415 796824786 652688527 930626375 277330605 714713275 729374460 269302697 22311749 97087815 68841363 65774960 359544262 138757391 561053406 866006341 586065906 235397513 288658963 539838267 634124168 850968656 703326052 349134177 678042023 549981894 845520434 281108135 687157263 6366544 210741955 709800197 662410250 347074660 571566406 425102519 425501338 715536187 619573444 492351374 406720355 219164576 140818825 436386156 792292356 592794032 925203023 181649834 917361207 95160812 794628011 237076666 710248870 953461107 852235591 802882573 963781279 358038945 510005429 858072219 453677358 221894131 163817282 727028158 987910927 828694123 305547752 595455001 540196473 976202997 367474460 546616052 44000088 799335069 174813841 286097233 134266674 699071067 884183307 268311322 356904368 252921031 417011632 123740567 649859030 585694079 848721240 907931684 191577996 795836409 382949172 502869659 705168434 142257096 922282196 152987832 982135717 377216498 295067694 320786592 708902493 23166300 214449649 688715245 671679566 372888389 611731212 529085076 70604880 854823515 585347758 993003419 258272935 413858893 344277146 400311076 214588116 781285755 429458124 954554632 942863929 245095553 952079950 565585532 729929877 746614251 158320212 806105247 787251324 967478836 516638162 790349235 686064550 51399468 689744617 995175934 183943482 538358034 883314308 9187365 946046197 561049383 108757811 3027687 498702356 979186450 436903127 511519400 406107282 964578179 929812882 400200853 845602358 67522345 309516270 565305187 361297416 820336846 298239021 301413511 193701528 507793256 795994717 839597365 420637334 606252190 582250477 359919322 124467828 943384024 848663985 191691403 553861864 429458177 503356823 411708752 245283417 678832702 810667404 934295728 396089563 575990716 182343201 744484849 830868519 9256766 140728653 421792359 274663596 548058609 14905007 821205582 665897227 634603043 177581962 776235825 299686451 630090333 507098265 724248499 530511657 736488163 228458410 372100755 346235899 527128805 558550010 258194338 435328675 347195054 780728015 640679211 911259548 452969991 480532261 606675310 990275352 805425402 276989931 448842113 210686311 275413923 524792763 190993178 858213459 335387458 210259645 356446726 321514223 282134447 835289630 990165990 590977663 219118098 560032663 271876717 305914890 469502831 76617200 496906244 718842739 682847209 784906406 398115487 912791101 494215816 681273470 922995299 105987675 923464522 635995817 331252906 53858560 621850361 178316726 740830380 933583322 337760468 916904902 686708723 85742818 907225162 124522287 76824498 706069370 507500084 85878791 605761180 10979020 970358411 120636273 63714017 39087286 183726377 745528217 497934579 650882744 179348168 478986141 788716132 140778639 521163724 223343281 912012883 235636834 509429172 66898534 610774456 923317235 451158278 418044813 339551836 291704041 864748796 439905365 896294864 935361107 714116008 279566273 416844666 87432342 457021282 623079344 214555150 327743993 296394281 22540584 768672191 637367629 422203789 417109305 764934822 842017352 912741410 377048006 218902186 612209339 557501523 400688302 35510369 935192672 96895856 558370785 99339758 377747985 700753045 973197821 716092778 316410028 760667922 175251074 713032055 147545144 591472837 633347502 609931310 375860937 153715961 121384971 38156014 161028608 373380662 719456847 965414726 994682064 827335013 492267455 568735295 746170528 325813370 624924221 394288718 105827779 878360968 523013806 447244838 839198067 483132591 360820072 691507394 760236850 133166341 220619544 90997874 527994445 735886046 187200039 725211345 933419476 30114626 295689279 732223866 488766209 455483691 157181608 533188581 565413580 76426895 307416512 777663205 819737241 15029444 550879509 577255147 5070444 263282829 895915843 522432194 558402593 564514490 891976753 600827352 983356026 429981222 643656065 808824158 703094 294640162 466067794 349898243 848615563 820245217 680822705 120079921 438493607 144095811 756087956 348113002 181850218 460952338 322509531 768037219 914957911 55873643 463630163 143957914 481525567 789861010 819834881 918544856 970131878 380844089 49860241 348898419 975275016 617100650 283945728 527419273 25777727 289529887 902277214 872220495 658176364 937788144 47189386 779777713 900548566 815282946 119734112 715147685 930202278 657569901 362746346 611552117 223721872 261217911 663348480 142831762 867816266 857827818 75374290 805803783 986119473 889828201 514041982 477080272 139696033 507862595 677249462 867369655 489155177 119855024 546447555 228490050 421639303 922438696 120833851 507769512 978709126 128512780 976329731 175372441 923308593 47545842 426863495 578985904 63316727 787513346 171062244 601442078 956453702 767421412 717171585 754781542 271290232 377415356 383470684 998432622 225816642 533245279 120120335 577935772 40607386 944499074 367382072 656494160 133872109 769861061 527863918 401152977 249583068 15655756 989033134 590908595 992062956 304611444 243968674 436230163 455904136 494732538 447342994 872446441 103804880 465963884 585025741 922796924 348779105 324791047 517770237 132709128 719176980 737683516 527927246 250642628 189312179 556350395 428095888 104355280 467823576 366438749 676520682 311719246 188566692 262379131 757453557 959361992 57560601 513956148 665551587 476489078 274610736 242907018 330748189 828827267 80568199 366965061 629451748 470217219 285561445 782119289 49279775 436062399 595819088 897958113 67459799 510734858 283758467 394640671 130159607 12646422 343264132 740651708 82416366 761809088 89492799 229624639 167951763 502405641 631131559 218010108 340917757 286891539 684949703 735427676 12058286 959689757 845987976 720939545 853950747 574311285 848908557 322631738 637273395 196601805 586525090 497050313 364577875 930706249 194192692 22716925 113080402 283132830 361359288 265688697 172649713 180939345 697351040 787255797 546944528 96715112 347162886 721548823 836546790 94211593 622308352 846584682 19073039 459012856 272861766 149129902 921874856 535853721 17252630 313652657 458709954 654264012 804371489 765780039 569844604 846072717 639593242 767441863 570022474 484438698 668586448 97949240 111159906 498785010 126256255 141714435 270367383 695435111 416680131 700910226 152961150 143308387 671601453 74169496 647008632 694612210 736500479 953198720 310031920 510718023 87633585 545442639 11798730 86354941 498980231 867405252 645006387 799325824 240694805 203536818 256124160 352540932 22362785 467700176 29898829 844785970 155872839 99022598 843020831 323876657 180642247 374002231 153796195 800040612 128433335 781398059 817036363 818702445 308891737 718890413 418009554 950213866 912719899 460976800 208609401 500820993 868224092 488768454 642659940 818528524 943621213 475836508 184895557 827995478 235242958 161763285 719253982 169335900 545651560 614818734 40467402 63774229 765161914 420928631 584019090 533678877 723145250 960935180 49631084 261946640 66043713 50172535 810990784 337071095 258913188 92391743 865783955 927698314 142774144 482537902 318001826 782031412 692534820 726629164 296701020 851257019 223388345 674180451 682050603 782703952 199903601 52470785 884583214 14579516 372943311 922316819 100346666 261842449 778002334 340361021 937180613 179335332 383367387 889170588 694853407 967201436 690265561 33821719 12460620 441039118 605130653 698827790 834699504 476121856 980705227 906296793 416006785 202530252 599341260 949053090 125285883 911172640 467046501 33052616 772641687 966670559 618789909 683093205 775716225 247465112 18240450 274492611 799832998 227840021 569668122 828397860 337095568 786126838 505225736 429662407 933083291 286657059 215508153 138666452 101797607 510486522 597631454 813018354 882996934 38913982 117648073 25583845 111578112 455013800 62004103 81474613 969324202 475806619 442508040 536475438 137284307 308860463 701029535 679966123 273813335 929826068 881539480 805752369 145580688 362057369 157842977 920492460 69524872 633825879 524607450 352935001 973866882 709884791 942587329 326563777 547197961 81466606 775428709 840413852 799143018 29455730 55486845 830307412 481531491 509965786 998462769 277368203 136155684 380507364 810340447 808272943 92654271 318291787 472232067 238138359 256087709 507760972 674833514 792774823 86337095 230696307 100866642 400917540 929521865 183828940 217368834 115862479 209580335 69606444 34622913 153822482 437336995 364894427 949706736 418450515 155377265 858133677 544465060 665215444 498606292 785721401 314292905 315819941 769981130 486582995 293904055 898106573 408183741 665897403 675556597 933514151 361101443 479886265 214404241 220535800 653962061 367594087 899374205 62504415 403165369 63836981 420197332 35203643 709678301 742810919 28286383 749036514 968793394 414971979 881709086 39843415 746412583 25576547 36773405 327000331 680358570 716192952 449539640 978071522 448771371 775986993 347269921 828680470 461995693 822645034 63501884 832642151 715736555 483426676 976221422 71365960 307380134 927676722 464760241 653334411 234702627 11581039 330494130 870579251 2455003 368223603 830192096 897430162 485063778 612617317 584319052 709199443 709150707 148541422 602812793 792351448 266096977 902977677 391562900 814652126 292189739 626817777 232496451 363530053 270647208 638345890 544849560 911024302 593598672 867137744 759027624 435302363 200106484 755880354 413879046 949470999 986106109 441384092 454899 453331842 822074368 929040002 116386120 314978678 186535463 173448651 42498575 867865114 237749144 803980321 910920060 418424187 713848367 75937786 581715551 831494733 819907144 552885133 513804842 182939563 390651767 606154904 125341360 853159370 411759960 718928674 924271164 16821214 883238804 331750177 438559091 312349279 755539870 972917388 922389709 844686730 917111489 100089296 541912127 501284663 386452135 870765531 280868164 990190283 824793158 598140358 130356348 40053487 282241121 471547882 47091958 538982489 148765747 323940879 616828629 103459814 931102661 205961026 691037995 977488764 46737068 847332445 604748998 507028656 623396818 288855458 584226803 249899931 780104655 857161558 957381497 322975298 451713314 218709863 138839745 998218855 728584934 205690212 628194343 461023354 639788088 48693657 58464050 987223035 910553666 347120898 348106057 890508163 289298605 629961997 409446783 965958722 672803935 501553410 888877512 800947738 713327109 707326916 77309267 748093010 33710104 570678092 676784413 599362031 367106235 365189952 492178045 257836084 156856433 4863669 948027656 592570277 337165294 456061959 895255027 201165026 288769863 802664541 781685010 905958269 161567742 950120529 776208814 251101244 945335143 474158223 317243596 884970949 314317937 295683307 443921256 285837797 898617107 388667603 771088980 768770666 992189361 430574131 530177618 430971358 176893646 806849657 444102787 426550110 806229229 794282977 692786693 788460463 808811131 859707711 901292032 123486186 499574565 765809550 297847915 781903746 875635945 420617586 750929896 991169757 297073368 466827958 306923758 271684481 334260637 410950326 230524202 990986631 591857919 163978421 399970395 85427230 99041529 91950660 446928437 138354934 514318694 992295834 366256804 388762308 938383065 97152787 204699834 122322065 21472926 48499348 381763821 962755034 554531526 341798611 153060693 565641575 534877092 107567396 304533574 193651215 896174394 439884980 1249403 580856365 634449779 293321310 788931199 922231045 126190321 933225938 872298349 61800551 290185773 318476554 450485551 567827246 151273643 96602611 401659296 556234409 760360168 66270689 170399254 746154210 473717031 360874181 679888540 113244096 798480597 146793635 151030933 914812872 147084451 155759787 446611570 387061954 554891855 635389924 806108068 660091914 455491928 605884362 51106652 951607685 811081622 912321321 449095710 565709297 914371707 191349615 923075473 579340221 448321292 397973095 697837130 568532461 126488820 904325763 254002462 338618163 899350255 234851515 224045553 861174442 731665516 972149647 11919238 472987397 895739912 937260334 51896013 150288825 892663332 345914128 505817644 624759112 41163398 753296363 523068457 189061780 263362781 381982703 654954641 502148020 339793064 495023874 817264782 909291075 259434010 535397196 374690622 245186409 642852434 497080667 95914835 888923508 696593288 880532710 2330116 383274442 56215125 413770952 119006153 827973490 172301909 841598169 221560230 21300996 173445412 151999477 352885170 963456604 391819565 368196885 643412647 275674146 543164663 461734057 102212527 135064712 982599791 513400102 117172281 515300263 281490394 950833237 549660224 773835121 441849339 179576001 682708061 53750144 63367869 544288372 221884758 197467550 108308211 382762830 170140545 99975374 264975108 196852284 294321967 380512349 479144471 71023056 570333191 507924736 89807215 618108690 988103938 296970422 912725452 752022470 787430299 694158792 314640820 766002390 95945359 316408368 976351821 329916075 121653934 614276406 356149829 755461922 26289546 303115826 455688169 239142189 637118144 368416438 951053765 414623002 662756771 258992434 249419448 90958086 93622307 582066728 338417102 752536471 305895029 743033801 841097843 493803433 722841023 984077979 810846308 879408139 154348353 30091213 693087562 93100711 367625060 629135487 316438244 379781605 523496752 152903429 391347167 122793562 980900280 487177787 278219282 712975630 882503250 852951799 972462669 982095933 581454654 833988511 754985624 851476824 322236064 938759373 70457309 720292606 155671356 158702501 826687591 253417592 960418664 824622283 953666360 60355048 373576540 709212657 572328545 315926349 578936452 66316624 262111615 156555333 911505733 981899649 765271132 402962560 732935893 886549378 172654893 883214046 787326680 682004796 781241504 728218759 299083239 638633895 434930790 181293153 710899577 947939751 153930906 143417392 444920341 815733743 394216269 60824665 107537599 658050208 642141614 648030477 248085551 483444377 577527483 729783540 908643213 700188623 288539892 148795321 885149672 278894011 8129824 543253753 1105916 272954189 488980318 255019682 214264779 98006 170078000 246622124 693596225 238669645 315601092 907064727 967771003 440017529 978131933 882269497 224241738 905804506 508775857 546044692 398368132 613285296 448331034 876078729 289735750 647926399 179939976 285508024 34982675 99961392 785568375 691717796 530614896 589828591 995961109 885222120 950309103 862596848 136859154 310909340 927219726 924239687 262165837 628521490 319974676 506396016 567576744 699944413 866878736 116629500 909623367 843005310 352107310 151010525 634528634 612405884 814519737 306850282 473110296 599595760 686120166 981471216 802070775 300039459 597413496 168499665 999554621 27290269 347832086 990461033 573872722 864191015 39471722 318892819 755456318 651423633 346382307 854633897 794188065 187760854 834076636 156556227 745878370 147041338 789794890 543064159 278877114 527727717 389849285 306570038 963893268 237519827 366755934 145459474 932645567 391840220 836147075 535178326 146913491 675187688 772699081 185960030 821156348 294319090 598673064 402488733 638899385 378422665 988052176 238323228 907655821 897815227 590880483 957141177 975425697 72265277 946771753 524610982 53242062 389431860 699633880 373083082 303934159 442770774 568605319 992014744 571671619 758976966 989853318 908108048 369051519 43469457 616044987 155484555 68682314 47878269 183471909 929873410 989067947 207957132 153131634 517892928 418875127 56528101 476314817 39891015 405094630 157355662 942408518 411769465 7739262 589058418 989488562 505757747 726747746 800370701 880796803 164959158 962845722 584433319 904993331 715704038 427009873 706652667 49627911 947626164 244688330 354747206 177516220 100183395 909513538 149205482 6857689 539213560 473401951 431843025 652186755 393230106 897048134 876215045 511399446 875118932 734954255 785039251 39747118 24633483 785568616 432365228 196152852 122013136 286551049 577365690 168964970 727059504 415507727 627187436 907062151 826267598 512529754 157362268 476957813 201480508 577189716 383296103 280716256 383757921 394851887 688663865 8413901 270929161 40411558 986148162 266382975 468547534 673604505 16801971 302019314 415439890 661908295 452668889 496034061 289473381 250995171 156006220 797608908 511979374 16336872 238176693 197324745 858463459 118483009 87713873 543333616 76694896 981622277 320817054 651160389 669566747 748579415 613560371 660334907 292981785 29773584 734989273 996582080 756498299 744693032 655441820 898957092 713908257 793967369 248058123 533895883 836781359 943931726 918579659 384155849 480024283 951576394 532122388 576364799 407434471 278736892 813318472 634623764 584589228 867000246 18469678 641535647 885897503 610531833 40183454 723362970 734894002 299203154 652367268 899824624 420971498 59034632 180860038 192913993 324956526 673496442 80487686 149991487 788423985 634168928 959029877 633124805 418712116 823024561 831929985 236528852 679063130 553082031 586869435 156601165 654737429 663788737 119297274 829251614 723048935 311619355 203355802 461004582 323267614 438681371 627050104 93418752 106623491 43935259 868375684 352709103 8401978 342573598 191819598 132369505 159971496 32655016 373859694 463320789 683189034 898333441 319981961 378095697 525482959 392571131 261897051 683465667 142442487 509112103 223972182 548231191 564158989 908514388 958136767 36973770 883875868 786840623 980842177 14674435 773075571 878142498 60007331 162733992 216008750 631418746 489136905 712252518 579231573 187668323 421717975 464091088 488927310 861679785 295272929 808414830 323520306 178775060 543909801 855485611 876838224 635172330 457028731 456827844 643032785 9632007 401816443 686271409 818606578 151922406 760087427 295763047 855920979 853499872 43064826 1129941 749092157 816088833 841759118 745230588 883554762 820004318 717186697 368179131 524962495 246579837 311234922 729625108 516962022 480433209 357098775 907053610 146037488 808976303 520232507 29453197 606847534 222228814 929588864 293281966 657929857 712751880 297911420 253391977 326018534 162781509 249682176 698340309 462676594 423258047 386635734 996639222 222042321 951216838 658188428 673434383 2319348 545193645 235418542 651986085 475612274 634632511 656753566 373670730 743890523 910411085 912302072 880463859 729376576 219920711 792689949 722246022 169963674 910504986 719936864 636186720 550898213 145902552 264367337 384899443 447482317 917441881 822668870 855620098 113523834 500897248 82942922 972469926 809875598 978861715 664176539 588345472 396821199 881320089 884724701 837931703 743246516 996866485 499504198 882427399 514245463 761188530 952036538 812657634 123341178 882657324 526940879 43635043 275285222 27049939 136294678 468457289 589300981 102049802 259934010 560885021 280877806 212263814 479446179 324371877 313525243 516867556 383815480 215559475 163676573 490531370 624156582 734989908 860858403 226724554 606907788 313117929 543380181 19204781 15996037 951858568 590745074 463661220 744286278 697638537 637813357 125740481 219749658 88169032 670280259 599115043 643860832 784549000 634109723 495807781 935501893 474752347 284844434 641364024 347854179 35094035 467556932 244080490 885804089 393434857 564911658 948255981 937343407 661509406 996961876 686892847 963894737 390711625 59483453 50523422 640421956 511163909 811932385 994291374 288207919 758943426 822425117 230280700 424276786 155987228 68212907 835891318 577127850 988370802 808242239 307464999 163321863 550137552 401586746 174705822 136957439 947729661 734364141 361662136 548245663 914539780 500922446 529540549 237026024 897409217 697140576 277653479 647278849 109159549 529897325 411482474 228031384 369525432 729748084 85572262 425366359 679560715 768610411 22710028 137787941 697482215 162544618 275512388 652086560 868295713 304878576 287829244 107997165 76251500 2516458 265718992 618018550 968062520 881982119 667893834 606445959 399140891 553457796 133571270 371437777 856535275 977314172 305101701 618283207 782455108 99233917 337467277 144837944 792370125 546834749 207961896 120694559 996619354 716311616 319258763 379408927 879905179 550596600 632727342 494758962 799543899 432457674 542151169 180974381 457481610 438433411 85267452 711728263 479238517 212378602 249698202 753999713 773956190 618647942 545624183 335939148 275173421 914595271 780754963 61928127 462338039 125093430 376720656 850441055 263787178 838738569 111855431 259858729 230220865 959003425 883848500 236417687 732433879 2407946 247463935 281662480 229607150 513064650 697259694 189491617 683942493 64416588 663426324 25195333 251312970 873126959 685924564 252154836 834282655 322590203 736756612 282259447 425875234 943996321 689197795 828106603 768415187 869110957 659890398 987014214 875354514 514477227 158953134 407201642 172975059 554035718 210561701 311657644 130010825 265798294 679938634 869303238 468346305 300899669 933932943 192012117 742427043 114418118 143772137 241493835 286090007 40268794 460996710 227499330 823952662 188630146 675984670 254529017 614505638 36381602 705369401 846125666 15930657 844721501 855862483 956363436 257875228 169408464 111185297 427907998 676063586 215424229 927020791 190295383 874057951 662632859 617276116 466339401 698827547 246266777 836909269 288153285 885132392 108598336 425208369 165662297 231257101 240602459 827477098 157214815 275423687 929910161 244457883 759471407 736054412 935878907 663103731 365727041 874510107 282935524 474659535 123733195 634651019 40338461 973027745 722724629 147777896 447294798 810704288 710451629 365947045 775261355 507724299 446952328 670789394 460270870 228810958 208504015 529299618 485471483 6656697 226757058 573475423 701620168 555285648 459233320 725321423 213362508 236046402 586632966 761050092 847240876 993931016 52988100 528936028 625882934 999467103 960936691 814674035 570938102 890069998 96343175 493240114 817933863 831564909 500031603 39101795 530418508 362153125 994283110 286315374 827876381 699867544 644680099 813348977 234110227 388710930 887261167 911668493 344628667 582344484 404199364 132834366 359867218 117788111 233451312 454689570 234749491 255344891 504748103 90945617 718714673 202451103 354769397 400388452 809646594 644197615 133181669 781581508 385752582 231287419 681949954 336362913 377882543 18231161 989456754 449031223 21173331 485160297 899136048 452264096 347790417 590136105 858364415 196425594 278317593 982449998 985799615 931498086 543548801 410170325 350541417 448206337 360952082 922443978 889908487 172708360 417167226 361839647 387289029 474935042 832826568 207003896 881525921 695940536 863805826 683486106 501607799 384515886 66018590 518700656 431748091 47015416 965476254 676032549 401690310 407811818 383814175 508453137 1597971 802971877 938292947 15293520 767351610 699825567 32422655 495317501 183421054 470540053 664093110 886283471 927951140 473040141 198339719 491040085 149036059 607116758 166355590 12247779 280239651 672523923 955718358 398840132 259078229 34915849 935886684 372915142 222181350 385334496 22796267 12767972 969754035 146148534 173210845 602514799 998106614 160882640 191167748 5490472 702515597 715929672 709302453 85323472 649255816 21804115 280841262 814068873 904065354 887391129 789366887 311103989 921073972 479585739 904986035 913017957 482291902 685530843 77038856 752473749 226221950 237511815 30631933 520026880 411669085 737618519 527415928 442573742 199398292 572157345 147368541 620271213 498407817 303004817 38792498 592704745 843006922 161778510 104883533 440765820 905583009 371444459 938913897 553508906 764188908 232410399 354170812 491323037 222536999 73528037 25454825 616025565 923001335 634091568 387059037 280419164 839025695 647426653 600723629 140541918 232459466 675791154 23083266 957209889 725703833 682803480 924937975 581637338 497863946 226664409 185259161 342827265 748951223 396525077 726668471 564209288 965843088 705317155 295675920 843925357 532504681 374332261 764406738 235839528 728562137 921283318 585647930 42588809 781083395 347348033 126431517 119565078 717613585 193439246 678832099 893182283 449751272 846881325 639969520 272855897 476384296 502836850 8019303 597380145 157668423 375448980 566526631 867213445 574927799 212215548 358790670 901832257 461609113 168399015 316336503 633959010 382342926 746283713 322099116 547278946 64341717 225981583 153947388 386466600 331524643 525868761 213697159 245755113 749749096 103573549 589793664 292427520 270950644 472866334 283565568 473796738 104056264 710459118 567987622 898611665 641909185 287917218 748864586 379026967 378696071 395860927 823666324 393972786 860508488 669912429 150353305 117548294 798060115 266131085 560467273 277107178 351231731 713214191 306819759 850726672 218695611 364673319 875384784 851899722 73224146 908507144 156742396 190055477 587200016 393245545 485158816 171267657 326601553 540602639 967285122 204986528 354594965 392794304 241464896 862585415 916511165 941716169 150241822 811112797 49095312 627375707 904011943 712446786 383761503 827671368 539832820 380970216 46344896 80492346 187254526 708859136 318316929 154806825 457077111 834340695 826182058 572109839 340070188 218166254 687084138 627195541 992849022 927105225 752051526 643844759 90779639 125266360 358119220 97766106 949056005 611412533 335272524 139529249 198346458 472665933 685037532 300590231 129245132 817423524 635273855 316799090 389375664 612887620 99200462 665664368 665636098 849515981 786144114 754257575 902377347 347146100 431702252 445442570 299113227 867073145 325982246 818714441 839802498 809627404 751256906 979238569 296027461 884337102 755527251 100668989 853209477 918233486 746737353 732822869 47304605 371040426 65699078 843841202 469332624 591378170 836592772 9130637 726083229 992698175 236367643 550227060 854777379 788189379 727267070 448888638 205526346 571988488 783425887 10551152 722820596 703392704 769248014 98540483 370384216 670293942 828846343 840395599 290612843 687646345 74838347 9724981 691866063 576433551 811926469 884822350 279320953 361146184 531492488 816294103 778661629 719675197 220468038 882952307 839211066 665303680 484770788 595676048 356947831 345645880 65978888 881450844 381572930 359501969 188481566 838542815 697360691 815611265 779745662 817531309 590337717 666603461 284570158 473287910 26290000 361821007 347598097 301258274 672259473 724706259 654599546 619671851 21552976 77639703 569991405 804150814 619407410 989955878 335662097 14632530 797564305 15193908 945319969 307203389 935552825 853500729 773450648 411042398 49018342 479450551 680210356 909110007 221551693 185750633 450254542 956951108 372701140 611940789 422649883 436868907 243460245 723630884 684979685 665886542 408610696 908242458 27798760 959048798 265864949 236104617 116557687 581922346 434773864 984276036 500817688 348283273 982104429 453742784 855198858 688579940 42527943 664395513 653644205 661293897 280259274 648184932 582804867 514335847 965962569 746850661 232281138 22147454 631086165 331512030 28690260 636888645 781746017 497585241 717825082 926408600 813700621 937720943 341023378 29893705 39452685 929978363 995426744 570502837 18762017 490715467 723599017 57965239 347037713 827480071 835993968 725343698 715893918 18479625 342261554 320765992 649764891 321674713 717624427 246399483 985075296 237525787 433151547 328766317 513158155 44372390 291858673 964272654 902043620 878539412 664943885 226151856 257754934 901793251 215787842 325770647 523425577 140102787 147390751 182092245 62576280 880175407 147905328 327125595 716449849 586484662 327783676 202947525 332985844 707407673 670693756 852485610 549285889 721079754 377209657 248351267 288558275 617658715 802560922 33272154 118332858 421247691 796607248 726906463 473649531 504582420 585285573 638449137 743292821 292365392 567233119 780055694 211377003 229208515 273867704 165706079 597826740 139186474 834263615 658373472 447935507 178899026 937149324 393236017 366141990 391197751 722400943 477359179 505498045 937178030 285460254 580095971 203646107 630952254 260032167 337501434 389834661 129927177 938228781 172441327 368609380 221760083 264473323 109694287 596901382 969304498 601073805 885127647 991990030 133886006 164374799 569202668 985437093 31108000 728918335 827152956 136485270 329894587 617583971 894640316 390164710 374324799 260621144 869471972 884801954 785480671 488640283 218729779 909181306 268493272 933317262 255653283 679432624 564260418 525155761 814750782 554391775 279459552 989232791 975221166 104296150 517764081 619539506 627280990 794800756 110102053 16612938 69324707 445231032 179465605 134885060 568731343 738796295 672663829 102185808 651826802 215108490 90714090 745868440 196135746 809678205 488651629 632057142 290213434 286949184 482660386 566484161 503972115 879118551 391055497 700739507 220396844 111793393 81271952 932621413 630431287 787975932 923906082 598035373 262469970 53520808 840474453 751183960 823214125 256391454 998751409 757810865 906937374 595587356 857844451 763535118 720561417 518957021 805043143 587273495 669401335 493673535 558668503 202340110 536879663 242812126 42272530 136893320 931310838 718506637 784194708 967497341 654372428 142696025 506221529 946265485 236855932 435851268 746347237 297030889 228439515 335755846 588793411 156185957 84461379 917793573 837359251 185346673 609721977 403161428 952958256 317735363 586570691 262110646 995508718 917775211 825718760 545948839 554667027 753237047 395241346 71831678 506875014 257133865 229464306 854656204 425877660 606414033 935488320 564418102 660504779 57055632 856888437 92080022 178174433 333547223 110910842 22750140 638478727 996726306 724587653 754542088 836002156 932863927 537478870 47908213 36750588 92913212 698891311 884714358 889949303 142382713 928101199 865098412 778775125 372063114 922482800 812989784 475735156 551566272 281503597 446506547 424942489 714108531 431391871 838329987 421175673 4995449 833671232 471456288 722431449 42866573 314144873 597247071 206495661 354817918 13958931 73508114 644103566 380335045 819285681 75918600 133984357 296638515 838834910 188536537 992465633 99672435 377342636 151028247 509648596 741285118 825773655 297544103 653390598 268311616 123013713 830466094 879969154 811827081 36522079 141590100 885245308 301797637 417242383 753881904 721787078 284091571 412040842 178809770 977539263 791381846 22025081 280088173 476100837 101282724 229798636 555245956 344228594 48403084 729980602 456680688 352849036 736886867 113352899 773355813 620550249 21078175 497892960 252837493 90602786 232002173 285219579 258301955 155500289 293002174 213885229 299913364 83438008 225078622 35167579 910858720 101859970 301519198 771326152 223359841 307650352 806876146 504606173 916879564 973762148 354522251 85394687 541970602 455467636 421655028 503520676 407024383 600997155 925164038 221561766 724541190 74855510 54561129 868819771 330537698 418729054 648453651 222675857 11152160 886751231 948512335 309537021 232424408 478569705 740718280 157941756 487956460 191491015 463694292 384952161 12051031 169682490 721802412 855565577 965106787 254396506 400459869 450498607 117373867 659535909 369374372 758247765 434452073 450381895 264271560 810617473 642554828 99421465 486167489 355971577 492931229 343530918 967744847 410374945 827670008 680962179 62798568 501769742 685666172 902178535 563721864 368156829 247740642 488399094 784345800 201139370 537990776 356796144 397490179 306685069 177549967 755096797 419490394 238191346 98266727 798290509 964248711 204120165 880069976 496689367 252732637 696457491 487639013 379734378 686527514 735884855 212754726 504321137 305558996 734983516 226638948 899662344 219252447 198629359 670524525 278700406 798656640 24811051 283206135 794260242 639250415 201830851 618372569 869301434 783885598 56066572 629057411 798832637 767519469 886030324 675843683 191355806 534671752 870984361 23803752 904589885 28662818 591206051 576927044 166923767 244887501 646798472 133789033 199183560 472210641 604200338 912364000 495607984 811152608 43954597 131496835 365351671 238058651 52762008 121748708 554897002 50193313 140549006 235933186 846920849 951339229 774961876 838465243 286311886 754851612 393256406 584383904 674000040 775700218 509980782 138140734 16155050 202616062 945538921 495294837 90510283 985283269 736542405 632780308 61936119 735851279 322273911 484608607 613524752 644237404 368517605 367676591 398687914 940530716 846265984 501957101 611608458 747887144 412805743 97687541 366385255 918464787 587853802 611472698 807287434 591917660 991830601 99874460 223908102 129353922 762239118 546978574 580571794 746217066 823125923 698250365 644886636 853989360 647697564 446865640 132197367 775503708 313080722 499326786 105671885 250226302 407811899 466346180 509108012 497476781 443997020 270152045 601455959 70414800 122549357 584894708 728115655 99179471 293144249 580402684 130402603 865759513 421631801 853522001 903387943 454425285 969560881 33097152 11278049 738402955 245726358 302080855 272859910 759361583 726257485 371933255 652798406 844524720 150881944 113597536 321309963 325314374 907293157 507486230 42219468 780601957 552456028 633827840 2070804 872704913 876135415 6718305 738175653 789174107 825682438 517262700 841999653 366200282 126566726 977439808 973700145 21155059 912411478 650254886 946792334 760390283 59627351 731780290 198940905 582707632 87102289 950619549 669169866 106126653 373725890 246934399 445661388 552164442 225357571 379672387 617295374 823361455 313544983 547219988 1550358 923790561 148030397 897213777 944229712 990158916 955806119 518470175 68548164 711499755 49314952 725189595 628051331 33969265 938362289 506030882 453564237 960515906 988100449 49261492 283065487 160318958 712118525 839386494 933984779 749436570 190000873 122079988 497917801 14611835 662421331 121047407 289530917 864326013 998467447 866840902 586376137 489464963 936274456 310710593 276631283 165818848 479874927 373395345 681977004 435804905 101939543 601821662 467098261 453256272 667911178 925946872 652034283 506066583 927175270 265474129 498315922 540926702 969561801 238777575 52182449 2053754 953348390 930282925 723893660 61457000 430299228 912484574 484646643 154388594 247550281 666711917 414033922 987966491 416433616 845453730 443288550 935863810 978081741 608858245 241848624 905409897 155163238 966578260 329256836 541433264 83048924 917147156 112481306 632501995 937881360 351758294 839338781 869413330 319463440 792633770 634649632 644344026 523870349 685576758 385375299 697509708 517809581 1463879 118870155 349793379 932640339 153531329 79168342 770087057 446622464 25397455 262514261 257120766 732730079 127959768 758942300 612167631 289037552 518240199 779737207 519802495 765463669 259241298 309610612 703588552 934612011 356581326 247792526 3393755 91470375 526330771 737496598 395446064 292286376 381366518 497705435 474758461 806054048 371039645 140524822 299295938 510468811 505444801 431024817 94520586 907354903 410015984 814193920 335736975 486548901 662079587 156812435 660288532 759050827 999322749 99638983 769373786 766967612 876138105 570758995 68908542 535293193 350092838 390084666 823893937 639878912 895034586 153883889 118265228 884815585 132464488 431361741 65199978 482354894 838986328 107383155 947208893 856862369 608455627 410011550 730114721 485709863 53967944 279128090 106060321 480609012 244541226 545447844 834102236 573851046 787680483 28982158 126272890 138793580 986771746 591302416 265256325 378304195 733594450 124392754 610672898 748989843 669769439 161802709 136375395 937668382 291863874 52804197 543608246 151013329 394824251 807580885 892443507 953349909 967458480 665891636 397851012 878679615 83416719 428972823 574571337 558457354 803297756 260831471 210158381 37268332 955775100 160063498 447803078 247757441 977799715 490813930 803996429 398300300 407527939 666428320 879387542 210822229 303758426 998893246 921217339 949535695 760033109 331987057 630743137 810969034 553457353 897807794 403312495 661675973 967880893 310894679 490210360 341773956 245955544 986551566 620225674 949120255 436725324 68381753 699041623 707066570 944106540 571019294 306220413 806544260 24467934 713080862 952289981 498674826 281917475 411444516 897518594 382394924 405540627 656954803 182611802 732453778 126019182 787660862 20593533 21787903 32765561 136062768 915527554 850516709 145115546 29243085 952582651 424535091 219424603 879164495 909512959 903976615 547988340 511822065 404008243 482419220 889190961 611507888 476734259 683623786 664919031 326918825 230730922 186107814 470821840 977801658 843516263 629834249 779355086 657021774 770775927 808931057 435570957 835230086 124859571 208583430 597548503 98181706 884150120 906330153 957476154 480614062 909596572 817784487 290760151 879883673 598391061 4707440 203606308 541144203 85832880 366050174 238480501 958340558 2306339 373511124 743982467 580962513 33297852 862252989 784351740 109591609 736415449 391973273 246302472 835500062 803338186 9898978 176020531 654812491 182483150 662334896 18157072 957921260 834679945 278027777 10632301 326037803 658830920 60939636 301615944 796557778 833443654 20330936 355271473 682725963 963374075 619610952 241171431 533799339 799038504 275555769 597986421 807233777 480599137 795280775 163888714 853271157 112000616 361723031 286856209 469270827 177499592 203078215 851769908 97094069 895524627 56240025 826341792 858299175 289295280 325630937 367427400 578733506 685577787 323581465 648277029 219016706 80951426 784333263 48761243 309753688 572826826 491135816 81441666 982642493 159373884 943136095 770094678 648462286 11389854 215823887 282573 233512529 289672825 801582072 490947438 77138531 486219485 36758505 194374946 396458900 786640626 942472992 477226918 455112911 133598811 566297753 211051072 619245920 484373144 330615195 932122028 223159606 861331759 873509166 482932516 538143331 648867499 537282764 805389863 215124890 335660032 780113696 258534200 711845334 317248140 233701215 341387769 391619116 660952239 88856911 866299192 215309306 53512355 147821096 312474400 281528291 406594138 144759832 673246385 273997565 937990963 369801904 846251016 672453720 527920315 266016722 768497781 156415594 257132841 845592180 914073106 6898344 614787715 815675661 886388070 90034848 160716731 583400214 638926917 629439712 514221057 721690517 685784276 98552466 802709328 281876608 809196364 524537403 617892717 37690266 258032165 269126798 904414003 660217166 758772327 50517665 450862648 492062642 284216746 994490194 154557590 219032329 411454311 370183859 418387936 387395915 911803048 407557899 743449506 934986846 165842001 52549703 985470841 390900294 259793608 51140480 511912086 250583800 939635350 456655931 301712695 609998194 53158807 385419247 932130977 377766239 314045540 557731071 562734827 554546901 74386053 344259713 764143473 477456809 432784039 848433101 996065354 696115551 328830319 765295501 699607742 470159102 426764602 832976805 456204262 673594051 194476737 41440194 205415452 216384218 579445655 304236319 300653894 129901549 430933993 212411549 140075658 46922224 659966355 864204319 183025922 323332528 856192875 660553647 981552398 596820745 470077835 524992811 233479263 719044725 146780283 948751064 55681384 292823841 292348406 67939098 730125729 661947752 200676068 117015706 360178365 460561063 415497503 10304147 894321197 101145245 639921592 543546563 129419186 695495086 124637294 984401744 239515144 142428094 941142005 57233344 417955800 213737034 431595147 851635656 544249979 332582800 244918459 593964378 109297113 175415580 535203745 984263444 979037821 971722112 943539819 904645017 192670251 914775262 832884974 598789443 789196132 453447769 670316695 876679213 928974772 203512002 486827652 153796079 846740801 516436422 698447924 247763131 561144158 10092297 200768891 687350384 872958902 124950512 40036604 471538618 661580411 835665894 289779899 879436778 572867206 677152491 662828837 388647628 233270413 175602909 133559831 159390663 230993909 501308286 357071934 114319681 379417669 351147214 735617815 908965742 726844742 841344238 703600740 852136197 50119792 556542621 435655020 430702751 412772262 17280154 80415691 489474561 918889583 572118047 503339265 148897100 81348972 129350830 669678902 63018510 827508250 537185782 143034078 751033503 253951352 45838195 553324868 692495637 528899291 742194161 144964077 267340467 860800442 848825729 361157446 202521582 920320281 233722148 108854622 771804240 975195422 873480276 138450911 516100471 698252063 984619076 628596746 278821450 352079823 419919636 471590976 375304217 184372712 108182597 279335540 422617187 303014964 624269883 747778276 352620090 594934436 591820887 422327222 136227182 420203173 189613175 273361885 952071057 182881286 92592500 84726154 855218594 640886572 667230615 605416211 456966583 754815797 870144463 350444505 33893873 407089893 896745077 254277161 373464042 689878023 18469339 702644003 461950373 935395760 946621335 497259401 270196213 10026179 165311538 293967515 421364128 125268379 582994136 665078099 396212474 879678973 206531994 535987467 594952476 84546384 764503175 191858340 18565847 853974284 801065492 348643282 718641286 5093190 373622809 933050375 500624969 726750025 596038104 190625881 871099144 641461831 487562707 911119339 117855198 302844765 403032245 115917660 385199938 718558004 942240671 429900170 366734014 331749254 193734851 67334440 906837121 378568937 31376409 927621265 898874084 353841359 542751482 622804007 508686359 299315670 599596881 211267260 393613490 614402446 65885256 866310661 548988452 307533251 377622311 976656187 214800517 535412674 868881158 76394244 960701700 945675733 237007224 664341049 919882879 585826370 540424359 494711316 203690463 622433998 195061314 891242525 653911600 774984814 683831975 603129317 437886074 851613998 910395999 447966356 764255717 562864690 133212518 337147998 754564115 52092190 51337772 328411348 151197247 753797903 120821212 770973304 674852940 267939751 917576325 498019430 495853783 956163284 193669723 784814555 901884461 769497546 224338693 739765980 762705656 718720400 4383983 535839452 187940727 875480093 733496828 279258728 846275915 531246382 186843208 548615164 742404943 880839618 420235333 107834073 115779283 270816472 336674619 74676985 601309908 110556074 709586701 156722169 403520533 993416213 66528541 171621096 692903778 563733434 944079076 563629954 338631227 902176670 609811808 766201731 202416924 48995161 54092709 730511075 77517404 117806614 210657135 785787152 357939642 178231257 918888317 760354418 512513204 839972264 105606290 803192639 436395480 203897347 390436617 319956429 939971412 920638276 850421389 502003471 374435566 970562057 613280061 76018890 895140544 975765686 266538667 199084862 862569457 612181081 548231391 596902013 545783746 877154197 442025347 719449884 891393218 639434726 976928720 501095813 962922365 341788108 628565419 470582198 627794309 635811111 367866661 455690121 677191568 702449132 636032382 576426894 293238369 670242457 978018646 166120494 161883625 224850900 35764544 234179752 603488610 441560901 154101777 572781194 61861096 233176514 84831950 690046419 986958653 52287612 941482579 435199694 643962001 516980975 402932791 788381448 973799272 856874734 20861738 907211121 597441426 716478190 429124774 56764988 767264487 929210679 867923471 451753641 999031472 3167898 770779544 821152373 540408993 138188353 785781485 74791625 584609482 503572395 319593170 174457336 279086583 405778944 746332274 178746817 686335279 582746227 164393522 687615338 290891443 339221832 505547268 78185965 969917804 3827070 117976838 237537951 406065188 86265690 112034735 263978639 797935972 878254632 610560247 499630256 802149338 686988678 219844919 886091292 473746926 380496842 466865768 464585374 227046196 86515984 265853688 243222655 913287423 552107902 499796959 200913940 53107505 824354465 107893972 476392705 614393392 562719826 642620884 593191993 571982525 808145959 854526369 803086853 156647644 380344803 520569001 285789438 820603568 605705860 764976371 919872273 478027702 615886970 365233434 867946665 938149285 712573539 690352180 864930809 188374475 553528655 323489655 13641093 332760732 980152666 620776974 346590991 726220999 957917394 461996891 308706373 41196136 458015912 480378589 33083821 146031343 737466036 30634035 309180810 195905860 540677284 489911622 455636388 873906084 430587371 647544226 653608371 509372512 525815409 878848056 714899241 849741382 954304329 798467171 426239090 489787047 826623421 76940820 585100015 133992772 792296834 112988708 619613571 201213396 407077897 342282537 783281835 26761205 498534335 664166569 563506706 394824860 681112043 625737785 58308663 125794067 251197647 916047571 125606259 953919977 364207010 648751285 562681342 44487763 888498281 444420922 927783275 392894441 362813137 264703534 608002478 366451016 266014456 347826649 254034430 754551289 734798313 621477087 658917983 601491471 496380884 21423546 26490714 868961207 248922975 646658715 616053957 56540011 93909614 238952222 161325525 802629530 369294592 414783118 652374629 798929539 139905076 666410662 106533972 395442492 354563459 58644324 995733722 446512869 836645895 631894287 109265063 248405499 927302242 607714181 240013455 612572513 656424697 640839045 340874427 450906035 802525930 507777857 662086231 381429651 423669851 666074956 984819154 481307529 270813471 247237792 74619425 554147507 212062192 419776435 200279303 442115647 447510855 163436616 778202187 377531732 852522059 709496703 495692413 688993244 12529394 397707207 757686198 751729522 920893372 755330996 829130827 134783379 298102696 313945258 320479674 187776567 190600240 116027347 638336436 559637719 556656713 104609480 657375660 165387794 236002521 55589603 928940573 107783551 621769479 195880280 250408579 533331632 877685313 354108945 304702181 914247757 176437585 337767431 390596872 553596122 409647927 505939136 756127907 527965824 829284687 722759950 335894270 764781020 619164007 79807342 243018047 875950443 216106445 184722685 20025232 658587538 58214729 197631837 838354426 112461810 276634315 525535262 42224271 436781639 69547744 356251924 253837873 638866410 128914517 680660940 359074359 57656358 680287981 583039080 135133106 124683252 97906227 279479593 27749110 799717946 92127095 837930881 42380536 323076380 930644859 108898922 462157353 382040761 105013426 98736543 284958801 960164902 868799490 130962255 891074490 494071588 882842293 503903195 620818613 817008269 243711530 771952819 220115981 741674525 263395076 684703923 199907413 158664813 637221339 206841092 39904442 73394898 995153752 393217707 939477379 988129376 952098241 388688468 994025642 90134073 784735207 403808134 958388714 753083784 593161731 928275667 924715598 639790395 58603599 380766696 979689771 586505243 657478972 958757992 146961965 544309617 54529256 453017924 356782738 398064561 284661635 630790561 835842393 71238469 426831136 812206032 852651491 256217131 742733202 715816857 697099390 449050434 4017778 611004327 733641344 452689602 607346632 43472679 762794888 717642523 227933608 98498741 996530889 479432363 918395717 525759159 467102283 475427762 791784989 558629504 512480074 522689594 246488720 273748858 409555110 263946769 152633546 532273970 953778383 963949433 951984070 575478193 936485334 213646737 272122299 662658989 164697880 603047277 626774361 589709554 845087849 46791428 86818180 417979545 571336818 192214219 416563263 68528537 62853623 573191287 304237075 529055518 536612029 832819458 242998604 540270413 690266808 285549764 772740469 210284802 202660476 39464842 144116644 959992340 141860345 942836045 235766462 673166282 847047984 626229539 41016703 178785753 31434754 233414364 997262343 764525452 692086380 674330767 464966699 685439839 173904032 580372325 608746621 235628950 944582833 594426089 318131246 857121994 445813982 41871165 785553509 341295492 183319719 257843027 605888908 93470142 89577746 670768975 643190100 28676009 914231536 177199543 517779061 915193375 324048049 708317455 103993248 765505985 49906111 484713027 45171249 81798672 278064039 744957233 480944223 518760066 377610871 226540750 414414885 91466794 289773460 685893997 647198272 982001789 37829901 768206587 171593000 710628524 262566487 630261528 579178111 822296408 840614606 752035161 368756299 872892044 988405440 119785960 26711945 421810924 139501495 929650168 83297365 603402870 788881594 726225889 30995163 963412244 296708733 569507435 844813901 118408812 653086487 484276556 812216799 955257645 506840133 872962675 533200735 799697566 174611535 843119220 991316706 575470478 256766926 927234483 973460865 843710537 502146751 751921249 250354615 811216987 514733211 173341070 535683843 74103073 177730296 499033539 616645994 945385577 684666141 768442231 295861433 803700794 90487442 727445967 279841301 235752263 373336705 383886873 43660975 262207360 523853916 725800449 895700452 884223859 678453586 457212680 47164494 627129873 46365723 441793776 540528917 582370712 977251938 511374739 509016245 888399470 27212903 684348790 709342075 428223683 965784690 644930845 364869508 716402621 253149513 252385362 79501550 328517263 445891553 655155949 888233149 855767355 829129991 243381389 233605588 119710216 891811826 831903973 800094438 777122407 283569821 911780463 86500287 447672907 355704952 128496490 689631859 227963890 414464350 818518090 267671279 678814643 869535086 275489904 273892507 491022435 531794844 572563449 319994461 369885547 504455004 748503431 632831040 413165853 715002190 466153637 953793897 32105089 254844107 937753749 601454041 657818865 138288528 904958612 765748172 930823014 960441898 119177368 966636047 175002299 969239508 269962754 160074955 348501092 549724550 445494709 887920084 110691029 612522083 42389556 894128155 239257748 153230908 258224617 924357129 881705962 928970565 659838398 825259828 45405860 9718868 243610062 986021977 357118783 960234834 602605602 183447847 201608107 400868602 695682792 512617493 265940843 217936346 842308971 270256851 324778139 902377905 107977214 506096466 584179636 320351991 537860473 388105480 24279914 123695593 155078989 339179125 387150138 745214710 268759278 939437016 222528534 953541918 266406120 519142174 75240785 562665275 312664934 380320833 256170744 117851271 873297610 11639894 38838621 122479371 933389774 45924082 155921959 713957 998273810 270871961 738468177 861659958 575454756 365282848 478472844 608531531 651588230 186310806 119449054 911420788 567560514 662967623 640682166 666635380 276845704 859766049 201559165 320155882 174555363 460992938 694669764 468149610 7336845 972435442 633897877 143464497 480795477 167377053 479021428 831566019 59765490 127474026 142904356 103259056 443098143 536719625 879261068 855744743 425155015 455465250 41003485 485272784 837879360 430981757 180755902 775234652 829705805 373926791 161713620 9994409 197341100 744718805 545849496 648542593 8251103 682477184 322162635 265567629 446037032 531505789 22134924 524618339 899165992 817108948 331187819 364664802 716183847 495327160 718111798 300282986 973847049 337632501 252901641 375516858 554394478 815537075 406573171 443310853 688699039 828698499 758266068 946140846 652095043 63013513 168252632 535047950 451357189 275585615 867603613 591809872 722012521 69966 529435426 239270914 613671367 665011194 785561104 534367652 49641999 984814127 878929128 191055130 121452931 500705473 121365100 983193779 991419655 768595098 426974395 800262040 628325130 642979515 808892965 447563562 431239909 747969893 932475788 368669930 208042320 396834288 365101214 878539944 893134516 855291715 874021723 561036883 349408559 68389429 845592289 507401993 244989928 919273108 790820294 56799106 194615438 80997144 902122665 223030771 422234876 619919187 645291330 991695573 335998405 657928192 785215242 851767182 438495301 76689946 769458734 270006070 12993168 415103135 517581422 486508880 488116341 8820004 411908994 347414942 857113015 867086844 133467318 394154646 23138834 309856188 138149442 336498395 460542271 53985731 583803768 458738479 489512007 180403970 419655030 896635426 547657420 253942718 711654257 875603758 234230290 64929411 60480845 562167201 369756644 901180349 838556069 443382081 61193099 714558906 409110950 734740820 451086835 142203572 119964133 623762892 496661688 649152549 528818411 246430807 83257067 34496451 576788012 124036248 392572248 47334425 88703024 831845815 91899106 188943600 687450186 58034373 497623361 651543388 361402488 641440190 619748865 19882346 160025722 376752798 622100219 497800729 985089643 540834917 92957114 300890796 375722493 749889232 805441786 349341999 626168095 115607007 378929902 332510811 725801815 849084866 420166224 694405369 597079387 683287787 950858373 249686875 377985963 794102943 471858363 444180966 277979417 582606109 841512118 82739819 889571786 337584955 903676092 342338420 2605810 63442848 218736456 865733011 185434930 248596212 947011547 203139216 565315898 564860203 658583743 619613433 649017036 448137757 608832913 156948282 264609820 260733384 357079756 345639917 526020515 649150687 278300959 143036399 291406886 276829687 346510627 967305185 585938507 608966571 816270098 264848065 587302342 19080623 291990291 282137106 207369089 358930008 187616520 54598743 890302828 817244707 832332205 388087974 458121847 961563753 688286603 142287956 50901063 360202086 510367356 566561085 257884111 296082640 109753707 706900179 704649342 914335453 991487394 139014450 904657375 717174572 218166217 825513635 364756631 614631674 499275135 526916503 582085903 410408696 787613672 703281459 637034426 815666602 980152494 858506282 564750779 759198370 375139431 150933822 803487134 502219586 147419671 739260262 848736408 397414611 119498993 342973487 311958654 166132926 448060368 240844616 659570494 321794608 378232535 23280039 737648858 571926630 49199364 786720375 258113758 336621514 34398729 619471188 698890830 238819210 206436507 905382779 185042362 2441724 748948524 6506614 869774484 620671331 777030273 761199858 175106655 50115343 174257011 233702925 266263434 19045315 686317391 557209217 439446224 219699569 497439744 204946087 915421745 907783345 236577622 196290410 363412662 751684794 453514930 627604004 157535157 785089381 7938263 312049854 443616881 626594372 739183025 520380180 99575847 621284936 957072654 114958714 181561170 143903431 741940305 576918552 922533907 518861300 579145067 482178400 610415816 937794519 374207163 184687555 287027048 39826872 911609661 497494529 637362591 279971576 972682166 317014039 72905548 807861059 699610464 551207453 370378544 324214135 131777974 700523142 153278465 139949415 355890068 734227749 111064784 342433684 750648880 420787521 980248090 777881037 75945301 677078847 828798189 963920925 500857790 948490544 683221418 192251483 935819886 906319275 115040564 680777932 966142417 743499698 196613569 253631020 918935687 131976319 942158519 334869040 199385629 454400583 785729147 739800632 318799040 789908317 237333658 315359382 65636314 702501027 408790922 801293917 555240455 201158256 955115379 279270551 562969313 165393035 638400002 908545563 207540628 692753420 859284282 843049595 358254194 931360772 304679954 581011686 331115006 680820367 712864853 265542744 350011245 358931787 493830429 639740862 314138251 260182334 89076538 571760075 523932054 351781008 32582767 814225499 43275453 192380675 858974786 314962950 467865919 478069453 960400708 622109063 373420785 214299696 622002184 938390438 684465909 801816270 666556883 429634228 498568188 509052874 347558020 992913449 262316894 526106213 966998891 414535881 385100353 746705019 969303071 736332198 77064437 731962748 25421057 422497942 660209011 803654079 628744106 811315593 633389162 121556244 178599897 674556330 891637837 877466837 309888241 433358474 375238281 945986137 740532327 873073539 283918369 446439820 782825807 551521148 413294974 94860500 172157034 442948872 733788157 925104187 178569406 549157167 71545860 172993174 497381395 85816332 605325192 708399658 670088657 142914616 316954498 486156672 507550464 776977935 421897286 945287415 377731505 421990653 611039752 402834407 348749238 576728153 857815905 618689595 153719159 369064076 870221993 544206462 436646293 567755945 706968745 345366991 942520983 129587983 465409402 3474831 949947484 855533809 757092063 538768482 824135235 163203425 44026446 861864906 571689601 934684159 727518778 826196476 156084212 851464383 203730614 912052045 991072373 392987532 816814229 145538707 372732775 174246066 740286605 776043712 36619795 797370527 366905872 51612073 712775082 687409098 727515439 336461439 469001935 159885878 63419797 452814684 642028742 433948960 753608225 811064568 274023208 217194079 541167580 652182001 241924641 781973149 471885091 393050350 247305008 538966126 881629946 945450636 608069051 233496174 717418476 510253795 406630688 710492297 497327233 653151280 190437670 532525260 668029001 373119405 105686475 916503389 769585886 231415891 7203572 344442289 326780418 249106622 553608453 147656301 268329194 340093531 809340290 214120178 109804767 735378559 494370374 981100134 610387757 960175215 44825706 917871766 88639668 97845550 765614895 190802170 199522980 80155755 888328803 903990167 904802508 573236482 4449367 281987568 163382801 69946656 729657109 80160747 282168139 205574198 292288459 531228881 904390828 615500704 953981022 678979867 103117445 50086187 309643111 173843665 1753449 334972768 497040869 510241833 840045877 93683537 697633587 420858438 683092260 186999553 608586667 803824200 937411162 250736944 902509441 454862814 647142165 267382189 453907564 24110259 846917941 167677936 452111013 90884349 664984995 904395153 622003521 647389286 869907752 420989108 328899998 759435426 110805911 830839575 321828495 62767481 472256771 971593484 831693772 227956813 102661655 219065105 135978706 132408956 647702974 996329708 948727576 130875356 32374781 21888398 819533724 57002456 267674284 20736404 561642078 853669438 116244292 824965974 773948911 32210614 921141619 794564387 131553178 59436652 312561123 710427461 225950023 385183328 72656347 188402430 793674285 577885625 536126260 452501159 80713306 522252491 659084312 733533455 53078326 804445286 897383538 709966400 850961120 245123473 257027910 202008577 339775032 805814440 296116287 643101275 920140534 772399613 914319865 489311117 666582197 310818747 676515618 268738646 357773259 199296729 606197638 593729262 874087210 115580783 809478895 307870516 665732845 454102390 47868854 288087593 144336504 821025972 291595279 834224086 959980367 838222873 171376452 903165509 704730472 409209698 142047512 121945284 28506445 443618157 411011002 197137548 928992717 517990885 201922744 380363012 942549915 354832886 910960437 921785247 436561563 430393643 736624070 252212611 549332938 469691039 620430807 921594683 107770059 355385128 259951001 995408709 622933953 34777902 620392995 29413515 585293321 671566559 302230309 675438415 569201295 128490118 766945202 230551076 980222500 442179918 348146063 240309476 680244387 252533518 218098495 757919552 578924641 399484242 442638082 601902436 143698254 301832737 316984242 332047400 201364123 610503599 30506082 289271865 809003969 974914110 613398683 899057769 221035331 464997348 611954465 866118618 85272700 995870978 448152233 261535262 452305768 397642132 894334596 585181678 53108354 331245608 507294747 253899309 533909990 740169532 593034049 725329253 303302421 11915646 255258893 567001207 206593081 18918992 106189245 272505986 913623810 595257305 835380273 728098824 821686179 130873427 276500887 870563692 362952929 63911564 263424673 966739736 459400029 429190348 55570585 495476087 225188706 974194968 276845190 498461061 949250925 773077384 258700867 521736217 726934018 127920066 174599486 679135859 641442431 287058933 8462977 611378613 175062199 205884173 699847468 507687753 857309311 755388913 593049576 870632937 54094949 526820314 568501487 144238232 424103589 970486769 484888637 693557320 916020647 555584328 69026549 39909953 159447380 515588291 755287634 646409515 464842839 506120091 752618452 502840019 416779794 463935486 185022975 101902704 695610213 472304490 812093598 687571812 111008516 749958358 2761451 476722703 735790554 648986130 583054826 707221198 344235094 967404593 463087620 940984282 975239977 310657930 839864023 291401337 758481274 261363327 231814032 373857569 538431014 320076320 622514068 781555851 238901820 961627883 819930563 109240558 774529542 468358241 795392516 173600867 791578578 977927437 272351517 661855283 598222961 833786491 516499833 680473773 266059537 702753612 62651123 569751922 217831508 122920258 816220117 750649790 381441451 577477826 213170810 163306811 739343034 905791265 604417746 816153023 534008502 540747706 627055583 250079302 598371388 838108751 413146393 195769838 800820628 299327848 847832866 483768794 468413560 489846750 903885177 785364850 332684888 31726862 433770659 893036859 97153365 351203038 586509270 359967031 19146503 274382210 318685841 3487405 777276938 140711303 311505316 465689395 405770871 474900653 39098130 593714898 733502045 121947586 366904138 295730897 761502134 375614339 328091982 139684491 171458340 755708198 645347865 325977295 15722197 333977660 609965507 679232819 638394107 783095049 465353888 346886472 4491642 395061668 150625936 239842216 308632854 754285983 682114063 414266784 689166910 667192311 566813535 113059725 540511505 983797592 61311006 136035430 999601329 384316073 881018504 834846080 929601603 76465363 956626133 662827732 170297778 898021608 227964550 14085975 278730881 26505756 295589584 90967553 979181453 53186218 114185216 568858331 721476934 292650134 131036597 976186222 38467007 543668368 205910792 943800226 919223164 955554291 666737676 761913518 491689639 92360342 972071082 439691259 692404925 350888084 18159862 868213492 296389139 406861606 871854350 595792385 248444687 689787221 440407160 843116295 356900831 27544909 366392459 592777800 265430556 22364090 419223004 863387679 882437860 865911394 135380860 5578591 653877104 772142047 967030825 220227024 217613745 598132873 139016997 390213304 858479585 982386503 422632381 373289380 579706622 846687481 861386 451270695 905071733 266104639 869652285 407189710 336235884 646623324 590055990 739659015 105484750 59726206 630673784 109964447 864534391 985770421 387870077 325682608 329132940 785694736 460274652 42153512 735379585 844415931 528004588 294208853 147118683 265992861 893883313 470943919 237071602 831438098 945656487 154704368 172372164 456082217 804733240 546907389 735664241 321236608 395243476 132189119 725811514 603771041 688829672 656096723 987248957 120310117 419775339 927419985 114447833 13577556 59650314 240672537 676140851 252027062 278616910 65869726 420895956 180244984 67412594 752818992 991126092 89125506 315261515 166839003 759936728 543450522 446360661 934715324 750574359 763206897 668677588 837121565 918308239 265243407 937611939 903154491 872840090 316875280 3472035 285786199 997483508 110147103 22490339 73841392 484074500 634733929 687928914 482142008 502926831 610050806 96199916 833939306 385345740 788611516 27965448 552680725 641157519 692993474 977274973 988845555 427946045 499090149 34874313 674302896 700680278 987322330 78564941 106283780 541351675 516751626 124618435 954716748 407459111 69724295 687740742 481927742 322574666 6587810 687483106 41149879 604570586 267953617 537526625 106578162 257766108 366911682 263962637 611423342 400243154 294066407 269106548 60964219 377494503 542204160 399862524 152638427 749481798 989734009 946865982 1682044 896225515 349549722 638860312 557856699 182130232 886338297 659147723 366157476 71389143 808532831 187296631 892768233 84436392 292532943 349656044 222731313 444226590 983671668 69183746 455444064 798283285 591196584 327611640 135942993 100915716 503767396 829191197 666691001 665038274 426097288 431989550 815479465 204608573 380553314 969867880 946585222 187995189 781507837 173595044 861470147 120701177 265664072 16014287 588643107 73328961 124985943 539085889 509399571 266942377 42296394 894614180 383520826 739460395 628674581 369576049 519434819 933076842 509693294 239395252 733620284 577750050 188591321 260299243 738131505 753787614 926090554 581741355 27992156 337670275 117110604 146205980 24924903 375019402 944299320 260098817 260437639 811350514 56809325 58732284 844049005 924282714 952623262 66573729 744503137 661352711 847852659 339834466 68180461 482456048 528402626 106251054 965311630 654193639 666919237 672830225 925931731 829530486 34553574 478715589 748886829 787079039 765369655 688383956 417587833 852052457 437161523 311119213 60121386 173807894 760213532 692760879 614887482 139076016 910762634 191466575 650967982 656379172 278904431 931582685 933948152 868617380 394036066 869467918 982084566 693134710 407889409 364221096 457918688 343331906 553051871 902611590 762841335 631487720 343248174 632349112 589472058 448269289 268671517 690815559 926910830 789884021 177990834 206783275 652437597 627937936 422546143 697428777 738467675 987191028 94250639 17935665 630288710 422411644 321410611 470869174 380378040 766173260 641539214 82757293 619353717 498238984 367797044 454114533 289329313 641983552 312500379 948287767 765500918 616244392 477303997 50152428 168616922 522972878 413856725 651771495 839832011 88058556 153060884 734571533 848525274 971672216 133897841 980295536 527442907 342615295 182245018 712157162 913427525 136286342 493004227 349905551 625772314 362880873 457333263 90322864 915009629 984720820 775258807 790499360 92855416 324527504 326523678 627540980 908683492 672800121 80140360 659514695 807891852 68617324 416102476 142164695 801109530 833551680 317113225 651933353 683726266 709455996 304803629 745558195 78801241 183980402 40489900 521886132 69269756 718679312 124401280 713116022 620904421 716672964 732988514 847051299 741903656 623424327 848127111 97902928 634702301 372535884 215025961 714060162 913941434 293050373 903735896 589991092 728107405 721201815 658545054 585148026 962488891 535230563 357345249 658320416 257106714 860590758 735817092 404588774 950562689 155726140 935070647 939923299 971877330 743653313 859908650 638491932 836882541 57252692 100700327 5529741 59127228 739269431 349571708 318815650 115257160 650820792 218675332 733951992 388218778 189766289 220245966 880847367 23865325 616998111 436165636 44523978 494191121 267121669 356901501 766171948 519108946 924630954 537037687 875546924 154483236 491778096 364713355 13039942 498863148 77435031 270493487 975933745 638726912 454414913 700730988 736200831 877121570 92052730 841852529 872331853 309250782 630216366 545904581 560509051 920455861 305466495 548208520 132912092 495041823 121941341 547848403 294427416 796868636 866540085 935620745 248715786 482310994 573658241 25532533 388353361 555167925 963292432 891149719 303425576 552929936 429565319 493263178 585876140 444204823 287319462 23596128 264282887 733140361 403877123 302064005 325453798 14871830 49556877 347021221 495810279 729421336 695152494 575771238 401129893 645774808 289965902 186506333 860986356 666607256 475193311 647516935 945669998 649128294 667602286 219580321 129168264 848605355 980737454 747802136 486381106 845495178 7422264 540999155 598238828 913617836 110539610 265734679 94622661 479477861 403667776 696008614 454950471 288851179 75325547 892770063 153132918 392814917 618761773 630233907 30621374 729808991 644603108 774580279 378403865 824224183 751451676 50210452 127452607 753039576 903063237 242403344 968910613 33417189 496315345 497018960 350978042 797491650 508116553 525218807 766857280 634868019 583095856 321382090 544305323 634448789 949991235 482995197 255189552 941680306 778221093 36278649 390084099 711260396 460537447 954524991 49051184 220634859 241758225 880139210 707906746 477366667 370658040 341830747 282108972 728155193 638438980 822729849 391470906 851371918 359186680 750469180 376548633 326400606 673596026 129029175 467439615 266238168 52081116 879665997 445005038 896203358 348922359 174547009 956955382 827167297 195255810 964420663 38616445 37264412 63247118 245448760 654163711 865927236 351230182 938324555 274409435 60926379 122396459 653580461 928259966 441736563 352487999 910709112 664999652 28794215 139830566 153530468 73610225 600678039 750775354 424868800 108063565 476602151 820983807 788917230 34388267 784710592 570027045 385151802 251136905 348578562 693002659 123437729 706512539 820655986 681100165 382438095 3322010 164803818 921128723 286341821 458772982 50746838 33714852 174651300 56423295 772507326 383243324 626001396 672288293 117986391 376408768 592602862 684614875 643807797 927976547 992785475 51050567 778580489 668450935 462499183 379379358 971223768 885668766 695815682 180149832 615976682 743852420 715794866 740932875 674262049 717693740 593097453 826792113 978450036 480821042 220960448 933971332 299544960 210649100 99447312 944407999 511231192 940594668 616854571 478492788 531280012 767222895 326297056 342382757 269024127 385287111 912154937 445116609 281971222 246241682 441698933 154091941 666444630 572948334 322802304 26468692 909279203 307565909 888327314 579114793 894558612 822268373 218644684 222641897 292777962 552305835 272419401 69438457 828186081 186571355 87432800 885256252 499854015 987169105 357395814 201423367 174013548 761743043 900136139 270638499 392934562 487418760 118986197 440062911 321333868 688517555 741284243 163754772 898368877 853650054 708641475 427067067 889562024 786038013 527082503 599541791 919240509 104987223 150344964 694098204 19594616 994889750 331051482 599219068 470541079 3478622 400510940 902627807 606596562 649469381 953145568 820764567 930404657 867862329 335612899 662385436 485418463 845670206 385180689 647350578 487462586 78836631 776274919 129787292 405000547 622599839 427737992 709846449 68317054 295354095 215664930 199347935 735775623 128227325 700823797 477840954 4995912 363301073 313202754 96300672 72303951 464043846 508837358 954751532 231462123 770661373 449194218 522115330 57021722 463573583 361544468 251336509 986384021 517603170 891277436 260892661 147524773 850819859 768872204 638178854 67516082 939664657 846899982 364333890 575092876 998232936 369126196 893658558 551238761 711633486 429603854 575806215 500210441 870605575 803396356 378350475 634974149 492507173 583563109 78535567 580852670 642989897 869324674 975245745 346625590 112154819 970176403 868733175 538655245 966449994 735939085 12060019 701426025 361150771 202641644 641891708 903076080 129788144 573106558 193127238 151117380 927189300 513408940 801414692 346899827 75672483 413459976 516858663 929794115 753174159 628126510 915512784 805844590 144270106 691023705 517627576 506625381 79496509 468066537 479640530 472234707 30667469 188762727 86827152 495340588 964261595 137279456 737760967 104294890 372269311 432134470 32324544 719319535 239448700 851238931 407407475 453236237 632321683 104222221 966225154 556341892 210844163 444082248 730210956 142405571 380394416 582826704 576200540 438270811 343543040 793961879 696438251 828355610 189257200 577405059 914473492 498078336 384038809 759239102 662243185 259946942 635337671 891208660 367609280 798100540 318863022 934257227 292739316 299182538 122814382 2095932 24965196 687460597 53386062 827025884 937153771 135531032 178158071 345215533 382061677 689358247 114831399 574710208 291582342 59307040 24968046 678734979 598223602 207805940 426386356 614960328 439341400 848123363 611486986 67607339 226038972 522101363 685551594 405339353 461781245 636657749 127739205 710087263 800902479 260713690 518520852 728548717 492393918 293499991 364200860 840391941 103470033 130678030 872551376 997436056 294243947 234537410 606072885 120930705 761245871 294055579 501368608 681519520 686671062 201786188 60535651 951379393 45369501 90332180 361853622 138745477 458760629 271657088 781284900 691398889 854579682 936927573 340121638 379115850 277009452 25043040 678376443 660302737 12876259 37778091 796703016 903770958 165096069 70348353 337652643 582636766 88506008 970971762 384906145 415259011 321873066 583647618 676669715 469805277 980639598 96629607 847583595 937662666 264807463 182981755 227032444 418463683 783753946 484539904 53260989 350161342 315045533 736370485 905040150 582460245 991049985 607740675 356432778 143537378 491145828 999388800 365610252 521762996 283598987 44050353 924319072 420917133 735376963 837813276 431008904 223582326 882621827 17438843 21480438 443488314 907255908 161450814 624273505 334813972 748445044 689586379 154206200 531015663 118120960 592238556 365888537 10382203 864782877 366769146 201885587 181625550 819088714 6277870 171416360 411045531 202780600 134186251 266632644 638954803 597064300 295501151 700857248 764048174 612967528 683824779 939740695 302802116 103532349 748528986 237910278 755912727 520168555 90805672 828467983 629613568 934838112 452584368 724368396 449052667 948784679 277338586 294609591 763157879 963637370 220131743 458360417 549179132 881886375 955017083 625168382 223228001 925098929 110497523 11795990 811497239 751821533 536456141 88234928 816103729 34349584 466559314 612764316 502055105 718074467 898247083 17288382 711078912 297902026 785359775 227822164 12504900 464190003 803470370 221293575 530738055 934651383 909412495 197727131 31644898 146854766 312204566 367657523 482207003 282588012 445608778 102930812 53695431 999729469 471335907 514273720 351983081 744669214 864830049 905848291 183831519 66541996 238291524 121010832 296836987 704081916 682299039 964969249 188461638 850285107 493885707 432776104 709893962 413180667 661975165 684307670 987459884 17775659 577446161 339648860 506650303 963456186 491423060 315706092 927261981 285615917 114148223 326394319 462930693 127308027 547894033 921770204 531014656 613345178 820228673 275107005 437933710 394293517 622822603 480178860 257409419 584616345 744322909 357621192 509797975 611714682 57817991 37753843 606161217 853327143 408456241 859762568 839603227 605990811 89054735 230519039 774795890 109504859 268480761 337550017 756793338 742199644 114171426 792331383 965571452 997277904 542247384 874884441 548681008 199502027 651945960 542487317 276786865 318146603 19942792 473533840 136616419 361979720 12429170 102319237 569658533 57110001 575152071 18476365 962083980 604655307 704558736 369077295 756727767 112893804 618246833 880769313 559527374 74708332 269242447 397792904 788284220 866182073 289464603 979334651 410168450 766275796 972837338 606200775 976083069 779361651 605581545 358763871 965744326 70800000 958943200 41723829 197894342 993111117 761036497 389746109 771329232 924340020 985882014 188635885 846110658 990125382 423802542 375071695 476597033 657324685 672244032 200470396 362669233 189239584 294703562 477026562 756520560 484154621 33334515 176630043 5622384 967283489 724588734 261788069 443524840 769253512 525458331 801918330 482192199 681247882 690513745 787932486 437284733 720816438 370651902 20086171 842945528 933114715 678139151 603876009 816809086 646875452 97386084 402165642 805361642 542075929 210939041 81962177 3904088 386351648 129787348 381284653 292190236 68437703 580700301 808917450 64659599 730908113 242572191 362806438 162904795 708358083 121689020 474955363 404619584 55611843 740917382 209527085 631096673 997791887 431492429 751641987 377118693 836597144 412623368 733984989 846222084 913997163 990488414 767821392 75456910 8285673 786188134 344785341 222348510 98559841 530413358 326619044 230220312 662311888 271680769 519952742 603325697 677074113 371546647 398099058 908437534 290887327 382551790 983803984 203370128 370652685 590264310 995849110 92177168 445641285 737289869 45422113 99191561 323422851 895311071 379670836 151879444 778326114 894676961 840044957 559384951 793032026 41560348 250386 932739886 379685149 363920379 584566315 354506237 989619159 459674676 614559684 353415926 42721155 26454363 647992925 155666475 8315233 666725710 819875460 456779931 879516408 284407675 49454484 858653348 328382284 819408319 563053877 833702253 208468166 213073495 110413900 910086391 937647555 264848939 120716736 441919674 5048176 764833281 698417153 809516631 351951790 418344558 941106048 636776207 472531735 720878852 103573256 201490577 458213917 857055017 704802887 772913682 243656861 69850956 159690624 88543949 278681173 206083588 155074645 486763842 165760905 918462457 748287590 476526136 369856472 220989846 858913208 555414116 797166497 229907992 249903754 800797854 59163647 324145022 521996801 7616959 713624292 415283017 345141036 226766881 789486447 37536158 354950766 212487551 190089559 385570880 204706656 77739628 30652177 786335087 635317525 290858980 602809974 250797204 162252923 778097010 712411707 909649258 238280254 935438418 184522170 8647974 56561165 817453831 35349442 506625959 611321007 44139845 254195104 694909284 867328051 720126588 905036804 186661828 163514620 591311339 903827028 264728483 727823522 998434497 500850753 579955413 219756282 68848671 408712567 324955304 728751519 956638202 917304430 615655596 759559407 847130925 8339243 497455324 406553187 120495810 967896743 300949015 861721444 138821362 479750263 282766042 763872734 855367870 399618889 858591892 213812899 217624709 51866289 509189066 118068631 743310507 882483525 18437177 58400196 659314316 903719519 813755705 551310096 776087056 789498863 489900249 998664285 59930794 377868128 931267038 524116863 451771253 942034814 716589786 805058305 623266724 16001707 875900064 574365705 144415468 340802552 865946669 378677450 518408616 264478275 3481474 580196699 752190544 341141290 567779940 82345387 222148558 946504660 177843205 325733225 637589776 346093119 438431149 786617761 705882772 707928589 730428896 173301922 549188899 250298959 704637280 794207261 250128101 169873402 366231099 704565489 604472457 885471386 174805874 287969889 990598037 749231428 668313199 736862472 824600798 360734418 59365109 620912446 993626492 725724178 664256102 969881693 714211834 105422810 549016621 37471435 597210428 845104360 453931632 474517344 37864194 402089532 42027038 280423869 173223124 799191212 69632640 737255980 825983817 12390035 127873667 358528195 80384353 563183316 429618705 215481712 487386170 888704180 184342274 966120468 584636516 704194934 925211141 847484826 635304945 288419926 743973033 196705986 515923808 101553169 210857459 690017349 7854192 146971740 241119655 82878180 528705017 652793066 768258189 151776984 804922886 589630578 577194500 120383958 405741919 373974503 249051959 773546918 69794715 703144559 313764108 829559662 88087625 870682882 643651303 10179039 926650997 929340193 963653732 720641306 355984144 265684303 251473981 686358133 634632809 673242249 180957544 666521861 119663822 457719400 967160488 771501431 588244427 632969534 709072038 686794519 527007746 24884055 189234203 343081421 471107652 262977815 204151569 799908746 42060417 508320178 958681447 862971907 593917275 73336135 154768785 26520092 761487479 303183601 106971600 54579898 119590492 470004089 637516251 459614231 484786250 759738652 27435446 5605005 14027287 433099113 661543029 106386090 967321842 348468544 386738140 855652430 82176431 649366047 992099323 257157278 287874606 445365414 645001385 134150517 750470475 646014222 462992461 346543777 269089578 364379853 137171764 970796462 480868415 578183570 233761021 750256048 399884418 424702756 438686468 931129846 93650707 258965295 920633614 28593578 871572437 150749402 93712589 18721414 352762958 325966742 844043680 51678615 402272712 384474018 739673937 595069603 233716615 771928100 910176368 768304508 186868515 296925331 665081609 528538140 674988580 604606687 786717473 909232223 17642561 395986041 1397679 465449488 643257615 699747028 879975666 337904007 602947223 376357772 859706817 715444046 7935066 164949746 617569790 347869540 9245049 334709292 247012251 330516407 604395228 58177926 402894351 852199816 836184581 549835690 791504647 101471280 22716150 955449235 512528928 105626113 925882827 901988713 497140491 326412589 37338768 876021828 519423540 368738336 28215968 104154519 982185599 702511405 315671124 956285137 425579898 447960962 872270747 850786590 245632678 450310932 525452347 908016891 532500244 57777533 69528440 67931964 57561346 509802672 862403005 621444397 736161421 621894496 451555743 678617696 296825718 808235449 309174923 785564393 761682162 196950071 738091860 627214162 976383017 968466767 87160112 930525527 16547030 734966039 518930100 917639215 133156365 443716613 222510466 10352233 903600570 326845373 858634913 519487359 489339447 971236804 599023147 666292139 502245588 249447270 949276894 830197748 993868871 401525177 859557619 57099046 738767384 634411977 298062446 835867002 132936795 361327466 837195255 958787034 446078128 715957096 672620067 48633648 119263687 424531678 316217131 65460045 147697435 241632321 730501310 572112575 199027824 361989457 119054458 945418393 822840895 198625803 803169235 613030465 675894024 366058339 645167840 985919873 616983228 302331332 116336336 435617377 126090854 727167086 441340936 27138951 654561977 196108548 416082706 398851722 453470261 943493725 767621339 648855155 783176895 108719291 39930010 738163719 20108078 569589733 776930584 552479209 35450550 566253756 213800374 986351378 978385376 341057565 708790782 519133939 219290509 788811806 888770164 705626277 99664698 776377595 239335548 967046433 38292180 834844467 183634283 190138650 164918878 258168622 497462986 656787484 848372925 596725151 898130118 77909132 703504996 207367870 52618361 281943256 730255385 564090924 77231876 227749061 590847760 406008693 903478566 794031078 747892499 235000399 209630709 343391289 551440768 340074155 393178176 13369602 346419224 94543442 752762603 922019414 44873796 803788671 667771489 257560611 344976350 863571123 424132478 540086281 610730466 446331148 322796262 400779923 463651167 846551694 918069202 304366316 808880353 344015050 158586205 3636698 950387382 432933909 688878525 618183229 861798085 847786999 341806830 173921541 463183733 609816503 221815969 640803341 255259165 320873175 572812490 854156536 34657097 850761744 766244566 70936233 830274200 113502888 473873410 458518003 399490011 229461452 36630843 786839395 632319585 618600432 571042793 602365844 692047361 202381745 373052973 245108233 245884403 872251966 14181018 771138465 322103668 490726508 329815314 275615884 638020785 396037040 347278367 182957736 741225050 357956429 13672983 858034143 574130474 873708998 836188291 614458469 432226395 15278773 57332560 840249828 46358498 830998527 174842393 544136449 640981554 885002604 656961798 717313373 646738410 89257165 380518363 19243273 696543154 593325286 678640502 199198622 495610872 207501166 316598742 689413363 569243280 967445936 154980224 184317827 693835184 242644439 522933215 163261732 665333131 296953786 609230765 952058316 438650654 238564216 982060477 981410262 22803997 370620099 247515407 890452680 207584034 950137478 783290570 202357041 778529209 877294906 19919143 605203420 589596700 38568585 821176867 852152116 649674975 700713537 644994000 344481926 84934116 807276175 114510484 973153049 370493429 744661381 493484875 628024514 102857792 480887346 817647545 856701334 85833927 273857005 747006018 660799922 755793216 848327167 149105642 115456136 716724195 62652858 96658014 94158910 464444849 135691710 630139578 904764014 132719119 336384533 853961058 91846704 206034522 601252132 661995463 388101330 807244057 191731977 384205200 37723433 587871838 878480976 896455566 37443010 693222384 626824754 782691381 182127192 938891312 178200648 302914669 562493819 79673079 429256103 642557507 26399013 33615892 112614433 40728013 645768918 191030898 378000669 632723693 88157002 737105066 429981398 712835312 485442917 608171979 764254890 169612954 539249907 557955003 235893898 811350797 338968315 10327963 573546943 472725357 128888061 886735594 217517140 741733418 435262596 348364295 233310185 169489365 835968245 53890347 236352644 26631662 687333932 146724075 972918635 245747473 517213618 297665029 619245127 777180402 543254368 341119192 147207482 754521840 939966142 396233800 604119548 294145998 271932103 179249221 615565120 909884084 385393594 335884565 116005792 735035636 902024450 505273793 107554044 515684469 780697468 625347855 985731742 907676564 479665700 433362656 556653644 545399408 97719353 213954418 276731684 297555926 223590449 804163547 493861480 277330382 718772031 896724817 398558404 996676196 596717635 703809328 386867947 260813956 616814197 508544275 657691708 549725123 653624097 897320249 383692363 300953853 330593791 961917288 58664486 337524314 216458102 611631364 702809958 444532650 213053637 997917279 33166086 479384599 280007852 760614544 336198108 512387221 690319967 589450905 734880354 225495374 908684353 421332700 433311286 192748638 231573640 151787900 323551233 538473288 604247429 709539467 945230308 985284574 119490387 333968981 565065442 477165812 136232644 593403452 480577931 867368750 705618962 349283691 528176511 812400839 82229275 811378938 808347570 791661661 629908046 660483094 698425491 535108915 338255546 713128295 735172688 706105804 78978231 573657695 180080024 987630615 355368708 73968270 521545532 253267209 34687027 893156138 916430292 603709616 220618281 925617720 46576717 697969160 297731205 775321536 939935264 418531405 277334047 63618591 453331677 294503335 552901876 653502594 575773879 297635849 965579845 72011532 236511060 888247042 644151112 538879897 529468876 954047966 862455978 122862016 465276299 372909149 255940856 108491508 373956294 813900763 759372103 980176628 52558763 569481471 805745522 640837964 299799712 729388037 23112811 211352397 78713801 18024815 626279637 318851130 610272488 976137199 761048562 231165298 941474196 663480227 768525697 725877927 267095958 466020057 543963003 716329207 257200455 516796689 868777417 939548398 638668370 413376305 430980126 442910305 476289920 835814079 99443448 959779709 740251116 589124100 806208056 858271714 930964371 497046219 459759799 900807132 393321894 667342073 34511893 925318478 978770550 818956672 217941063 785421548 305361637 365165231 367300850 194809630 363523527 423932673 905535124 449388560 811841215 58045379 282977998 417041577 390503238 3922587 141077246 974934414 778499055 695755657 639887090 945931202 912189891 943970054 411363036 579654264 968743446 780700420 667358007 530643685 571822977 424315949 829264104 315798130 428450752 887923580 584108673 806839061 628924039 23224482 362895167 771570483 321237484 861526175 551499832 38988444 875505344 811626338 162964963 697369771 185578668 956762338 570609601 728101109 264287877 964637518 81503767 507774373 409497898 526398096 612911491 948983419 903317324 335370325 406746465 519640480 302617463 195418863 830463426 388763934 529348510 167059831 930702882 443739416 170343593 773891570 640927562 614485740 79794532 935967746 774038302 160598141 390460302 404232273 250076733 952812311 581098449 974880867 428508952 551282289 846562798 388270049 612881925 407605529 210086122 758751698 438994865 622756828 488638025 169477206 558637303 253415939 149190618 972722654 125647032 322012672 722746720 246566576 200332417 40568600 17537244 795072871 728250282 581506078 773450861 317602998 854479383 434721428 869595522 713736579 210578108 141029790 33522227 13653089 483445900 429019743 761285911 628517342 772776141 919121081 632498909 89911251 16574846 299115866 707039790 295101705 380038822 50424889 738232499 178630610 355202165 890917936 23144516 133059958 621496422 134407689 936936049 62141405 351282888 586510752 285733634 345025693 596112963 522859130 913837544 815259096 184584900 768959874 16805541 833437331 408445734 994642050 203004790 219196533 928251765 187304064 568721170 209907475 52287321 573139632 268372133 238305223 272038028 444758841 504805064 630875595 57663193 161754838 542297103 616735649 435400866 847212910 42261529 629985298 223524783 747276785 293499307 513465864 110121551 386988332 437676554 56010435 278346556 641372483 925572860 564133221 153918061 43677630 496538370 107889934 29992445 131674731 710937838 678640387 490733158 72014149 978679324 176577908 697810228 870742351 930521464 261568331 250588405 107155593 707495622 498293072 330965399 798810399 147820731 678421793 74441650 590939724 309983476 105372663 303250905 908146462 297242087 601980201 771400076 924317790 220997744 161351846 294206681 878485035 873364427 993725579 69578983 730845692 460686683 765483280 204712840 752822405 535074598 54910547 672380879 911958169 344251251 773755525 135209269 952704612 763131690 393892780 245134247 533465357 952393900 398134475 674736263 744719928 838163352 666813905 223711956 647153780 632168140 423658272 388564121 205716230 680594504 786895545 572521143 760942067 794580073 149050862 557858420 904913882 707969326 739154463 554740209 479808075 911962409 958907853 399683346 596649294 529369117 157641253 235567956 712086175 842526640 813811167 255275889 575977718 439430116 964368127 513536876 772509142 761542343 509333299 785380201 145110486 896997197 956697895 654449000 319015333 414255519 517755183 650842858 777056114 832546707 606247178 467946734 733214888 433064639 64884355 902564155 579385421 547395830 583689808 344547700 409490793 210963954 893089499 249303078 778128579 685382530 680639602 78367096 207519397 772045622 907244458 471586083 232942120 233376752 463064851 110435186 967332877 410615873 35486253 692280013 792195079 286760358 787044524 713812466 652985419 84719122 459330297 336229461 48205589 348823025 376476799 111636486 978840312 598039675 849005188 322335614 703590904 772462079 280405521 454799342 756320313 240119096 526309343 645582233 61387120 875236041 680304852 468512904 234987527 725013625 979134209 506463267 386411629 115331670 57192073 463328099 348944395 684392094 744542796 944189260 307483794 509644703 73378269 773784185 637007562 402682476 414876041 534627482 949360523 506143873 314201429 477223114 614281565 837764753 355639258 3158558 347622678 404768791 645314419 124591668 221315260 405115380 531648715 263034800 838285568 258956522 910066469 193094997 436366988 245998697 993983328 789743228 619893667 300017821 302195657 731696127 476401929 387429670 38715568 505673497 999190723 772840046 597388818 65651282 244321955 386745163 454462127 521343571 674069351 858152146 914476241 506769442 796336834 200991993 118845883 500155936 629431360 1456286 805545229 731558758 904028296 270077410 341143350 176193690 898855326 713177154 128860698 78780435 993581465 859021515 953710101 210476066 463756829 183736057 740222856 264003014 694371751 687253274 776722640 164780279 656323222 87285638 826388252 142733021 250479856 328485339 437939338 653578044 905854727 122098251 941075764 60278982 843004241 89597875 367549903 466559956 531433647 112247800 210668775 308128150 487424439 669946581 225264208 864365116 968734704 466195484 464775291 106920149 244014831 688966765 636395044 208815379 845842303 593019858 921742145 648751447 972275727 395009576 972447135 19062326 314580208 504630722 803444053 905637531 276345896 917079444 432667774 503812849 513819204 397602778 818853809 646763553 314887288 976298004 99599477 207616276 700964913 153191908 293917560 807799000 834957104 290676939 906199976 974515395 248916716 506138134 493316379 925722890 145905908 53291213 959268293 772154521 925846259 831624708 151982900 970314364 560263446 249804313 169227324 930690859 832472017 883739649 598749508 512272979 67729811 725936705 801117517 124777913 645716437 140786221 706316221 817106239 654542583 30582383 576691641 364751036 737836705 607732462 714584514 998614773 734425322 8916373 266515694 181060961 243388043 872907652 445980172 128249382 494105766 993587744 573752305 285819644 298099219 968317014 285115397 210507850 796088497 37282066 343673345 976839097 768867516 724655826 282965489 210994181 630708618 543282072 939473397 596006980 146745227 38680641 440812716 976519916 759472777 117172193 54998221 129633507 367262369 556290607 175045817 961340048 783780359 576621865 547166752 825587074 293239966 598990446 20350552 175943877 942033148 970828449 634582491 171923532 781108936 674309738 377230915 735227543 863922707 549415142 908627997 15990786 770611215 846195613 924870950 627258999 934178038 609463729 974808756 382238098 501436166 977762467 697671115 290554276 19856650 572370454 640155960 630383155 513179712 891993119 579518805 458081498 436971017 480939262 584693532 26876497 947190303 427324377 623850064 133123957 227485045 820435491 70463408 399663637 992921312 872092677 566706494 89433009 457609045 583730346 474288440 77787665 64984513 12582269 534396774 343762048 581464367 783211932 980167714 505539934 657464832 594072025 299353717 245442225 222848170 372435282 742721984 984705490 395830267 101576624 566109739 268462450 858861975 452686323 417683630 422936821 57811567 231171559 982212775 119585032 3850261 137846158 805033 234918373 541259539 170085622 2118784 623734849 497927048 634952883 224900294 26329167 956506 920038270 403642653 428705716 8167310 824000699 515598097 531492669 770280583 467777902 931673201 697882753 407292937 267127294 239949355 292464673 127987965 117188918 613881010 429005673 703895457 460736945 138596202 212452962 865172631 518238350 705313304 39885793 813641213 633571543 991430343 465807360 579392304 231301605 555002409 447907973 280205156 913974685 507688235 980672549 520284692 541208543 909356096 354517854 98912671 590472883 507422900 198349268 384305152 127621392 21076475 96199632 119880424 661471350 485245305 31628563 193056172 412842781 836162611 800018760 241253202 324846594 199581812 378475951 34869758 313040860 187252556 584688075 604826419 140945245 576117144 377397847 848722964 531191409 259876748 613243597 488397211 156207327 517092962 219139908 193790385 350158963 313423307 635855013 770254133 874322474 381029589 719275793 452227825 515080981 79839543 578773233 623818248 505526141 640589902 921379531 332441065 638043510 454433823 482731003 129599103 121824922 161535767 422538300 593188006 580121654 966010362 79782852 929198279 319146887 310708000 126150850 963291725 903897514 545558472 611174318 292419371 515161972 56967514 303440045 753877148 752180431 773627427 268256193 659449837 368046083 766209097 108061293 525486321 411147013 442158926 641020833 270948511 752344342 24943221 219391689 444878224 740038136 962938695 423344589 672531160 976584753 262394284 518875949 62990948 222287161 600282457 917586292 886199056 331204582 751141712 253415892 59564037 508892509 108832870 223022638 417956386 206447504 542924766 158977700 585592630 805614350 639993656 718844941 880007879 539058780 419143112 612031973 421199530 374902092 149965971 560740773 899337827 113479727 775096036 222473786 927306745 92766270 377186258 198429030 852546863 181170472 911309559 88851032 398464179 753847126 645358830 179434776 721375204 161422048 777961125 807815553 898222049 233466274 277730722 923069814 449361194 801312942 899910781 673087632 536556551 558392775 926386257 894959834 400205682 268397810 603469408 901542974 36062745 35410635 986147797 368943931 648058866 649581446 608369520 450244735 183100242 452469551 63009600 311646340 581489592 117508754 392089068 639232652 274806540 336624606 503599826 396580190 711199390 128987235 816918523 202443077 288979734 393246858 624230677 994492764 323515546 86896364 406779668 414209495 397433827 440584306 565698869 452082262 248567849 684717877 245749690 435656756 924238525 131454708 486992011 205608539 63879735 899356330 920693688 151321456 638500426 718570058 798460861 5261837 870026003 354848316 909028623 259863502 824562183 476678776 525413927 540244633 476003902 753002291 759281347 564602730 123143240 844129392 28563515 234558398 730704203 946453604 348284416 14490009 149137258 265944627 75980159 938146285 426744919 909640852 899386946 644941072 202081223 672561562 319066060 159351629 925607038 62432890 848425934 574851987 923893266 821890843 577977177 772712949 39552430 98502698 625521454 4555855 756673868 188951927 142588988 21486145 769353842 238906963 781634057 840774793 703103792 2111979 673928012 144124180 833722986 507448693 635121409 579414982 974491643 178436601 77298697 943110119 590219378 115562928 568233958 593720618 828093124 202501152 676455513 465894035 69824347 44701188 730681845 947410376 605828529 900235505 126660452 531766713 373751559 923299874 557182937 845915306 464666364 363142214 930010536 451136197 12914438 427865250 931043943 855051176 51952822 223652117 112734106 60218530 464262337 692462401 650510135 783986974 491958151 356916919 590528714 741863407 244356794 789667750 96024767 739843378 589917173 761524756 723528127 298903968 283938130 683189601 163795988 921554082 352757219 10863938 254643555 55641420 783333516 711561438 194878841 78227376 446368246 240311362 757942905 263917806 839946195 581205376 566284227 529322338 84861990 531819815 387129256 122310040 692049577 160011930 870580417 793510107 578705740 190098889 782550394 434324703 23792333 143221664 103135771 458784929 467012545 354315193 600499520 770668077 810778400 552965336 979776846 225400360 259880229 472601882 743570115 723619195 920771248 484542418 163396282 298240071 23918146 676124978 403028042 527206164 239099229 232749460 971838582 276846054 831038528 308375453 471658688 238973492 764588996 725573358 95445031 894844944 771986437 605786900 817311527 100087518 278706186 133311049 393741829 241666807 317934276 695144231 483009883 950558863 897359919 536258872 138465544 606438784 968309415 294276025 874642468 338142856 731474176 805757543 775465126 351726893 787114473 255250707 401894659 791428707 525080113 886255078 209618223 909154635 988608496 817095006 830512380 721516864 608044632 606693384 816166021 903837212 33141115 555761046 618126047 450864925 858710878 302538421 322042620 817892086 784856894 632942970 813256183 96322961 766478650 664257373 28236801 753728570 431702252 716657085 427383403 962608148 315489442 883800477 14009790 161505176 970853846 913108931 997238234 716428436 6493292 950024530 315992836 867046475 26721928 808709476 205187082 827008154 888313318 569571429 169908872 666879648 592775764 747975339 249608163 111917214 598270838 350622568 557093823 679593672 396759586 951979897 767598056 32695054 397154711 685851053 252123260 751128815 764106949 885286276 354962320 276681613 403109824 742012710 722320882 463044654 134845114 445459826 769473992 765530994 204029415 451642876 426984328 342051273 629667943 717315240 847405979 994716398 638601389 447368277 936975641 269177760 566081656 850435082 330482513 706286237 835298580 145840310 669251927 855460963 506499025 337783297 314351668 119766803 243338525 590539112 817284353 930302137 139891494 741891890 820520973 713120030 412632759 577928727 862649880 305614721 481856784 312196688 210344752 965495683 551266915 622704355 278895166 499808409 844026430 511701821 300448031 490491130 516621577 725870089 230676115 558525045 713055455 410816400 393286623 204656202 368219743 81955236 248869416 477158171 658588938 114520822 570711671 873441774 874286097 662598144 215341300 65541057 698255869 330349931 701026415 253118640 134401961 323909522 814818594 808212371 633922145 22998044 828459127 7698528 163634639 70985096 672295820 310410422 477637572 553670599 877555335 282266192 639693244 184853175 129628360 342564722 700206815 533240206 778059971 160277890 780762599 910448341 516591783 832607348 645032027 291703726 937382993 817563805 239858643 185837573 612291119 467636878 852414834 154297748 306786250 227076546 809499176 149365675 848884569 419399840 749411489 218999339 83288845 340018949 958748688 657716374 814268979 458475436 80749624 617655718 286993431 289888659 957663037 553622216 748935643 809634009 639197655 190434048 559117654 155035560 625667019 425705362 776893664 194259544 262699903 971122211 942497326 721250096 712006520 305831500 81113755 214224903 80921963 122132357 914568253 128317091 132581287 826110544 430451476 851081676 928440658 425386765 512019999 854579290 626596103 134791582 172658534 849497453 26397888 432031692 876351785 271578701 836712862 316524730 968990865 138513260 586211376 424329383 756205380 314519543 227221671 708218631 959680082 875163893 633504653 564063168 388988308 872492430 279941917 971062649 927892616 772802846 696103962 20250156 761217284 353748063 285170703 665531082 39919850 397137590 416435460 137761797 51715796 357464024 600354342 337119310 653352085 506751694 645721910 563147905 826955212 330021247 378682142 324496129 921445531 529893880 273494367 475374537 641005081 931434418 543016529 520836339 10147633 696734911 567474480 523144244 492981279 612578283 355144708 437947731 736917468 621108645 109753800 110169837 904851809 288166832 855304842 573167661 359658420 973836812 396121036 513909070 995240322 545994397 659187896 603716142 783087785 679891985 295840595 847500117 495040326 591462032 716074945 123852964 203747321 171711803 385216932 116110651 931022627 615580179 752860022 139739507 205611370 934712398 632157281 190994249 513220079 344263083 211328185 512942192 510614667 269820660 677724078 497094436 83869716 331436084 119168620 617882905 131240393 402373873 998723988 160647943 425503254 144209648 129942756 824918346 306802326 998518200 85568198 636698358 802598023 804994508 742142999 162441300 14728257 826666374 958846141 420997657 152851970 411927771 910274394 206115469 606873044 510382329 221437575 557124856 956269797 292234765 345040943 820477610 621925622 262409136 991577079 887921281 194941935 964650935 517428681 339984531 350885263 172168278 299644842 493036989 521727845 205268498 9135506 174858439 94213037 675953328 450618601 857801573 905133877 139156582 355588406 572666043 84135368 53318519 722827674 318352701 875418324 803749483 245687752 987061420 430698396 55121916 911388532 219692302 134466872 207581148 682950428 55774266 3038066 943910269 525405602 422139934 320843801 57917116 659652536 482786038 338849335 222290745 853700158 433870286 536803126 252974392 193330829 837275710 963580870 589806086 115969987 447885211 696845569 923098640 930207404 600587167 483274323 111947923 543330590 306339778 903494082 190370653 144986213 90147579 255002249 986781282 517057083 889753456 722071330 914573790 341970774 452186783 459742934 223859161 389663868 568280154 969547482 892119055 246699927 123969618 987335441 56214196 254072190 956316245 222421613 321305906 447564621 556195897 604725821 432855163 436308127 972274904 17033857 805885619 937408377 931991541 283230787 870676814 503225523 735908897 483106170 485343958 242548155 549291952 107873905 2762137 247874022 261677286 810785680 982643718 966215821 883826874 737023181 974996867 982722405 893349649 904292080 929123896 261741534 552667070 705245405 470402737 342296523 787281373 677795930 693493960 745911920 630286743 860703191 605201075 830542982 638547838 96540823 840949062 795792427 153784236 466125654 403318496 278417074 743270345 924300169 266646739 848747046 917886025 131927383 102448081 66676133 643164682 510734499 568557322 927827340 804928220 575466110 804193643 755495422 872046666 518011647 725163857 282569908 621215377 549124981 955392369 90391043 357060355 73816004 866789693 271526652 480596595 475338513 260898379 676774076 571915148 613275224 201733113 496289833 977106021 301566163 843741351 462915746 231501258 672546770 513314037 381236323 892189663 100543906 290119552 707835136 572999002 904445038 140969569 195847675 581654576 261288685 131055781 834637892 259042639 634526573 953732799 812542281 425610422 2292546 758063598 83950550 777440949 482783040 925958833 66652818 266441093 165639630 430393609 973473009 610566365 779735640 328653440 670186818 769805509 875288839 717797024 504469262 356218778 660175905 538802613 78407203 695726045 353136017 988307245 136385388 477735378 120891146 387958037 345508809 962867651 656969716 303213174 887046167 291543261 395918929 482907566 276358356 214396479 831905238 871638887 40193936 127250110 404307658 547754661 943399021 263349073 74170530 674774935 174155330 397556525 133703172 976818514 781996951 749507141 263894646 843243613 296035301 391453536 643979922 208834032 434653953 593006975 519212709 830462232 874978075 651328293 523309909 26083987 962870855 173396219 211227492 433084513 785026966 480861538 198760618 894567235 686295279 614511843 890301496 910021738 199987162 367181990 628146297 464339073 696982820 735544921 718899931 321621761 932733492 63660260 644126048 544805685 714204741 109818079 504812357 459206409 232281648 14381353 893071409 467031753 691701741 326220290 336096764 249965613 688600046 530198039 364108455 874897447 775426243 417885734 691680355 610200365 324243921 540509735 904214699 558459696 122565059 703461649 601031725 49339058 140070306 167148475 335716623 480588097 545563112 342727893 413978140 161374025 60133973 803151902 546669511 758589898 191952686 873774650 640967156 544302931 807975248 448548662 273780873 558448807 781042226 130678813 681902379 479258576 925468693 784706146 206404463 389940054 309535569 116138886 300526472 831245615 795981590 282391297 93428880 476654738 21160296 279994513 42235479 70882480 649620519 163870716 37263231 490068032 77197791 839565533 124330850 944170214 513431779 399899761 214582545 761252164 541756563 571519888 682536565 330445404 817358156 142363449 849598083 198285360 237496534 554927885 755065786 740237590 781787974 867362074 79842317 442511092 308949592 661484195 280702460 200987183 833361987 943347706 318887002 83010537 902138927 543666332 758048026 924308913 828650210 994988798 699882228 918927195 785601904 408595215 459202723 288147854 146560408 266042632 446283927 995601357 596138729 285163826 984564538 921304873 435153766 964616147 313489480 243804510 292212165 975191331 829692443 495272286 14443782 193562350 124956369 618444860 530346862 774176432 705277452 21228701 589495809 680565835 260564788 303745224 738034314 761380206 48933287 681243394 228477498 449644692 859043658 19136811 238893321 982429329 960943712 212081442 24750464 913715385 181663172 942324590 219623606 428263672 583104185 700867762 461971775 77180292 877086146 155762277 376081041 554458096 735177596 433553563 217672309 699946102 636091851 221750954 997239860 465333506 198787897 438881936 69149770 895324821 982536219 108820169 666455888 343796611 490692349 996220453 208435122 458882702 404585321 435151031 727603497 496786239 55508933 27057116 573653321 30434881 570572851 410480152 78066741 398453715 724102726 193702528 347365052 707754224 173008414 795975573 493921185 668644000 689968197 17723062 744627550 903005978 828764907 139146831 111202987 555706178 750597484 92524809 868261846 570991294 362444282 366762048 109854614 331871761 691523584 429818705 467065041 958546696 252260843 82810512 439809895 568842167 666396654 317460703 290961770 546455771 326706201 357357211 637164830 604085401 732878548 154128998 631374150 71232821 72369327 116543986 813839338 287398661 613208893 887968706 962910050 783170267 396729664 876530731 940010638 170433290 893566783 949075925 877975129 449729856 206335783 8973913 910092334 222451334 61117056 125403145 297668823 169848528 613496611 609568133 460179986 564122179 446763999 164133459 955168678 546932477 370321702 180859446 2182574 561278852 246164089 909467482 386691138 668945902 199972536 843576228 399296188 102883304 764997327 593196157 526155748 648844369 627890675 230161612 164794493 744918401 364643499 35301153 732161239 247988072 271095394 973727275 59966515 663650234 927114654 7210447 730506175 995920441 627771383 814747573 158632879 92628211 872529201 567511741 261972720 611763497 468803639 268276731 732835751 257040682 645555459 725495576 411929177 66113746 89392949 755351660 338389045 357545524 655300179 908218592 300706536 652722606 460533752 677229531 376364259 636267475 316262070 11866075 262784649 31853263 169162605 337367966 122234377 378102627 714921333 54095315 9848572 89201744 83683139 154375200 546991783 661384253 384801371 804073715 72732123 624314982 188251143 959641263 999622997 15895054 162176012 695455719 897634975 641314008 660888909 895113804 680818659 267447151 725806731 306203699 491713392 743206933 23249621 332044460 77774573 142003224 155680697 639911372 947186962 927710069 631518927 383111162 646324078 179303121 313831240 707438577 567445399 965300198 828330267 472276184 337903557 194992222 571143324 236703565 888232267 898459201 769524278 796474545 683802360 565715766 604457504 857980592 604700932 377357997 629076785 756045323 583174378 23640551 292659290 854990950 183336925 875395389 525067590 181002402 855396765 749646232 575049226 617003980 853971300 731380161 843086963 766821763 14130750 887298474 9808116 992458824 179624971 604442365 395322796 112589382 718204903 982241038 315364768 473027218 682357790 356025791 834691102 190687192 807227209 748502530 379179337 469256334 339504773 669582848 857488553 448819512 529407019 374173557 813705345 934563113 830097586 919663888 132894814 89881395 561061114 514440613 583611074 960061897 56381192 308553559 742287066 85427574 515391498 864355874 9779783 583423180 429077092 463887091 910437769 88686024 79299683 19607833 688943567 847710449 554403576 752096641 334805578 324177718 584097903 500896429 697066108 811204291 29536018 998120327 823369214 122401296 500196088 51812723 421415337 812078446 106776224 103014759 104347975 7011608 216611216 354586769 745157699 551967244 175880999 629538258 975828723 832879568 441333460 105066212 366879457 935941379 474499931 951388702 619665824 436761879 459641399 363635609 72110089 450816761 559199878 795513458 218805823 317286380 442972187 1672271 678149543 457272184 906712437 17971427 916940667 885052685 820408182 597023026 452602945 274393218 271110505 915435080 443885739 890583881 615298831 642708658 427869411 308849553 371662604 35257543 908464893 532951387 81933710 131144001 55499668 382202099 833825987 366986382 310610601 311925988 428812848 156208041 165585265 566180233 497282736 844113704 601214937 877457790 244731098 780529414 100216541 980355331 610263429 663784700 388250520 809014184 986704238 57539328 731299150 152589407 977140520 336684146 644249446 123602565 386696931 156605339 524280801 828661001 20651630 925444315 880220924 858880161 285140051 355208659 821471382 951520548 585876329 855665633 407537281 966827553 856397228 666557350 141386542 119871045 134889571 325429151 304295806 326584248 313351478 225828382 257351947 42176273 60321127 379102228 565995909 179776785 110562093 335727817 587824603 785904627 772462296 342578614 185983542 60641561 634783583 993698014 512533507 141573645 585685079 861188250 288687614 448015968 719556198 599022266 974847368 758708743 805238653 932794954 84662393 377875839 414669682 852443000 154968425 902536572 171464898 477341481 839778963 686351861 695279492 665694838 893693144 657997901 712733246 933990559 603881312 181146433 58165118 891272550 522878431 425240689 509630271 118384005 254213667 495360470 46598808 499590465 879740524 324378639 688963387 611478409 958785790 597407678 802661820 502926773 431257491 807222050 499903918 917966511 374237709 961842073 778885746 295407621 30391658 40490034 188197686 582124172 257844123 99844017 772176336 580290450 129226735 82569915 848759583 732399401 433806501 476850639 75088443 890684218 296051026 744118377 525328470 621131716 206812600 905538332 821122422 698811150 578383640 279103036 418262528 367509994 428339560 34395344 397340346 628729267 654684119 316583370 450836190 202739219 193720558 994744803 39890380 260663284 681217220 458616591 895822577 666496504 284218564 828848671 989133480 92109045 618712021 125993729 254615415 375873096 247076753 757215663 684526104 311048725 242385081 368228564 865474414 638704269 898596383 784583611 939364522 782145163 962973602 392355105 113111617 33314174 795219080 189820412 863914693 32052499 462873691 691619602 768460814 343283022 455470658 473154523 235142640 151032420 449272766 9204764 211994588 628202726 130818090 554537963 689957886 485251830 485890829 390226371 792223583 281672 14482627 811181395 189445047 897109969 886375435 488336703 623220895 75063501 563379629 224684328 447285809 77886352 176672833 33773012 889041725 349032774 494700175 884693383 806609425 337549742 994564049 238314480 548858463 653124954 669703280 289545578 859168537 988556558 803465301 101544285 168073101 459229263 568084844 688783071 49327523 500110132 74820242 885336250 777195449 252122903 211405416 185928061 279089780 729095225 295065185 197708907 785296239 580128025 802647185 821830249 728374783 888176682 479699356 794832624 577144477 952785496 423542643 743106238 416783099 686653089 512797289 130350244 710438479 491150417 584217578 610804358 324512435 249323965 380406643 938796556 771509962 804315079 995212677 239830578 719651299 455487820 155238312 88785157 480938166 436681729 55672259 450418261 17325299 41847245 374824008 374680895 860632547 736225183 93841909 600614186 81132585 419248636 959932972 356001534 207764889 723423054 549664855 602172302 428193924 798927735 374044162 124264192 672924618 313173541 983723158 899315319 549528045 473191529 641075581 639180181 67561026 688499261 488174339 278030567 76364404 21304928 988689590 943001571 148169976 427202642 9838119 766121882 432088270 369186476 108827172 43598963 984009078 904234119 890125018 958457728 114084160 580221095 683763993 176068841 247595752 959001286 589605032 253193426 157145367 896547720 168001885 850870253 739023003 456581918 947228207 4870337 894859156 938246050 651925378 310155842 780378365 606889323 314486542 506103597 573401 922612240 182087899 246187790 605448456 716714519 756799270 251853759 681734078 64295478 195315910 700159052 202336744 537040176 101805243 823848834 825950411 871614148 351744332 886217603 435607256 182477426 53672992 878350832 169651214 3771389 303890498 989826178 300447692 705362524 104184605 437236171 727062545 557111787 800446846 436140206 993893186 769539085 600736809 829800469 276333379 255335862 819153181 570004290 686005800 657073581 308847915 496046804 840721597 812543503 146699316 858088350 154010400 161366627 838623697 956496456 236443246 303970409 783704788 301191570 618763186 615506803 976076402 351340434 815695849 69368928 553537416 569133263 496411820 183773990 538570976 281875969 637959981 379284460 925830592 580231017 323400706 817637163 899508323 524260486 729187927 212761017 948651227 378904691 937526799 117838830 722955528 54791543 278463564 594375794 185197588 676240143 483753298 366838490 856707127 361920975 787693884 505819331 160501913 452160302 918684119 715685417 512885184 987917651 406203779 447893948 233155574 476800123 367381852 66044422 220049430 694540595 217040208 629557318 4105678 855422686 682393167 989994979 495323445 809776008 153447828 84119464 825874591 974882217 22957307 692957247 743311911 104271379 551439528 555691899 827734326 526683838 212893977 438514484 345973964 982922842 959514770 169136899 720386335 222638610 257496247 125201625 145732602 88582350 116577086 434766806 312821538 720606562 550305514 356272248 992933379 768975465 326312860 662564625 312720737 471091564 687585134 594168063 23287647 656819464 146850291 500410128 572225020 767216262 806616732 117709744 700530078 833903136 621253812 967114842 996707512 894867189 513213738 568576353 509129241 788868364 102615696 138820393 615262355 708954704 45227653 492458327 835971982 549736094 988474891 895211575 384727809 904678671 823014395 926064587 526155690 724146690 3250146 601272329 94901584 885117636 249700824 579045731 240141657 4886583 886829213 814918720 501880893 175540343 307715904 461083899 592601629 246661428 166472249 171197726 229034655 900706822 273782222 87872019 2716829 52446464 404263667 490132269 728979952 480921666 539003638 615901811 631858844 924310927 286329555 529734353 735066278 885552378 690965263 209522533 238396043 171052599 666594639 709259010 88476210 129095681 962073605 8423193 180309416 757243159 540804886 132257420 88279037 186339126 61641868 325929584 69123578 893327019 898654191 453900186 697693519 595109425 751062607 720502317 404356078 789344802 889003485 392553118 782360704 446866310 241326640 225499863 691582035 945328260 510750857 399840543 482666063 725482548 994354412 581479790 468019004 540752577 744531063 638121678 731702392 146648749 28091059 45115102 918944593 912981022 629736057 707320310 815181775 251226626 28429705 802675968 627984564 709855620 895057759 102139454 145715857 724386376 913495287 406227211 311125479 23531308 31963819 789392079 333777053 786882269 945605423 66401624 328801017 5842601 493654950 171380009 290586775 439623070 106330188 92989729 408326357 136210025 885196139 399105754 400129311 283510116 64520059 757480109 452508386 85807809 813736567 512469090 658676770 199570901 425447352 487090625 518926756 433368262 161197845 623067714 774084008 656153404 184747774 338423247 575109 717323062 872045270 438821943 602907125 128539877 825645602 543916079 221411167 33971829 512877246 909399137 373675450 588873768 258621380 480377379 74316072 150133515 463849355 678538918 743504281 925488486 523915654 474837610 954225701 93568456 795013227 503985793 996706460 871557988 692969037 620876628 428994482 558558127 891409510 178444349 627685425 751667061 197109415 717690791 671163112 249936590 894070864 556927884 14501878 152141041 116984237 40063158 967406601 977904717 601380545 470892339 807453089 817519888 244268799 162866943 209642548 652000062 171523660 101652994 994880711 33778583 61808159 585008725 360734796 199696136 390592516 336517690 325610417 972773649 371117478 397434168 175004754 790610790 993556540 713098519 652935756 952397630 297618363 440200243 910209951 638464882 800216609 152258309 816548990 432494159 180000289 667009011 639670626 206173226 568533160 106903069 305278544 180517122 178881028 818189891 66717169 120960336 489838115 520908793 473167364 299499958 974365388 357410134 333064145 973237219 241648934 123455844 360593334 250530536 716330015 367139499 358466432 675933768 817174734 881943135 995772517 693222231 187623650 135487352 414925117 994164214 96583429 632026756 819387424 854920530 245653358 379161614 473362314 169157625 878311898 112525406 608302813 571125652 31782575 525082671 79638613 829978431 826152602 79333858 712993271 465311677 876563162 799874860 139695329 338881790 179516481 458013772 972812756 407055277 405342216 997903452 142610793 505169438 363986282 269156063 526975749 68885027 226485317 216199881 317534657 803836597 676581645 190790902 487936729 441237873 627863015 396404319 82645216 15567312 223196202 448439764 91401321 502996668 184839910 243728407 653364062 129532419 174621909 199050823 612775495 875301504 807377703 248618390 456200665 967606862 65497579 228264132 256423672 672948780 107372167 690543242 405211895 497936376 872964525 998776928 233342207 14302943 676299417 853667905 883491218 524638870 318089149 615936587 204881422 266341786 705321313 610311977 725040042 910319475 253670257 725494000 416353139 583938867 992509854 24773851 544575924 304747921 865806362 806726308 114230920 868116967 448418485 281430520 78296190 198372368 825969817 456300621 188963470 368956258 652839995 618131195 784237528 292745021 404609032 378329443 884071314 718311795 457513998 960374346 948404073 80604083 620507203 647770803 784834609 664483035 420853786 123254680 176546178 822482332 126769112 379060546 406049659 534313400 872716827 442298689 364857501 581242094 593256100 692377814 641837777 484431176 276571989 183001430 95744601 518445485 665324917 261501219 937991785 615022790 865992845 685991290 379499842 769049479 462861602 54436804 532388498 45468087 401533872 509218693 9283366 893921046 935121867 176664014 962153368 278459196 27523428 559960300 876539061 958658962 506674151 327914128 839211224 848220538 99622537 836244123 789246937 795084094 81599752 795416970 955367591 910250300 633708009 709016731 772524729 51727222 195168826 624592695 914659809 241471130 188082244 70292231 446523493 1235965 861294195 259508988 277548362 41146374 453680237 197312070 440017449 326480529 812578763 766885238 242868736 567312217 429674708 391267730 974637976 119176600 309619329 27312392 916722227 794468176 786983302 457306052 217271888 77538685 825118687 368590523 93346870 634140496 864644310 297474191 105702074 886276073 117553374 460908576 179650618 131009342 451244536 124427850 511282667 994320007 832806013 446208600 878390417 239351125 105264520 78289114 38682105 719248500 976884274 937600115 169900907 407488893 798843649 697669766 753077360 555986833 983865951 927940454 183162259 259547408 540540544 248550993 28461456 655378141 106177738 104026720 669474816 448489977 951863484 50028641 986765555 269164360 774012905 843613739 806504065 81278461 788213067 673919175 23343661 292715256 199814133 758919997 747100431 735648803 537210853 790840602 107489342 642927537 720996662 918563194 485370439 872747234 393220414 534168686 628976288 547688899 269567758 67916701 100483755 132506946 839755421 690480304 628253760 792643117 167534582 110569805 171649833 764895873 32333220 848285277 116469404 446224502 959799010 42200349 899888303 496457973 834467260 3595026 281331490 269385373 791509561 18533061 385389234 367774243 460850494 693046725 603257397 162840695 995471550 412063288 542643838 6113185 418705783 79760345 921547674 941166695 727972542 621972544 109498238 622986204 510100866 750560968 835546735 168192075 681124238 661923244 399151755 960206123 582044415 85176595 783978326 44499687 725410246 120020813 728595397 8507736 911978992 614174169 122627449 138185893 303741761 414592389 22389041 396692189 233804642 619691165 350702989 495532465 981820379 664476778 490637512 422851498 177561259 410585641 23146274 234882694 138521599 912916228 892815401 459151783 211850962 951191890 705379733 394539684 168614286 581629590 607474044 787863335 51525343 430334700 40670776 533394456 207140955 399683508 648210945 24609091 11564120 501214977 919790702 241830287 724151822 457142168 841259177 933907775 417128396 395656482 941210335 481931991 513808761 110926710 706457374 786405941 174576047 18749246 674082843 87652075 581355173 324982830 749326671 92607311 865143693 459910090 683101887 96177764 561966674 425984737 10483786 355565033 964481113 279301176 792022770 417236108 911947649 811030212 167324157 427950600 261477107 754260209 989559543 306732675 466294673 245548029 596927973 89344459 370752512 974849618 193341006 625672303 628455529 886488576 215274576 954335831 695006393 819659042 324846199 934159847 857135230 486521594 630899704 66748416 418995123 52910830 742575962 945883700 889255027 684264768 484395928 602675205 647035737 452334512 474610037 788000493 523838524 32756824 801659625 888326337 312663871 744162593 493873110 186158176 502637128 897457755 383927492 347112088 899935668 948013199 757894231 61389117 733141452 995393818 38494455 421382472 306763440 722252307 222922157 481645042 257935287 77421258 497447611 230638130 243918210 866602031 923469605 708866083 204213902 122612820 594844009 569565583 21091094 620511122 299203743 495476341 770861346 483569084 177958912 753994568 309350474 378802923 168085144 51057738 979032507 488766586 473313961 680065595 554467681 712472964 932570773 320343902 55426549 496979000 322993895 991557459 179270834 464697809 652350536 944077816 719792344 657514890 100471482 468901561 835714241 40488348 578788300 334728317 569455684 451277249 972378418 122180074 985201047 441610246 522845205 420744912 544861835 496159096 716256926 995687820 853757668 63914996 973822926 630324906 981965938 882483989 891715491 976406637 468553203 172056482 725759883 335557966 301454803 493401091 42473413 159589872 637426491 556296448 219317004 869908418 958252860 320994039 36955569 165693342 407349895 296202054 198512220 880612930 491615393 838583674 77622600 290430532 127716385 420602861 437915150 141138772 649633417 6452506 602430592 461051962 723732463 6868511 454310730 293110707 196341978 889390280 335497194 938302052 384848322 446557994 503901644 56211398 748723006 981921432 170675855 584845531 634698347 851874190 185421199 587814666 388322842 49695311 375072662 495247535 305639577 232817278 214194037 896001148 935273870 695089278 919411775 441501263 547884027 739464060 416923681 62276983 962135285 353180805 837111097 359669316 151381061 175400270 200163371 458225792 24030075 293872117 852628990 185480366 521650550 802523617 202354921 815149387 173175228 513089095 470580887 713250584 639692216 195350006 935677889 935924856 394828235 922603597 30071072 46647464 812853375 583184552 537103060 224191643 598472229 702270832 454678409 717162428 825731314 270278310 206038325 220596167 771967909 849342301 34849988 385849164 878216461 812429866 967259630 613625615 567560396 753937313 587575562 466110797 616981558 719243536 393596289 950307270 350904059 989787530 838007120 670173166 619539856 408331014 759456144 780325655 724072183 875811885 912407170 803269615 54960209 314461478 368235716 567285038 825334876 770412414 674744269 741606603 406658530 942128638 289384086 956206364 20038036 326199122 873728640 663274690 774206377 953440739 403002152 674613567 940045497 437828120 168961647 59524334 779916663 672587306 228409973 868811180 206549043 155506023 495233768 554949976 520411836 258110739 34946518 510095821 823755948 734140393 303037547 319098323 693305168 467143788 15054607 273916667 321094452 613344591 623062637 239684870 960426671 687830033 391790284 514928471 184207046 462400661 282355753 774323343 252680222 561168450 780610386 172887371 394859656 553200073 569870328 945971552 687381356 528672327 606226206 743671618 868692219 268688299 32536688 438856508 355317317 13197906 843924251 172498415 579935134 381363171 854944671 917065705 584847423 539211851 124137128 866318392 180023303 486848491 670555795 103237433 393224319 396804116 504355342 610568674 199916573 246489739 348281348 292455883 529482707 426002206 618424935 788109594 150380313 519230415 448311810 750255061 547210349 775637375 596743367 46746717 919797982 283728501 858450137 996532724 786373860 40989603 868223669 172865148 474788465 445248796 337278987 744528331 901778236 820300495 130663949 858198584 370488133 913288766 584709829 385995716 716998328 454817935 17602429 598927968 529506949 961856835 874494032 326412759 295029720 253467317 967536962 338572278 602656375 558544955 362987534 241668973 423421834 359352984 679564266 874572669 300102442 728897826 992002646 931683212 488580221 223925774 782988225 635843329 922895634 376684083 755241825 400502041 355298804 464571334 975413764 289584873 448024580 679513404 383185396 754792457 652367102 749599226 127079778 679676061 966779353 902129249 878929415 815783633 907868918 970174738 31416408 142698831 953938010 940486919 387069412 936378868 222566413 10583654 225571982 221128197 714339028 388270450 660961825 288094711 895711862 49319291 165730019 542282872 941885849 379916800 231308156 738750023 35805312 171141244 29758411 994436265 702743652 2705588 491615222 40189634 855594002 886277274 431472569 682021393 367119207 439731939 964510184 62393385 792562064 373800030 188358523 854176659 738426235 621513452 871903644 448617091 588971500 708534291 943241944 143987719 804955156 25452986 918503898 540449413 215783370 809524590 607089992 7070431 941859263 887054661 794749492 592837022 837679462 788929022 703582787 38690747 718443618 595312825 579000269 79366426 935110184 874555229 747840536 969516005 246508302 618998621 865450680 129090285 766919510 269162394 624264462 396735886 38610273 419275440 180967842 899147936 836186751 458609917 556826534 689178416 7067373 941677409 487554704 194110083 149390106 412503940 480070735 6277360 125358452 100282874 80150571 998569691 459001245 216505452 738508231 265936635 645475564 228139081 610383747 592027942 816455252 672003536 469412924 983178867 465368463 636787934 74725581 783506326 453458992 70717344 430273544 835130908 964623074 878999175 795688026 772450081 650356300 276258512 720877309 234793897 113711701 209559806 690904906 66720850 616281689 762694075 908667643 216268050 670051281 42661145 330823701 599245229 350409358 95398675 307229643 259226535 49443405 153638135 28755522 668249761 805510292 742862760 447796060 66277354 119613332 613572728 158055569 102496321 68092877 981382740 224530098 879161861 594958563 860080055 246276076 947583362 283725016 492202065 658362830 690869023 894877521 563041218 326638028 250893576 870741742 139421627 759757896 117274255 797655812 790465944 522272940 426593958 679509253 253010999 710898650 914260961 8708938 486252470 513275456 753952741 322171377 698653760 537115257 475745287 300921403 483694156 507936869 907588353 185949123 817265112 94123245 969603477 924113887 504433549 913615421 954850307 724809037 817201362 233958842 281199331 546997286 681380397 832343649 748932972 89341340 794234800 53664965 699770331 462842890 561998308 658266395 12805456 541979405 383475619 998257631 270218558 435041419 203330327 275907602 747001917 938481365 819289823 585102356 340490878 490105012 542346471 157330926 963998524 3350821 485899099 902956966 166942079 533254745 289482246 516924735 504434979 144793832 909829772 802497237 916708796 948503489 908355947 494489466 234348060 318750127 476683694 856887680 669443487 484641772 264822071 176228828 298975516 343733609 185957025 447485829 14797598 438066102 82181737 945860030 296176519 14835680 369729598 678839354 100493317 538132077 42871043 685423276 124710010 538037618 409747746 872467071 821211852 32866661 976020043 278767802 293832233 21316012 771020802 661823689 235941944 57974646 359939371 161620216 696328418 463714417 944313286 682642504 237387899 5210927 118267179 721946675 3828855 760212223 122366522 386916396 838730456 68255376 354335088 780458733 573846190 376416417 450886862 37151069 395703459 517488134 481515106 592161084 404761974 33928539 690106521 114580146 537344309 827402102 59651592 582476479 596617484 669485574 34827426 371872872 3576128 913509341 621400293 325268260 350580855 267221052 787490830 380252213 959264257 409953815 296522285 738971140 23474392 137962688 780978658 337344117 446975695 926071954 827839823 602062198 897619561 380165721 440719989 434339155 182492146 441693711 867410173 218467488 667596048 301910427 424131535 268451404 330518837 335830996 72108486 533244363 994822280 569591497 227792995 815052262 254237641 869959221 473228358 779609219 419741100 771812235 301598507 925923964 940901181 220101651 396367331 966204582 662397089 495983305 709741154 92237468 783413184 58318278 917828338 937084077 618519863 974742493 572187355 785671181 863345389 237640576 19030639 954241405 84734119 79343816 90037800 12667700 954129397 535825686 933918640 474303253 543036002 423961917 935343365 620579205 748282155 945482969 834041168 251489815 192780048 900173074 945473210 351390986 821693352 298725969 992734216 820904474 357623025 454240167 157364810 442838294 429704380 829623071 66718269 122107136 966575589 732990628 627261427 829722216 13976597 811045963 672531147 97595478 708325121 53824588 803051589 372789900 392029853 654632129 24625846 797128934 481292877 602226388 580030496 763069111 766278981 472754348 203373204 964549198 791759097 922738026 633819127 537274965 96996137 162867498 12899240 869634493 703940359 60143045 923477177 369871406 907957651 893459491 744747124 356515900 436623874 681849989 716002912 234542995 172349426 612188898 111259437 90380073 104539626 823110380 159856913 184987372 326828245 596922947 464731549 613709962 490665789 704279772 669895153 379686218 731330799 885673274 509668386 143269962 58735605 922626750 619297503 600587924 810215178 847437346 341475138 22296809 558016320 240046888 810269692 795522852 660723819 325264167 57940043 133115672 985459322 372682091 577235677 505783313 152847704 45014646 551803780 512481428 968243662 692786880 24823932 784791885 830891085 494918041 340787789 516594858 369445464 355159757 186016369 506685154 877052862 795090143 49094740 395250066 992067853 582300061 717519413 257341279 111973260 995341914 654928063 659770272 515353501 352824900 128847457 56544982 548568952 29900720 650337130 800330805 95517692 140967191 779070378 79873891 922956006 523233888 222552161 490259791 283439247 627279380 212837224 130114090 415593293 354834419 991908138 362421002 120230319 579736259 681962913 273609802 820366005 327811919 352383092 288912504 447304250 83026930 517111430 676762980 457257150 223800192 646915595 845589000 869915318 104940610 568428168 254415819 247894920 498894280 719450437 401621925 717342346 620654890 20857237 498751714 157248084 447101531 76199068 939016228 802272373 658225156 43721341 377707824 26562270 274481910 514954958 539616336 640048958 752020372 920670331 677088872 482930412 287766996 580018508 175140055 670178997 598044178 294285921 176552785 301718210 224060812 162893373 397441445 802171132 76994457 814880917 896607758 435591797 618539736 670574554 365938872 902908577 200630821 63705812 806139917 12387934 262771255 965643709 138160559 941990292 555131143 959868098 639491026 448925151 687443005 720514313 942648031 431082623 540653980 705506369 770245449 161461387 484584238 188927927 982343551 802847094 768715744 509114758 758720035 412609754 470631271 755253976 471996301 186525846 907034844 618356592 645303054 277132906 384090997 279224917 895922597 332883141 193343783 946320029 644577536 412597064 915507097 434370134 3474056 626100536 236443908 954361320 497174873 76360137 462183570 847746125 117157187 540750349 537537010 119918242 229432382 678506567 149165253 733703877 38871936 369496599 384308540 761034062 21591300 344344320 666040075 610811180 478433620 399179705 674020226 621931233 676667585 10639319 694922657 930130064 769447704 828432774 366150317 944074239 977555533 239472510 75492409 649068498 428429 349001057 125591854 299247978 952074257 152487584 267926424 411918735 771830254 577985471 371783032 651809979 149851831 537751380 835104949 520087669 782760309 806759232 655357206 752036184 177078846 637072270 259335514 998151326 761291080 99199666 80387806 870462058 911279516 174214784 424031594 961893543 766649624 907663065 539395636 277084351 972467437 781318889 908961144 563271019 880782172 136043024 5995492 171620425 645532044 658827286 959246265 804538514 371756079 787964250 995563886 981010941 641324339 231366113 31373836 342405315 722607540 768526363 44633819 933510544 908850692 585927707 81680957 57123693 362785538 811706505 799495778 415944325 652955280 707578459 606461225 250513507 755084412 43551947 877482781 42207754 842423625 366488832 548834191 927719431 30419738 22466648 23291402 211708198 960851495 329728936 541791000 472755486 898241556 470928750 18538007 920234028 273164195 50561909 701288010 347381362 95301450 604101550 315625876 588429268 351852780 288014062 505084065 17102975 709622877 402034395 748371958 370982689 251596188 192997897 114169632 377555659 474965126 621937083 429484296 580111177 367238751 125606360 48173545 857798817 411221057 492644222 700736939 48049496 584824929 453660625 198611954 559613673 299887045 346953964 21657565 12715833 351813521 111165797 321213983 722703486 673379017 981623680 582328995 634336323 782516479 471416288 86899537 6400094 771735924 729665301 140425396 925601872 333729533 886891708 762636652 920717366 174583555 438213522 517941843 68989890 953868298 751430182 199819163 191744527 311771438 337295174 836347481 501602860 168401012 798611113 417470401 189348609 767543166 236645671 578598211 982975190 390760773 903513629 44155275 630473099 204949559 343162696 793836882 581900767 61600364 612313209 684841183 971272255 805174821 411900493 58843223 638002279 134332739 418303470 393270286 410701234 49726681 520709638 634590812 671697909 305913857 170157047 395142399 747611571 56916166 569577035 762143469 635362026 409785050 344086719 242982486 197812578 98681316 664517436 86511262 444759011 955466738 313406315 112045047 4023455 906552426 805064764 514003361 710460628 480649756 894584492 877447558 617318183 202938561 870891329 847914598 303047939 692121656 793550400 995907757 902398951 190303573 287220081 462115712 602843640 253393469 228797861 774815167 429194132 286807790 663440420 18224306 638417701 809253060 752618875 273253954 673252082 668435388 401874561 752637940 631514589 484143167 852875387 821281105 28008137 129463370 811891119 334305914 853037943 391997234 550192141 826348601 882545898 293743256 258942757 669295348 544805261 461948260 441899027 851087252 869226322 571060965 828906331 589255009 580287745 159917667 100336951 138289688 871131146 321967078 761428229 37121962 54380538 288780608 594763741 518966974 620505906 189549586 515819086 399631089 222475204 690187376 736638792 283403221 7497324 925434124 742782188 34772435 791542521 42609048 849629809 178625106 596083056 351212349 857559617 643865289 280555887 940774060 236358461 724919 796779255 314576650 97610232 917055422 506816979 898273475 411430112 540118438 118165321 649036960 378632242 57240849 702023368 973042248 160734113 459824370 783785904 403852998 358038632 683838422 310570254 747100330 452768228 881963519 999411788 653291174 477559818 721610081 230001239 420704849 881366241 362534400 959696879 566576371 526733827 57909792 957766095 297208908 373321331 917616441 624298727 720747 626003329 477431557 113755390 780340383 414974854 73392925 491737903 233163208 64462889 199950126 280442429 689595219 94388141 589832195 969789314 495605514 856953504 192799267 452454178 753772140 943928913 823807819 44430775 389173170 299262117 254516877 385324446 452566911 414170169 508404413 956169331 955984885 15483928 662561257 252181870 612040134 994466735 858287595 423398707 190810249 506414959 896737427 35176820 796236922 376361282 837636808 846050088 551785261 306123566 234232688 291242980 396675512 852483567 938777761 345734924 33325393 947352773 861199059 696659852 702999611 957605424 357253853 504830243 592810892 617329266 653134208 152131408 547075692 196710624 751009194 713607402 490019023 567388892 220010496 677797359 638816680 533718114 912086922 291696971 676137089 852116675 76352733 917081117 241988290 225763465 321591806 850278894 994106592 695126621 276056627 684183270 514412374 408817876 788680246 951593898 698485092 308314244 636990355 790279525 599488227 265147703 509414972 828833995 379916569 708510366 570719645 505953573 154413833 193058322 593169440 187394156 85269932 465631542 935248943 47157581 14025515 13109528 768349672 513260327 196142661 762263004 629709891 959249416 399441952 68956733 901875993 897487041 547251229 906229762 869302773 736209362 794014490 800253996 66577189 243436168 165484505 836176867 426954724 145352253 395208609 58609875 430755568 582218963 268363924 590686801 558660654 265120399 823563598 762514297 325231448 97789855 877302909 313661720 130555654 251337335 421766967 612406912 864516545 498791359 716584825 960435004 394141261 673904947 461269135 168958078 945178790 883185045 63175564 682744047 281962787 914085745 876155199 377716737 397360878 22254670 753854918 458170911 403477849 690211109 509348033 399667205 164095558 450994642 515178937 777172889 816453205 373754777 306358798 603475384 53072617 72726463 817113647 340447925 165699370 795803851 302771490 339942569 692872921 765751066 824750577 754255527 102853248 26628218 273721543 716440590 677467649 918411008 61373976 739370122 416107091 999662243 937544325 913637080 988467090 455161304 849430868 194946778 826227537 687561783 864964236 94034250 263916297 860368984 486109101 234169669 119086413 600710776 972395526 235480020 518303442 996398420 860954531 485616565 15788703 244545890 721928416 413848284 960378958 158924712 28673399 222166720 907406625 610029293 285585804 674676440 645754654 261215112 545169886 714577274 302376138 294138278 98500655 697785422 207040285 994795565 873212864 359316241 746633450 474607045 993601550 796157268 818306922 963583257 247675926 986512045 68512105 695627324 643634460 210130156 780815100 445272263 650143948 397039014 894995681 24078700 153874949 777372746 69281342 308995495 887030872 937291760 270144034 102659874 343091723 873448472 679130137 48104738 480722258 867116181 221828336 23366037 57270942 167729971 959489036 405455399 412858882 193983097 531962427 305399749 174991589 283187950 648066238 977425628 534117042 250504677 468287979 468801367 701793152 203990549 614652311 116586257 778808758 690870997 699350568 283621047 6500222 576383976 235698751 964853301 767524295 997893229 434580623 727792654 439949108 79826729 961701161 409264260 102905038 91705559 295034783 442670028 314980277 964413516 419718388 337284340 225956947 879776617 303040296 193809615 714794440 7830220 524020313 53260613 602344030 941802665 354904765 56685165 682880028 326329814 153915679 866581645 472456831 873598368 717979172 216393395 295425588 767148961 833637867 686562822 218467877 322048362 114066244 634206841 834013123 410327596 230282596 175629810 268283421 954070221 675102459 26734804 168593641 112242209 570649408 534153067 621996221 173263610 551268726 905897659 313394263 363516574 444092184 902689145 578181518 258680395 523599289 777291620 789741782 187240057 900493077 646311273 677586503 819868643 924540774 530172278 484752106 914548893 454604189 860353517 546973912 936016984 83585193 37261942 786185493 827986184 250487259 289059045 721153682 431395303 312026165 22852695 177302727 155820793 943673222 619872888 830960103 574721874 730934360 609537777 99141877 71288299 608735109 778916706 372403622 553156498 876024009 16812754 470017496 624781178 706411440 223529036 857856435 152048534 471831987 833421005 62921630 179946943 921681011 58778887 59474590 270697439 80930589 673753208 724864475 404475015 181838148 93547075 207166955 954975592 333452251 993647445 334359414 697370786 532294734 500032426 807906891 498279769 313507479 413469370 528995003 324909487 117977251 665834538 413511257 535099427 981603432 963540822 349610981 653566846 870556818 155430254 501183653 458522793 284620507 822529152 256440075 162909233 95707335 728281921 11780852 193584763 681608397 437154099 471591939 798782116 787139776 341094519 300969734 99288600 485964449 316685355 620570643 918251246 818124891 401196521 259054021 753170849 330789283 704017997 633051333 92994823 225287722 790303141 317842867 893383521 670333741 910606913 135938887 698153736 955971344 81713510 194848229 726707319 990009808 302430756 924884203 679354940 175300897 819642005 123006204 181855509 501380786 757835180 724840660 170395082 145706543 680747226 380290926 708075842 580906669 113087566 664092955 675898503 2269553 629443871 263756106 8995855 997845222 389039169 275669187 800413093 398109718 966968475 790789904 337405518 765992938 534360260 900223369 335961803 321801098 654979790 640537784 542086573 696575414 440370188 102089258 586790977 739887905 179343465 434879204 406790618 253927170 508355526 744713826 299833418 722566586 336272481 630013586 73295461 439827959 145453344 69892876 524574741 423773050 961668135 553833147 746219090 6962065 568668338 369130869 466591034 832913609 326061707 13812334 738362053 992344214 370231907 398436240 827260368 585094248 737864294 822390180 851868778 239735068 317745837 151292833 113992403 559622098 953870171 643652324 417334750 574737543 203842527 918726773 968551604 694224308 828607395 288209316 757512379 126068738 577008497 235624406 602553686 817185330 959578016 95645713 918154423 347690519 692458192 705132305 340277187 979782952 801068891 428749123 198201531 887449567 51982063 492018108 127684462 337073038 524149000 67324403 428145210 397987182 228190840 446381337 153215518 254050034 907666525 648126824 740616390 505822205 892065898 816180655 169759064 90886641 908890596 831634912 605071491 33083930 824212951 359359335 749913616 832273320 828982755 650554087 786085646 44904276 232770468 592075305 725606599 197920621 390352846 88887835 206785460 286195690 726937402 513797484 296150607 352553831 214367098 979498891 8384410 804368693 309008128 305318870 426016747 868913278 499401224 641082592 950180975 607042743 966413371 943991344 711623072 184392432 234990383 772466565 360828336 82122335 312967441 206806643 152269026 242275966 865358700 106260765 870836084 543931790 555657355 323421451 735385007 958216555 397076273 9657299 91896276 316143368 234033393 960024325 443685351 458654267 398761062 506739014 883746109 677642047 437322212 250161748 444772019 973932657 11489615 446338556 903421969 436918856 968478066 657112907 274057217 560028130 205617982 806030037 730745316 705177515 703500482 86388424 898775892 76346122 263422431 389979484 955313313 592497100 271810782 170384592 983540112 897091050 982704322 806203935 169780845 810255555 392131049 351966183 269569659 209648604 141523122 778181462 286254110 533470537 342101935 49460106 885185402 834192113 150632885 38870983 112963461 461048228 729904951 91087982 324481494 442627331 335558830 631975397 975009661 26343172 619650981 957286162 502103380 665389032 946418899 662102434 576333711 259065150 450843371 320564203 587710913 426639124 80688773 80836409 18682109 545144150 72126992 113585795 791080053 18943453 905878268 662471705 979121066 520177974 896530223 690871266 646511804 236060393 236541853 523522476 740731428 961841507 785245782 706672884 117330279 407000290 500094509 16951855 229855447 948004926 717879906 958571970 721631871 977615033 138382077 691422823 71338140 11504490 834585313 565840426 154714837 664227298 637736682 348459884 620890701 772426201 878280185 462945011 337852961 959428011 312726752 743572582 876170473 798350995 816455279 716360962 803362942 889028008 47782464 601162334 381123777 947280073 570172646 290080903 58727373 883668488 596149848 609368696 525593957 338836355 823094220 905723475 584523545 419517496 327097762 987337089 540031985 695939867 401165253 844057765 926072536 755612925 89650170 588860923 598318829 40809139 186637103 697898556 530467183 914626590 194882326 718232969 302304511 394990468 354698956 741717168 954735003 713750254 247195365 572226777 767712449 496136794 243455867 241540360 452112280 318022680 12716612 373756124 525027646 933926484 258747736 467855700 895134614 65539964 512403264 930961982 415952013 688383349 265024571 277127096 686431630 755591434 860086876 380221650 526786276 461977685 691458459 44465200 754145017 553121367 38814164 71660302 562711003 696562024 20832607 634389406 411696070 56001786 634872677 604730340 170219503 441916804 517303125 474643095 717636754 53073282 118200005 480953500 991409686 187838532 174801466 415362553 669194570 159308082 935201472 173777426 735651796 433193436 874523676 567873221 541027894 601100890 347822625 518261977 466838326 746800929 918536352 419003211 422557293 41411373 504143620 654349928 384483885 842058639 622000760 497194794 773131597 322663720 661154129 152488055 468581230 830045257 906727818 522286443 607344886 591399572 555887899 519969335 553893501 271943380 705507480 947169899 869427632 989538168 367321268 11135408 603741095 743144066 128514740 254438563 909431713 482756080 126860279 718836987 908393420 5188083 435672397 19734600 605855347 449801402 223557513 644157094 140485480 268845164 714672305 54093992 367515268 657823520 597677357 27869716 482659807 337315031 886180080 688548072 886490531 846138606 751757289 857722411 365952575 46944629 144225733 237433241 314446461 247212612 209625554 234509844 856284343 401163452 647485350 483057111 998164596 94142300 427030051 576532965 768032208 150504836 324285756 175089330 835861065 119534017 973127129 411882456 705277005 135384977 378928161 793469754 373086833 307996806 474944319 882326241 992036849 823227229 371161323 716806950 280881574 932828846 483911007 938081613 19505541 883993388 343191744 142289509 333208216 867060925 262871708 701387136 618445145 694304992 22924934 662563050 998834501 610940273 981111818 597151000 395548772 238435684 799576508 941299021 310095099 81536244 233592352 361397271 218000305 518742336 127202112 162228907 401347483 837864709 769129784 813555951 974404243 81860842 988467944 262695266 843796124 56877533 171790387 806747308 208128929 265722062 826268219 905121708 604198917 124772611 111270998 300347093 211972787 236605408 796862920 872657154 342418688 655846747 651925950 378087415 729822191 348146929 887753562 18750818 982038098 413661055 353807652 539811134 233009265 152930717 743993700 328402505 354760930 471903909 163383545 196071241 215367117 300982357 710623432 944369630 359409329 332533674 209226677 171371406 115625145 536843748 838463911 48789046 73691175 377880752 660492525 335412380 361049624 917239004 409049122 172175242 954326187 140096488 642895541 936796638 693427491 72337107 496274526 482003783 115245111 709941600 513135517 564481442 568873564 368199710 292568804 397216549 607430918 557833218 544317492 754773467 23781770 268909578 10888720 612705917 710264813 231060096 924349755 135936924 553998084 872629409 617393910 116933909 13439111 548805852 561479272 398529731 464423658 748995719 55592594 169295701 214407029 70667588 118602215 173575796 35087510 229805378 328824194 984150341 107275433 584137595 779278361 690629871 764594086 841051318 190824516 840325983 605925697 914073587 960986388 636745066 809352663 317356524 321718492 874462705 824024741 400319508 735865285 311232755 214722724 5504327 546720224 328681396 857266793 160659374 309069358 113167541 376321448 198366040 378650839 349079582 114092429 791604058 14259493 129989171 330408403 889673045 653766515 832031027 367807422 540654059 698635896 894056646 663701686 801700894 134392730 316421430 981186909 335872345 32571599 640915218 790013723 299218911 668022374 83702409 828768760 445435145 647683126 630318243 7952264 935733771 213139677 442676812 685952750 254662040 879329032 260482003 422034676 41701877 677394905 315574018 102157974 783502002 158596768 23667015 840136728 119999012 744214289 10640012 271617608 128803311 961041283 255167852 56246011 301701533 65520661 267087500 925404006 296434439 535003995 721134766 823040131 609631760 425598678 589231848 505749490 955512090 140817055 479261834 28996242 233883543 326816817 626298047 446396366 17980057 169632750 125299687 666629591 433582900 476799318 664530212 241025971 134375530 822265448 614420623 542897637 797608760 864783883 250801156 621793749 150721201 942616708 407349705 708727725 999496177 481620826 699307765 980848205 593272234 68642042 510736963 163542893 701102504 398176864 267185135 522571692 306949469 64378026 176765253 989677753 69864416 301304832 994840716 753721397 623929026 949591038 437761882 295558268 957170093 375502726 885344097 932791560 865133761 320518206 55664153 243761362 296701513 189610936 517289142 291880025 256762068 146478885 151350212 196707009 713067706 478563230 807560379 335075610 680692106 987572060 859025789 988754448 244274260 913054171 562666346 864780745 591859837 946012912 269573024 284036146 736335483 343902044 536675389 108433327 355671993 480998970 394666427 702567882 951625386 191256935 434012759 988151754 223332767 259607041 373864386 612493257 490244228 491202881 512328732 569252954 234737236 611609114 459771007 702636318 700198816 891903608 966293088 178277902 874651499 832245298 2447424 921876680 689591863 109574888 243572747 747289895 235519933 552747790 159932506 153690431 542875813 6248072 655019998 126596328 596189328 972451006 726596105 678748650 954596298 377217575 616320854 863977500 283725099 361288593 486226200 535638531 230975216 192318828 467238734 824336043 402136089 823016915 413562905 460953064 63576133 996986947 538926986 973202145 663737769 189334285 439958133 139016022 121349832 958718790 878777520 300759330 766765649 639055004 625344156 869271378 761338393 131108028 145138010 870950092 418925165 714576120 825692291 990144024 2875590 677243410 816785427 873811929 54158503 426221696 159193309 882579864 57226455 452396380 849719406 6360682 112105607 347816352 574486133 359228378 45166372 598033220 20043879 503724944 461814112 268607150 614611666 672996012 559743485 977483392 149377747 724297619 117129981 252686309 952061739 72755470 428901512 523538358 913086418 64458616 809555012 60583258 691755325 198227731 522119867 503893533 874850046 525403046 577276776 868308930 720259909 375728670 244330991 249864456 910042184 88246683 79052239 225323659 642527036 318436770 74480040 562176146 960832420 918752940 648221135 449137664 191575896 946950148 473016178 75153688 849718678 907814271 350369744 313881632 657017373 897331970 411243040 113382717 96587982 916379077 6244452 416860990 808884383 349656488 501785537 609684057 498291537 919974930 310512926 472694514 392587990 794409736 970993313 549832056 853547168 68843041 756700325 841982039 741903552 578028190 46781918 481531678 260388644 446294210 910156002 733011166 940154697 103514747 475881693 827537186 750128296 437809058 299166736 524619824 203550311 319652990 388745430 717443387 502591417 447543259 763433546 238553362 402617963 895440590 104887377 965387672 986883704 74396559 324538137 154739845 793984382 982123655 644041998 453463274 870677456 972603730 145897719 268686140 338929947 510489167 900281283 266693531 426601554 907449464 897752090 9840001 278155704 882451064 615827807 975760305 68803224 683901488 853168258 377627722 795924134 434338061 995020232 90991026 937486310 754824096 11995317 364058674 448436008 224606584 446561309 405085160 585928352 406861748 463918084 928333822 218050994 642214929 56770578 316204 57772473 585882290 599553911 39338510 409517322 904827961 743414467 502810529 358760172 730067423 677194004 255985285 170935962 926600437 180837200 106983746 466251845 480090110 86038709 34590401 298128472 692778690 558617153 614529022 523240881 564187352 371302912 793080217 804421420 272404372 225633467 604930185 656541341 163169178 28699024 871784643 573005396 747518677 803650422 453632546 401721065 50611910 913529996 669094505 739835764 600044792 736511119 256055814 490977203 612024663 618119465 274620388 605601728 968573380 269335112 155504569 696953285 843102499 925141558 190780284 279000503 401322077 128793624 551120231 21230696 817986631 484189860 819123644 639753993 694437870 711991561 203874736 728320753 481890520 128811071 255713934 628729306 7474822 916121696 393561435 305213380 329743957 205067789 134265054 491973823 229302962 378085602 515852127 316434378 577471041 352915334 980766963 878529959 767338812 791102915 658737392 23282420 375810478 690750942 593016487 557801807 484595366 933474947 194656515 148708720 495029465 608765294 47955657 577473039 341504254 269397267 652351309 856523393 693173266 889347377 772667858 539947776 101133818 638315537 526894530 303166639 554274939 628408087 267196195 212401617 733699981 491316294 808663982 181870831 668459496 688077721 561535710 534776310 409867864 339559381 681522357 230390130 178695251 353059679 720844191 196934234 45563681 451021756 373114386 640601915 516704115 58459233 912682513 240365460 853490494 603258423 977195607 246421834 355443431 602576898 401475340 4863767 169373180 790217336 879864011 89608493 188684070 291620932 879779827 609371821 532046809 685165161 307169372 440496926 86193728 632934463 680828976 539240157 489899340 220197031 950267266 349532676 776090386 306483008 591514705 687679554 263515431 328434803 270125208 225478257 883459206 39905837 792938655 913533164 678419843 918406523 876821678 210912309 12583516 296660292 322697886 732424020 701047003 463744610 321039719 807195212 982650698 188188161 45235017 892184867 397370090 856577619 502622416 160185785 98887712 180641805 104190810 890354546 895178193 217564645 365426330 738208950 480536037 83040040 45655595 951249842 345148360 183387018 34491677 119506248 70863535 172626224 35395122 670450112 575096445 151743888 758137156 362965288 277041506 32658118 253967558 210514970 137360244 199034736 460945972 39171334 708103035 789506872 383003649 504688585 185618570 726342709 826344407 780613279 155004255 21168933 446675068 275526992 992577554 582687623 219810957 159320645 904801473 109076716 795149017 569959493 759672062 321352689 563115213 435132890 485311832 977323629 331428448 783065715 709700988 374157598 587336969 367436637 287771439 315449967 787154471 269257604 897072686 893556675 856962132 273266453 894862883 407057069 92702525 339206410 4258088 888429608 760431038 70856653 993661845 724927768 155120565 254802492 249063564 622797053 23396075 993466770 165473989 662378586 764015332 273976885 113929236 19791893 881934627 879491129 726738199 604399092 158733774 291108509 344192912 237717643 36994452 499573809 810168471 782939048 438702809 293105084 356858771 232637092 74123440 125361320 359654845 311651621 593679277 733338023 344111782 742331731 128752722 958884132 241994153 775658364 634539923 317483468 822562640 434456548 980835100 762322953 486018557 137413086 456053243 397207745 81126277 775958508 774956581 152156271 817536399 358694138 662274000 454515917 602353938 972264702 103872674 330766113 125894716 554393753 119478826 93109201 544492517 726264974 463633036 284622787 656405282 959214077 886304688 50462617 635512029 164459656 271781645 940328503 78767992 228386280 332689855 153538533 280626049 443124813 814685537 305240650 138563618 965162649 611976089 550328984 410052460 447951079 962012344 147777650 935113882 888541386 793571845 654919521 9087954 323008397 135508015 911829645 439386519 889366900 47601941 547312965 263553301 550744541 297002960 865508656 191556221 75180477 193721294 602950965 980370234 425329822 39889609 10107534 853500840 194557283 956623574 555330429 651440055 471933922 359109088 552173065 158276218 474604568 839612881 76399189 346099283 506127462 974785174 271571217 731212078 497559232 964125354 934382166 483817057 583114954 7208399 883469958 838704482 969164127 229471021 911003471 474585057 819979077 475545655 28069741 375400608 379109338 860173526 855973387 318043498 458076468 127272461 882230880 298073388 364217699 444658734 646752150 514431848 355315357 358067554 906457189 674144188 389389135 814896765 916592573 698533651 747050422 907731352 578972295 220681953 559626616 567954012 952451335 71634039 962920900 28170407 191370666 442578131 99161916 363378605 244536078 378814916 771458794 191199621 990736681 218619471 248539293 778268924 498140156 370201837 958417306 942640563 615047770 54055202 976947492 522007456 862420612 571819584 329116703 48562259 816402804 915337834 999063785 227978842 805950770 625316275 727290495 357355157 485290637 945448928 684142497 221890434 311814687 192107607 543648663 724421093 569492400 78117575 498557139 773956855 770150878 126220662 179641043 594885646 932864392 297370935 758109020 740538589 811048402 394201666 598609294 734755487 426896018 407842455 512189890 546178131 574265031 810826314 475370915 436655558 119848236 327689964 262440094 66398479 19935122 425127831 761108094 153966355 221163955 527016566 340812816 922738722 364701242 424594884 711450984 791267199 530323261 449201108 15629123 408589267 221911401 743234535 923544017 339027235 370530268 15993219 51846550 133617255 452723557 100171289 623835870 386269256 801145644 555060878 307623124 375152958 744940878 545829854 611835053 136152300 388540761 622606237 948425650 616305517 814920649 951257174 383258704 627324141 938562552 149846187 196122236 145426939 285016647 560751039 823995040 40460304 259843486 760102160 979343826 676874047 377076991 31703578 309629664 544662628 688742319 382535487 589450916 735429014 160771579 936796455 782966454 577844837 630889383 94772461 452770628 328523773 622714050 777071901 323205561 927565815 859769552 866223059 220473391 490420428 975131568 133397266 903787826 799173909 589570830 330416567 549824741 644805140 378935470 140411190 428462726 338909950 248541672 556371468 733935468 809323076 209685247 531836718 49356303 190707009 26503797 690757563 472078296 417223051 441369975 349671069 986150321 439447126 672347282 978001089 402967252 678555577 10338570 837368828 39617363 807621329 510879916 600743761 399288692 221046597 231087365 425696267 323745976 181547092 808781116 807044848 610454945 528898901 941966661 458848466 581868519 93691163 987156342 980771536 407423104 667390667 342739981 436843025 274219827 50951363 68089802 422759470 551455723 592940511 953702691 932302059 120593259 767312511 984649752 104017701 786087077 751904670 247572534 239307912 565985781 260691365 280295752 14685044 868778528 61902457 87614031 845803574 138493225 161400574 701702412 421792503 170307854 271256210 67931029 164780570 377558571 557884054 829514167 455555498 976873501 245106672 118841854 515820767 934701961 292416695 329409818 911487354 967600604 330931547 695562920 290941401 794900507 284600103 809265347 667139981 552649847 395830527 217222183 797268613 397937981 389590582 154716884 612560987 366689189 487266655 605541322 829990452 10154234 875931785 469208866 561854470 648448366 61692238 133212376 177279539 653363953 434953497 263170951 785898052 189571270 21939041 518088521 15084758 27271769 485605047 209249238 23543798 396974924 586722832 270263612 674361890 782211689 594441083 60321574 197275456 628677191 89396747 720255514 252261797 185369203 960091080 49498340 202495397 36095098 815082291 374558095 744258745 623065519 294504329 856799179 267136698 695705764 92100330 737729747 99038219 904503278 968894260 578263452 535725986 917684205 700100662 816278761 787591418 718417104 963673576 503648599 893386349 41303889 185939224 180058779 400082733 569750016 546621311 3189963 236627554 681001722 118860678 503697597 187661525 993985437 933685747 427747639 151125745 892295854 767563254 917765563 352763325 284886668 614235886 860408153 256328776 889847492 294750792 761184085 271017196 277726816 888522578 137279252 748220719 555330818 915759309 842708719 632261566 125836274 44932247 383746415 694198008 283777232 440299805 986270634 347917908 488009534 905265061 902990097 696322615 509090950 100515894 387873818 533648610 582142841 791555601 189212667 393059303 168667652 183936868 968166064 604052454 245743123 837510970 405082944 652673740 966516207 274657090 281882417 612185829 176914533 660528148 626173581 76707528 844531627 631748619 246242557 533038095 847066170 431439234 817756989 606838387 745899075 23146766 590549693 915018861 623883590 401344965 224305042 129233095 260456113 1570415 967872097 169299640 556885283 229481452 311783331 226028403 750711151 45776278 88548102 259384114 947556433 90728732 439709396 136872913 123826085 785667437 481633239 927408487 825764615 45628374 318589848 85021314 72758623 409159417 497135886 477456541 304035769 322230468 714954361 111124600 17351147 81848789 842886163 177806377 485462736 620407510 934389320 907174351 793107729 193528102 615497098 782037822 28057086 36453734 59153448 124197135 794561358 870499742 728364049 854928886 13265999 521182419 245572702 314013959 846150136 907928178 720973272 205978631 791964772 904978618 264941034 179753168 532449179 907429986 612224317 925462763 739759387 634551988 993190170 439880803 394134816 131308447 561580365 471890772 693977391 940708274 58299362 898841712 609943139 711292274 790259651 212086111 480443117 736051312 570915882 377848613 846256967 998088999 205897878 704402926 459756901 787807308 691848451 404750888 208658027 25125135 487021526 750356775 823166506 320033019 731932011 314106486 625105743 262499868 14177630 93911499 897409355 288118337 988756613 984260556 842809346 628932546 802751040 768511815 475015600 590122526 349829084 91359045 542873194 352979582 676578017 192319477 778718102 35889860 917609661 590810554 684448602 451362735 5150390 676561732 803944324 446126628 543905235 222994651 833350270 448115841 205466779 368754655 634010937 659064849 777403791 122832030 184986144 612542641 530373324 402438245 880477329 622639553 18525385 522301187 169067852 335875763 140720205 97353844 431738254 697207285 243762902 789291792 753297813 511117152 253404127 921198662 910723220 404289235 32266226 523069203 964010950 182794704 731302196 218982063 538720785 920430338 366552776 897095961 523640240 84193437 876322750 664775313 53228181 228165523 516520239 302652917 757770973 973222930 706496275 978165877 412891525 886498567 677796602 217978562 307214340 731928354 810276555 229111792 609571420 989921195 285162389 760643127 217939294 452012915 838282024 837301539 564071579 164593989 457325627 826962917 605704121 496026386 230341677 766318219 150756298 935171281 863207361 275077251 291039082 692314416 924662099 345441458 518452379 826088316 565811735 926162476 175226609 59806138 893692441 474571916 977589486 429191378 30607552 746368040 986419753 586533497 936333559 528470973 199082742 463046358 96775264 472814248 739598561 705094387 189739695 88771839 907901250 920453022 254045983 581840867 488425781 902349197 620173029 966008300 527089701 257985254 937677724 196651950 202876320 301253697 74124921 257714869 945917542 193685343 772714025 780761410 727018456 227717218 925932910 212917773 442722203 801822156 872930063 839108231 765902994 758249487 501817355 621876700 329905457 977075459 69356167 171769029 476378950 117634466 815374012 821106781 603208802 956851126 147579011 379528102 295657897 438627081 337760612 953647393 394801301 378441480 190582909 56877119 881973605 850912893 294848331 790771721 710324009 400641971 89394689 373179184 765646874 293244800 597717243 826235671 913149831 115694571 303072930 546851884 563273791 772103175 426376630 554691151 364853819 941890676 665633836 634178780 883989773 568271296 126502573 109727556 586957007 26684980 749744417 989899505 794705767 536543574 374802728 444533565 682912732 308299580 463750053 473262030 978031473 22953278 742229523 129499726 584152429 656959815 134817033 790417345 108797550 253919767 786934283 719053905 719087661 333355153 92417202 363143242 233904662 21916072 153832953 517415135 860318899 243384030 929249443 913689373 487602269 424812487 106629356 37162210 273632632 597467094 187114852 809453703 408840343 990375807 991618851 636551920 781612172 472779095 133006151 501716093 558296865 6784457 13333593 903602544 71233192 40047352 60017771 605187882 273547911 101092685 184994406 404926761 797340273 130573775 362652861 563604501 178314399 134647235 896795978 379075422 826446653 429861587 458188083 880425045 938486144 668518130 354396729 150758069 633421590 993291757 426820487 149269335 538822995 914151923 301287016 673307836 859999221 649967775 181452500 226766504 540392467 417596152 551298603 710707532 316313304 586419184 581712556 410025053 788994867 124331319 349541105 949681362 595488626 543417376 15935373 623795840 958573876 488565495 610623133 446283811 30770887 527574906 512504133 964077369 39542550 890098944 642952014 470961514 173524017 283549570 33526624 438274407 391463449 545244326 628619886 619436921 490824007 719007179 163220457 47172605 23086913 59194899 769353388 87170590 283899464 286829905 612602655 378449077 275895494 977789141 927968662 206622075 496709430 800434305 310075502 360893876 287690657 521374428 534186164 690709894 698554 542732214 632318771 436468002 910576635 651635879 284776857 676947028 546495536 692868570 294351963 852592526 56530764 657697254 759624132 767852916 831914408 24406733 204401343 150837721 684806708 81212564 658893734 627100520 638851433 122711614 748089937 612036703 795481096 317507812 572388889 46417562 16996460 644772527 827237925 221150329 171308669 859781279 266631165 120670016 976767249 819549588 348709246 52706114 421652440 671980791 671683102 772450172 999327751 946591363 692768458 399591414 530675179 710692322 435147130 338560098 837165358 82793204 313883177 815837802 89454230 620865469 244477825 354622503 420125029 322913749 238328997 793113883 497886188 295220328 763727392 339589595 764784437 512643730 390289019 425133912 790498635 585107675 787848900 187581676 146068738 422483585 136639086 411827977 741855970 745109297 269981720 271369650 876828596 308364630 748762318 763308944 178991844 63675428 789781839 64290866 176214409 200943929 505125830 104740819 322061005 308738591 297212692 185956189 297533810 31931576 513965738 887340778 986096157 279994290 579832077 730524204 645023410 137823899 221910211 170446937 501510978 618577765 769469560 24180989 795386367 452410599 527843068 805475635 292799852 614458241 412286822 895954309 180203929 30841663 315902779 561868165 933944504 678572284 881230959 888344610 242454468 885419674 431359245 708818985 189234583 538358159 77565020 995182513 268301812 884740283 320220669 529165155 5909906 413514554 903750292 151734360 961487859 623036300 182875780 317567787 830908275 239733848 281620667 939298510 206957226 567278939 911086305 466751927 695592959 169028614 900382254 883060169 772932316 764994807 497431943 474771870 910269959 829778308 215215048 974231537 726440115 782061961 908342154 174404135 915224093 942870200 828681745 949286145 519080599 237270642 713212343 9635285 705769918 866515108 985127495 271409568 252910752 686986474 25760166 836940333 950280986 484067741 499777469 594966837 550547268 510858853 823884881 970921960 918979781 980332667 295656382 957369867 494525635 766971371 185670507 202517423 434510016 475084844 284946196 651284645 470751371 943982850 902106271 385513314 786909397 499209828 218594864 976236948 303445037 478629760 412196740 917170978 226890678 293892017 797402003 499860702 591440730 268270943 670309335 481836791 769519308 853154702 79406081 794903680 833825461 134492232 772905774 909430829 847227997 860520631 895181267 914661241 690811246 980927464 756562205 125938570 533940025 539827181 125660500 190191494 128014056 837316333 66761136 335991106 608083063 376609745 333517380 43885418 667624303 525696764 849244330 358831489 721976707 85635069 137017031 406412967 880802969 856261378 859442099 622033109 837947222 806942333 924860600 50920878 569051037 113237107 644176148 268503393 744782397 374536584 499425175 972028673 51615617 362560932 91041273 569330124 104019206 876148839 866977902 440229914 522731341 927077441 717762274 374716828 444943832 945859252 448876400 429004450 662215925 874350480 907289200 591274473 19354586 923340477 55503689 779248134 280408276 9177463 995884065 590260533 53124208 582325792 241179335 642175151 40473170 369307835 842148710 435455224 785478244 647699417 21890149 7861015 105604075 353886156 414099351 747546317 419672811 936072483 424568716 98197057 236097091 860235268 769988260 103219493 541767166 210546571 112369035 610462515 735573720 925359765 239950624 254295 869865959 551776836 455408153 586269197 320164143 802514205 634046923 787652583 141523868 226350231 684779486 788001981 459444187 953850297 710789813 482098308 909854551 7520804 646729599 985382477 367973219 56067076 801149583 227735535 24744045 736745538 80410274 349282773 789979505 632247121 411696240 300721748 307125463 639851042 573727460 801451232 904440509 543224414 55690917 316089842 734479516 387531054 326015164 474152189 525428788 37795166 63401661 908842873 242900248 307939618 36048891 187254145 273715844 269716027 20723433 104038595 321520321 708149509 178612838 108961598 79812638 756673080 306978094 321429737 693009336 438395080 590721218 375437860 42161495 345472570 326212752 271929274 190680388 359934886 697522939 512052344 142531387 91136868 247144289 102580380 939566354 899805119 190583053 991143825 544139299 297079881 256917828 741161905 436881503 137283068 144538527 409830386 172259427 78781820 477344200 165175821 220169470 765302999 452398601 595598899 759194161 646822097 400681416 8483609 821973972 661635501 437275111 162337200 255905874 717501371 643429934 376269111 969287781 925729637 888225525 11726310 491287280 513879109 843859129 448159822 30576903 482589509 121593472 345889656 593876708 31910480 904875880 297499506 143674856 949830797 586967029 330982581 579758294 359252474 893934346 674984803 979172480 484679880 952468989 134477174 167481836 287565005 854136185 627615306 326349817 106027952 224844183 978713329 241872983 464031530 759695380 862208254 947748963 197340880 844957290 14497043 375314981 436863346 659855076 58837268 485624521 182650586 396055524 977687358 613636169 634654906 808744371 253578269 941372174 625825981 912694300 711332201 304699772 191420095 616310860 558302401 102255030 756553132 790568538 833605464 175034720 910876170 73555164 261625004 476878612 129592255 504053680 578858339 520819231 568206359 224946857 620205914 355346234 459162762 370165870 205833474 619304351 651907207 384399548 747833519 276876876 936964133 632390185 514449934 663130040 718956816 392162178 401485177 832237106 252319270 926006619 129833082 751396664 577066880 162996768 613223751 535863821 734786633 165376865 737712283 92442661 955892891 512880092 629916199 72978630 405387682 666979196 279079437 661582715 896539906 902508976 501778143 60296558 225792426 321519556 802465605 234775185 207383046 719806178 258801318 477730858 930215372 519000143 33018485 104634480 973086907 862081073 58218623 329517834 271806357 298347834 340660611 359588445 571937628 110853284 559982981 294244469 377824357 204735261 448258470 223113751 237440755 684104535 517568501 671392409 155240613 73270968 10434911 800911812 932846638 701609612 878093095 480108316 987853731 93757707 316911492 328883490 328480360 964386461 156737641 221177788 627161534 189380430 422498558 402315680 234421795 117111187 720237999 728912177 830757576 402521011 255800460 894246056 646449347 287672454 892776099 886331695 42940607 942842495 428019169 908848595 518048036 981981737 100261611 37808785 156887879 731628309 535297731 252159355 862251195 185548022 595212632 264349530 626679202 260768716 559300929 90145854 379840156 622594788 946524766 591673162 862433913 171182559 543011734 868765784 672606845 364289601 33585079 234976358 476123489 52167529 293756945 500256909 883976491 449416218 927281006 912019152 903775322 487114499 187705137 526979673 18353496 64077116 946699964 644986276 305901285 571475177 558685169 514241940 891951608 716885990 245321439 798899514 481165355 956856542 251645608 309010482 987996350 884117673 575885262 683450435 390028381 274059765 655396270 851350598 844843446 421592538 235942782 870077356 522228393 318948768 663153291 261897990 72613899 304193888 549951539 200745744 16948340 989014546 135129174 396554181 893497519 467894152 696373001 588425353 258773735 729840167 258927858 249032191 600482820 941073202 735169023 391917429 682007416 53922861 25937667 431279622 949907704 702840542 507437536 164518683 447202858 992171922 169567760 786039824 565815672 226356934 136614708 236029744 203257230 380234718 659402130 733915415 561183722 184027662 584261951 43817797 711032203 94530642 318855536 475240825 632007844 732280281 490727214 686166127 22921676 60430554 90021946 515519977 502433256 345086057 266326758 483574038 951254934 415399189 786946428 572356516 501406552 942639910 214796506 120325015 598978086 366581351 451821979 37812889 314254214 11260103 807857295 785099099 875640452 609566907 818791453 310926981 526774825 486831531 312765116 193651498 180475924 150933698 493536222 799258106 728902899 524265973 173889676 658296938 846437329 251312297 260481583 998583857 263916638 652140275 293746378 752492793 248204461 461547211 577309794 918556698 258078371 146410098 941710430 475925171 59372703 10832516 596448471 273692301 366222439 986101120 221248172 122159065 928698068 438459923 54234316 289514933 813387875 897602639 235121749 936538483 232306607 235413151 658986149 568196279 77302585 664678114 845929894 823934867 198970296 696499947 749065714 216519021 722480815 91394801 16442711 110063910 597010256 174532877 635649879 888562066 396283810 347890088 910765267 389227906 460398935 630648022 835532461 641520350 638600575 663383232 581909589 19400389 927324508 363633508 868827847 98027774 165304680 254918820 68484200 252144711 221472174 389186151 889488660 405434712 202304287 883345155 333675467 103659123 651861317 945996580 589548345 982490924 292613963 287751305 531376284 152660798 129217124 753769403 631361476 825645367 141035934 572420924 756436755 53247279 461418661 221395497 770983670 782451486 344380982 212486770 784129576 41392294 338695069 847526660 42882935 630133251 514938501 309947949 170053455 961666621 260531777 533130717 32552494 710410129 997624781 957745018 113232671 882463913 892289151 560623840 946695319 694722982 231145604 231310479 985378255 63966430 234917757 697239614 155075387 156746227 816321428 621063293 893832871 873401219 849910829 73618334 490894606 154123954 938595852 839328074 221285983 757902930 219685296 697365956 838352930 987615010 448790321 510772490 325314834 311846941 802595607 289448347 639709169 336359716 143304927 230946528 388280089 186577036 778291303 128234244 421036318 102319751 499232543 239904583 941373384 513844622 683951143 464393210 915774927 567336114 406014114 595526220 926776417 441226198 612475143 19977825 798970018 118633654 855910355 648791311 168399365 854738013 341509484 362718078 299385604 461466380 363309751 700538677 274940575 608541857 498142136 158593324 871567441 110618561 705533868 423573325 368951880 898112853 480710595 115042356 830128783 220972087 5958181 439502013 928721840 708502200 945715465 957590254 422413524 325978740 396873334 148805192 324753510 920742964 724632614 257768664 303231246 424154167 955877794 344039014 435332617 163329483 93501125 65375740 236030626 735412099 274066087 4792647 931871921 171498701 93425159 835373762 768799886 459131586 967965116 34125426 209416720 717181763 306691585 669532024 607537037 978450422 329469551 845210726 815549697 19180657 874717367 944812066 679453961 784583479 549550404 534439961 143003051 154936051 431015701 939650414 941105637 988033934 836960599 805187268 58239587 731094606 781005025 415016159 262467048 471155357 741165501 933373648 474604655 548664260 849252833 400228604 526089173 580070478 904349877 548549346 492556734 933295812 597184393 854376979 41109743 11877868 495705159 610608133 888381314 496300475 499669601 249804086 557790792 393707895 780985014 632822041 748549223 966542725 27016875 85564069 693257874 244464989 706767441 86966859 302166957 670699217 255464042 938655481 795469780 468152039 428484074 899488898 37243598 953492701 354132425 317312377 967933286 515319677 777611577 543410737 827154976 156606460 150526962 478234296 849086703 589663879 860879825 645782407 938573069 479633318 503708338 26556039 793781124 413256647 326115026 235882463 966106545 936004876 311486473 617530850 991445267 448939529 102112996 628740733 990360936 422219806 592109172 664812427 860127744 233609570 641630444 63739123 671193457 756594318 851624182 589996503 281506026 125664347 718439511 676506964 678646978 73803771 110215043 870730088 28913159 218207964 658981020 425572027 238567394 68469005 48595230 607301263 504910971 844809002 904702109 264320361 941466051 852842899 537265927 531341741 860268355 695533533 704384642 674406560 747499380 797037957 932387 528747743 716388609 835481022 59983108 778726057 760007987 795311121 460612514 382426266 797398023 871424236 707725099 923432996 82973667 73905845 646975945 416349306 253737048 689552958 881855879 238488308 658561600 417503229 537490596 910121858 564364412 294126912 664147719 485075760 469928418 553688269 827737898 849325515 880170299 564972848 898881732 655745387 801008515 902804338 112814839 230645851 568716232 581014055 370713020 236932096 469687455 46224192 669523589 622651705 155692337 824217938 850946699 284283439 28723994 878396386 170787739 641163886 925720815 888156450 879342114 761527972 421967159 375030376 177522784 921855724 624837664 291822243 477525221 412476871 989017652 464101210 138168893 251662466 605132134 813229236 330718720 124318117 656973362 438521242 61792406 166615306 929133558 252793856 118630575 259633651 20526748 660903298 909971049 499872589 687250440 638257405 651612866 463436875 543565400 226988281 310613223 976642254 140360956 974262337 454881253 203061615 489888954 326194692 595012051 699639762 369441888 237393410 465222754 395035007 573784718 741729746 659282525 943690340 925149327 471400191 149328866 63201904 304934817 618266342 944173956 82978441 577607202 936947577 488196359 286867455 704561891 311185462 25266374 89037197 7919813 663141091 877039588 379115713 568583632 927197660 603223664 841072612 170754084 865303490 167964360 199188571 560956841 813209922 439212248 331982300 495810242 936418250 811445282 548831589 699858213 181052486 72073891 37165556 812139666 215252828 310963046 571782505 101691515 532824060 965656792 893308992 489558913 348176596 849800381 857035487 959784223 972373448 574490974 86888301 327317220 546695778 469524154 374376295 107599729 822226837 752290238 154399801 92230522 190161118 222804641 167034880 513884850 845868637 203588873 714395533 996886142 6669077 367871982 649841599 737155694 73695229 790359572 305392372 586119050 40810702 806159394 984793806 332627501 733178646 676576831 904482843 76146011 614001030 32737956 435471957 753716549 319182385 395232609 880486150 989060925 363672880 296694905 60205119 933791843 106052392 332674865 35927939 795309782 188402983 462747839 323596002 739198852 450181817 971232332 643668611 833116522 489434707 517984321 942626121 183498807 426394792 284565169 238173609 194053833 30463710 634193928 929810489 213590901 171970066 553529947 984482352 960037015 170300089 563260847 425668559 548173106 62691015 529624587 279883063 812302867 694800320 43531864 371272414 964649830 774527587 782675055 946706529 450627158 210089162 44953160 266185777 527417480 29419283 405552217 735558934 787063268 561397172 220245346 270075187 932124824 162655296 259251217 86014303 453455656 657836887 439529209 258288792 974286672 772595321 54475957 745770830 51469849 765718857 488390118 77738188 490466722 514155844 232478984 671178709 531527539 570852050 983051463 31109557 334643058 738131996 382370004 840399038 66297859 905200263 388187293 560293466 82610414 661992651 614106344 367248681 529365963 792252581 526814477 373264943 82222861 799525865 406093023 310570762 17555896 372482872 979446799 769385907 71167147 738671043 648884108 114933601 374123055 911401216 81889877 679179161 631485487 283270366 959053580 712792472 296847610 266179115 969329938 550224415 708541934 86802564 863147886 758315186 253064031 930051281 743071415 898095095 300773689 265391179 600822416 96819729 785218141 513339731 348613382 162035781 180607410 736009464 378005504 295414412 529722310 11576166 488150754 958880325 796305655 573396498 774228761 105875978 992598014 229240578 369346949 387704666 423222567 81035508 516624204 41768164 815662435 18085337 817258174 105855387 372652335 22193222 380165345 77468246 242503461 311078931 308850012 710017372 37425178 547781482 749885294 108050146 582508307 822274997 221926323 601378637 949104505 87769074 339910499 372047028 348123837 115478769 515357954 857146591 64921547 270012329 465524871 189769592 666248856 360270849 975290922 281819541 952499083 270375265 448551032 287745610 138830675 471973496 24541557 542998961 246135542 369861672 407289618 702483016 370915365 552453016 918692811 239428674 97586267 550547924 318526614 205654529 613918436 475090712 837074741 978790377 308159796 748064017 203277208 15700731 645515640 225854900 922164610 68828857 271899313 316018751 665089402 503864447 512161138 957142738 495670225 382716185 211299276 850275819 836413284 868503287 791032731 451551139 133941551 356641031 254574446 395646237 814535022 129056303 665022511 29758396 590404409 605566009 843089103 872378629 887300820 726854332 607284768 913783540 636179070 874233482 726521486 525666012 714163476 430786602 540369241 148485402 832149637 603013349 772338867 843523436 530290028 933328951 471355310 326608847 935370598 748258275 482047006 130859631 630026170 70247214 311766501 108383717 696442078 707198409 309650474 104833313 325097823 533229042 181096804 863169173 445050322 725483710 147482965 164054384 533637696 287175895 842551336 226020458 560929729 727933619 958388243 810600061 86088567 400967322 894012385 264497071 752484607 405388174 756632574 387381005 803033522 418370788 284016164 911682446 891745963 651657325 661082236 472968241 658831777 951309515 880984746 131270272 360647389 288123678 473633446 360734820 51361946 429586166 454635053 281825853 984066261 995929746 437990167 566841586 563718455 811157295 227891159 58453718 819334293 968775474 363733798 50954226 116611093 626159148 878172916 560033884 680256684 36336538 696169569 673804993 285652289 617880813 785034605 562642133 893699309 917761442 392320237 931624795 923526548 393944798 105785796 183857154 994440544 529147860 6787680 987493478 592591157 405536275 149761046 468999855 591160524 141662565 543908870 949241419 745989047 2921170 660051094 362482761 315928135 960555495 631385127 713265710 721726274 795513133 224276333 180173745 676961178 317522272 147156530 300206324 797396675 418197908 411684073 998471948 719937239 35455871 587858306 650007373 553152045 224803588 237769675 812966992 30143138 368894303 121567120 222351097 200080986 437860411 767730813 876341034 431592738 305224953 136893786 386856760 854413334 68781273 589117981 183748451 874724471 209464292 861278402 219118876 334776731 939446956 26610833 43820201 127521391 943064164 116486173 880076002 969100986 968867173 571002046 549997045 2012149 602215830 868489274 792564098 521717455 962404004 329890559 860314150 332725748 680641036 436733947 248222308 330185585 862205854 202708564 107510147 406966441 119514210 387592335 409542696 220981917 689543902 163702348 162593174 100557870 864044737 276786988 705800232 196946339 677264169 572748019 199903898 687184146 87625163 363268345 529212028 343235849 701209279 56491422 811825586 720917233 722605702 136863333 937849171 464860874 138007154 876531872 539752911 59318668 188530191 608256984 330176435 277205556 559256614 108581881 791575644 101460369 300082435 147143989 139088802 431006168 11530956 86806435 300246147 866358341 22214033 38715835 303780603 340813491 607856615 330788735 346672960 143873326 645164886 384652796 403882238 901101506 615008406 663366337 498477044 354802381 138803363 407075153 110823324 369869351 18923141 996293423 290929268 133528924 185568529 915603205 148606251 148498231 471936398 389901308 773610956 557440854 422762539 417642185 681446148 868580381 81080384 643150265 382975922 698090597 759022532 77620153 976142940 554731696 36297714 435717621 689102421 505551591 679312675 94888410 6236330 364325436 542428251 397816947 354902071 491377825 663684333 524355157 256788849 912543721 491645726 21222039 495684980 64295713 154601981 808775231 367001496 910618177 914781642 860765397 680253974 137509246 960247870 326900715 393105527 535512121 47926625 692643611 285647844 456050507 434540866 498633285 32621430 23081920 306735652 611842048 629310824 604265831 986212697 517658781 184537739 247329883 728868149 493429780 511527221 816204043 938595280 593050862 364224917 362150356 99442078 917784339 10746431 122341681 401863662 976906855 164820448 936508429 287357544 790431656 631337979 302249992 663977760 463608280 127629125 609213673 202777673 323119822 137813505 570689008 483101718 260750773 344170675 615700402 681805189 118569061 26178681 139553148 448424555 541397849 708782442 782084851 60537499 617461792 325430501 933821895 669486588 61706099 19172885 664509016 250060340 394061750 327852350 351634236 684516421 542544238 84962047 481912828 670365977 513800756 94399132 682944839 598475487 828587264 145434856 525926905 16907430 172337528 457106031 924990094 269287606 92894606 339369724 60405053 543726182 486542431 827264425 987902665 734446104 854892832 2028505 205437952 64582191 914801758 565736573 497381212 201154670 427844276 758573758 362560015 736128693 352429364 319928373 537538929 621315062 275942888 638680578 449886646 864617046 82305271 95054472 283852673 677314615 610780627 985990135 754981918 144682466 335205479 123774618 940141114 412950013 345619675 50904806 508763918 578288872 305216607 137046138 358885551 299991959 395430342 648806630 944057940 836063501 315133762 799576104 604848272 730584418 661879186 424957827 612141667 962589282 850217439 859810113 84898438 110080549 700065631 479353565 1073378 111282739 994676809 358349765 827494784 866084472 586722772 989683174 225304039 281432256 135364881 166950797 979685053 37127332 492657943 904209010 516563939 722532316 394323376 67485652 512297461 811407801 408827373 286007585 748739471 307863223 383929366 673571700 316790035 320593968 239053724 634774659 194184303 976325253 824402049 61430884 4557435 103111555 770717974 966906060 756456762 957654631 794657119 441541535 260348626 994325332 67593679 929566520 285719034 333177592 406108534 189143499 77318844 763350591 743955423 646871885 351317077 988216369 648873640 57124543 671951189 105677147 14256724 768450828 968066823 447142296 896088782 938842671 686557998 815205443 574154171 540100543 727012300 376382151 537024492 783338342 649784477 576750305 716297572 451908140 281464247 712462761 127222264 162182323 193775500 498613611 202919104 727437559 254261821 482683558 435233903 22129256 352876869 519807787 351390411 69533562 116976096 280918108 692472797 962540982 696611386 894327681 322754689 698644102 697338147 273904015 566584625 352188386 714335644 698521117 8086839 445167980 299924578 293192421 479733791 111996908 123927181 17757726 4955755 23505915 566200747 452213124 600852412 245199342 570774935 588773056 870196893 3291086 670292958 471109048 291564628 663989775 417628728 711593602 341397805 234348235 723228817 334733061 822618737 434459233 513867817 569622458 923876910 907303052 707413107 590566530 996886930 260246376 69602318 247193363 696749523 706375148 161144688 66335962 190531904 136277010 139081488 34371497 534113615 594374495 167389028 988242318 460902137 663189871 678441758 988577494 702706917 571286680 23404939 432702392 639849115 181501833 764482172 659257349 524524138 992680454 981569465 22824511 950638853 684858310 908661750 625255631 89666226 707332897 504918257 610926723 192126239 331727625 193312969 673042907 50147671 252175298 161662542 144006443 377013697 684205950 166069378 576006886 849613864 272850682 431428569 413572906 611661089 603298309 917188252 625990393 693423943 230586621 180478837 498239230 591424385 55448982 611996106 402825908 684510152 913355741 456868143 516135427 95996080 529757762 200547464 684493272 991954774 217750857 995109575 63391757 552194171 822974495 583813364 559898544 379742410 860463765 565496040 833821622 645539173 727733282 860889846 511554159 323801615 209084639 449501529 883512689 45699717 171340081 940153341 296053181 119456019 920252276 351147805 467919420 455208741 892603659 579596579 61151232 382052911 848563860 940234886 355007124 11243073 482529073 582147183 488841489 39506834 10369549 777647488 66323690 147436792 22859816 139162856 960948384 689250790 435338524 241350807 374203804 698503917 327534038 652441373 470911212 205481380 354937846 805828446 253298649 88443916 909065469 966527903 470399150 984194244 363577346 604840030 541832108 812670415 306551998 668915521 113083723 161027437 794055707 478847849 520948091 282632924 644832739 570241150 226412999 288832657 141383962 242829207 799610191 655509758 400863055 940003241 650408730 568952349 699636090 750215900 482630949 965979728 267265296 114109045 536408697 234445821 795947546 543809788 590626725 478497931 495269229 266451479 446407546 501797230 423574834 358336351 134527656 74490933 684189804 154704106 736504558 464570406 787313175 350515340 689882893 221164489 507260030 284249244 948299863 538562781 194560132 995517706 789948791 152927657 21112542 650498589 181210702 770668523 798201860 223568962 480704522 294956848 521746711 564888133 80337081 666199019 844638883 801905782 607233463 496146388 523701878 557842798 937829568 490464459 340671300 689828495 898201763 361187094 595106771 129886761 619659811 330935924 522325856 511282793 836229315 264539418 575599457 931058285 263187279 656249655 686253475 510254395 279405186 654679995 280614261 598224809 430780195 574336543 186685010 346494807 629551301 436115101 701036670 143608012 824539016 70407015 405605941 101644734 287857989 51928189 231406436 649678517 597577768 156501515 693330933 696775082 480600285 109111846 29396433 911850653 8814027 160539828 6195508 634120848 239498998 428958859 234823195 761290439 607873176 913276920 203076761 204276357 73803455 690255212 728333165 517706072 467578455 657173575 427597708 60698030 212403600 840794587 254654433 614151338 706375419 512808791 410040884 530016080 496747897 433259388 948878138 929018004 906693547 537039089 836009044 652086789 509395271 904878714 358748756 541143930 967796226 379197882 354318849 488647920 397903826 715679439 356857976 776475162 461907504 431847769 240323116 722079157 845264893 640033250 894886660 758998058 826498448 307436301 964344712 33604644 994129613 276965993 296842619 510887394 122697177 560173479 587565710 856807931 54329126 25918316 397837279 686837378 641290636 291733092 483893016 467014211 202624947 262116047 203768148 151379097 534057715 429280816 178398964 993036160 84996572 353425410 412558360 94426065 263714562 911352029 403072281 716688476 734839659 567948888 64346445 168897736 413520504 220461912 303383847 744149552 256460556 436758861 883412602 324397876 938328671 346552343 325715408 247102963 645459993 902603155 35252598 85072370 241256667 121532683 985536076 625216054 370577887 132832007 583228656 655922133 489732403 106330438 969837083 833936069 528329168 80855269 504579840 493495467 218656809 406036677 833915482 657645779 499902055 677775660 301600342 982031203 633118388 287432798 615471293 294940719 99850729 547373657 291971983 760955728 957373720 154415102 89303618 179471279 762392302 95779029 114480793 415297738 14596755 294929536 923173650 792474837 336052610 701409157 454215500 148622888 782528391 378066326 247613379 681580058 394384198 11852270 646757200 903321692 980413597 504063878 215833580 407097168 777314619 450432426 624415052 173574706 146572663 469812865 43214971 38148532 219230423 617336870 816348844 408513406 630328793 821783634 568154219 356831495 316865260 998798923 690835527 564924515 49163085 323345719 736348660 986224480 828372003 492921661 162785003 358321624 518672438 827662641 695474995 100725122 143827876 168199790 296189481 877538807 917677570 62445533 593637365 720062477 325294414 331272121 69609116 21539075 694456208 641356861 900722061 353260653 981496906 429474645 53101677 184898437 662232505 863913218 404975516 688226478 222584397 285597849 787311253 196688677 118086697 611848815 445262741 618003623 563013517 326700811 780926970 756273981 491728246 515780840 85089787 808526057 971966280 920485124 937072548 865786197 417246684 970421223 108478675 914370858 330609847 522087223 852987691 403024369 817393748 506181549 365569337 720351648 801641236 457613 804921201 524394937 132696888 122519471 431712037 574426056 68443698 272778720 828645190 41185044 276782445 926371563 334453862 788703557 939304430 59738667 394167385 924247651 640760763 523639261 166943543 119902333 726416822 637984289 797605988 789756540 558405424 53788181 668361641 760494463 481874350 385415026 441775198 444452057 122840218 915825164 871881804 761050666 586735561 682150953 257242478 594296132 877601560 453182237 222181358 190600671 810009829 719174424 128107833 529043032 249505419 716825435 642696763 52273436 230510412 218580132 348990517 546402917 448257482 859866421 26002587 453794497 482629090 3124458 354852610 178961706 109992471 812204576 969104077 103256020 955823983 519488996 963594273 863546522 766930814 724776651 283369436 702765644 836560228 443529849 707835177 571143087 598726432 432350788 525400157 640196078 594118233 214280368 523925949 314626250 947934371 766616675 576818887 611466296 605466619 414355187 727314305 13546731 904650137 403631397 50544437 778479327 683589330 840441676 910455293 37562465 987031900 490367242 65939796 699518144 765241294 449089137 464233108 499787112 283206171 96958347 790814488 144292719 56215219 929526621 343046142 745266624 952996644 430390372 946989106 599442916 464968414 123553565 866074860 39840206 948884986 926232497 556808333 802023951 704414476 430565020 873819192 570904623 319334451 937110504 221535173 135057522 911964604 803422473 795858697 775994186 52852436 566813054 795394689 327093788 624407880 773533643 353428554 9189901 471647236 795777090 672277272 814825480 563700239 364843813 815331678 307863428 961570773 836312188 32754119 2658729 956218810 745637568 542200736 796957536 362964972 806995799 910686853 382481307 880207360 145302759 308380456 590241192 31978270 614763956 848589454 667778691 972114255 294495825 761515175 565965694 976184065 486956684 729890490 236705144 115159976 916970001 168933019 354179173 340035539 500390230 728130138 432070050 329246620 591231029 670021675 524967833 293250670 589677736 471270293 773890104 772305165 263476898 472742459 310479197 829997115 280256781 62790780 427502678 520567488 662979440 7405521 287567098 596271793 867373406 138604647 25102183 728864663 971068301 469448443 348705765 673432975 716627771 602295537 141075321 398850828 130958889 54097734 249962132 901585057 981853317 854811954 826261502 655110759 529727249 187831653 311548629 183920457 466343742 409115435 407089353 692260383 307103759 296575861 708585189 984342403 904553544 138931750 294226654 494870481 964259269 887626151 861623397 217266301 86926173 432776032 260906332 14865476 94663059 201453989 917656756 358649309 592521187 761892504 292048833 517168120 151234299 235401824 845771205 117080470 41636731 653267232 732394336 739566385 235869417 411056235 712873426 316093132 216085355 700518405 146637645 493681016 845481219 856622081 834319351 769096093 759053693 513251143 657043337 495510882 257782159 626289782 208408151 633573512 575702904 769633041 48162645 199312513 956264270 50979598 700924227 848096416 403721422 616315446 8040290 661373946 125350670 719033483 498969000 864382714 623577766 308726339 413717691 305427425 521806104 559557662 269062450 265794773 345720185 575483456 956275459 93494402 684273216 556921131 696501043 529637741 277660887 339761200 511103904 573470582 196011096 206009440 140131562 341332635 638155246 309081936 699599713 546494093 564589140 456838690 533876606 309357303 159129867 554004517 406575118 566558086 823993097 426006642 103562525 851845034 220426498 688903267 532340991 127567929 758820775 254679103 603692922 72928291 495009844 689861415 841716704 249275899 16277814 341763871 247372008 164633404 606201991 379644122 522628169 154603381 235154510 197328476 735397942 779869951 37446148 97331335 605974165 537451221 307094871 706695777 318384733 239602684 113532091 991924756 981638183 711917732 905287112 462844893 99089031 666924973 854670075 609992791 420233359 798226238 992337856 713386001 658639886 20920119 496200044 40648062 938686359 783551139 933549787 916180734 801583071 395414527 727404861 865992966 407207894 888513981 861054378 573888968 99623577 929784859 347011291 476527489 732605203 223671145 354374753 611009327 68484080 632673755 401435157 209610951 607897532 995845749 528693033 657196480 445065083 410385182 128692613 214143985 384884724 557138871 397848804 284795170 268318043 431319501 724415342 466928261 973200385 16827915 585099823 701519276 419361232 698496785 157705293 80806558 531401020 450301010 277779954 457740285 192809102 989106485 947000480 872210347 183748906 521365426 101129906 49305054 385997431 663213399 315402318 438008240 758205431 556067413 483122518 732094701 926752514 672063296 505550085 519733395 679337644 896437756 882461836 667646456 701431541 64643706 53724573 141176614 220704944 71170261 974491301 92718360 2126944 125698754 298682204 82068385 924013178 750773041 772198281 387271228 453785921 740998859 716888494 927716981 859384220 182855499 274284268 897037345 43824158 84194923 769894979 273319758 366691799 310368228 865655632 956300437 998240364 556011451 638079874 482567321 277104173 424764483 398283118 698263655 662009422 460654039 308175588 954697369 167719510 124894437 269123489 755213642 793505942 47780613 974683492 384877622 472043978 659842789 723270832 701815091 397217489 256661867 297184291 398688343 629279377 770183476 814810886 741227468 191532097 804495672 162760931 166753077 510420673 919441272 784905812 518843792 363064857 216601112 986992627 868155893 304170988 842377993 10271188 738593575 425641688 287737926 247656094 580022648 262488870 858038224 279856473 418139715 206931488 103688737 423927541 993734390 112453640 501733018 394813993 695581897 526163614 96427617 246724897 342976461 968483296 434091859 339272161 319879087 705351823 223541775 98501322 992000280 889605171 841364497 1515183 688328776 643559251 326246516 600384002 644253409 802075133 641576826 529472623 839600158 371504354 961389424 577251927 990764119 954785888 783020245 30123590 902931392 954172834 368407276 351125424 642549423 249168583 752460372 88874666 575153697 325681212 240643328 391297783 850891569 530916778 82610009 693319717 257308100 930349931 36128724 20045816 42427696 422168622 253549923 344559513 572218874 368698176 462608534 333361938 395343205 745509813 499437399 474664072 114896371 451168574 50662971 975773564 827500799 255098655 835692233 913842419 624947156 935345810 610244448 404399320 745610907 590482001 100930546 784218456 224745772 103818058 75277519 412659595 245020699 617092909 428259907 566076606 875263080 303929674 379683735 687514255 414003109 772394902 568273659 875737569 589384160 989783215 302028990 328956365 173814328 603302377 562094171 322395046 43837215 368719134 94250447 619363581 994832242 169558881 766610344 71460456 262295244 368914104 379467548 759830443 358874859 711760930 753106406 630272371 11368412 819921824 466974502 17866022 284133688 614182415 280959839 3269595 781050062 608110703 34512490 582373872 19035884 845381044 696442260 245965003 662662811 660362202 452163198 194779861 605747437 986406131 562822964 641427671 994824122 413781214 892393206 590444872 409584930 703839137 588984761 981785838 821363960 570567200 998050027 606573336 641367674 337560511 676294773 373297468 510251315 237167278 701031147 653824216 535064526 283772628 595003792 449165962 757228528 747792584 640956508 996207594 96048482 205803135 418720574 610192887 582072471 89446607 13580083 422794251 131875918 836351931 59580485 684690960 996332343 55756427 139474661 994277077 190446496 511255707 271739135 148414796 27757338 447116476 298577691 253486029 778255015 432802179 15787565 457857374 43210386 458542483 513906474 40144668 743873193 259224471 620384561 698914246 647554672 5884155 668789759 52732175 623903277 915457409 854540644 782006704 773919696 358325566 87682681 797627625 226213543 805534831 817750577 41999485 116515702 525779450 385942334 246945116 811979665 263405051 339408245 384125224 752592021 582948321 929077594 810341940 670586217 188118213 954218809 981333852 710087470 966949427 568033990 750790706 273864209 525310750 271045213 86445041 141426834 253768774 254661562 922929794 619214825 967790574 63393189 713266919 406742953 537432538 418117680 389543256 705606134 91142596 895226236 420055147 623653765 230655927 681134680 806040431 85584880 662692382 379761441 295924655 867313344 463128381 812064578 604276933 719109602 242366333 577077040 810166566 962058608 117162951 535293690 538044045 5959980 168940303 127767962 699506211 426942863 923548278 46792612 994201768 519383968 452995703 473207606 793171302 651056574 348896459 30050149 88588595 893450361 354619724 267253984 463740715 761852199 366009885 816297735 585607985 435854383 760985749 649136589 6054328 821249732 943507504 804227787 566134026 834860662 973959445 68392715 764134581 517264152 309503018 546553820 602075141 820650280 938982110 359363443 153612838 842854758 311173049 899971192 57790455 781940464 253064492 430504827 906020897 14524087 79619104 67138445 689950499 377756064 952252920 654328285 804677229 464574499 929369688 511372835 782083581 608587697 150270702 553792806 543770722 196587438 373769711 975561440 480961124 349716124 72154689 782756757 937229076 168674473 592897143 450246818 943074178 755561289 720172836 154092659 132205778 859652690 165317342 941114181 122303041 468739985 445485357 772568910 289671598 46217589 574633805 902271719 999718555 223839618 655300559 702337501 766836626 689343057 235574121 53961950 783620468 885225343 371798122 523958066 534433575 666903209 448219825 566591123 566316685 40311276 604981684 666201612 870905 445846897 104248580 621143900 918802749 85799661 425280664 735104098 284055416 320037702 495535285 118493839 739292419 671247267 153883443 516463403 65252444 569127440 880811187 995028764 470117336 157523503 178160535 775898709 490531893 963839704 3571136 503722506 253473726 780484570 527814681 341739872 666891757 779938891 493731243 271305395 502660082 531443722 95874720 666024799 108548773 356848930 393878208 337289562 134475268 933282236 209834618 808622642 655685611 600562883 750575813 999207882 677542780 338546487 209085851 828046992 442864434 445514763 798717679 132746118 641984933 913594737 197494637 35238085 317366849 904478779 203758236 396424724 452076165 960318154 457649395 409719114 375527221 941986700 687419557 925764451 681528149 668098632 555019033 802213846 922022259 344197721 700241575 831622559 352671912 493392660 757238094 631260814 835320085 37733302 401405586 847945042 832685372 931532808 726342678 48594109 234913481 494398378 931746317 107613185 851086613 315768446 802863002 460817902 12248197 618744439 317210908 450927298 861495211 373526578 730108885 100350973 512590339 355512322 276726925 303251615 348153118 948222334 894217494 852157496 31219757 941797829 545577099 32023644 142382124 190971681 884156062 660934718 264549780 640382837 29913532 47282626 830615864 418276539 624542028 40163690 510038310 878307121 528372857 192472716 963647210 783128889 971696374 312770647 667356497 765812088 168789772 962410746 818122317 844444863 776653260 357794235 868405999 746241105 347004806 756398230 539233659 90272765 397473064 290440629 681036461 978699897 76653824 474928783 638582934 74395039 992758772 368367798 79939865 194089969 716626767 726633723 218309254 477629188 718943773 413797540 672876878 536828570 464661724 538142796 647253499 630951452 802086569 586388748 447777836 245188018 184363205 895322952 972659848 606674623 815605769 458820145 513777932 437845779 152279977 120087082 490965866 168622937 871941363 579337936 906198180 949116676 204657817 192223556 627209283 194879299 808231663 638529309 121695573 391586016 760167491 317908345 224025846 417837862 30574643 440256396 808175630 395580667 264797188 880016567 540408853 745948172 160240380 734029585 287728925 25404850 104284506 587816466 860185807 659370030 992791352 170189810 54807647 766725487 470152113 837279721 457193514 341384190 346889140 416211300 519122715 309168220 367832185 946773756 251145282 608408997 736397384 389524538 50924452 494963155 530865455 929292770 65391513 456989763 497960286 966313143 639841220 738856327 804015099 821601840 902427233 85954160 101394943 367131216 974843729 924727545 936293845 634793257 410322661 852629535 330265267