8887 495923607 119216747 26313294 931352602 745457913 552602826 119067790 213446827 728322181 188234191 361173915 841381043 12213091 270545071 96517084 386551742 467059068 318260029 451902385 416695199 23210397 507160590 738742524 133024447 149187130 988278625 807460977 84836058 52069332 347377058 283741068 443301766 59622746 471137818 614324155 781636239 215130633 896880494 952394014 798086529 642544340 450837736 406532856 33621617 820123331 232451557 4610459 133462893 125932796 16786979 451187211 945429305 12277664 960819359 53364610 745498614 203098025 81422618 297467493 803006875 19150084 444645856 716872646 883762292 138306061 600704393 778192307 286285813 855046597 299572615 656881678 551366144 289323526 622143078 314734590 10241056 409829803 121172046 777198360 416635804 414127517 973645018 990782826 684616296 474385135 242597638 372620578 983404004 270866751 339189908 502086817 228043622 707002315 193040601 757759459 764332633 613696258 930811785 720192800 588108031 527320913 474649406 659831279 717081322 420511639 400731811 656547133 113167456 598726431 329827265 659649388 175249373 605271551 537460886 497513352 553846262 447810805 288764490 105917334 900080206 284204818 894492386 492641429 812960012 123220467 457794344 623258549 599721185 635946310 969716982 936840343 427505337 193685891 360827213 849002560 145777067 413576763 580491788 42235275 951091417 871776008 347945945 991294170 786685915 452041766 118115735 230218261 487920296 310405238 99283300 560402811 567235240 236291152 773620662 163482188 502667019 375838917 268309789 848888896 207296316 819398942 662096291 320819314 544916256 575648356 283037206 107523190 875556674 733457645 976167241 798768610 944539361 946872985 698394719 102848838 602970764 399930240 155975966 31850544 514024149 65402785 612389044 903607164 295501890 880535625 250423392 83938299 925532149 799887000 964886376 879035624 759611846 100991159 395062956 857665989 821576562 244852290 520139114 846399955 577159182 940087499 315259419 111005428 516616555 955247954 912219622 971359843 898069484 465507300 915639847 730517676 315000098 923492410 308276989 484789939 288808410 414365208 412147274 237186494 570805670 599974414 342923503 659241515 367857134 835229425 895365932 792375610 672745790 969434677 288723633 803796309 267386609 909202721 83509356 201561428 463804071 717066197 559808295 629911937 458703734 681656224 614436640 133946377 315892289 220837930 964171524 268354647 462188055 749448971 216821479 346613853 334525638 614447148 518357966 320770387 963698752 766494374 16719771 811598436 723434167 744451181 942107164 804093148 3871890 156320182 456558586 381378692 582581063 416516530 16789122 36356493 437494392 173405899 950078353 577392872 708422298 694977941 205611256 794863736 360819287 123958196 482972364 198884614 175746277 189403693 914804973 382651483 817396582 699690724 52965839 229816246 700570018 707988923 109982828 188057106 156962939 206435374 821540670 326099844 275423547 771819176 458793941 513491676 283311120 635799510 784703056 788745063 331742396 333597424 186589653 125087205 798507188 184299543 364357311 325758379 291750026 798414933 637604582 524190277 614880286 436255257 249362069 725354205 550631003 87707195 85769933 645009951 120411561 881330287 153063510 398349769 533472377 545868594 127868487 284994233 425346082 53662393 555948397 761894105 34595558 791303678 36327626 164258853 505734465 530202303 974069802 23599360 301627048 291412217 716494762 840089274 963519295 50723184 327223001 19323214 432755927 987296352 824010802 782385453 932156923 263984099 863471775 547695519 979559601 344005681 777854740 855273860 587331894 524460356 217748503 48173903 226097178 93925641 625039869 380353890 727452696 25063047 128268920 940910583 437868728 486832125 390189430 217003163 280821467 317746822 192822835 574530356 634253095 808993924 795306792 476511867 700308443 648754387 362552613 616673558 432736296 718443740 345082385 37018218 535171202 688230212 220979121 400720373 994246395 300812280 304192261 984329839 296429958 205833747 309874175 71331085 339858805 906275692 14487711 438790638 818904208 259007441 279756185 533709511 54044220 312183945 798150417 471980308 310391748 282661434 205503444 32463360 482035917 263659210 450087053 563647675 258504743 771943482 289640031 458744499 952990775 749721285 900930299 178760735 542388116 15465908 732333918 638624745 244193760 100295064 126507065 601273674 109516662 186468816 71654902 896986859 326699799 502670662 237827397 232396040 178536172 219419029 54238794 379101566 872708812 858817251 131126465 413889273 830241191 827814865 42497798 501731407 459300798 823647988 9588966 496532352 70968780 54545013 569970695 748555514 925568564 466424321 957065811 722959175 430477804 850370009 355722429 477793354 590778451 462991684 894059604 955725752 164139549 552256477 867166014 871043287 363691689 378469307 122974645 671426671 891941302 495726960 49290001 791242846 286119396 282269393 613029587 515905968 80164746 62148164 603156695 81586959 664016029 601833148 496170216 773479727 890919840 876612372 659704516 301231312 15074810 670231859 753395385 167576204 524095186 394619347 138494250 648890622 250362325 202540681 49286129 406783151 544541001 229906873 269554186 164558448 827736990 148446259 31519887 856538018 648467505 982582303 327554162 366353921 502289143 919473973 180622358 777217652 997388182 400869393 51210638 272643409 774255958 837352266 134477126 797564924 603443898 555152374 197185924 17614177 605047652 416978028 213979358 808748772 738410919 401346924 707405640 658126938 439358914 499869145 510661482 906442607 209415327 191231386 151375847 264982036 554328011 289155729 806826555 843216069 259419476 555065525 909154592 666869566 205708682 616188589 539124505 616173326 206631174 948963444 199349021 744407827 630544962 520440151 130896653 26530012 233552938 232678186 361246208 557576769 935024005 185895860 687133257 446967296 212395721 74175037 6818036 418985131 45132134 88534551 385603442 980667603 366604255 676880310 459291502 846870984 65638070 10176101 36827448 908510761 280286594 276998151 601068611 695512268 938877591 642330822 221804306 664250989 309759248 545416132 794563604 592680317 304891694 794887809 936586343 498476570 177417495 126245691 606615201 769491313 898693363 133927513 832719468 191634971 6320686 290714611 691088692 248766070 743637249 558587969 113871177 314079605 747763737 772548821 913964941 78986594 883743814 412928323 853682345 247301172 861955258 292940538 521597083 158714256 864133186 807152342 55762051 42857558 820023768 875200843 23004161 499632385 519202432 500444609 780586251 372921235 724586778 231956270 234134724 270620333 153601316 257576786 927765112 576837396 951433858 140129640 830604954 336921674 993928110 242384431 151927725 316133443 308418126 112269464 346065388 590658799 337297557 731216166 951027329 907154876 473600974 552867652 734964023 854338812 200399482 844871369 513526314 22778800 359548093 664897487 951676143 273101984 663380160 75942626 24483847 415451596 435155351 926034582 789570630 915361838 44477804 274320660 983420318 28728533 782739193 655551203 154044241 214753798 587116053 27765031 135449781 119816542 806294014 530519859 562803649 220214150 640395379 754554421 266929152 718533851 638099178 789088419 650551249 784586446 561480380 37425877 822581537 57094626 118617438 808559974 700349721 605633932 126428236 721173753 64854753 13167384 745281896 696702691 759872939 68510238 58768508 951088640 634094434 993427212 789750010 652484517 221829946 700713332 854448370 499800707 294247329 908327163 754541264 416900647 390666259 792408610 128825983 718385851 70583905 435040361 716411126 110161889 702108951 919224096 42415310 736858690 228511142 379853116 52409611 186693151 512186626 375898291 362243279 428501600 240580498 467950079 214981798 505098432 67225199 386691139 744282643 623003347 458373705 810612386 958524564 169342762 633033549 162100021 224427942 142465405 156493149 169077530 658827543 95495824 102132333 428295261 578570082 585537572 603791103 244726801 606908753 645211908 246592210 694918876 284653355 372189103 191395078 94640898 333528760 763142070 262077053 891281538 420090470 121787421 318021034 641185572 979582573 624723586 10177540 94824657 546085947 732599990 269415318 548371097 661617410 800742547 40658367 618362564 866205652 138772754 659226300 322955750 464397133 553519725 244863878 200598512 792305403 171313863 535970172 204174576 26287054 636149570 811376776 857705405 984678940 701919480 137779042 849635113 66473660 408510638 847194310 896716188 578782549 327330525 232496679 788492843 193489109 507979725 215200951 658157355 468913767 367087279 548049008 166402950 842265666 741229385 603889442 840037358 594651980 744480390 134468908 167720303 43800523 699022086 670657679 399251109 951722203 134692024 218581222 44373090 115479418 385653187 469602870 62365234 861787630 548027710 916136184 658787560 455584801 76416119 159151981 142349150 651511210 179613028 66465967 574245081 251667260 26363621 41578574 510355126 99598522 13186573 947746509 622584396 688006687 714723506 284034881 143314171 145078204 987265662 557594457 237055763 239594972 433343630 181756152 868209760 76824652 410618601 805086598 50788386 655099021 531340253 25915111 616961074 152233635 538625583 589831451 975217356 278645120 914622944 221853925 300301428 417571184 775007863 823770758 964741094 111450448 258196598 909760900 984596273 892283689 183709474 343987131 621658337 47174564 44105045 667894077 203050 180648144 547026472 347452173 948168958 128199502 593108155 997707748 951036591 832613143 821745308 720811138 229727653 150619031 422481079 401485239 183664091 19962387 554846019 422882475 783803025 599258189 328209310 765402007 788110561 779693933 525549741 80735897 259532182 633108451 901332406 7624903 591207177 708987355 148869897 323859160 600374384 623702675 925916259 477735795 631385943 512420281 17136119 150306148 738492402 908497497 203026367 345138616 840157901 408581597 757553447 798510976 590954120 751043999 570854014 422814972 478105865 515340338 922160601 238487289 477032563 895830771 824879781 30072205 531761011 750297510 246909298 461810584 782898003 20798737 225114877 681190339 341758871 110231577 824557194 64605635 724274939 475456238 303202665 974690290 398905272 577999835 795796792 860286228 412372737 858600124 191330988 415205002 717467185 480170809 543674254 188674933 5974091 766937128 562825961 164947752 23694572 730880065 890915287 824756385 810732326 430669325 324377698 154418924 348793731 900604516 108402153 42451356 262358182 587680870 205092619 481330146 203217015 542031818 472250738 137661132 165733024 831609643 434744026 492498639 450643549 519685136 111001305 359159043 126723533 342462230 7589182 192543220 399114701 19032356 234408516 132117939 805424056 759614407 58762398 322171664 882810669 867534947 705294447 56060679 214110207 564559798 392848182 793640949 407693480 120279208 353683700 487218945 633308288 823225743 886057962 40341903 642373324 478661731 631410523 49465589 942106399 801324408 820411654 180364801 20287538 111184019 72670341 630904721 839038432 148141435 53536109 860005445 688406890 238399637 11983564 219430118 398917311 321780238 750307469 549841871 953427151 158059977 923444736 133488849 598248170 516467264 952847040 850035893 183816379 726715796 876335468 251659146 860656640 131676959 199623949 838295537 49140246 381496980 717082096 540044421 144339617 456512495 452146209 71382953 156683057 494985372 266023348 109951633 288802424 954973419 612013888 472898032 567938340 796382312 500357085 114339654 11839264 160107500 305204055 226874969 165744140 788807517 565038721 853602798 450435360 351536741 767751531 120148572 703049648 528902929 378980229 578086721 789306057 629574147 778431492 63576464 289159940 40198820 948441102 477594322 972745304 560437522 627480580 987468326 123458098 134717346 929811357 783129974 626530508 440227141 708232619 471210641 657938919 280224755 790430890 900017414 276389313 179455502 29261954 267499207 542681032 570639925 613577444 77608957 374830702 330600862 788692623 635459620 915691370 501301897 99406012 367926130 859758175 68539694 39075979 619752861 126960442 625817053 89935715 562971321 368792769 744534612 115084814 714152884 219510671 314135990 19336745 245377509 742920130 1830239 160320556 921549958 138926848 472368901 814428780 745105703 651992177 811928024 8161557 159551138 50366885 347347035 812455836 452115175 357974305 902017985 452289167 848335866 463427171 587192677 104149245 271811520 248730917 390033624 171425672 571800336 1891217 816499101 316356714 143451457 326538232 493887171 157514036 571244065 795468038 703455519 23404949 88157559 917942546 338228310 843450380 610801270 217440699 234651865 792223757 33991833 646413636 225854228 947813321 375425744 813916252 556577930 23937721 891746853 288476417 761298348 11876203 863003520 998475368 809152956 657626137 537293660 21697162 199946663 272807121 336477893 880545264 996495534 339806721 77523596 860723408 594606000 849779410 853373876 395023378 526619367 75944030 794081563 633240297 663698485 872150972 788740682 21842053 835133833 946327641 820524488 566738958 812492966 695650407 228133691 322717117 706558631 984987122 223790197 549794344 552130017 289988964 973428504 97976023 388322424 695774005 514850309 391241733 456926505 690606923 700581536 758671251 173798146 271014515 557530093 159354556 828091051 669006051 834311361 421749607 357618540 328967617 651066518 217906123 773356695 619501075 293948802 512024604 248494704 155484613 974237927 931785530 522345432 885680667 445483344 638976788 292855411 504579416 37819051 577406032 59860487 618658922 902779686 380576057 702533912 44611188 947587336 494178106 694801265 44783342 84823370 99706870 389584628 738947543 912106676 607585307 187596220 3102258 778050683 4826778 673581887 370968990 347960771 132985963 119653916 964656256 89037557 150619798 654411474 615257149 993436581 692524106 288546037 383343085 519704593 108217572 74362325 267314990 500188701 655018894 116243399 91823293 625446337 895463409 659736550 467627503 227625063 159158440 335015095 85361730 108404286 386273623 12318732 950955331 28250294 922296350 764223824 32694062 112984862 797746047 789038937 791541555 953993992 113758013 724499948 612047640 61325119 653238082 56645417 741223631 259268121 174331631 440412842 311541581 815841597 223434737 91401472 210372623 427703728 106629275 673667273 384558373 772619412 590080093 178522726 467999951 747468236 961818458 981770449 81246834 455014946 739594488 311675193 15576386 276035588 278325996 44511283 162271585 835120002 812756278 805323840 474798717 916876003 772025306 63326742 331219440 627510132 942588982 373495723 599128046 614931678 864105074 13909700 739041078 46292812 774655262 84053882 342221100 255313254 312776936 800655615 72992925 236277521 613335431 286747017 206109198 8100762 393070425 767607763 613247446 153868166 508589 174786391 780372251 904539760 166331378 714631672 54768697 136581511 830845842 501573845 31312745 953898702 871008541 240209162 810372283 271230025 466109301 519098306 605041863 764419594 143443951 312614958 274164840 580311471 307771608 763855225 594934613 427231451 101567543 724679298 60187073 129192739 497344075 933307282 125812575 650464987 91747301 862871132 357067733 130295015 650662896 269482993 547839195 523058549 733402470 566585965 811529525 685652085 541143068 582586984 518578801 671318706 672666084 725933880 65987441 33171550 373315520 415631144 704915536 3942107 757971439 226006221 400368946 297943583 903106174 920734958 290007909 1841648 913219888 585449034 859884187 848509169 756063360 991688012 375166259 750405299 205986383 324268200 336484295 833116053 255361496 65830208 214496759 1200897 545728888 969664321 140060738 130584618 979658906 842888999 930094880 683428882 735876766 833357441 797852078 25658074 567762565 307975422 466496310 292041018 344908888 568933677 949270854 97706675 110070082 603474613 516892005 392276893 737130241 570564188 416276510 515206100 901865334 307894154 171907563 311690826 386481239 421152112 144804110 828078878 772562247 268478563 157094777 707043686 468267870 47653014 997500930 637867759 847463854 896962324 777816947 151152001 178869020 793350707 317803535 602884835 507466231 658949220 90560927 538149383 615142275 256857378 237000452 60611035 697165588 828862119 422369002 617211273 144673233 145113210 204079833 70722762 249114303 298107253 484049008 247162939 213222016 940620542 127305506 610065996 387924630 424294242 598553068 328021064 373692639 770840370 46898544 575768914 358759505 904495684 321957943 832038097 83413108 812199946 16915433 199178328 499637474 146709915 811701885 19030705 71391290 883511714 556914248 32022864 630467009 294190839 889338620 826528380 301681629 797967769 576877344 786840512 522767916 883094018 167097869 837685790 105972293 162445919 534447913 517335826 606883930 401310369 806381619 327990341 487993133 880342937 95694534 328238860 512389914 761215732 269012654 262549619 989024579 961661317 181407930 625882173 504033417 560761306 930545015 567937818 700274665 524189207 419089475 284871631 101818494 241882823 784488826 983383765 789992033 281275530 528881628 157142169 18992802 576315762 261383625 664025443 870495490 431130500 15372741 186967072 338429392 701705889 370093043 473491319 993755276 851306022 365860111 399390717 498531521 300098852 991563000 878051190 394817871 484646275 190510612 508397129 381163124 441922511 583498621 690395883 478594541 357325488 242117065 617722075 611052289 310970480 523041140 869752095 155135756 421222890 21212410 848325776 463755459 687111343 699388109 43470456 74562772 379454717 103205749 568683048 343401350 295487769 905055970 166275078 874088558 780825838 800669748 665943264 360109293 373459542 767021066 252157209 43592792 726632928 46028515 169771658 200132312 130179249 997745051 887448198 643150222 623624879 983541648 696736288 114966235 142862392 325072114 998957911 252888636 525155615 918708630 25385244 187884698 237530856 503365336 139985161 747623391 407392307 185757415 146213152 439798157 667796593 256029543 286658831 475008057 512453010 149516384 63073512 989043770 814001403 118186674 909579380 486495360 356009676 497637653 66167638 412778501 20042544 308827930 932841106 363448066 881055796 439308625 291642877 132062365 748590665 575744506 835201311 508056801 706956835 234070941 249956768 830135523 220914369 723772999 459728213 860299702 541214430 234709400 725398635 815758422 208362011 454010391 448329054 403050445 59398881 935367783 267018616 725304851 219982988 630437731 879051486 293315564 128329792 21734548 296758145 51146472 720794084 264266198 817261369 50725439 481157701 867253999 652893086 643545141 972919268 103852470 408385086 307775050 634504704 239857242 275628987 368714169 558060647 986696607 939864580 883055230 298411326 759294490 370575887 908720083 341082476 332158026 372733186 847581477 485838531 968947019 171405041 166136083 931190526 486118262 807444770 268822747 267792548 95638972 558222062 80166248 992022706 966090598 938679415 617470316 139497133 91039603 958655835 639297584 442672836 980694503 583735009 55330345 542634271 190549144 117868677 133172274 916320462 147903443 229263685 388355 632030676 483439023 593847908 427287794 999239390 82931708 618154111 910565447 167838288 591982581 691749362 668568693 291347323 348865317 659047198 247411979 374615552 818219051 918170332 898786646 208643447 223136205 329324747 861716497 226744464 374516516 583451600 232828741 188233410 551910526 891607888 172517466 25098073 396142420 669957082 472280713 490936655 860512852 19965372 561551296 397169106 176149181 465889924 578708935 41526989 753368150 980883554 60706434 190362944 604534390 331732042 377991192 264944652 556924982 173790749 195933017 20902919 779263183 232123726 651985023 431922714 373947915 787989976 219046378 613168657 492349031 636901119 387084957 542509004 118381583 435218290 199141797 173963509 539261199 472278244 664436953 770812200 101829492 733629976 617025682 727318658 690600990 322640458 140129969 196385870 453293162 124909845 619107066 715563736 829379378 180361621 767652302 145319246 897256355 201397524 343818626 114421222 593866552 523665028 341723688 995018170 208975595 177483054 806159422 912599537 129925790 12427934 95348848 218046207 177734778 953804746 436160052 670597651 540157488 417250657 83097670 388454416 75572523 738203694 12972641 745055364 856245717 311945111 787974019 261402788 553010387 225122045 605219204 264240229 294190977 8478138 915117801 938140112 139907728 125305487 495294564 996058811 630174460 523611234 423099315 503007965 145716856 500288835 371383986 800294049 172366563 533941585 502971955 384461782 645952916 741199779 807203679 78921843 430487125 195282166 518450971 395522222 390833740 826934959 647755780 158387854 414267261 319580723 556355822 126032334 514252148 203854660 500982480 298854719 23928688 787458914 932298509 644829271 528104862 616469832 581564703 548770157 813200764 475934055 80848478 779812355 680377138 907022597 564285453 593479726 762016642 615993523 687041212 964713401 8795238 57038168 507856363 572335916 716537125 628615171 48285739 781181568 868672183 608930599 796591682 27240062 420346216 34278795 776434987 962280315 351521891 940836464 183283117 844164396 12462662 744805478 598015950 254703337 526558491 281018350 352441241 262172702 671407359 71461447 292543434 876964999 714537611 441743518 26241569 789242920 18479155 619429037 28861628 61466881 932993892 507088062 614517845 715623620 433410826 215411702 214089939 409288892 12359039 778263196 788759864 925501924 287152114 958640078 27263932 899842092 827165654 544968064 392774335 133782920 875272506 736334297 323072040 242873462 284473988 22337652 654188072 848235929 366941305 849917410 720170028 467074545 33744936 19725989 848795788 768407896 242080171 895582365 378304585 30295961 976002580 759377535 181793881 195288251 720649906 657918062 157524311 489728870 724536207 234393184 91137182 179084039 753818890 800674938 468510799 184302733 176472378 219924615 30044344 20644160 268073172 871251681 713726883 112299638 527345248 959673465 890361762 54797742 205240838 737728337 123272183 523939313 151760751 399899538 424895934 409438635 389228007 735349107 739048270 71349232 879404298 193981513 86778028 294853782 809223629 676725897 19201292 738029818 470229349 111482069 72946115 57528449 296384940 992745198 904509428 997882358 480307250 57571522 307753930 336477794 724850520 139780472 898349125 401306951 889150825 143393624 640823717 310804507 278545006 533817834 168725393 516652650 946140984 563492185 545635794 150567165 885919012 407988731 632108182 460003808 575152659 438927327 284767412 972325350 949439890 906151990 193775963 157482477 530546739 967287820 75931112 435835996 172068304 233079795 821892555 762014475 114090386 286356869 886384427 389917727 827298329 127239247 11067729 555806682 582395175 654557095 511596004 413541893 33251947 813317405 173855523 748073699 782161573 337317402 421306313 13441206 737708192 33595786 303626682 658231256 47240254 866949449 552313385 35832859 977119792 868725306 310193129 470689533 259160121 549251352 656357657 143474312 391888087 513867723 600645724 871431328 54499264 582994139 457873076 787850249 249310653 718013120 894194060 495529162 134871714 852951251 412329230 182704073 771699292 93093928 604979960 172443843 316861176 743322528 217725965 334381045 927732867 403299236 616956415 139550224 30969649 637781628 11985766 410337068 440290808 747578226 981513400 469599749 932893699 385536255 363831029 42693443 711342783 200232334 924906407 532891663 472729133 458731498 202629011 190628956 739493991 667269016 647005364 496748468 470813618 188791802 986040839 348506000 27898453 720303370 894642166 649407483 112216342 189084571 851418915 130768440 775959085 361924437 113934923 475360442 18832441 339619269 896381269 959899390 200154264 844906864 512302868 626263163 333489885 649252040 60062150 944658339 157555721 608659071 603013098 497430191 328846369 379713938 871840029 827705765 207827576 399889920 45501909 58315335 272443785 362164949 803819450 959921272 923770097 528808088 615312645 503647304 838694679 300794051 676580238 961830513 17518697 99845775 171750221 239410740 365604161 949042292 864198370 722018003 913752596 184632118 932146752 515917736 8252383 202295488 950019587 159407353 748510480 869882306 682421806 41876250 106840348 30948769 194456082 492059137 988671155 26576661 886435156 99041661 727952119 699370883 936539155 367877675 113181548 62968030 19474196 240903098 178239548 694752352 7993294 619811930 336463680 11419977 277862690 134428171 184067730 48750246 825670632 736816340 600928695 769271251 906907361 854129804 204652420 688997284 309832914 456671212 339909958 351538992 177401147 194824254 976926937 914358886 21773242 565760631 992893135 218185302 719356986 329093002 216983287 639330922 201410761 942605271 571418208 800008343 722391615 607547578 481713869 139918007 187168795 659308010 663421610 781003573 344373277 865355632 141851494 249512260 740458955 304486620 960455722 616305290 112145681 895529233 572813645 665792537 69175918 530948304 79231733 711901052 678633308 138892004 703990329 149335824 188099015 510669045 390779825 762112278 313734110 295522145 596164749 642294208 442704561 267499474 397202462 105786958 391921935 618729873 454252505 354887511 304423549 762722640 976926142 93606715 178039709 847145008 994177160 103012453 419864318 866258380 992809824 52266365 285477409 901936134 465345588 25459048 610855837 813614247 898448836 963238164 749799021 688664455 265282126 919437867 496800136 55479317 910442041 460561297 425781798 787132257 593091072 58588567 807344388 688544589 249429566 411191842 291986385 145851556 282612023 553493363 846170425 934924929 586821458 517229196 493665811 20366012 106333484 757013240 306473549 638559140 252879833 480029290 477376975 323629315 235867222 183136 903945079 580794090 865179605 720232405 737775718 70233706 45819615 147924541 799232666 59418232 202636349 428645186 355079934 877467857 190268059 834622282 740119501 878864349 895305076 241371591 154332106 990404824 314412619 279077670 508902770 893530131 695325886 288063076 654089700 25379746 575863802 444713298 279309580 734984821 711370557 381990948 269299707 670785080 114331090 142397840 673727176 126618542 520514166 720415103 854184101 126364495 402255244 15493757 3962567 538952407 463347599 439247908 853315929 616426038 956511726 387688992 554008854 433411303 820419705 398841999 186297292 943765523 936303515 320795904 177339 695486507 340514852 905727264 252943995 78483548 683345797 425229787 722612083 234709275 694930936 370526860 616979567 540156601 731784775 873233285 431303316 280910471 231504541 264809583 668055604 271233020 46999131 204182623 131474769 429921055 750116851 6703443 19856685 307674877 350256033 492255498 10761636 365049281 307693343 257501608 137319621 178951168 354757204 568298356 625718047 828583179 288839276 597821463 542760925 377153879 46616371 222309904 632372579 811748172 922508703 819667884 357871225 523080083 87879922 819822596 207230164 688142863 145722276 95227851 662425563 744947295 278585318 787772312 401767613 724551533 515687569 851459627 450513576 552674514 166089952 488985470 215803841 964959847 318888091 569771205 619179916 437145457 133426881 991421828 170658983 326644940 338862461 420901660 209963251 368684230 634597136 489912198 978368755 617298732 330388524 143183017 515270933 363298669 159236289 449723185 784255192 237858239 214167732 649822303 848080791 771749534 764384461 801606518 554207319 251076246 427383581 562568966 614645600 298058095 396181330 122847985 784500819 645164021 680361940 851130070 56721077 971888087 287554796 129573258 62224733 240260275 136623771 943741655 411644956 483244199 790043881 320777153 453203375 767681333 954494933 444510168 383627320 37983937 961416350 155592937 126067129 700080794 38098865 509483421 379238585 770888675 419643234 254490057 260543949 503355182 592304253 513196748 186523177 429295281 151269965 724211905 987804868 887692183 8262643 334947241 140075560 508394228 255701742 85972603 671126877 271761970 661989416 526020744 231049454 650856236 458186245 404219840 209375117 375612250 153270842 560956643 15444746 417855830 856008284 515798008 114759198 43202502 597615399 398244734 122205362 614355824 782249111 305673524 496952158 61670998 179351065 83340959 154275051 397936716 430821293 45624432 36928447 674109868 257712430 929701486 653579873 527576761 337070318 655294687 599455750 625744350 34328836 220997648 455126928 834984636 396148043 642630053 657064501 960871483 84272925 655207420 138922295 698210014 426391151 79970417 714720599 530395652 677035995 69313771 909091208 837096072 701144612 148835387 620396789 818771325 785854793 260152111 771787359 507864112 555131710 273683362 378794176 316128451 622627369 446958859 699146594 539344780 786361515 44568601 325444799 553702402 533048222 102463286 617218251 991717440 220079293 692282104 624526884 175336473 690990807 690901076 921335771 188076325 646802152 392029963 49858804 236835129 259545671 793168223 9220777 522433548 296559967 926512248 626133916 45452440 271022968 277157614 662180768 763313946 531795965 448350698 853450514 724588369 160151977 388911496 113158199 860777873 153297246 286953568 326151527 313217611 103359900 456290803 382453668 626047071 775209469 305649729 351971504 353806981 107774575 571147202 540985564 611636357 302093264 614496827 94278840 338436194 129562105 781251844 164282506 286292753 11871288 33370102 592547801 427093724 655030207 199551386 787149350 378167500 125985346 35573439 101714252 696346475 575890071 257668051 659144216 405096357 226506787 891369140 40720571 648072116 802073661 549827937 267791846 543272984 618585124 29501275 405824269 653860271 281512748 246266050 118121875 332719736 182699799 250735593 804440029 126656775 65166711 103065887 745234777 381764006 580595895 501254606 268314148 938438214 658823056 153260123 739499064 988925349 301246361 78674868 387005035 92045435 981672949 137655557 951434174 845894595 406840445 424977629 166622371 141886619 717027803 2255655 264473930 187150958 736482661 772896865 466070487 967314596 126796496 491487176 810991115 49269768 117502393 16707284 341573479 883961416 170014113 652396781 59535712 384939559 40537705 77152224 102303075 109601678 312300026 818283351 969932936 493733565 893636034 634125637 690995513 281719370 819276728 511204116 49255517 663409275 30092859 720517013 961635669 825799925 929537153 82840921 712610925 783403013 594570395 169695313 8955998 278372159 976563148 122982691 173015803 791690695 369120628 441801953 618652606 312379334 718536254 430616159 359620523 143611254 875416575 352441684 686976840 860117245 547168796 77632312 616649510 490733000 101422504 745924868 794373225 100558326 800435336 163759817 85209336 130291737 81102988 42238654 624746984 404919724 404536944 676197400 938793135 579572811 432823262 14579125 105540158 827087338 335860392 51250342 666194640 350240747 949873317 16160219 981595175 866403078 919521592 347935051 96906210 954885450 805911322 104114637 92189085 717504751 718295149 104226896 70597929 591231932 875517617 24417942 61306918 877978799 855305940 230117361 184811595 58817567 36660581 60203350 690101074 603921913 135424977 791393984 511902561 537424289 672175841 909672213 234690737 447000404 336237942 729110375 106067165 888340053 129372696 808948034 123243321 431040973 758250985 952023903 893908662 398031801 234082404 674356059 749046782 854469748 332988343 853841546 636856289 621372511 879240513 462337966 903847562 158524985 665798701 362311140 324723578 690986737 848873152 134232226 585077948 883733157 888190210 268205930 413690134 513990223 415638255 498953966 824512707 431062368 295150748 554421470 522135223 67368067 227223084 556423928 589724688 286099597 958821106 178234367 972052656 989002009 519922197 183471499 292289891 619318744 847585524 796601482 719590990 226703815 274936579 700750365 940947675 508579407 476761418 341156580 766413866 640059878 812913852 62602406 985187161 134648701 839509220 464264281 149637832 739729683 253512448 142095120 79618547 183330005 815162204 938321619 66012139 250464224 734699891 812511793 254796231 415474815 368353993 403937574 950896350 683304083 594361532 66642573 488052442 60750755 686685427 527066 203542664 807813821 361192775 655276023 161030143 841144474 762455929 554134260 261467057 604826445 25719955 198683425 78195272 531751527 169895905 687315868 929371718 443071943 133908574 161326593 93945488 568166434 823132681 672472097 293913860 86756573 268000959 325567116 26313116 687044053 300519251 198176859 329806146 323580212 873709666 280262344 882607105 61494578 272918675 408235612 484450015 374142616 22576183 382562182 163809064 524210416 447289879 495453229 756991937 348759612 326784454 253351910 151124797 693619823 232661741 23797026 450741374 411446811 805672835 334497694 953717190 121693134 499586985 563488369 531449474 448360364 559558539 206890797 111344570 618767111 806653357 690598440 458440563 785219575 187632808 784090735 974707525 455251922 705446138 8136777 843753132 231812375 930118541 788053513 437164041 785549904 841953895 133873704 615349032 587130016 952559448 656429419 968882141 258513945 425759944 863971721 645879905 579975820 679997085 68912652 959094455 887054484 595715273 892465048 765400504 677223312 103911027 114107250 3316150 34948664 839012439 14750605 97186916 422018187 608820085 967669427 247774830 664354497 108860708 391632581 685084370 238779202 529155731 768027954 126972083 269490644 550737217 639050924 298464258 283920181 247514765 223804865 864419345 800670491 401999530 749264321 232221034 239195672 458635807 929006419 526775393 66704490 230486276 751065671 585956771 773177649 919224502 556774276 411016755 244178694 144307269 220908583 832200420 762425560 462303792 470813148 483350571 176622071 578823360 383073227 892835168 889176598 763172960 40844374 403325300 90736743 672578512 33082364 762543539 431618200 801066563 527292906 262710058 481512681 359390326 813858690 258723544 55529968 390964163 860414689 13547732 40491937 759915864 525205439 753253061 109612946 342572335 23126871 548636983 534443166 661493729 150744239 525696594 933897324 110784390 277012995 527709960 870370913 487367559 753909814 226221785 1641734 976949391 481279102 224324505 883672048 276647699 186404830 283218114 131284136 333145863 632422692 683228498 174910382 432445971 791676394 218971576 90761667 22027492 826542038 706306275 328220316 206034013 276233459 569014370 737090292 509484515 69090526 739148861 987557060 631087600 297174615 768521395 542664567 195176208 222369511 74146656 138483442 621927625 798177194 880215549 616683805 909965251 951318316 566558327 847286072 922750899 475421175 967175811 472724405 602123737 249012979 505275653 53987196 575025884 209977040 854740102 308666842 752951285 570205144 726061125 411357256 805229284 219824136 12509414 677289248 980852452 279883761 129675304 354894574 129712794 31260177 153037650 394734133 748383412 853484075 503329115 835690347 471638910 797835781 872029797 503690869 207097159 733268712 428670195 313027659 905275175 717344708 589064819 60735292 285723873 324990263 116482517 739917789 505244530 287840322 481464259 580964670 982384641 51537934 120185842 606306249 94928196 342304902 808056146 316953439 964961208 536751740 335157155 322319446 543204801 761856450 814839410 492350839 883380940 675321786 766388993 202698280 189371525 847006574 950529209 619506523 54014609 782326702 350686124 273253655 24486743 190489797 735172868 317064654 497441233 66770656 371326801 902756017 803060690 545718646 626578816 382526668 191053212 103890946 590340081 305776175 164753066 36848306 558798046 553705688 534338445 668291556 232196637 196894084 940074575 674661492 12473664 199522350 927498810 450593319 412320091 634155764 851781048 237039730 243312780 428263749 70257939 684436589 601885328 52210879 939612033 173933142 739824766 357129871 31505115 953927456 205022130 865273946 407552327 581950744 885474004 113345630 678536492 264081496 666805046 811016175 190830854 584368258 882844368 667086014 951649271 436802080 17457327 267649269 476933411 759062320 209234490 433475079 799355823 159034149 121856290 164553496 276530715 416609946 194452543 973006854 104554807 667522194 179160138 597051941 750425840 828594572 897796444 358784708 963451534 619528927 764529300 338545435 879393933 872945821 41387022 46580066 610300884 99004265 678053682 191759667 865451847 276773554 283380933 391355360 71624349 252449902 418138555 741439294 209019460 74087050 905288465 3849806 282389966 203223039 74660190 607661886 990226045 273887937 764478483 963537836 116500220 145912872 1726791 170531081 116472801 11105290 149896656 36520527 465834531 993456341 772352657 301546513 587860666 660048068 748628683 33780806 29826056 453542296 981799598 748542422 360543900 755150128 65204917 966719347 908210370 895048674 543703409 189443859 472459097 80379036 791162463 712283080 211205961 44020742 355604248 159313458 275679823 841155036 834753437 723955147 76007468 27850970 528642801 715906870 608445575 467098137 522312863 34031930 967243726 843372328 495392566 235097317 956759030 108664217 181566028 834126495 147500991 175401967 920472346 322874818 289649651 960413858 392384248 726800210 14276279 435810006 596409888 454045228 992355350 826780206 954919471 917461107 452632692 906459693 453313546 302983517 349588929 686110644 649830402 323520935 955271424 545243529 196539059 31336640 391890761 530570610 879636266 954422678 282581777 881466484 407977278 372706486 379413706 197381207 135825234 200930828 297715431 158111217 120926411 495211941 787040994 231123885 127871103 30620089 938300679 923117193 371644991 691725027 136256670 185955771 605128844 731495248 26496359 955067938 704287490 591742676 64664892 519943543 33464837 977982397 766340544 211306524 23577664 252396155 678903051 246430579 941190037 284266534 823223881 763292486 528725910 922886444 472296362 225151518 178662861 53291984 400647512 232899679 90365121 9671567 516599571 755997488 86385188 27698206 248549334 15595128 135876297 630693247 749902823 135371967 474926736 720695266 479571508 19012497 586556 689405008 184491157 46218503 942530411 787616062 136017613 575630097 329970460 145760586 775877612 515180123 15793776 338578989 987331023 182771381 142605973 641190675 2243731 979550846 298749851 183028063 684526016 73537173 960989057 696085998 170283126 633095038 723656927 863233839 82042298 868899230 535148970 878034739 698211872 31433067 724768919 666075953 339578061 985139467 437351792 7033825 928166230 931082478 852775366 57134253 32524643 513977703 467508113 725769553 522554744 476598250 251447912 895328493 791349517 465093164 870944276 588480922 159387982 821917949 208017077 15060916 209390963 407024367 903354951 212152736 490365895 35602420 700023179 965893898 635597521 405051435 899470857 976611467 882396828 675725937 981406159 151244626 259543894 753246770 120572169 171413477 490115497 136810050 433882060 558790574 823879979 109604505 659055073 719628218 688591316 608577873 299722481 681138457 78687851 902816571 63420246 950708152 521062338 338178008 208224653 683096191 635991142 624502655 140774477 560284238 202685008 867378033 899268560 210902107 17704203 648006754 893916930 48252130 967284691 382781914 408258934 30652301 567593703 588562344 66013458 417456159 275945706 180642516 38261867 732381243 207620935 685922013 453203042 262477075 23944578 49847367 183747222 557998359 552071294 62442333 983500384 725627964 829749578 62185162 559976470 656336630 626788268 342882398 201651302 861361668 378557895 723572976 260642883 82059174 530154690 466600014 41936939 583878337 790980207 760874724 450400849 77729697 81593554 435629485 9954585 410152591 500264967 34353313 808572448 361944429 348682328 704903935 679473625 386657446 556074329 271723280 900813507 331138515 833515817 250777675 935087450 187945986 669613103 98609723 955309584 237158436 759139434 603185746 533854650 861319559 911900968 618689711 332232579 89167868 353008838 868883643 227951100 51422494 27973019 165125251 322481783 962926956 287874339 38932413 582182122 413250102 184326767 748322535 464778033 178513618 690681554 556816198 291136974 993280361 11139162 700002122 507882241 226448391 228847708 684543972 522693950 2945730 110054670 710253076 757965724 156074524 341302740 299836961 340689793 26385551 251323204 6277366 390487070 274582427 182418636 24985961 185587241 350679494 388418321 877931820 487611200 915428858 760898534 52013056 253232129 756022086 794438601 321233710 946156152 764967268 448335941 579190661 724647540 442839695 310770958 155200462 112642753 590800485 315830637 328279367 338995421 201597494 589815672 36654364 44251321 122409915 594345615 265321087 281570080 669489626 857907843 676561797 585373398 91154111 253254873 177590980 216814948 767841253 361810772 802487589 118547580 804348611 179787554 65578077 191896688 840147476 31230523 105916091 97516508 408657710 888894178 320951227 358373074 300879251 554217941 91747106 387235402 460381677 293021973 435084540 967820529 779373293 258188952 727673348 311451164 497539351 390910177 51384517 791157008 431791187 15999993 763278136 120588698 617196870 482750659 769348364 651666797 767736730 12612369 376182918 533948804 887555302 724398494 495265194 764295042 110669492 839481079 365909164 962347860 653134330 424025065 127015424 752154775 452368598 101224340 416744699 285185465 716305041 819763380 269381916 979333280 54431704 558258582 197516331 49730120 598559488 854552300 943801721 49483367 374995755 446211859 68881253 111073580 683012542 338682083 170762456 20467043 160782634 804222985 888112033 916298180 385055834 406967227 236474600 346774814 153632666 48223808 880607912 637689286 633538922 998298816 550659480 375170763 36816558 271956902 963293110 707316905 70836309 404274605 326570043 129109484 550494034 128040754 692887011 762719960 468016721 614914679 839103306 968039788 745635079 95713804 963468487 98936964 754264875 900264838 193404832 741754584 615301869 3131237 707526930 250885264 389742144 562569840 107656442 689076311 108576772 927465829 280008859 137804561 984133375 31823938 421991998 107549200 628172039 401123770 948340151 669639332 515080326 822465070 259124591 538183851 870727123 508822963 333633343 250928684 730180315 940086625 284573311 526454003 211387446 377819570 439334067 724595738 712872283 845737053 277689578 307794397 676203336 159959570 172901396 502866632 184824128 585716675 248961278 379706285 99943693 3287702 249845282 462743723 163631317 438450116 290132754 750164071 539847473 28221861 87148518 748324429 973497850 898735081 766828943 304819986 776912572 413304802 225355343 702209214 433214249 400324573 706082308 129353137 765937370 968718458 513677623 792456165 315266613 308430125 399882163 233808496 997716515 116299397 599875510 196769387 603099453 81516671 411798780 275208251 373441274 171114598 889381222 392502997 716587730 194170253 244863814 758604051 82295628 175423114 14010703 531045605 306898289 239590901 44460462 312065495 524964473 305320159 878798947 912194225 555023403 916160163 334205814 918511647 354773513 961317799 97573171 624753052 612467784 410490522 150733287 756612156 137335175 517373010 958106156 778413338 445878029 606910885 358131987 342229602 393084083 230994619 477192216 957988556 566088692 289963689 305806484 135060103 214375566 268230981 710088577 903430754 792015828 225808930 724629743 452797147 241832641 562606926 850776673 533009900 19357113 254012970 598562408 729955734 821954150 273113516 714631859 843703258 948402846 345477142 504655373 707381392 919050835 134114419 804416132 453215015 785833929 273199686 111986464 294905082 656736909 796308343 325096514 401578412 376410698 546214720 306855292 382944491 268694485 172513172 982350968 232245807 402391861 238891954 987638414 167545129 95483265 600451750 951996471 487759568 83266775 353434090 781321575 79412721 578945595 132091004 209912886 319690090 259854435 9453959 995776859 334708916 378677216 683159878 456682640 794219274 345296248 348037168 836565610 975290382 31049524 233285746 817264220 463600383 164323709 357592720 496202089 688553213 114971529 617958155 563660918 805543447 181208357 816999938 172042880 123459097 523718180 868852705 64992474 655966199 289546375 179712681 335203501 629980643 369327096 804637504 34753723 199798287 554284405 825869492 434926851 131080697 782824228 100632884 784773584 710255708 275209290 896056100 675248415 659068150 723124377 6621757 45376994 377545150 172206406 872801298 256593332 246415322 100730123 955318855 159012216 540490093 142966273 171038777 119584026 509852894 436324782 502549506 145039952 571195036 419184035 153344311 922194124 416089854 338615327 185442717 326755017 211447775 558418890 349289884 128032896 149891578 453234643 426417875 664640765 198458935 898305096 390405540 206570481 829285868 227056705 762995892 988368090 386439763 172074406 700546587 673216558 969749302 369905522 227100337 244752884 455287552 798466885 41487112 957919656 3173775 807523802 771190880 29097967 424988161 722465077 904320867 84435089 752658935 422249104 300596340 78320734 842150437 70575080 761141933 343721111 9363126 311677952 386857489 762941729 802840214 445918363 96808098 774399885 46154853 804406586 557714680 565607 365120755 59523973 106940377 211207271 954904161 806205616 944147004 870748395 984633757 473232255 926904615 847461424 553055618 358722335 626900087 663756974 540156285 736302604 872814879 614556974 771578564 841219813 114740650 78305221 798619134 86950713 834822897 961653241 531407186 874519702 968193267 891683857 35961703 529055026 558295453 100365668 118802283 265079353 872820076 255313445 902043034 422857372 643685912 689438655 906852774 171202248 469110955 223376773 847930022 426200138 701188592 767225297 541615319 558740147 307477770 848546884 919999996 65476345 151232400 925864397 846016440 494399278 381098213 969445056 356204705 563986788 169345005 163715950 887195816 466600031 980167564 872285738 149833907 293236589 53059003 717371640 224856202 589934390 809528630 624536622 55478613 618085742 882091406 87015344 820173061 919625879 620014653 507104621 847370335 467540529 965992560 808210764 567852528 725940874 823099080 956964895 640854516 761844745 824628232 663387303 185575882 36454507 935255011 394611301 162798645 476212930 717328139 245738998 848317286 426484860 188216980 31059003 904521424 322143446 19947579 773828906 632880510 53623313 406767246 844489856 313577595 8237523 187978210 373872717 770806785 65010852 649614050 300373867 884087320 50606921 839282937 877187516 306168750 716013592 749689312 134036466 336383050 484281592 885075367 921906012 986100702 580049066 793043930 184560256 561503435 991961370 494262760 480417445 767230184 370036939 821926824 268503048 706956021 398306580 509412956 98711976 558224009 786052522 793261942 212737117 857961435 881419021 350556450 333371598 615708134 8495737 814327873 660220196 266546873 780278470 365727213 657523538 949936546 53609477 604963292 687493257 260242220 502561620 306666388 939639303 838400784 721095153 153736077 110989985 488399249 311946505 759953223 154920085 534845951 150582293 683165184 324646566 615887937 234255121 736383621 709036712 761869904 170242482 425412743 186583215 856454159 267811633 699545904 917427055 219080746 59977459 168191211 949543293 586786039 676962691 623891988 231294704 581822523 851930371 140185164 17830974 2401047 441148460 785724710 949806667 756484498 805126252 877512479 40448050 909389768 475364684 471833735 137549225 927966504 559859825 321261191 254110209 422204012 886285027 208712377 506671735 384336359 591221590 592569190 836410344 859474140 556867049 614002481 334073676 191069176 287460253 300568122 860389948 37225084 367686323 501169379 586873138 738207377 551121143 170092771 324513023 861100622 109067899 880147864 835710240 513080888 926985893 794712257 315137303 715783007 69755029 387857868 3236078 790039622 663628865 590911956 163873163 381489446 719692749 99869863 640948329 238505631 948452583 179622805 885322164 192555860 921151157 72297020 353232422 63025952 2061527 209806378 815665935 731302892 51144991 131758979 29966848 150828902 52588979 672807806 240040390 730693674 61973601 886018024 872636421 448441596 11932719 215293383 976779372 700410972 846241577 544019795 31090655 72970180 521528662 13297821 458533796 182797029 104898062 351172825 393544748 224316512 731272530 337839200 841425898 411346578 708012424 205249221 61405582 146811644 746212468 883401827 543199290 513576130 790727084 278524221 840989036 48145210 845317514 71807087 985038935 967019531 767641805 60381373 928486695 422770996 158682092 836477596 640883826 80984634 172048305 737175800 529008821 749437292 271429917 615445207 387147563 704753313 42552342 343545426 448834622 953377623 686706569 645862536 418193652 636253667 687309477 882462602 681396093 397515374 163408733 849737215 951796989 468712083 253990189 24447697 760860919 157387583 564282233 94909606 638389684 486710008 663266583 649861470 260019383 234355136 356437659 552976824 238243816 405884785 158286170 709084258 837275621 485772064 513860536 103701356 596818811 418529503 56301657 74447796 37569510 356692311 592368483 527238102 591878717 267260527 684770242 457124601 896058543 45255139 925598795 886400664 840955776 495438325 469710813 916601826 900572417 349887637 103905847 281330430 717829856 607108325 943378624 658760881 700031614 174959167 796288181 308430875 547035777 40201731 974422315 716540792 521552961 64626389 842936271 816035623 290721589 87319392 129355111 313602568 275999648 745337786 876440353 279434611 630154050 22230444 904205603 616350185 402827972 274402042 205404452 403572833 161604780 146728235 841686474 345306166 883862473 308323030 429155751 170162558 493544799 837418657 868927125 778051634 488584449 672179900 481200074 342962 478828769 575549110 277080987 249080016 51211995 706111185 856269261 995841203 209168828 501641448 930848609 35271275 171697499 255432055 633120409 684682408 403772685 561385595 624164458 70429069 14132126 992532599 5071794 466882011 961714936 159082207 754384466 255238242 720224139 85366566 223391457 184204748 272024728 754881870 512527437 97970792 59350831 674780938 353996668 115778596 329803255 447954491 322529688 365124297 582797435 431081898 643561424 316345891 136345217 13550732 713967141 349168695 270727246 215405335 237765646 261095392 197894253 880430386 21329141 500627133 414039961 234332419 161165924 968971945 740306759 452225951 282449437 230752018 264868441 175379820 109972129 230740112 275074629 280872292 624838205 879746580 55085804 865665090 330168687 726414155 541069260 117746687 597968359 704552854 702140306 723152559 325473594 421358875 120194378 661332839 349836323 517625528 236170099 651990415 45148122 107709394 436910287 845226734 429742551 299053876 774835957 392126109 502288764 451217781 256187083 103550372 370671222 565468085 561208834 306277618 308930780 924749584 356226903 461544244 617813918 348142802 72799275 804720195 98214969 586257328 215699631 870059596 291585723 821205639 172718539 721813969 46293588 375470864 306307784 326639764 310366879 232942890 140187821 46294606 248923981 808767591 239442193 69140222 355185083 217044410 822254497 474766554 76279137 90555493 512233408 268790708 870505130 123922887 189290860 396817928 761736753 582366635 26160469 679501698 332247941 836819495 520914460 41194563 495948617 553783775 333076706 93868227 52089049 859834614 643670645 87041550 340696241 496971307 654045226 717103699 707352582 337941093 775669290 773042356 308512314 956709198 82055253 765250122 433801126 996503098 122856890 481765636 977350029 242532352 670878860 365340963 515800204 131180650 532621058 631651497 464862743 373521796 998902656 301143516 981239324 187291247 105313633 843569683 364700610 32423353 272669305 406195948 86777674 815241670 475695861 269103878 774220541 968486466 68050894 880839901 384310620 217846611 63062788 528741525 261891688 386765754 291860320 817416850 93774963 624044606 173650727 515868889 924074136 142284981 301832424 214218534 355319595 362164331 740496038 826103925 662318364 285984255 775959001 936261441 202046375 517065450 257873170 205539210 259543267 880618763 511229939 204218797 723305260 186565146 589001584 648302565 508379132 125354959 52341017 686505494 960733162 450471401 294833857 510977139 584784 443917147 769479559 650644451 41362873 941620471 217503833 483589854 919353375 169524770 23526161 266240744 35093286 420104766 842009303 411591916 312514604 510951143 643854653 209435474 48962203 185520384 433214516 184230826 172886147 739474755 150506614 77378230 166056348 865524335 816070586 645349216 594249550 997896462 215987487 658251454 601215989 320138963 122046328 693374321 261592890 254172193 558806933 868349014 454344446 491377711 812632148 195547673 99049168 952674326 391321429 971255238 17388223 393989795 213100138 32126770 702475999 318531742 698369445 20712804 737918621 59744622 658197928 852592300 77585050 3574216 786043891 94521603 301052795 152802544 40724564 398318691 283057686 427424537 231541121 163335982 291869685 230784633 563173627 785788755 367188399 348438038 907896896 86872536 419890332 663742944 757679595 784784649 807215104 633638389 875294949 114787205 116573646 826289955 141379095 645940289 833137828 158706106 996959131 963017340 183470632 779001806 792295792 582029144 626426846 388986291 957854334 184336813 631739305 29010781 837140132 713644707 719819519 87576841 641958225 152399638 420943401 140341119 897593303 657437076 534606508 238509157 199878624 121538426 666325822 417685738 437229580 742704869 106440929 992073856 902670596 369169404 184174659 767608740 141193227 43108247 74223206 319580888 3128835 686229892 893859000 952459624 848504181 710415832 244741127 89944765 857850105 296905906 938939019 731238017 679413260 866182672 944205689 243704512 543653628 934592191 211819573 85259868 792450075 779616466 698818445 793791495 901218486 813089587 868182094 293401420 372473433 845068482 779799716 601338054 880428961 412879509 179915603 282598729 301016440 29522205 676408705 714108485 355995871 7328303 645312089 162632483 490802103 663315645 311236067 326374215 95819968 862750098 26581462 709161312 108096862 564857904 277808457 995620553 850081149 296457370 873243167 639544563 33280529 132508376 57255594 816961094 37195723 182803710 184271328 736691735 685988713 505328361 721456398 168862168 836113719 130668543 871165990 43308094 459226585 68896923 730208772 916452797 992956824 475132398 938154363 650157259 550375800 203660923 167645653 402347259 281109599 120591806 55520660 983390461 353960342 595235630 108221270 755346269 20940829 445040506 439974145 998531498 397533175 329788310 885624615 734903253 556311721 123617142 384035952 885515801 98472002 757672728 52547544 943994164 89112779 269632323 881603618 205841833 58281247 435083648 21846694 403416450 633597058 280104585 418914128 270001122 112391787 920538176 40654963 704596683 401716150 152250215 529722696 778508647 97151301 789319639 101379321 422097812 813454857 720305839 962293325 875624169 182842486 877722482 326091009 85948051 187243625 79716310 404358254 278274907 483317031 974700352 774780125 981884904 760711305 156316723 626636283 999832407 9841875 230845166 207394351 393082899 938676830 417363693 624220982 116175578 296082085 831042379 205636250 135386021 851923284 849139315 128450985 383298350 210360266 560582186 99064203 502523630 83851361 595826622 674612973 202318282 338450892 221644908 194651922 602129718 229858399 149627415 886632221 100862714 140544016 506109438 339092290 624461908 686100092 104266324 34155429 483695368 466605947 833958253 321482125 827350283 140520645 643358301 356857797 758229165 38504124 631071791 52841887 590624169 803181068 697993187 62857364 24506204 673429340 205909324 885521320 944992774 642088657 90286801 976526723 214786859 307818281 391167747 356508576 597042995 945291014 755591456 920963734 682633425 571486072 830091837 528552674 717363809 546958969 252666775 962457308 265080128 935145465 169675139 254700091 788142142 299977373 136450704 642727947 855128569 471068855 577230189 672853421 838194065 339203095 431909884 392943027 749181543 802814299 292383851 383614631 248744398 685537264 212849515 74946017 584590861 808458089 206644428 985418857 464368212 807107384 277784918 194539266 953258210 263522121 330799214 703154875 413007768 226916242 207634719 293047362 292845296 151865758 362920872 821767342 353085414 146018522 910490853 768534726 780463787 347687036 111053266 140364201 123241248 897262698 492902303 619667966 217482936 391604919 951343519 305144167 6299995 597087756 882218150 708624903 925767121 391609693 670295134 980702250 470978669 588330268 748832703 483663018 94861199 122407093 284729539 4311445 982978998 669224421 143411603 443699211 178228582 979314304 227792972 772117480 382285099 715595702 586821728 222162443 760663551 419827304 765771864 228643811 36273634 876614270 716003667 120341627 201004899 727141739 818243583 485231045 793517906 146378328 287465367 9480398 115029288 28238102 138068061 443883413 338660888 769074349 994227398 400767676 420974865 874649610 6360984 237331288 988816232 287557446 771128911 256316477 967487446 911354621 869737341 298407018 239060330 245099085 902040471 941061671 364301162 47884718 623361232 460346170 458960838 931533378 961753225 545374329 831788149 936769364 298111043 898204214 730621714 221352285 933725698 860255118 78500078 108000513 571844829 281615113 489465212 375884575 325401641 887789412 784495620 292977193 209087495 710902500 204603059 2444126 766978900 560159640 153438236 36577305 402171627 548548683 231564554 177275545 27572939 796694275 251908854 469402081 90330280 489186594 895179892 994876012 819553837 970497420 112340230 23861765 343677661 788272447 82347343 167115498 605530833 797762741 358785872 215946149 129916365 849172583 865560091 886168735 522950826 132147565 901675409 734126739 740953223 362253198 471411027 567218829 121661292 385490415 896183818 830811894 602450665 177795562 799783555 284289629 795713678 427908872 498508981 976882017 697767119 672186726 243757908 95336816 734250203 441065330 927798585 764068357 331271059 151818511 741161147 240864767 429111436 718560340 177182775 884267214 67808405 701862642 51958833 28546229 278863136 421272796 960447718 740850960 691340507 179681407 822420860 473426958 646504663 593860576 231646347 467540164 162195569 845596582 405229342 415626210 108635513 332679511 19412892 830343440 62071271 712311746 858298399 792299736 23252762 60479162 234602628 333824526 129749838 768583723 269153413 235416263 605006508 298343602 126289577 25478268 69921291 55845608 497669754 945774410 576877458 808230276 310896654 998496823 383547042 961788378 44520376 627181632 232594322 702792675 352007401 380533388 543068517 72688720 372002966 62735617 395099769 263505039 152911548 660178550 763310382 308020127 488287670 719564289 39765105 735744114 735577047 554969819 859236938 903972542 145114735 96760155 240158623 586209342 372434148 724431184 921050437 285325759 54339753 96303369 877357824 460233303 20089261 158136161 383051634 82498448 973056322 679695329 177674548 141664791 552846604 799856687 601347828 637825691 108213649 379138521 736690976 70964083 385941521 257155050 149828976 664707935 127832353 117929254 184581485 579769944 863827541 381044907 728686805 496753385 244288475 417543701 630675141 90858865 151026928 967169924 86981163 503833701 299169687 110469870 940825426 693870940 145986886 147774235 888494751 886837994 85171493 97483328 118684753 127480749 101459841 860482056 230864842 154622942 242454960 890344008 702850724 876190025 776526772 764550343 699267191 641286864 911892958 645426996 804603416 676980436 75616835 112187114 88409138 995670092 865729342 688516357 662237972 537043427 491892719 918293621 247546092 423234121 191798802 948683674 617361102 625486036 224715456 6927200 379550643 725734908 583847228 221000583 217581479 209245218 263050968 86990422 375182841 877423123 277072749 482048612 856250495 690290288 364506418 980709373 370115789 92127747 11058050 100375894 667486157 102690180 196872206 69903662 959710549 887900142 447157422 612644606 845331359 947090220 96041291 411874102 872283893 142247847 355687054 96263246 607137846 178800143 323634205 349559026 290386049 662032825 341476199 520143550 476453553 59095901 200070096 282003133 294384017 250913734 905504210 285786087 468090654 545718341 396096089 78965738 806289122 767863152 437143157 162506333 435237991 737617732 195740281 18221465 180127142 617108018 11101979 691657152 316458682 626023304 672564221 452048854 260875268 966294057 981121079 472938350 375542858 813365488 660330025 145802670 232954313 886866038 544109564 349376047 961448903 388176914 93158924 622123358 986147078 478242111 707894514 428310301 728238112 56690494 697926154 268627041 9898963 58530572 219796710 304961753 188181175 62941389 951919714 94530334 485442980 21865679 690002534 782771205 110063479 909923418 481096713 452113303 306340405 845382147 549330216 723173209 113076893 216446136 598599462 322661002 259491876 113518223 565512385 240984222 828282033 909464904 672249565 297169621 70905444 12072698 807470525 705859487 743227813 499109917 148462834 290630696 701045889 504981550 469750418 741971208 561938892 678528789 24167115 404270129 978377597 421649799 219362049 263336107 707251062 300550438 296606111 165330223 229093871 777222992 683488287 982524935 253375648 287294607 740497767 290909917 400027157 175301052 764169707 448099024 893897563 502698767 525088228 217104417 379686214 484895010 42988469 458944044 604762839 326138014 620352547 692919277 975785986 245889158 388609182 312098455 819368938 20377733 618443645 320782230 777845193 671512851 985762312 166898830 575777266 410985584 52776350 295950573 71235376 124196385 166357977 231461437 936997943 940802340 629493237 17259199 238971936 199281674 205555679 201484345 820005825 645604635 154097128 517984619 581286057 747177287 417318888 220240000 649445931 669687474 723079585 225898179 689682409 916809820 46892921 188338686 386065402 735933978 102926305 507358193 172792621 906341163 488306965 361221281 540394643 75846176 507854067 335888081 342489821 557924258 251921369 516093521 262900454 401085886 71901471 532235368 619830396 90558510 80407333 943946516 53822127 203377158 866257880 491463368 360688097 823651002 751154726 297547761 631403494 20645139 961974483 489125385 604140571 522137448 194385899 184427726 203769766 667559308 33620647 268949148 354579045 694771825 940330098 565497853 71623337 329124838 676753763 727134806 334695524 899128542 293327234 312190081 950483992 214069098 273962214 448204897 752683013 320385929 538871880 364585533 950906268 137044084 668149057 1205914 887380707 934099076 573405659 673325739 959074752 964655484 544677593 298257283 866714887 243332045 227711120 279127622 204866657 727856552 497052742 665069833 822759811 925854950 315307175 883147739 65684 121067486 960496414 815187072 365359102 822642271 995655542 428920962 521521785 416878121 49136897 640978998 180492935 971477835 102241047 297523753 454293117 817376986 801149611 790356804 998220538 399859340 560820103 441036543 173230411 571151283 285946590 437858542 40856269 371506431 986302548 769754896 251890426 961837552 250702709 834859452 28093680 983250857 689414935 694637555 550559982 212357430 709901773 285077091 490202192 240066853 153087441 10240762 535705690 754882998 689664801 275484363 220606236 882906714 593985933 634576991 657998800 263158024 950491794 923288637 160872654 819192546 969731796 489022638 506957149 446181019 650542689 427974184 493743961 638142461 675403520 150663147 653982240 985124953 805963349 149739809 244391378 909460454 65553136 457012491 30439412 770979530 511077235 454011236 280181808 115083467 574362086 312286862 939947036 963678237 89830291 747632028 29019101 36526620 870640431 752227322 517122217 351095684 497759094 245011174 903995663 400285562 780784716 121028482 983117961 162525105 937040702 923709094 459300115 324418729 159385045 52538809 617001004 941427809 222755844 674774581 177730309 376367171 919980858 976955710 677421317 830028666 119565658 453844571 519238539 602001346 750570362 817857103 569924062 222436243 286045322 9240360 788445013 218740127 276295726 440118812 832363919 235420656 972967743 356498989 853582940 627137869 657292341 756530738 414375518 544959655 184818355 752870948 84336386 722726205 204800514 169435748 242940585 755718854 778766270 612349777 327624610 374100655 872996825 765399834 96896461 392494974 513310906 122525324 226629458 964984081 431967556 679386034 247958630 840302910 458343695 831761700 1131243 441282590 910197948 449459125 771484809 29762219 241439988 46195425 325700823 853705822 43889845 17241092 764628331 114006091 144250961 776484107 929518121 272461759 802286890 509799867 574757063 513260444 387038154 532565990 857653002 896557055 982022690 283062475 497908489 136268143 221571756 224695772 541847336 209397087 787646856 873796835 807330992 419757637 504111162 480867653 123706772 77065164 233978751 100994784 147798553 51382921 521359379 390472437 258496496 809092099 197847251 45776206 274534161 199319961 770117661 652113962 499408963 390430528 101140054 15394208 344591862 804551672 87790693 843175613 458296446 545701493 653470582 159586849 44788213 721152490 155993135 103070607 744018559 741105722 51973583 288586682 231776818 466714692 772087340 953908974 870054908 877951647 165724761 78337287 669432617 926510163 602346433 472246257 340580995 767478667 671044822 41803573 534235553 649936257 334113956 867486286 901946385 762507219 849646499 493513057 643547678 263015530 923633902 694324657 617378811 110787596 411992462 202709986 266648882 999122001 128877601 620103093 927565515 774441368 503684184 515142498 149927358 992969254 34929408 831715011 630184797 775477059 566450525 573321344 942376740 338505192 250661820 773472577 732050367 248718349 50689751 160848716 832366058 781333010 947746727 213443172 667948414 909094329 685798668 562461325 123871087 701483947 753789369 409940337 206381324 914357019 258482577 840857468 957099339 102482067 46846328 701227081 143031479 655041077 30423248 744416585 169582848 369474311 790865942 976492513 325028041 508327144 695354922 52779350 518106262 737380582 259695353 866469387 288621615 278619576 394167843 548261437 900625788 93628428 241359543 239969724 356499130 252393637 613832993 270032267 816182760 101822974 635897094 262966658 54918047 436250000 720505702 381194955 627063506 748798234 186677590 454093164 785521202 249586593 327023753 63041481 73941060 799946004 200959477 576442345 682245601 657151029 270881398 419458101 625034607 559514894 95006074 164397120 887925302 492026334 28855122 117183460 472379136 718416400 923246050 810382370 702226173 947413096 822574697 130582599 466354839 47745125 146542969 979096272 582040070 439398048 164867866 377402017 773558229 962436463 879632175 716502718 812616422 297113444 467213857 777204971 160831244 982400577 599839777 773602669 25026872 848763923 992862674 840895351 608821365 921537319 140747896 341292454 140151495 843719110 141447372 47236157 14010439 424533657 135979966 604246869 420386578 278569657 655038709 313909905 103979871 345165759 401008944 965482411 525890037 336115920 776797727 733168129 239039512 886978234 806131118 154765336 262170406 6259782 396919439 539521185 453827344 775447123 756103540 957576097 32793061 17648356 846506174 40612308 24433624 306302984 537357815 442554036 545867994 803281227 822704299 409932536 43541858 477097598 552004955 966131709 237708567 593292338 518382993 542389861 276295511 214304839 682016852 186365177 646051957 699271075 988686119 261707636 585460902 698129197 856773936 444876514 752356895 886599079 260557594 234685029 693864614 446894826 81030060 409113831 442736207 477308224 648594712 157736029 23659646 744376430 576506302 401698927 703924353 166911308 569803511 427784148 332677491 212373453 353083918 915533802 617018795 88177231 570076128 813434390 312417091 872231782 545113407 575876334 972019990 484684956 512676473 280269796 684359287 634567918 68805326 926078085 746772597 595257425 501274644 212875818 109522718 279088381 614500759 77871533 35501227 426372437 952988702 360011196 473366892 211700413 491124937 563713255 251451177 656793964 941773992 208263448 909254325 295148901 3163106 310929877 919447801 775217435 59485398 878399696 936089846 910966126 651331039 608332909 289605148 163894937 897634259 932263625 183800714 566498339 478500002 181360994 28199711 873203508 220751371 493784427 982615092 92325098 379654295 951127661 444141679 716270382 826991467 467729170 38111129 1298704 910325695 782844990 284229702 423689650 534446783 615496297 864006539 891412534 377808447 486101391 735084553 677967055 388209186 286810034 798261019 974066263 680595422 68773347 615927185 447160661 673336562 590266023 616082253 369340066 35473414 641525589 97430296 850448181 357024619 819322759 671807025 719210103 112397859 622502991 95939219 135256858 712248935 464651374 790486875 77193671 638273697 736898030 864594050 863067406 352423959 898114204 894389549 157976991 383509159 678600254 646171068 212240551 281398120 68137767 619711851 183282355 969727605 895082021 188079512 886100255 165008678 18426875 783343947 853801484 380999735 826671902 653407441 884282086 354021641 801306719 23230897 597253496 850407952 39616933 44027364 52414528 710666763 746084276 824681936 193539128 688465908 167249112 215980281 888617902 13661484 801698516 455443027 500851508 219873242 762299665 845712927 907974093 196141181 769541851 935683544 419875548 250857544 306794992 230277961 754863659 919327556 623290080 310914134 891740804 610710465 105701170 835555949 574688007 683156910 441221086 182934411 468034658 939260569 556880115 928346503 261174138 967244493 903514898 896557501 590512024 69675423 984071334 726110906 81183705 582557096 639485288 678228786 593409069 343693036 291143052 785390568 319987035 739525328 51611027 552745054 98772659 421199183 221166837 997083526 180789194 1534647 369259744 224652278 426592859 199445069 806742391 669997776 330659190 115119599 60520703 228069758 116524857 65682295 453374132 934308499 252627470 787366407 597119237 638574498 951758327 369168740 412512715 170957632 249650646 76132794 243242948 165863865 767506584 667827415 927591082 742159822 480009827 646828001 591252084 402626954 29945131 148651801 427707134 213170548 260117168 510647004 399133039 83438637 834727353 319948191 804471186 769753624 175850066 337465091 307028519 551790088 574771167 214159317 93007532 60737127 103241946 220052650 529095615 508970995 108214472 574209148 362808667 33496023 602241352 497210392 852956431 596075224 527596694 734107894 44113971 413608336 85200549 132944651 649952870 224266098 928115048 261257007 634896608 881828590 84503838 862830861 569081144 809496015 265049703 746851131 15274493 584617783 424805567 687683285 913978394 946374799 383364350 62456631 142060540 549405225 40007269 621439893 455438407 100863254 424164405 64947508 590580003 672663849 43191298 15492483 897391636 81531725 276398968 89748803 72958133 77065179 571494727 900466671 66957946 58074995 339114984 158765668 151991587 937897660 940658782 142594127 902551590 405714007 547193413 671390634 525124312 547533470 213956496 830750789 473798337 423807763 929527612 296677587 633533270 888831370 11182085 798191016 83063316 26262391 890012591 669790051 359033209 271044289 526549304 242223634 415948018 898430820 210684648 236688366 59912765 782884181 380558330 475003261 445251163 210483647 687260807 614862544 330257895 370235253 811075339 8651085 51946202 377243566 76144904 991667225 308884965 140454490 18319689 178734932 737959920 176037357 438720430 569553628 678055668 142132059 768253003 790112132 177072407 222375709 785637269 894136806 706670873 403381664 375919676 636134101 150146778 223717680 739735582 136594053 82712167 967313360 988632470 228902508 600192533 211369276 611717897 745633517 69737097 614369332 157797426 883911732 378593513 618337575 462379642 821685966 280844136 52772379 998678070 386697368 943299215 956379445 53995464 85818660 957202055 564504427 415748419 79108306 219923167 163733486 701939463 501454157 685047276 632811723 256547605 951743070 88543750 244480622 222453646 543467031 550572679 76137581 604553898 898898158 946277976 188029449 220780859 998001126 865834056 135998547 844463440 98969623 407297885 86190260 14382304 96778067 301235473 892348580 888114930 430452325 178357143 691800313 286109130 806349006 278605408 85119142 990081045 435916057 616786187 638245494 754187860 799068398 247819079 386738743 325800881 676024076 622269025 604115023 22353534 518513989 58638552 38562594 937334067 710257617 808917126 125739367 412190263 664642985 217073220 897561089 120300520 429259995 781957353 705014552 149723658 109746122 690439140 57968325 927675418 730836889 156612705 118674573 723752987 142337418 461412240 968881257 431774765 319446317 684726606 719497103 802394924 816401464 784243280 937555638 379046398 792473421 952756117 396058893 241519270 878254725 238665712 472370942 731882380 612972322 831342899 683821900 157332231 699317712 210490988 914963747 508508727 478052443 647540464 235527917 911732099 825790633 884387280 423875346 3059097 40984056 720410993 218225884 957591187 180393976 75926380 884838199 681718974 952897461 176792065 763407177 917920651 410607663 698010802 215441246 250615153 577240151 557555653 380436119 68675171 556984504 259228096 111880603 742471551 524941563 192412814 909053307 749571942 18051942 253623152 944607308 795296448 434951903 272665880 964519559 151816851 112821586 911311918 764541211 469270661 235849032 946361734 698952779 120375238 428954416 401387038 134498088 348832751 131703914 181440001 498750113 863110717 512420257 279482124 118558642 463169578 308907263 2686535 63883119 898921869 38401504 930343148 29189053 407484403 418622910 978643277 739257068 52672706 307256901 998939521 30705379 62936903 12772313 210016597 182536730 792979635 296745916 969181551 224690463 870145088 48650268 109240367 957838127 400484042 873993390 316985881 566330096 474648430 89319984 440522370 507218293 554390889 479188314 348991506 646347942 554204636 163240073 374015366 375120107 55890115 367731929 559572361 175889636 110032434 254108079 224157939 625410684 892733913 954963127 507077701 590693743 741374857 49223843 357591397 994986183 633498798 299213937 678227930 388471482 949992340 771590475 278945552 156655486 587479638 2464444 107313188 78652941 997399025 156624259 97570755 815370308 731210985 419113313 895186689 679096056 131760104 362584867 266115166 314530961 129752717 101459835 524830561 214284770 895236671 15205583 537253241 218452290 172555559 148004061 109487743 475242126 776802048 338886387 35446742 437753881 284675841 829960594 188138098 448697022 74368110 635091341 827697087 135860143 467002865 326323101 872753440 391566782 810802189 130048727 392430595 156625788 179277783 775931894 605434060 25292354 501533117 738016284 140403665 326358588 599807236 245963667 230571140 96555195 988603350 492010788 634370184 823659836 29383143 197624424 658634816 847986309 592706205 904952118 746128029 893874492 327711791 389436560 486413396 526144579 978364927 131871598 987660200 556953967 729298385 278547113 434870410 902470414 611304014 358518172 544535184 195872721 590720011 512493078 104441220 704498713 417481270 735722665 281911634 234113769 653761240 469870399 766938074 330681061 71907888 249792580 894342716 805317824 406095376 930585199 392288368 145204991 58971499 798823537 600803761 963620240 285012838 63422492 633042178 264999770 655797001 749634479 307061215 113205624 397149359 458212409 188170955 696045565 233226016 372551363 817145684 579104634 86956904 817482964 129643642 787980319 114958511 889983810 286806756 548870447 268849303 405793363 111512131 254414870 569022207 93013239 338371062 31211573 997053038 246819233 956143777 252701650 584756149 833852189 759248629 378153896 671147328 575091931 161094455 893041499 364610709 224769926 535662746 280576729 854319243 390955053 774638575 453476095 557402395 732840684 346014563 918576791 714261202 639108942 733043931 12060171 685758782 245742379 74608141 235730898 697177853 436516465 899126455 343909120 114910200 267217400 42339666 167020597 992854620 481724267 286241452 520779364 587393414 185891360 778021583 837302898 527155447 397233663 758507575 21260434 779705119 719321531 76278111 95821584 262088492 739901793 153200477 287359709 631164354 154306913 170616788 794223768 31908042 505223453 359128500 806105221 606950496 824206391 762527385 925003681 526109699 972059107 489809183 808215205 693249152 285267239 75035390 76332656 682059199 716533418 211095195 576076440 513935294 251528533 592969792 268404479 658863239 291249814 108566710 242982591 338956801 689741676 763121376 808010230 417438572 406704158 812257152 607792423 672295711 727274654 495062658 431278220 268149111 828212179 366026446 203678406 239758431 874786990 346725987 967789685 883188429 466218522 214481349 200602897 450093654 9072290 248967671 821323164 242232574 526391744 671792823 570835986 266771017 642042189 891916292 539815886 773600982 431301032 44221094 161537428 993259645 596407805 266972554 916827506 120737154 480875964 965128025 802352774 995047056 497920758 232152617 436344824 939291787 301246074 96261320 39305476 28568955 193454433 974031594 316193335 357869874 913983399 82708054 44567240 922755309 823987665 131831032 398572490 338541015 615621970 330647227 270974771 757707154 434776320 210880614 106026209 903347323 556784267 793858245 222118967 958410361 25394919 410802036 373248205 798337724 228905467 442909626 759912952 762987902 71351004 250110056 701882154 710301614 259070401 502735797 203748493 361511842 773640693 372066399 716440958 949565321 204313932 871215306 922656734 291445833 253641020 418375231 932877001 253557173 463778317 812899727 792539576 235677914 98831007 249767097 955051582 984590541 690284388 888234197 527033285 729530036 766904643 690073515 471335977 737688956 749899546 365779680 274895724 129570887 369987962 378112617 491465340 191866330 445966327 666796361 437923993 162460382 846939795 408089882 592010755 554910789 896416712 627991756 594556503 411961573 673211813 969462823 898245363 153307461 184425489 543822416 221414421 660055637 814535386 156368144 623871214 59918877 844431682 370461267 29553777 66316268 127685015 581109459 522762749 588105865 558582789 265352013 737664459 247484 272659486 158033530 45213464 711378145 181889796 768844703 254367150 769484813 592746436 993768703 983363753 211806761 548637874 510655899 149235493 141585926 65934346 234158754 40228236 253854922 847260898 317467651 77813265 263699395 891764358 697718628 646632619 864963602 897364364 469288916 86887374 977962647 518501555 774052025 36090494 279374610 535401682 880051395 300785194 506963637 346096202 814094172 279933520 273363483 16556176 766841556 236046359 401662653 184989704 517564860 3892514 800937133 376468630 180975608 295586345 228398010 92151639 235607862 154140674 57814037 215664816 208398243 679914194 613154637 786677294 746208948 189573549 23947938 157919805 655579543 560518776 205488057 875433036 200579418 995762450 949596248 532233049 818661820 469034547 324200051 461045515 175667194 662071473 617967095 805106445 962796934 447893481 293883369 676863153 530993660 692075108 643001494 152691374 168583077 532135680 110139054 181412845 265973603 51912745 597210187 84667956 12163096 208231227 437457262 933507308 253371754 351053951 454803706 314777817 282170764 438465483 926852114 939659934 755803664 237753507 334206532 413419960 252439621 253656908 160457513 177636024 269439938 103183540 62637524 64479934 865014253 577908543 484026113 402880630 324939960 401462996 925348800 111879971 96454412 145344365 216649383 67564346 733641448 512439816 760350039 907034654 472151471 66300280 592903260 222009188 212211370 555495272 189077428 684291370 941901491 501298909 66661908 267695712 223395839 197867217 554651238 454214390 657862697 122773319 186829184 413498890 706801099 253000466 286053297 133632708 147293696 833329130 771405180 317532241 371595050 798364440 786758681 279298121 336327948 208890348 737289261 683657472 853980090 326732111 845147618 298679389 288767907 563356119 583482531 794188329 821031331 896438797 135934319 193643667 184697716 85205926 973092460 171903963 49339160 579120009 604264780 121103209 428876988 125478799 639114608 517988258 215226283 557269401 586670672 987641187 973954499 753559737 124797495 46249483 490740580 769234715 888098647 557610335 331206653 3577948 35868180 148701539 836380887 946905886 499775401 536894892 47741971 909966439 380873196 153657806 86208573 738785719 695083646 6968024 109723466 736573531 336629826 19205105 87201782 706534620 667719033 802184692 187008287 309878366 477015606 235425786 641692287 874159175 370331076 149836882 274504193 405509148 941232104 570299973 310292925 87217220 921677541 837458820 392641565 312904208 963186633 586040677 138853051 495259607 287975156 192955664 334814824 277373958 152912228 49891260 605581706 881804054 112491106 512837505 559864964 842145260 52768236 36763425 584957478 823707483 218032408 613204123 721858729 276164438 35186727 413503870 174856272 726699143 674595072 267823280 556614872 823004253 572897100 580151054 441457336 298184680 668973499 355366824 775760468 295128122 800014560 802837990 622637732 698638076 440178732 210446229 328964583 434420868 238251716 49854184 269525303 321130841 138801776 967421629 511946164 492265019 225135463 19207603 482793586 538241882 169376158 517875353 603595193 973215659 822835701 317845250 168763755 972049297 864958924 74621468 84121444 548443864 127548203 227753735 137073198 106519194 206646681 613129573 325046290 456436295 112370662 226908574 941641732 114254903 905700791 202143378 276202906 680230828 586925632 504077623 417006433 272226516 880281491 417143617 235062614 577909395 310309581 420053047 774103531 142058345 663102697 905810464 21200763 819156606 437699142 191485741 917690834 503002241 260248661 288563533 402036432 2650893 404279402 188345376 898766161 804990523 623431873 129707363 559624062 564017582 442940076 208903261 572216301 826132964 116920459 976130338 697153781 618209769 842502170 903245394 270367622 631595475 66346872 543452927 330424189 454464281 709068412 128834261 750987301 274072599 26637919 568979254 435422575 947230473 25261034 924559680 11349366 572363962 573953199 485156092 376895039 778935745 886711015 19878159 307686281 502115940 341886666 406727660 469462408 492705447 176570531 369356742 77631528 194631533 124415871 214968803 549703285 796525573 35932647 3715978 46692059 642678017 686506975 584157739 62610696 85410654 760774678 3865810 676917638 823664525 62899155 398500084 562793357 498883119 183878457 268817195 176464431 15279205 528567865 929010301 439282576 478656101 298762787 131487967 795657238 946454899 173720760 636222635 236356957 803652077 560578052 373030790 495435029 110924078 657480591 192082372 86012799 232661015 742272436 23066784 446515597 875191889 54696041 773234681 262757329 923200911 328348675 672458404 916367027 867553638 147968978 5147026 490080957 112479159 101759844 646243807 760724018 92010961 455938101 598917941 606507218 216589712 51872886 933264101 281580155 176156448 409444747 849763522 983946408 261160900 148577128 73990316 986344220 57296911 607373982 262713010 251805984 778089088 187191668 83971066 636112337 293149041 665489718 842377993 688119014 62453332 232099199 726487050 805374658 988584933 18297268 940397361 392941195 257907092 298975188 773564753 88099782 566545043 201712637 587361834 308466599 369534188 671991730 954829059 516067983 60869892 190518931 376462317 414454014 782326708 449314467 552377257 687784514 150102694 363762830 146963636 887663833 146297512 677274096 277390022 312217487 540866404 709149683 130416355 422782177 512876849 877812779 639612403 183988993 397073464 720992111 717675983 157483428 227115173 319402438 929901200 840818879 580944907 625984757 509848347 208672268 582365617 662257829 738767446 384074391 243483245 18075912 963091483 532207746 150643215 327738622 21312625 137031871 941374114 974388053 140700999 337202612 94528187 59045027 339937479 556249563 529134384 314394526 970204267 129327137 856360445 922144616 373292670 572135025 821753712 68953365 217596453 669046219 860485699 618973830 255097537 640920131 38466812 441943519 242357400 712674270 968820938 217162107 825446463 543969951 89033902 299091792 145896784 256277710 303855472 274160605 483557004 821036028 762240410 75077857 406797615 470553742 294231457 649762738 521583455 222417402 879553294 830185777 134220017 472698224 728099525 446174602 886188800 738121428 469746091 997233933 208614119 610452608 662925689 669482039 136388415 238956441 433579283 737921817 113033459 419905294 768001199 70919042 588571002 657431777 902683707 633915303 792170878 726801604 559632352 294050022 266310105 945231374 458818294 351032583 395544737 3915343 713287734 671317065 580775945 479352177 234028765 898754435 117862277 601434751 685531798 761039183 500752332 34212429 225457544 606723755 429457586 223839549 122953909 54426103 871487536 712594773 637783153 490360583 816810325 893847558 492002199 600429435 602161299 140244259 310521738 851310434 599523876 845527432 571301527 281081091 397630501 675500825 381308483 156236293 194321790 997429529 136491983 510159247 311694315 969013485 740673758 6763332 768679483 844388240 250690199 968099184 217162542 472039830 209109497 130283683 184308978 21039399 805586485 519371465 22774725 141013400 906478944 188131610 492522716 897942300 506654167 824343385 581621465 734174635 583517937 26109920 816328649 124135810 874921017 740982309 395375738 182020954 287074149 704396710 104252258 38836362 357307775 437022352 311669289 914302504 343878739 216206165 420130444 409961888 631971802 509877721 959777466 374882972 183778406 807264034 316928303 318647442 79115815 233779451 459866620 442835424 936988558 672666203 199698323 360003689 661314957 570401462 755940144 18058522 644400310 245182725 19420338 908684547 856477080 292217722 563430588 332757261 138126553 254111318 435118366 716940862 330687476 379805743 244853585 792961702 589086419 176771878 898762871 842751796 208469911 336380362 148704095 481698070 43305627 76864045 372823092 980152955 266574311 54875540 210312460 505648619 557714070 263287147 514408732 158325541 12278726 144249039 644842488 644511475 246745245 807500743 490634191 441395126 474005418 472317749 573471107 939820267 323576885 388587060 384874565 908106241 529417294 710422201 661832354 580176209 17290832 166189559 105380878 43776665 826446214 698222491 953811121 142516680 618251515 231223503 960204758 941164620 588885897 69193432 741655644 616792108 545677961 303400253 613671912 122227331 937084084 737460416 718178624 916430868 871715788 824120471 173374680 50238727 441635408 861633172 324528923 267756528 538484046 700436438 82551018 90309903 456593229 132157977 50138992 736417719 357895552 828125298 183543883 399561218 357208619 578465160 346168573 831934157 460264676 657740836 776756021 577312118 325036573 604493007 110464588 495593236 772141201 13642304 849552372 324671182 523659705 510759188 679846020 410784422 707823327 824466664 772176780 462690192 461197315 545206789 811708076 91127548 223264820 307400156 640364400 209798125 712747764 506149661 849197343 5186530 61462090 654327304 148825016 587517250 55385676 146740294 428826933 133968498 313588534 177885867 378490515 118551683 197327816 209257117 684132685 478633518 984812654 521116078 494998311 905389374 539814171 382710439 66381225 821525892 212537659 435173943 129276597 84354254 247987738 692323763 166551215 563182579 46993792 907385567 241498128 207735702 718612530 475660916 848500366 33036264 924947844 41167865 426076040 180248118 213595961 369947319 940294854 274674557 558242899 965926103 237115374 610191862 525100201 3986096 931980109 752890702 937341417 772433762 742079773 577190279 138910055 195955102 158319143 165766933 71862379 848986175 527851812 309379343 270710089 268189265 862744132 479631807 245025580 338542147 639784592 691360220 909488063 242065002 332733223 180513787 338036460 336866637 501594787 448112043 803418360 910629429 782196977 23517301 128778691 351614405 433578864 573740879 260403126 802097797 491327234 815341569 579725347 4781752 92272759 57068395 258615400 640443229 7355925 658120768 61275404 560642823 223638493 130519080 46528874 444068416 875019968 360385685 897413302 785155171 989081643 843383202 918040576 198712218 999872541 388767661 166870713 984612554 425159960 701369722 582384401 295319593 851713825 361324057 268376394 2646720 660372972 770851591 776514757 260437308 937259280 453619775 125360323 864670369 237899332 504613057 829056298 351602280 315021010 937247057 936522964 347831385 155818719 373187299 41042038 971821893 939623837 422860742 995724641 156477810 874494728 857418632 480014326 702777008 697571618 453789394 444467100 884083093 719925330 721412607 767227862 14594043 430407574 449677431 213697911 16872954 797699700 946845105 317693026 817454640 809912952 141308923 946802656 835856804 754776217 802563137 963036507 151264841 909439156 903332704 806078793 259240083 190388001 540661877 377493935 285812853 81228649 883945738 711331864 999083097 347485960 210836586 281431788 27952684 79656371 665093187 948940742 730580009 636167311 373498892 867234730 523658281 345759756 24974113 830466680 511799676 16369540 480477509 306410611 962203478 641325367 130195911 306166348 718269540 907328033 37969514 872637876 134235551 638803297 349089311 742938402 820208220 31797858 726008392 774006753 429609687 826488267 910639976 325733745 235720430 657811027 66906526 71987702 888564110 671753901 466818076 362739056 412355900 159595372 32036871 894516197 317239445 267068728 51773432 353141343 934668056 558496075 94854326 533133073 207612575 635903752 316394910 494106064 769068043 654907117 376858314 392588885 42982296 331883583 499604320 493185430 699101810 329573669 309602786 959440110 121507685 352862450 470368419 133850619 897208786 687020942 226221052 260340719 987111393 13266549 281912761 689244686 558528506 540973673 718899989 78084761 620599551 202837899 443611946 159776271 143972231 206824760 955672854 134581282 261301525 681255437 694037668 805456135 581318766 752482938 688813047 840065815 419707042 202456498 406325350 658214053 742456112 806510561 346966748 264594998 731241540 67907885 985023536 189266818 737090291 994868360 94541018 46865270 48269665 793393792 108087229 900406472 595535452 684653949 401258503 909784426 192385924 618686652 410705704 823265435 218762499 227421633 818800554 913379649 303525339 831164051 929946772 287475873 163225688 137455304 515173605 233198681 721625524 912692562 378264539 779518202 119873022 795718069 648472108 894665373 633389695 391789764 695299135 616862672 472392636 80794464 591253504 62246583 684343356 382280529 629933464 6820148 728108043 958800991 808971518 746616952 582208580 697915118 261865214 105470146 265036799 201872292 807467294 551576735 909938669 583927687 320543399 947823614 78335351 65498504 79304142 951646249 824734542 243962431 131905878 343899180 348207070 449580335 841937028 36740327 672715599 765977823 661159688 390632197 580058466 827315141 291654460 870710672 846898436 423382059 35972337 617815217 913933 758283424 655774058 181427244 551755905 518433569 224158746 150291692 521852539 482009827 331391968 639052895 967519247 990752228 996153186 358648699 346701452 79794546 901144223 677820497 545712502 92964361 112333186 158201876 811022604 624176868 864441017 291478007 720280936 187132640 983710241 38620118 102894366 536246412 656825657 62723318 185051183 945219498 63106224 80828791 189918637 73727860 573537976 540240254 209771100 290019863 60505694 423774159 445315897 401855913 72175861 539943480 556775543 28635049 209341568 711434316 294824940 3950206 608154679 88115856 419757066 362027937 843764047 839458860 250186196 970861047 69989401 504953076 404013435 603606460 289627541 557649488 414882936 160609792 76940041 410849047 343445139 500425120 393104159 76065667 486087624 534132610 70647810 333796430 6208729 493197287 259704065 929305851 135899960 716598483 100201066 819597033 740237315 877552518 637408944 927438521 467010265 943180737 132166795 295161705 875772706 464666285 489158521 328261923 724825831 32491069 245826676 205595971 41857728 795890529 764931659 432331496 610508210 967990490 793077691 862516059 43297951 165530153 971561682 369521460 876291412 889393451 699009220 350902417 746130800 706230646 656928846 601131592 773328792 155127628 480721949 988399117 71818423 784861115 238705072 674344841 414334545 875379836 830108262 8850037 88251860 50495765 288831630 719261238 352294765 410174162 572787718 830055663 347379805 495752369 66812628 912153510 169503414 857285571 489964572 239992730 151889565 611427445 281594736 763351492 277691961 493520279 155561881 137804617 320094094 708286974 291197949 229615317 956370198 630897550 191940680 637545429 496620741 516893963 46514190 198816359 923120203 540749860 965721812 387557790 134540076 231682242 228593028 783367200 594535155 917989095 946271207 348873594 331070537 3274048 239224525 859795085 475771594 980340238 841419515 133327865 509078953 585582499 522875446 231167990 273699454 852013557 482139534 733459838 30399811 136903114 489565914 666883585 290804098 177732890 958275657 959665246 401643751 535860009 645627746 686733307 676040576 447806628 718443185 784686929 954579230 44751476 235747337 617127789 183884419 581805228 112044566 927999226 441180426 391636868 767492376 612134813 282344755 14111521 883451273 498552258 566821509 849209706 720873610 815826968 682466305 601437417 908192867 551752722 124209250 252444406 882458168 5340549 740402229 509744267 948682334 298252815 107327148 683982821 973559164 338744226 604389847 134407690 109718882 648601250 567900546 959545595 988084529 145238190 992448482 392884753 512804275 664984192 304601312 982893589 77208317 289845334 484852577 847273529 182664298 394067699 453145618 563517689 694987340 587463959 844176403 637298931 627205643 33771669 781096931 233089799 273356494 36469656 754324912 666755159 549935241 391049265 629336481 714347606 435136068 594610912 181050333 596815858 230136804 805861995 813898476 159936563 959667979 24235999 998046585 694984450 413376823 43739295 820419187 236955934 575741414 753233108 95738543 330597867 845818840 182065049 405170506 375770201 175376134 260141576 860832896 557410415 606070164 303536242 485478700 969798125 177536351 925071511 35375454 328901349 561098694 272583315 292347194 957788110 798581753 78985706 519255627 925867378 867227823 66403508 376114330 564933058 747253993 854013685 331454945 509391132 694849816 240499337 801925329 359163390 694007266 132122533 763175784 164829894 787436635 568012066 876823961 244715221 66411882 300050240 285442275 426260665 267553533 946664861 291949475 897301199 760562334 98755216 160869502 240655963 488807316 694809424 289156450 643247126 601055957 974418715 934977763 456307878 135050859 213113509 876502213 460173569 981364161 591355074 214773900 549036648 834265838 692994525 71286521 565234563 858007553 311939301 209567526 231439184 464833365 655081442 398563099 341829516 864548861 559276772 863875032 722393431 531954704 771529338 167356894 173286903 772212763 215301995 881468984 660812920 766216653 653729903 253451767 218657057 867307320 690193934 548060384 620760204 576507484 16636454 984637806 432619254 191902039 547079506 335254565 491139211 388265138 721892033 720567140 855022641 285658387 533607733 311744135 260504140 450455629 448067608 270798724 608375223 84206129 404113048 874358126 62362438 933212037 240593786 166983539 35607020 263451816 585525705 527390739 653201727 387602607 461019889 673967318 388920912 332151630 625102372 692912152 668690945 131336256 437591764 358739696 217664933 244128265 880904116 313757998 34913560 137721244 664216301 754878059 221202859 101685971 203259141 924070167 155775595 154684020 881455871 624926415 492961011 955170452 741794069 845832497 911740616 280436369 69924411 794836136 948776651 196327765 230183997 464274993 737117190 420442157 313324806 880749162 168972053 79196912 546251995 879941654 531699378 238712928 202317828 790358701 593674024 431919600 460365305 90885836 539260328 220415624 230657193 360725920 2316123 347474311 307093315 108595297 18113767 508519704 656681119 354909324 144531730 51801448 741370081 251208216 561920925 314838514 455685638 435384809 244178586 349760382 506417869 936565654 86397899 813272571 121312471 807794758 770628718 627484155 268841086 132445025 297529853 512850667 604842925 659924294 475189620 266142758 642970781 624954757 93544418 751035830 122534519 994106577 875519775 716888604 644030904 811178672 245847172 583226906 861765636 456013526 56653394 803652384 521730945 816846066 872992304 463065982 244480017 741054694 226015259 858151191 690548048 554537328 797428462 683711466 866020757 824612971 166042780 130683287 198445165 309872711 158539639 150349900 701268738 564223973 268910350 302399477 552946841 954286904 465163175 102931212 244890754 625999162 67010565 472749505 118956873 23944654 611025161 697266861 150965709 16449 246752805 564973203 67838323 903797599 245727826 302938425 148676528 867862692 537429199 157730853 408490244 859659967 312674511 461330639 269761808 135405622 64966422 135105067 6122820 345873057 257084358 624962838 176356746 391277971 807975128 760397104 712131107 667176387 741905632 380917219 613083997 535571783 148399732 170243953 397249258 959482464 467919560 250793661 463116726 468456565 501387905 741612908 499129893 633103772 46732421 816824919 631796308 127530135 762348500 718263396 98161995 57833059 106526003 162994920 794465700 914372683 965384115 351573676 678138367 201184592 962034543 106782490 32418385 121542625 560756182 190200920 596265542 705152507 291378692 87912953 379109056 16328000 910855018 335869932 220976943 194213352 484445881 444662015 258115934 921719626 125871130 987274998 623283273 65280234 803859381 912279666 597266136 95461404 344542420 809407466 945445977 257098440 297978697 397858065 638956936 750694147 136924059 664478172 960911223 233911818 335054421 899660253 212531854 441651396 216058945 408143931 989738390 339503916 666878560 238398987 153152814 128423447 405671251 235330009 684589239 790600318 193916831 988366250 640327761 581266102 882320076 332014 785868181 715385971 870297981 141046673 154938620 936625477 518185614 277098909 519297288 34588868 848958611 439968572 839998261 429126296 70370590 163965950 337200780 877635493 833099354 606393349 837743750 620291908 276676720 872301115 815522605 614598483 124058864 234480545 182854977 713948287 4099658 639354427 409963538 813169123 68829303 596816121 282486844 199200341 996944104 4215960 216151949 991529394 147216194 317986580 931587794 30776483 401623529 889824439 356353180 515644594 814940251 155860222 34781574 405954497 353320208 957444009 168168435 979822333 556324260 697228031 618263378 148198873 150172506 857936946 147717491 828473601 548374556 13465750 199167151 276767192 417759694 608595216 511960623 287365699 173037044 170840411 392450797 244514377 34521522 819338685 455129207 81740684 147154761 952689861 187673901 146384439 340987994 86899233 66635576 90014806 338809960 913803469 701836402 129240388 352205072 527394779 811219140 208836308 861827146 345666153 139216138 652492660 972703296 740576773 767068231 156390131 724299310 355433221 903844483 768495245 250233240 1689035 99385388 248076240 643699797 46608166 964635669 536510147 467940517 504939104 520781262 62343825 271630962 247140912 995028226 133596888 102736133 726167385 990923908 259560331 30297595 113076199 717579407 515990616 719692092 91675556 100692846 960595431 516005841 796276427 93784192 125057328 258520098 763152069 940056140 828555216 878987856 608584092 416945828 484567665 925465955 188742665 386803972 358483574 367046063 265723585 402080036 631580269 497053747 208249436 919120607 542372984 691619773 69169613 551357529 37939524 455967492 353835700 855633907 29320677 768409804 254145227 666966792 291973248 470663858 674020564 96854752 119913838 515289305 628483135 866961092 945970863 186903535 934507661 270342024 178634750 901795822 597242994 185830902 231254312 987367070 811354965 203124144 567367115 162056236 425445632 285292736 85484884 374318834 455103 916179037 756767551 114112718 70463467 399331182 580013114 314224776 29670597 293879771 216586375 774012972 509109541 246486818 310725424 231677468 204064532 811797697 757001012 829379092 604030484 354319224 237096904 129492982 98441719 499065930 539909099 871436298 297999740 618841753 961254154 519529836 54444960 513342808 527854996 937708963 202659299 13628607 80244665 588901798 226191549 270889141 32629327 353965670 218886426 29300426 140103917 756928190 437020902 171471666 502253750 843139241 713419454 711005218 50826477 899857423 715468836 356894970 865832947 613133803 457985494 441762988 252249256 475930632 640082091 343014871 126123188 188090686 607114506 2193497 741935724 96761754 272076676 149051116 506448821 299168758 375419764 791383412 543622449 150157814 389049919 101773031 940578684 681916237 142316120 91667323 487050499 728347178 402657142 202108096 712040070 689984612 913808807 226458078 630497953 433008659 564217191 247084924 882215835 41547192 666525375 997855886 58914381 763815251 361096973 747223065 174882802 60907148 592423200 86761387 232114363 685626141 843108959 35265386 867535585 78866358 146864850 726192555 528173534 268346983 292409445 279937230 969566554 391213192 280177107 644695831 39083695 230257617 67202730 510423258 737429031 626414658 117377352 620362104 881875775 357260747 80796287 653026332 517810535 651346498 320269862 422471643 881229217 619862438 324267797 105503537 6896329 889967725 475275815 391519958 779371575 196695486 473361195 919146310 193122998 119582447 608851465 37621399 133206165 496264669 625092061 973514662 385638351 795939778 99225610 321231211 174744459 279687506 172249718 621900091 726861614 92833155 223823168 211628920 227620499 560237773 136014032 557084360 374080498 870794035 706251259 724953169 538025817 918186640 91431852 128253811 198714115 621379287 849697622 103953169 334238550 319056928 681680743 902136380 120174579 640261478 566233054 801879879 40863244 702053993 652924486 163320000 592880155 894334923 434016965 802475332 716112544 562514157 566899863 933286367 253772468 747987592 230737896 459385839 295295310 983058045 890915398 218510381 274810718 830410678 576220657 942647198 767982237 727781795 124450037 976287047 48532031 268704994 754951519 585579856 735948356 870387407 475859615 889475165 511027929 806401572 211504221 175174113 153125894 687244341 573088653 536337502 173909824 127749076 976815332 466738894 352043710 132647467 813450558 861709065 838119832 32900098 783272572 259653671 874166963 217036234 472109260 263696896 874684289 626779083 651614452 453548722 840759992 975219814 319730037 214278715 403214218 797624860 26425558 604148035 821389167 107978221 818932620 272284337 572748928 158934520 520106088 791251152 883616647 640034374 483846322 728765225 264300292 210401831 457186047 544105761 733854563 13811972 937424209 629486679 676726920 459042607 64068469 944025791 998815199 235207357 486475228 766029192 850031037 373277073 28375058 475512832 299950069 601465048 260655524 200397003 389837937 974670339 836006781 11847630 272625893 997465215 28967307 201881984 559557490 977694432 674806737 407468441 673043515 475549135 329661235 694799330 31955966 471002113 913599160 353243754 891357677 774172989 92697813 561009653 983785895 937375549 640564020 865899602 373427578 762339109 885580679 240155550 625250347 294455533 811700375 410240358 134073180 334121884 391711083 994311699 81207110 440399852 614868316 756725336 846725542 879379459 401380116 104400587 945658304 218557230 535381931 575356360 630510794 417359667 349286782 530034844 124136460 16886831 296094294 305872753 849715822 222006034 395324631 655956329 259732938 121473170 78155908 767544320 576333670 443929427 474394289 47259298 302168559 202465201 77773822 666621101 685302927 590630626 99471204 475172906 261933416 589686003 696453468 217769454 102058734 243955000 891928666 19226649 439054622 43804207 725855292 647029558 144788968 36122708 802781612 26582276 986025010 294107345 165577205 798806234 896889475 122005798 770039310 714034073 955231536 29860146 28448111 907404988 26003234 272952761 307540571 170172047 994150205 527958023 166129532 277787331 581902354 992831993 658965580 150528082 252836225 961503839 438916967 869092283 207726618 44541594 891421683 495677421 256515529 572546206 996926434 252613286 373389295 306391798 104233775 302190307 517235962 463890782 800663496 271993549 528890775 510183758 630092285 307288834 957470684 215631164 462742487 316398397 678689099 114352504 644327863 666461019 40881463 383192171 622472275 830810790 250153565 512252228 279454327 254003354 86904530 92915513 16798672 263364562 676406265 244531048 34000984 357575411 584940588 855635229 628234585 79037368 326585210 3505042 233516280 329801972 819311408 75719117 617665310 985839320 151429805 676817383 35801601 848849353 215104934 498518140 990050178 472052513 957210078 340866668 125950048 122599812 522942718 561265519 570158022 255814680 208966809 613362923 812952255 262713199 302418633 844504184 157146321 133843507 831267233 992278005 252702668 265413167 686297042 168432456 909284425 987082554 808184003 753892970 294823563 99304669 359326349 116086339 179472 787940798 510499905 703323144 718106161 490411666 537304471 558618790 466469569 687162220 795806691 801959172 844844325 498823004 912532291 86067265 875445972 201705782 177521477 207971985 607482459 197046358 606379579 935139755 169120583 245217636 211408358 89979983 291832667 548214538 79349462 861591614 648310689 947768828 883769190 155161376 905435941 845339387 893733699 528789581 771499152 721389177 294448069 89490594 156309701 658363598 119007415 210827167 102165765 927343533 940457230 320812166 677077128 362933821 956909906 485325061 736940460 26278725 240697729 389948071 530482601 741712996 115479564 647745317 238719797 497030631 656544356 965496481 217090721 121099829 784609170 282665995 702628486 318872793 785998835 116945946 849028471 571168538 412819075 975384452 233052284 913780045 66643194 999417750 53055492 117490216 486703058 952538390 552047737 815473313 639266844 598631763 30983406 217418051 898186066 571444373 502676810 94212756 925845700 637231819 173539552 985041048 747547271 278230685 45761636 462452637 495527266 919370692 647408097 810764935 826870841 229367522 551833973 812197264 133206659 940052799 865676505 563948723 186458864 11552677 238801793 898289602 363731803 792548937 489528581 642115183 725073175 563303832 70657243 910704071 745417492 816104997 311924153 72525283 611834430 678772193 563711995 112083518 196139491 897895740 49939528 951705704 102793122 50851167 209438596 209441998 915517973 188187625 999697617 108118958 688643536 426834172 310669443 145429660 465924267 714476443 12845538 703605754 736591231 856195534 46103916 121843582 444552848 878165885 161211181 309422744 592348618 404035783 579435832 243778388 183998236 5475054 426401357 545807260 516449945 570446429 343108089 996820055 373050132 741090958 756040056 105056249 417027744 813986005 598839129 934948863 62963387 357285736 500903357 279105590 686924693 322165961 242522782 10071369 324446577 793061196 471385120 416228139 490311732 125383967 467712748 697480739 871977947 642789173 960766810 247746484 204839526 708291204 271569009 862712835 210092861 654270901 680889616 12057704 349300399 958817410 758444599 816364831 356132248 806328063 986292218 741178113 598196707 420288285 73772633 190901969 246622940 622052655 432901022 151929580 398066363 999302196 57042723 93980771 660052784 108589222 323973349 595949924 31338014 227669178 222533632 608369878 735487261 152410514 835584881 283104493 887436715 153640713 217021543 754251434 116359733 849888688 592775605 161023034 12723387 90294330 383823141 45794191 31548366 960195074 410588858 968861953 795974635 799244623 818793324 874969041 335352919 643182894 501186028 225526156 374980621 83328821 524260361 747675771 719093432 402835450 860575894 538464125 99033611 564529874 937411235 535958380 247159764 141551711 910669073 456557926 973134072 41307427 884601489 865289979 482274413 935568699 221436995 381719173 412927433 449878981 252690689 25892102 173581876 271034572 582328952 442762828 822041628 698631334 186285477 458581413 773003721 810504595 367021520 465775080 339461502 724241086 61945293 63573701 454153682 938746359 764829509 215540590 226691391 954237856 715017271 410675106 477910419 61094943 557876030 91376369 815659344 174834422 297684149 118551063 283189641 597429963 244847929 755488792 126766621 598044889 299306636 398033927 208501781 349986641 731533505 290099148 585098096 146949079 448272302 482615975 413583731 542803475 567571427 552820291 311366103 177543 811189913 604979404 313636753 528186330 585838213 445983507 542643474 287318168 179974352 8525788 723314863 986570907 577533777 117067984 498167029 881707178 140636145 7879014 27120103 443480037 607384591 123588268 849542932 304006494 223467754 572214782 818592720 477798604 556642879 526772255 84182546 313618615 847400731 104312385 828960951 113848756 866710989 940484848 20557592 888983490 121862140 664886199 49860649 634551645 10441746 535417233 954028022 590069263 817780971 611548732 502513847 152709183 286844669 372741123 499729262 470404254 11624712 275935328 954581358 593871574 83757603 810578284 15658497 937089635 817289048 195882578 703839013 30150400 148755659 662743052 96520365 867251585 951742687 647837787 734325511 358032127 618017795 809140267 107917885 760430560 848108984 434709148 38464783 457311307 947613220 362361279 551617702 743872134 57918773 573502438 38199323 575934235 592644452 53934159 974102025 60397799 484356582 618859243 684703472 105562982 271107770 932737393 242171438 462529605 104614546 966629212 809926725 289829409 40822821 863833375 846620614 14773129 211303493 826283661 882088058 162601819 394915595 197410875 688450385 11763659 2213545 51222843 465833865 583141014 210481430 52936308 623431361 438803787 99660641 294470426 637004971 945050820 397074862 169663414 880827374 616482773 258009577 437835858 354885626 947595688 115371785 259517739 559468513 479066136 690487799 381677771 724690043 17948514 135571912 23462266 121945744 871956255 869947929 90508629 349007138 853183911 453188501 217111323 606986171 692764551 967404420 271930181 352952262 890243053 865358462 946547304 797826552 468606901 430504055 825173405 229508720 826194585 642260729 62922946 766512548 997491498 123321936 862936752 819074007 749356198 699761270 449295238 26111760 946117802 182303839 67082828 942842697 626099616 547289240 855081442 609997729 352284087 342699707 258010367 100455052 616620454 468826018 245522053 91414687 209124035 8447772 132768629 104992817 331986944 299311414 264645980 454168846 407076569 391054445 399737165 178300803 347332511 211522871 1362062 795066596 783876084 817366574 461822489 246165965 678038752 852398772 794582727 482652897 292916802 985033502 192727052 187365705 339165628 254312836 34851504 52270432 314021542 396128641 391562085 428384626 85143615 544959277 234709182 210684084 503657960 21001079 578950729 429499188 993484275 8850287 542942364 890564268 667384634 488597108 622953291 545590476 201590285 767785665 463310339 693997433 192822377 751397903 324407817 321192988 86787276 537572889 851001238 895448708 951076710 48766448 817686020 787643617 226881246 661365101 145577026 474802334 231137462 168145210 551979166 735199563 894212303 755632036 125793607 46776626 750799761 294702989 881415647 324086862 622791384 217890438 184604560 140237991 485201356 995162461 545573257 746778993 597338072 360150844 206907141 905031412 580448490 67128489 286512048 917162342 679286106 374206879 142774219 298551302 10324460 856071563 339766306 447903130 766896831 212343740 141051598 61320629 54199127 37650991 336063455 480754417 805523012 938759854 652051587 75301106 9730492 577630982 284458827 573747834 973903737 643754623 959521764 928908716 224287954 220052010 431614462 525456506 4541359 150122115 685166466 501013627 491478788 202020058 792736880 199263541 989774184 944762417 477317462 413893169 714297982 33460596 873143782 886263988 666887407 473882227 5178750 783792726 975008970 465859085 224723745 118899899 146746119 72746892 116893074 190864674 828551138 999777131 531987416 552369247 150404461 590023672 156772933 452634150 614495241 417461881 575913045 97978313 309581596 707674132 216701996 345267513 68573064 836112353 530310273 305683841 969297198 71868425 893085380 238699309 853627711 61498014 354755053 728740306 130130623 725326837 595210588 178142624 418767099 441771312 68127374 102276974 908677656 160932066 237979090 394717503 757818146 606527293 339264017 219712424 5049875 591238706 726283685 244150304 862718777 771547505 616504118 148809822 764405191 18835244 345871183 239458766 145954187 955877866 260644927 35566367 527942064 553176280 530387461 986769506 535748869 198872814 48883674 506102262 276631659 84559218 184943021 170157613 716841307 15604195 715046535 859878341 490927262 32165897 918199821 458769938 161592211 655816341 894573949 375839036 523007678 977683379 225189450 42788277 52030968 125891989 988832312 831901301 812219909 840561003 655420845 593278542 763271813 284448363 622595469 358155962 706233125 943801771 753383933 902327244 373185602 538499673 672503806 865116839 360818661 86615376 520273001 200078739 934285694 902021746 448443406 848657560 458050945 408218053 986263393 441996667 25170535 597019126 773890708 863745466 36531067 826076056 23794606 460765302 931408996 927712941 152767623 194146836 516727659 955214687 730926049 334028399 608307822 476507927 862666533 239843307 4015157 980785651 526221638 682018948 901273746 787370225 435274887 39764569 108587774 16019022 128813262 944656858 17988738 621571722 789295487 825130736 303181437 651623823 242595142 848109311 986741878 876834759 901644382 319662755 833167303 726091582 613544566 860172233 469773698 131861756 541545031 394933538 272507119 748852222 373326318 780621159 267996860 862940971 512191658 126843500 384239467 342291394 111233123 50081798 908996849 348375960 324792366 327400089 713689034 915025367 893897426 556823322 905237794 203198241 561943362 689228239 949689016 16647673 415528487 802464323 708076087 634319401 841443026 930392327 10870 277859217 865093410 270151490 9671405 830134815 140547616 441332505 434225847 279047262 110921428 762571680 73863764 878988604 158940312 603249583 97099531 297943439 675912046 606233331 168611695 116748053 908498187 318250486 867184172 275621472 608990308 972175508 53260109 485262628 224472681 282818928 551539249 429468666 956000810 392835433 729251103 165328860 577452320 432020049 970669331 794731083 794566489 248068493 20307252 711204674 106305638 231514144 970731500 348570155 419146045 556561026 119787571 405303072 531248925 20406784 677124475 644787010 100578611 612364726 28611947 322961041 312676023 212923923 853920057 104929771 7440245 867909629 499778260 886369552 297335621 857535190 537950309 217012626 432072639 892067823 864095034 55072493 256038982 182131587 848013816 86198421 488222053 727272716 551377229 242348957 1719477 471141009 881861001 930814181 736117353 104337667 245526265 476037601 669147772 573520799 936546092 751176470 771161394 131885327 452259990 185337344 205779333 67634894 445418971 429711285 650794021 608998892 760324937 947570066 627223255 453098654 814913874 620234522 415937093 998250974 360074869 165458878 56071672 843525106 699001764 972520353 886877426 871859398 212960113 57690037 210075100 105021389 484509620 173559516 683282766 145019022 228375923 474918401 195985265 129977468 553434456 793287871 248271759 489494933 124376970 82862468 807751752 273229749 772501382 717511896 895501373 624608357 545922658 520592363 371539876 577582427 447738733 103815232 912407540 567416541 794928016 36357053 974314397 475032596 889126961 4400980 157146754 989714632 279797923 333494906 467763637 89367660 121186400 271929286 589213138 397663955 799734055 454362209 16690703 607306372 798945411 183071610 838346428 850057674 227975481 218663352 525733728 202320696 206244500 846415057 269010731 461895523 182225733 759105536 789246709 767720431 999101850 165715271 277177514 536641624 767801999 320598505 16265961 198381300 174487432 218406011 997022136 89466702 288360809 263856389 940505884 715071390 354334160 980243570 453917700 65619055 186833946 770609884 133093022 699216516 149258826 640039824 275768009 260700689 958336600 782782412 329761919 743371399 922822835 855623089 128323842 596736529 466824599 583309073 931692959 515219392 324881261 89940035 956530106 842865444 718049637 343355406 443744282 750583503 993015940 318583503 878745262 814738267 521057747 875319697 568639697 955406700 400662046 116968300 479105360 414729490 325070499 574343988 679898367 391770519 479465055 5022234 509381220 33306645 889375071 951824103 641929958 300464169 883677565 530601968 817691076 863839291 752735876 700556803 945896169 830131741 288329850 126446478 617261418 369418911 560602679 751924457 236233029 54346370 72678643 419221751 938864824 519419488 934972389 88051484 742420831 798655707 276109106 841194134 533965015 507201178 61644966 613450725 106079068 253294937 449506221 759747720 865204083 827252992 6736079 507218369 125588588 586931573 873577965 277106611 577706036 866184893 614331937 894247364 512559492 629664686 320584548 555884960 809538658 810117897 507736511 855829062 150663697 32143223 717558336 611490063 741792025 776946891 117579139 16231835 682799144 745381777 564023395 597795582 357811894 742246174 582419500 901946649 255600905 457521037 21162397 261654355 313881469 248646545 693982563 804608532 752428227 149207277 195576880 298592055 748735123 712297324 887614972 839306689 68806196 627266673 272471629 824992228 395248811 190048182 539474237 554893427 856843407 201549615 54965248 307919047 795787242 199544325 434739032 537749997 192816277 6869644 616925523 265178927 358149996 73815230 630621089 950139206 345147787 601328403 146987652 487368297 493706494 543918020 689987626 877466416 598756428 313024246 296318480 864332608 922338678 726229978 341128081 478733502 857399583 924270588 806597555 806498471 512482318 232671516 360491903 737402091 126707137 964171822 16392534 513337166 432393088 887029417 388480445 273724683 503138186 992511529 138486464 767134118 463529462 209444489 331115216 46422224 875786798 198046574 45142099 297964398 876288119 475556270 219119609 818429340 383616802 839310332 108202173 12117438 775363842 634794266 888439212 386381225 55497674 862121993 371742555 15134053 214396280 913178679 820870402 932312729 434556455 236329456 501570372 388407751 290776384 31906222 668757249 218116145 977583136 638955796 76029027 28558320 320096399 379164125 243975707 294432011 630108129 185523351 705477124 164405056 384192879 965077313 182248527 896963034 197802945 180845167 935547280 72244321 183717985 982338105 608223562 230176641 307549224 437715906 455160144 796169148 327744272 177340043 364607570 493012179 774710961 589236210 150504078 58558821 467877159 744651472 852540313 530197777 327203428 28720984 269148186 632697199 108278454 372031548 62711446 904920473 526322262 775493854 218231461 469891464 886578343 505927441 630435057 654110817 168618110 140245243 131043186 537124131 474766912 203188596 88802580 144799050 32435677 51588094 119326024 146921099 629556779 754457413 537287760 378658797 24959816 474660425 360619653 15885040 818569975 160662147 827523659 439106395 448073677 444419887 704034495 133619361 382564381 425903020 904898723 199658937 286586717 882048017 624014106 995087070 50753195 285920613 159247877 243469376 813931349 377743622 69154757 368955427 851341901 675574057 586967142 546000685 610722577 233350584 277524074 3504713 130941990 361539542 889176483 271773653 267313497 157758270 860398868 181865103 38428023 287014393 809950144 378743623 464257798 537585426 482010220 322908384 152933747 957205753 748710304 259384246 958412413 624540892 366389287 987902512 633744642 277727346 461682979 970914522 910077631 934815263 45063147 967089047 391793706 775760083 841079783 470032604 46191355 40717466 254579487 278962953 489378446 393942601 279662794 40653233 603909194 479603600 593138489 417044858 608179526 69643508 939172712 562199990 428094608 141056179 742560633 949994800 104404629 31932602 174971948 246592452 901068159 335911110 271978679 897590550 66200934 327191194 63781531 234403878 600061839 277116622 216213254 980796590 852717389 454662323 889574712 525994701 519153198 131242762 753464963 579304667 9090194 789262296 109515736 75895297 806867666 683238419 278134407 22323576 916452315 876908560 965811663 477376028 256391313 773167031 947984832 455320376 323812298 964116100 267688443 122341278 950494004 789927602 513393109 392483165 308054750 978162044 884303455 183991667 347054493 440110764 139690250 514416484 9037420 280050702 784945658 87350615 605415007 327554895 889846689 878350670 104695652 321670328 30687797 223526576 994683061 867369511 390573011 985454123 650918330 150736662 78172437 354744828 666029556 569063871 903924386 67214280 988508365 189759839 573928826 235469450 642861789 132149497 4885292 581095865 400677677 70953607 227062059 294898249 352240523 921940808 885378971 155997983 135024029 821509170 2053248 125889514 960641323 415391806 592090961 907723576 487168678 861032049 913023771 373322349 374891293 267433797 790212081 374431966 242340231 942876488 665538764 863919550 197132802 64556102 525680122 126070161 266403652 711173945 908863397 654361671 239061046 679937953 410670955 221408992 388880629 656907769 323647737 370412241 78522046 355629538 388643257 160658294 670386976 173005930 925546490 232766718 564835600 370050794 428359007 410930268 433350488 230795769 206955478 560860875 506893506 622455359 536317971 985094254 507501401 806387162 84403821 607303000 540318914 205646130 107405574 190719835 471449060 175890672 354946711 274886061 61654298 407260455 3701279 378271241 996368852 128055370 932281294 643486619 504392468 950186887 427281873 664906851 396500438 505692134 191040322 685557645 11110478 176539344 870684155 878829432 33557751 667294485 49080228 470501808 160064273 949753561 974056055 385611319 423186789 943103660 124224934 445716591 689652888 817204669 855266498 684539290 968749509 233469484 954047531 89606783 485105778 590114113 343444490 112826493 118385500 228417557 214952318 150173231 824911158 677666038 464678266 951216645 729700074 407823942 57991567 591062192 256471355 450795745 587870863 521526091 38769378 411937541 900971536 289152592 818524510 658513347 995204381 275042390 150507488 172783110 896907925 604707837 234194988 136152277 388808345 78431315 100889793 829400230 165658139 123935679 546962997 840357175 474755880 737232960 887436003 855383903 661967413 106071007 237836361 483021231 341420456 658451311 351927834 367749383 748341834 871880876 311238828 644493825 23586030 59748021 80141753 950867881 297750532 307400859 343782221 337842282 166702858 339553172 864844345 469644597 162632582 376682229 325650779 168158033 500041981 238752233 613760954 440796865 767700256 125749353 90739580 834931603 239787215 551076954 927473117 875629552 271301105 675926497 775512394 721944770 576451808 273007882 351826476 137104131 802264391 911392398 710052860 175817729 151233117 174721633 336321041 81838713 322359233 925502442 86237846 712153903 509491039 215825686 39939996 316596149 385613088 188663009 192559325 241136230 284014115 384525970 59270820 394865367 253408298 285438843 454525203 258802612 188149382 72556675 40111500 528616760 547480900 634257538 193755304 26091820 77005581 779338278 901796402 255431521 248183319 120898749 438432699 733514431 461759931 594498713 68671860 30078802 25888093 258185945 993843630 683785496 94163081 848881604 53180146 585213676 569362638 218709884 857470670 872730981 832922504 800075715 970706792 342550343 88302200 494823275 167294791 36085814 802641884 348589478 790649863 622103931 51702451 468715047 512586831 225195500 362461943 817024896 23061559 939566686 318036143 711502575 949738212 238979969 620303547 274171612 774249759 60851366 117942082 402405234 31926615 802467878 988092674 883261532 589752706 147091827 312090338 60979081 291700223 254964276 528587989 905813290 929756786 853643250 51350511 179577148 703716644 936952444 333297082 22468067 28600877 450633627 804813016 665870171 719453088 349669737 797197336 89817534 929731172 13084004 142866145 509165229 392892847 697037878 980918455 54991166 141250011 205729169 15833160 80556935 69324559 675373787 238559180 502502547 395416128 750801570 439292055 78118226 591047716 217581855 325974580 32470632 106615054 483312632 741896712 877829718 734909300 208852957 490736149 905608766 813772387 641472184 458664772 356120433 350535980 291045670 297620224 418105749 12050781 936888115 270361842 364083056 919789824 319196731 637669114 616634890 445662090 150732709 938958127 390852878 878584827 465106695 254235635 922378347 889774797 521555968 162334033 249045552 801287035 484281928 30367921 887470741 718084994 501593362 574567501 66037285 852976427 265472939 428424447 693018592 286650464 699528197 573937552 986471152 284809344 15974392 137436428 542019313 883360068 520477362 472591845 437775166 357375800 150874858 215733966 55630826 63769226 38267834 871003611 33884189 237364562 349393218 468653479 910271652 862706252 840198151 781484362 105839023 308517206 622799001 272713301 277551318 500483924 719194503 245450921 316395441 47344282 873076530 151833502 8890130 776941047 589554541 194591995 462761636 679811852 158832878 327664051 803314009 714791269 587144688 621308867 991228960 57069076 768221086 923213532 835805271 283090423 989431883 863835762 369581226 878843115 697389229 370521874 841932334 715237252 705123928 928786992 242738931 284726170 448779603 100519297 942140843 521300459 414967081 590491556 364690325 306790367 341149056 313338352 596140762 950077652 882431062 331971461 155533986 461929551 26302756 129037734 586091443 925983399 214057747 233698777 844269543 69750802 894547716 826630480 476356309 632012159 713379232 595960493 119752600 459920324 505235397 393628925 820216575 751742625 182873859 386890778 607571945 737127876 703005465 295370794 923728527 715930340 247773573 932007977 812628442 725205361 726610766 41952094 297055902 374468802 90510119 890990306 697186014 539836985 64248465 938308353 33354237 151422447 446628025 81638482 389891079 388843808 455392212 973510719 625547894 675485159 898810856 510310936 387827691 305675067 230227482 874624889 19569770 519624952 408847664 191976619 83406903 111419889 453347111 307848180 763892428 695573203 943699736 392230786 720322756 262843595 820968283 110986326 859471693 440720908 959902597 565863029 566319405 582765686 498240146 520590453 118616525 672233049 862798808 402217444 33114701 59590453 89904260 365598763 947834102 162768530 81244569 795938136 830735554 376318098 287053177 110037154 672418273 509438670 898762056 803827945 654235548 109853235 314158843 203125798 9809248 357234723 623799028 882320391 340120595 301365744 788724841 777062272 599561036 632049801 207163565 92228108 752615908 34225194 710452542 395098639 405691113 794348933 101557104 666931162 716385190 428605439 797798462 529175791 396008052 347148809 379291827 835395998 385578632 604965798 785343814 926633290 3811138 228111036 974593489 80151432 411578148 97790933 336387869 207269772 780058842 743533432 629838446 412005118 146471392 862597851 994038019 892594300 392624404 161697556 302447108 304597466 621939966 776962945 726049118 885206807 836415906 247578856 112640642 600928697 808492059 672722720 905226026 853310617 211948129 862962725 809300807 63980497 654291556 676749818 30393147 966404268 700461862 498632975 403325000 565889403 938962591 858976928 772491985 929023582 240603761 199269951 473233885 801783979 419354229 510498504 547448965 796747225 374785665 387094706 231705591 543827099 658862968 851349165 345538329 639472803 6635109 285834593 476930784 894099786 522926163 883700433 138795513 752431065 470170185 695491088 314695138 435677861 42803544 819702852 2304426 317172584 79987590 515024162 438247546 860639144 985147764 812132777 322990250 38749824 216597835 522539672 52348994 329745208 847137274 56611557 646132422 294419280 563580529 978495732 21798571 362335621 398007866 505218575 101373835 48029585 435948337 35009496 974112267 559172283 661130029 433677744 454844475 683004444 491627590 761252720 780455659 790121420 86681275 596075592 535039945 939419830 1324922 941822856 18056981 289060330 9336990 808616506 635944620 361313957 693848300 468985062 475657243 281749338 438857181 688090970 227653036 824851206 793536475 495216688 963024763 66372570 897862698 794959296 26313716 285926080 104899551 170019746 175995335 703380191 402181496 978349883 825176468 277306094 638342975 194358562 869612192 940931287 890877139 936942063 880769941 443470774 414550670 39084216 285417000 977876921 766277676 727962485 993365189 996384993 369979685 400070027 881749339 333735124 583796588 743100473 693330513 69615633 470739432 786267381 44264173 685621543 32547297 869501337 992503410 730847807 746585047 245206013 468635362 187599259 891120268 474873696 454607937 747111744 442945770 601986487 446131029 76349919 68926879 140560616 856252100 638130118 772726104 366075527 850672190 330615817 142829612 306226472 337540829 274623718 721616986 801147845 697658463 961934495 177958935 648090130 216924488 568880250 822646144 473365833 221469779 871142553 69774825 919992201 867464934 185445258 558331831 749320553 114042533 144642334 5958785 835354586 619218472 575016283 130209302 977562537 335376347 6880614 14752944 687540459 578623438 254579637 694067162 3152876 584665898 39109169 606320513 405624 391016794 584517524 288052915 840887577 254368109 963093753 917696274 833746462 319991592 789652001 35314070 530267892 3336047 33270646 209881859 924646736 158364845 765083702 827117028 604897254 205371016 7679942 930003838 209223947 679426534 743205363 31901829 339201672 27943743 992204119 734000 79543374 527815695 978006712 102765746 258315727 546312561 99572860 81281115 943366445 761231707 634845309 233581604 398722933 704400818 542486295 282144376 546982020 182017857 788769704 316898365 345207661 625153474 537265042 902072450 178425451 462022166 986766491 649659052 394114408 745883087 392624005 250112420 419946135 614797814 32064599 740060103 965460700 428245266 408995354 428369575 333615453 653519587 475274538 163933088 305685579 601912490 112297686 714482184 288469892 830818926 393028752 943556745 142148086 793729119 500433193 121535766 150178791 651040539 819861099 16876858 681175140 557743164 151461822 991899018 89774847 225328859 860469051 776399147 371697836 426319052 851341159 579799233 528118084 210860240 298033329 956851640 140972592 876551462 505740845 134005734 792699899 593971891 337158614 365213460 106924118 604096561 105592998 277270571 248313051 779811852 684486301 719369407 860972862 611290581 830968848 637640055 954558709 262389451 684065002 460064736 641346164 564506452 664201779 40555564 979959022 180814399 225963188 824738043 83166848 823275806 376746015 284825359 256355239 401690117 833542910 863977290 681074456 155952010 708872627 183890916 116417500 148345448 179494647 84282181 738075388 931053451 580689207 997589026 471171013 687567185 3874249 331848041 438958892 141337512 46168513 155005294 963527900 699208424 3594309 280500416 994989663 913456400 73863747 545524162 424152071 547231090 392996770 636354322 374503891 272646858 513768993 770870952 344825877 943738317 13564658 837414091 814355573 987221567 65229682 856680132 351892615 216315944 117154578 924281391 693370998 603524741 689118506 150913048 888020545 811921787 940034200 235198359 720033971 797953364 299338326 537443878 546427136 241269120 500769579 162134806 81924778 31321098 620343815 826549201 482108198 620306502 140030816 751748772 547163691 334361173 186704253 2074925 557289826 43439772 328700690 983533710 860700223 419788082 723812392 472295956 247831597 867096638 346165837 560721597 560603458 89767424 287174126 800066513 641334336 921242940 533684201 630044259 373772451 243862218 320376950 489357704 163887052 871286145 52608448 146567734 445472648 534703389 796601635 252758596 925400898 505851437 557305862 230359448 157598157 564721733 754905060 401218631 666227008 498905112 931127825 563908238 534408785 867887200 843215277 841303835 521452176 545605086 201784152 979728990 951853337 346487274 550687782 427253290 125821851 109458957 71300473 753971812 880079370 466521532 18646029 115183879 183580555 93945103 526247818 139916451 850220807 305103471 685603827 347169167 380961875 382742028 251567148 108964264 666741751 165279535 692437545 512770016 190293296 979896220 909281861 681380900 164924558 323998700 134133265 332703991 878013998 793660181 269746654 574810597 819527687 402343683 27693113 899002736 457406533 476296237 114325238 213032563 895233497 197002323 403817348 194013002 713692486 718528524 24716273 107476067 274898524 542307479 513585426 748524497 147553436 42565400 551338272 348643337 874145576 74079018 104262158 398625546 255690929 616693181 750202653 403610176 231551988 123763182 857258476 697127402 724717893 691599774 827895307 628531701 696729374 764302851 605365247 904083623 758104881 128984820 590236649 586395910 705171939 90785029 518139412 155735764 45120338 657618722 298164720 511394921 293632479 109930352 751208191 97307124 401889327 363843634 195988318 732824 211178428 741742625 306787821 512568302 199787207 284289674 449663387 533109395 443304783 64541744 973020292 866085471 964767794 214267429 142761105 672566808 660553318 41660384 853115092 466109415 323706649 456418619 683755655 224737302 22477192 846552860 929369800 198828360 217475190 734835641 449874481 965130914 859662094 194643494 58740017 985263986 39150521 676899664 31062489 925176072 76973861 49695387 245721692 515264900 150592750 506590297 500129775 794092643 769193902 111639572 101183155 172034264 240286424 693101382 244102247 990173390 227630043 882829422 516343565 576585 314913606 765262382 7572451 423993460 801600781 625973525 404133233 383838908 304746987 164134537 995251807 334866099 212593039 755848129 429530535 341813735 860592713 734623376 260128467 343776793 11167245 877520541 685881265 190769845 974262080 611978552 123505450 312717528 885434245 961654173 615730599 216459838 129714348 369399148 181303404 192015099 104350030 989126805 136763681 439055606 451077864 89572949 633960059 841408306 893910656 49596022 233766284 736251868 522421330 138578937 507423960 952376512 82079539 238673612 711899106 305628572 414968413 83556172 565121194 551565234 812587107 119311186 498295257 706050542 315840073 779235342 213217477 876596800 958282010 834634935 244300391 10923602 326845320 157555093 916806427 484190546 25662891 20200616 431967090 473248095 666815270 867855408 851217389 473555380 171538197 269394019 93409188 746479972 444456541 480298589 242175145 492525470 56369296 861189052 499928921 59174874 556699346 435617113 846865842 590880027 711665799 12095183 851506625 818406167 409378818 745027832 667245580 989091900 964462133 569906421 803600925 540197631 628356020 796268878 63891375 307679215 80484756 413455024 293221531 858412924 615350450 282034373 16748668 876512445 90503151 906101617 535996725 448252777 239596372 403036175 273353379 419566577 328281360 932703389 917768989 813922764 159938320 342173512 881437963 54283906 247167782 682146874 195149445 487008020 361428366 135338948 895199204 459037981 418388448 873893926 292403576 169882421 20191778 837354448 98905992 707005543 325304764 912270368 810589099 679144751 698001953 636265057 101490443 623749040 319888290 221365900 116521086 197213052 696985251 736070897 487681025 909831411 8201140 111466581 194687592 288969246 444531973 304863509 772303555 330289880 984710801 463977127 488828561 392947090 758778218 546388526 160842490 960054224 687602873 635946615 19102122 29361406 441795875 592858968 30890344 380728090 677076130 356865170 409130744 974652213 569690531 86584603 659380673 166384556 113421262 251913894 392418046 715329091 199235823 75419660 764200931 892084296 252232609 531637502 13168001 829174005 516271564 74389594 572530962 280465570 716727562 865018699 267323132 935461978 286914214 194823408 394095086 736323709 202414899 816122278 719035010 198906016 790867106 499516641 420298812 945219892 430729126 525575337 420920224 702378078 612206134 186927130 558778550 861019354 809894868 323629290 309846305 159894989 516297948 66880649 391055250 16238685 968477973 434690908 205915526 852611386 58440517 704704538 146060444 381721785 219857350 749242560 289827272 459049443 288849533 549599169 293296303 826268718 710851623 535798025 271535445 433993141 536386322 162862422 262778755 110822904 423086922 575423815 407123066 848891111 136708031 62933028 315826201 14996671 273995779 519012779 571443776 88932322 747686620 744363738 253447819 293044733 456838190 437107208 929038175 582372987 60689162 439375983 650270596 496666208 807734225 146114797 391729649 992847124 913201137 798246673 63824957 939652110 642975957 838530892 532333420 567676416 254039442 657124712 686350959 323463933 212984834 963132879 206170291 891401093 912802575 176947348 107288498 299672555 26521716 574200514 475578086 883579205 533951753 312241786 784182844 915832129 985276090 540990025 954096603 202693669 425155232 17924886 809652008 940947509 241300352 402068212 778526770 670825682 55448341 234720668 653109422 330861705 281773922 244249834 692059214 220029488 952029118 806527271 870455770 151928509 581250867 50345140 934242044 91718738 391050881 535532354 75319427 964093481 224991246 829744250 194861078 698515979 543498486 512543709 35443909 565602058 109025607 955491601 473127152 46431906 942539360 795081726 77421659 318975961 152560258 54092954 885632405 766115172 989274864 222820830 162150206 439853927 974667954 694582447 798033924 728211595 546925380 684174054 382037512 35398625 259851089 963084148 911633002 534951438 107039609 930907267 830534535 684068597 207873253 915613287 649777653 245329810 709829129 572964775 327391939 65617948 12792277 48727240 498310945 138192575 222420369 861846797 304420713 807282983 77145523 860722937 58530456 488365124 303834442 650018400 531367838 109513384 946801176 440587971 992155732 536555783 319444729 395459392 833023796 974760589 388064837 606888391 908229743 32613277 512315007 362269468 604805097 970723203 428866370 344615354 260015864 296821431 364514275 109715561 459629892 669577672 758326130 481001884 651890435 260608413 643134313 410728862 428117687 270748736 836571779 192808307 628189383 148681218 34852963 687793919 86499784 66902222 69334206 370505533 115969296 270867454 759294846 20409840 68761877 582411539 767464558 657111116 28754883 511464073 995818244 298723734 10948513 392950429 275925958 536583455 916430348 792231801 565875543 25875999 479236085 690997616 649572462 721814031 766359891 999432439 398172978 832733658 970042098 412069082 78714334 341761661 3001307 283258165 935476116 198756847 2684714 122731745 89601592 187365045 103375179 257264126 154436773 320635255 926138737 84883211 729324789 509916635 387300437 188434657 148832022 540151036 893346644 689649501 248567619 532913658 333096314 535363977 33547402 489807766 592001863 755608029 67194051 491730567 529694706 159678145 418065122 766584467 249962887 144588344 903292241 909981558 470173152 366200953 452210568 736749942 166222963 531686681 887353518 845913554 682667431 161632407 621394536 72119039 127828996 55326470 555047128 640217654 484157699 448445943 766431659 329228997 161950635 413190980 289743100 905147670 389518011 494644133 538252937 272634375 700049640 23393085 804201584 215455362 636035579 924073924 251458363 117017581 355180345 718864365 542447271 366798193 901922305 289959499 467316467 769984012 178947989 266284323 978833059 477648159 686850463 227452579 631087953 53898447 357449839 510744047 691922296 786546082 693244508 995795620 517834972 504058164 120011422 477135754 871043553 309472526 117066440 798162219 186603656 56972737 546704490 422925539 100829062 30253469 985087207 304584629 690388067 798237118 567471493 655062966 954140826 280882982 353863883 188468231 198850435 874164281 28398399 166985754 62253531 101051730 307215992 37946240 829051616 537133748 736432218 220123668 330157836 516399955 653872432 207492695 47204428 663053704 752074907 338282229 496592489 440478334 422790675 739961507 968186874 815529816 533123409 501038059 106711378 833360735 772684814 378608296 636377435 73482016 204996389 549837113 300275253 991652804 657435083 426617484 566350537 616706998 151194658 935748956 15434562 362335535 156916246 660065288 190767101 248818579 319708085 955437620 187530729 347069941 162244694 90561611 134676365 911111727 497981937 120191492 341066525 654230847 74007177 341448419 74508040 409211252 616357227 585428975 239401492 287780551 271438447 4914173 80911707 456192864 239264896 516369566 446679233 844109470 126631547 9464758 487574485 196312559 121247974 90348229 187761867 793414973 700016190 560468527 275068742 379972431 490268700 59007428 88326903 497761027 111214575 242934680 715427353 734120285 960327675 279347528 285326023 480588201 245740391 214772637 892507890 971591579 520476522 290795402 733443437 834961641 740644665 133120831 664423264 876695792 868205728 660828151 515167384 694977118 250148915 851370032 293641480 897472777 432368806 32596462 417272976 570801513 514978437 86409730 901487289 664865678 745408164 511194271 295908271 693654761 76850649 716478950 766207033 761107084 219055166 279366207 908147662 633645898 288513747 904717859 713375593 305649350 585755300 294764432 896603659 139164798 457531838 938493113 104286736 337070083 167860591 922460592 275397775 896425672 82362176 101607300 473967398 656228137 953383868 676468429 616689317 375340884 947551575 747013019 983963955 743642195 102494852 372482833 948604226 974882895 691458832 590591168 200804754 318679616 466328339 163566622 647610850 583335328 94931215 969141095 22693555 215325150 674260084 294764087 798283686 276181075 2682449 149642120 911218079 102734082 345718093 556790583 873149738 155300962 127442526 676954446 372248739 961380638 975738162 476573002 382917920 73469336 280855844 968659930 761202982 592715077 960076841 603538973 378934602 214269972 386027213 463872279 28965578 58462002 437609226 548850241 97611276 913090852 656733396 555230966 407937041 409592955 985603374 796802896 870947827 134868812 376975975 937928730 697668405 416236680 246927483 712100417 858273499 59335521 826352855 535980467 491926565 738887939 659895137 218030191 866212751 94937338 119601685 515137882 79033853 207547508 235961386 818603456 657527715 954693074 262933122 937181017 510151870 612932359 187864203 833355169 91440827 24733439 168303244 683289436 68804600 598843423 907822122 798213517 522660579 466911628 774321902 391453218 726622147 679977767 338598525 350877302 139931793 455802488 328705896 606273303 109979738 692778895 353289524 893262803 505417869 119914840 599617089 677458562 27582646 760400684 512523893 693007804 407052013 553306758 213647146 544508006 387239612 808546651 93941126 41567601 90838325 723907708 332287299 773283539 837753146 893534184 953159495 19363057 281031065 206268732 417871991 8381162 37317099 88310775 50102166 859200425 134673542 749737592 64283140 437609965 416838606 351027414 63673848 30585747 29224637 876315385 344207184 601584924 886441655 204550157 349351274 872368284 510805537 490839374 553196152 129080453 476476708 726906168 119532941 1435994 314872073 976528525 823136746 369596525 365295712 268324172 332777411 311617876 488279549 449981762 413982576 321508736 552303168 500517987 876311063 797669572 720726387 853943915 199266371 830278515 381045181 508023262 840072762 32903317 702874800 111444267 762766309 373248715 806889204 593272652 894077160 585673495 249400050 698848756 767658220 690905349 994234140 453786857 394886877 338984783 560683513 478643443 27975861 299046139 794860742 781885600 578523034 282445170 188691982 967367812 174727111 429250664 120431629 315747990 843512756 374034419 311019431 528496020 156656382 699816674 623306504 723905258 344249575 70815354 435447179 838294234 713270879 41018682 443745996 44898709 176351906 20080659 211819583 405665911 268143342 698041341 846943926 734981268 664317855 488699629 239530670 432992679 46947953 130258634 649315814 253456315 543992877 88406098 711969858 108831208 418918314 923700316 649191691 539238678 902415421 203971889 127783312 118560805 204512528 302325600 351042639 824396543 516592598 899568868 166385577 440618172 70748606 154347086 132429959 677021525 286674420 758098567 528813864 110050587 845012037 486308567 423322677 795784652 201502033 833134143 548997407 93812797 492074497 903518526 278754094 420783279 913026900 449251632 601512835 463725111 875993655 795243367 303881488 561352555 972963250 94025852 192650949 619232744 857432533 585400951 52936263 32949663 388197881 233633174 574519460 581807600 3657930 913519814 107250583 296178862 9538150 288936280 117639529 383414040 347134673 520536521 25877542 35707069 412071310 186836794 814520370 113787622 693994558 891694774 812292014 699881610 762225757 114854674 600349039 253187470 13714542 783130355 702359518 135602061 78589918 664478194 88979053 204899962 599682413 469522420 631626005 406288721 874791281 179094117 268222373 424579403 452543818 111128542 483216136 520130820 530411525 427711829 589402883 106745136 698812142 593848710 745932631 790859541 402965301 830051720 469988907 275810915 142497521 225681072 913482822 694356158 437639961 348184030 336652846 817357293 120135860 777069604 68467227 216379708 449086329 389108628 691668539 149785978 16151926 218871639 772221681 272608049 138506234 127408418 410325841 55357651 328256497 661541889 749602043 246496502 76378059 507920612 169315089 951105647 78423799 644129566 226359867 171541695 361238977 839440871 903620120 586271953 623199229 650241626 951879817 819684600 773834896 299555159 739056996 132956112 617231207 215959375 707355335 822241780 539433394 427956144 411065151 12375815 492097272 554112736 517352659 644678194 549279216 422856068 933134066 159777755 498703388 39477001 754257093 690766247 537106685 979319494 711057321 131027232 666722419 517234588 33693736 288400417 334903742 259383805 971888045 777687066 647815404 116403969 745778950 322225269 482562723 21889870 142499621 379154929 982022174 308594187 930433073 329945349 55642431 697260028 125453856 181886222 245695584 129694649 624139033 860767921 109984136 87571055 935551047 12362730 336305568 811687066 507142417 786453819 265087472 695479008 931733978 311484348 833554076 136047616 82035470 85101389 248157691 146437328 369046429 533481754 580911167 650064522 51251047 356999033 777256971 194839069 983815237 974934156 357497018 1887028 307340318 701553424 470806902 213216149 788124753 54408421 606930979 597286053 143164467 110830402 732845489 896732853 460718435 63710140 674265541 962489005 925852283 604220289 260527859 636686605 612864409 302867239 174400252 10235905 450502091 402753840 259830600 36201830 120026295 160150691 231646909 168315164 588736743 710706147 506922528 374607059 177625505 970687503 550377504 361441575 436234770 360864931 403317682 123847084 291952695 893527275 801698474 393500322 223803671 123029350 117774707 300802238 179249103 108545974 736934594 792009505 921626031 42014014 388541295 905664360 942022245 363493758 305103896 715770531 427977620 195836781 884627899 519484278 957398599 543245819 228738 879256524 347053203 833325662 710998483 461835199 893326157 620437814 869425317 771018688 596253271 109554935 183694553 415857855 859086127 761980818 803382269 231621585 971219759 529229183 714606879 301359561 964906356 266367129 205036719 269404645 53212525 224341645 327538853 184380540 716664307 78481793 630691185 812307647 456409920 310620051 892384500 776666781 684185689 38736220 67598494 538729490 507640308 151225220 730008466 704331131 763038106 697259616 201724819 15635929 299660162 158391696 232835291 229050403 294092891 646244937 730628372 738679763 671414166 562539888 196388356 399851421 932331349 475411634 36186143 512133650 827690053 140976213 220720557 406693114 287026902 266056655 878161121 144556164 314377027 668533901 392334824 494423689 552740801 137270311 15667417 581336995 458401751 744593491 562548987 735404506 194704710 526125850 402378912 972163319 283977376 615965180 132928575 617294548 663820009 517829769 368479328 69152527 633408958 821325109 788068768 826712563 999671321 329084743 931108710 100708734 767394889 155455502 498138147 252395125 796725045 107976628 85871706 918267869 535079242 746734285 614306113 879599006 964930330 516945656 829424679 673709414 414389665 170261569 232676638 277073399 81299302 349817385 171255743 710315302 765437350 520669137 157848764 137023963 210612849 830216449 353126835 283646607 334945586 166030157 320680213 49256973 369839037 239599467 768573505 936276483 432028174 170629188 204384201 12075058 310269504 801160935 520879085 113121134 969606623 542424652 677414715 784973179 465436661 832192730 651324783 506399199 302257596 6950915 657182277 405024087 731455509 784439031 276231361 276519757 63970623 24396343 596441313 33207118 55931083 57505605 796310455 648658141 112962740 889909751 41529821 523128128 595368009 322908444 248688162 105122058 78259918 857232500 140090244 350619293 37176588 510636112 235815173 556986510 731999474 302113565 991357519 202449713 192771474 187768823 518548782 52485528 656312996 291184131 199278153 719315194 352525704 198002546 143916400 720515032 993112459 695220319 505131579 3758602 339809079 268741399 52871084 298669396 2299306 285418876 279041048 673421273 996740502 48728745 342979498 724824555 865684282 302580701 243133842 212465785 725531112 404989274 283434521 481797661 287403276 74953959 573068987 848876775 51744509 215107320 523915840 142266847 157541919 943526290 960767945 899950414 575894255 582768777 8975550 27595165 280384300 938438057 777113987 730376555 924503509 528874373 181657827 534003306 366015541 79077829 34168787 87975238 409531189 46970369 418693058 483766019 860309275 447466741 134460422 134582438 96019898 278212100 18984957 939828265 522429765 29513265 13971456 930427216 860452874 734898046 821075441 250857364 535620860 821383651 912784959 983826422 479386342 248238611 364162024 932001326 411584563 638824128 291431525 632749925 887141823 434333416 851677519 153705612 276445085 396697918 634354512 211594469 596196668 406550397 983307303 189899889 758148708 546743897 915589601 532975553 595620758 688548137 941746096 967347640 822540217 197804317 68178583 887863348 983764265 440513493 578134897 91983993 981167446 273550846 324580085 850325149 279140189 285460650 85773973 140444909 917796412 372863581 773651695 527840038 984587299 965579514 261435393 893077754 154965516 91337620 314424214 271955191 252212713 465661991 751492194 9456306 250829154 463148233 772839317 939445517 18684004 598632614 865939459 15927987 233872374 530891683 160287974 359051922 738365397 277064801 138237152 589067593 474554466 34356455 29085995 967545923 17031632 952321876 392809988 794377353 323438637 772140955 968819193 532525724 32807165 80601878 102156857 805669922 820683413 351975830 455096881 536104048 102686347 914196291 138221517 226682618 84312215 619869339 897542761 303675672 292484877 725062435 19374043 385208052 627133186 865467957 536515940 106030265 597356358 998263296 743474373 81933874 736626446 107265461 892491242 819469070 590623691 896968083 805911755 23134666 136995378 209267700 497485479 931731262 33278675 645568126 238157499 309563313 568307579 350516219 491748279 231545738 169838225 615481995 20120149 582796358 263396392 631679099 668707916 425394858 673446033 276001465 643747748 768988281 680994990 956181731 729574112 540576126 796212073 771622897 87801152 972504364 547701432 266241025 937982945 946099718 108558123 301690822 684669260 348725967 802604627 815601264 39568067 129775745 314722927 892482188 731590534 464710974 884325852 94257631 194214157 484301531 434405389 205880319 273124456 150786615 379296405 711652342 354699957 16773333 148133989 188808267 917778573 689122467 784541480 832963816 70143760 107542270 201150432 394018893 792371466 307208871 556483950 373014931 881882617 919648672 188650439 805497805 613925939 998369234 727245135 442751309 568675794 925320631 801571072 673797665 998648677 256816018 327344543 6241341 38662679 650161434 282757691 572361687 854759939 766804395 56702128 90277886 761769760 259038795 420497849 285209814 575414752 547057031 255986243 200546526 50208852 472017214 267490510 284288830 988420260 469453388 124033698 43543905 431584739 486901700 844715948 561537126 666295502 433169910 246895014 849587365 58236318 746552735 465582389 387725785 888859998 116841068 982660667 424573051 123293183 473272279 932025004 367928681 559254387 966393047 876079558 868539693 352206353 372829805 239945866 635400 780653366 88356976 559477019 184863165 307484126 591858155 850464984 285812452 914464843 488803111 755496631 275038771 428280300 320271525 661645975 135344710 296808857 364170625 48330453 373985751 594735499 10812387 101805813 657918185 738163543 818475034 611748152 726294046 264934983 726197997 986291267 111843481 602581377 39274717 398232090 779338620 801102258 105389636 459048983 447473169 480718197 842484835 63299398 153205855 938572337 465578278 513032559 374837621 457924079 757775869 162826030 706918633 701056049 305598519 626843576 418500659 245387121 640746349 60955839 579864027 976624333 841309625 34876278 794338470 538920892 262636580 36700358 895543540 160955857 830609054 68833361 116717632 677929770 213958619 345146658 270995931 887946850 404561055 122544847 568390537 346389131 930903647 186722225 977971117 284781392 572735589 512348699 750612533 958796118 32834598 535742987 525834557 506995039 375609566 332727383 90341440 711359955 962514425 342729348 717620906 714817590 945014989 491003132 798564015 569815655 299764300 552463397 391188520 416237381 188452270 600252213 755747422 281268794 155049721 331195172 141911506 611252617 775513530 48153398 262005232 602090775 804162649 131364013 231071875 379889552 971431800 483986895 715547503 583364257 277223199 69517594 781956598 72482734 322752155 700350077 221790761 927050161 766556368 584805876 195393035 218430149 685976405 182051033 156002141 92404763 661350805 616886484 172627537 788816210 588898904 504522876 272727939 7612891 929159261 262973616 224090723 189182728 639642903 802266139 686419123 727910319 539222025 903035288 692687317 272722119 22678481 764524696 101921234 527993958 925816766 413353241 128121544 530659390 67181032 35361442 449297131 285255488 291716983 517176721 239284134 402930787 403326959 693834859 952998289 95527900 263168824 67934870 293674429 450490322 406886739 86510931 229907448 60565631 962415085 500533237 665219386 14973321 937372764 533857917 691957676 30095293 479726919 241998549 207956789 148705396 480690432 458603448 534653878 188298777 412524904 545600998 35643888 461989460 695423261 377112802 275426493 1418952 184745032 671856564 801027737 51893291 545459264 912609227 943169764 681808525 497255546 933350657 70999886 647266884 553439062 51138376 720843258 636115184 236234402 264428832 621499027 296106521 982049042 786610404 928134706 741298157 130196521 96034312 458120289 945582837 65044637 288580847 788155336 443344042 987360231 289569761 770955203 339061973 307559084 252552643 131251755 243805828 356646283 276241830 161643999 111425724 786623673 60501049 91479614 625100311 411274145 823085820 817480916 239528540 420861192 886009243 636518648 641400707 975256975 580669949 405239857 976890318 266506795 172254029 89493441 608732642 929678078 850350620 368071920 532568061 450949336 144067801 36313642 249093956 305297828 657667241 570459518 747219696 81958214 326342818 638970277 72730764 317854502 783604849 184239985 331622352 602657489 298560027 189111476 493362539 931573961 360175085 897864029 478844371 827250303 218827400 847422205 846559101 105503281 392973040 39503378 176128982 352815675 38014922 433706005 308084792 703415727 325985795 135909536 689666110 623863682 415430895 607449189 924272301 214633647 584448401 821157724 152135588 270006688 315997561 181670927 413926005 228253070 323074726 69707092 669706145 543791497 969065854 419561255 958529310 963845102 249206450 901546321 940491670 758363569 2953304 114688092 453493744 51765553 981614199 115833920 56726284 985140710 48902968 774396452 149991973 80984504 605980540 944590095 400268564 693726140 300170417 88817876 893740148 786570723 135636658 811219552 40057204 682705651 261852121 272812301 742645290 162643758 597533687 834564142 702819843 73119239 255268594 823269424 751930085 637621260 719571527 240539401 464355811 227260286 999910177 719482820 410123195 974252541 251875365 808457968 280741788 706753082 214803554 799782859 157616559 760760690 698076234 920431632 967591144 112385426 462296976 330407140 351801700 74335074 698795625 911704870 576846901 830232621 308480389 890303894 973400267 105468900 174103805 666435470 839006959 335112817 550930265 708116394 156347983 290453925 508111472 579055610 827828403 690762236 518242843 825839185 960196090 686491194 27202172 918294483 952546715 332574042 183426420 893867189 128677897 784220871 728349223 253862040 143248931 285502716 327245372 719894798 576454915 682304743 62581771 186205920 675584716 186497032 629978346 773862634 343686693 933326392 851890482 24410039 815474230 948202118 394866552 30143046 951881263 447871870 732909466 776017971 641215553 589692945 518234719 233705947 506887141 746047118 219916923 17164404 797037123 643257539 494013828 368532022 723005653 566069096 982324238 364591749 763592552 171441732 671738095 232320124 394695362 995117795 179240215 385005241 389071742 138265211 694233837 282551302 751245091 182331372 522759990 116019162 76157952 810698217 111646196 653820397 625630834 874562801 447498898 53128260 236718128 81178535 859064117 94746482 508267872 800394337 126124518 607409371 748806194 143710446 725875438 441958707 219648503 961430018 865529153 782465791 939353642 143417642 176788211 150707347 557424259 767596804 919066945 349709734 108873621 71151953 760600878 439852833 972608812 265249113 410893873 423573979 130943619 146251976 281899452 93235753 714300659 716463314 398441890 558910818 511919147 580447752 170891902 815587050 904935179 138298801 182140928 789819625 939725108 392160669 409546241 177522162 924205096 160756853 523485029 71480555 895455799 190919002 4517718 770030035 827709667 20590603 116393578 715241022 40229930 171286914 524983269 278107071 625488357 286032821 108075950 684796938 930982547 42248012 427475677 380783268 2148593 414874151 547409675 679204520 153269212 176006672 183820111 195394004 800177107 173892326 409574460 904607020 805194 774336293 603685311 140929833 161816815 835854620 191173814 816362948 44020670 531512514 492248344 830853894 665899014 293105237 598317882 201659722 369472522 962667920 540656375 711079606 276426215 276920663 454646299 544149587 541367705 42189536 850637607 600778966 579720419 759642401 2156662 890419398 707566539 652441835 8965214 105763531 674706739 656608983 709823992 248686015 844633541 139974801 237698951 438324785 637833230 389478258 39429933 207314984 787029623 431357448 69951435 876792112 466519798 526180653 269599076 853387316 158920611 315460288 90022866 557126610 608054311 979186207 796562516 959396866 816415499 194101277 319648026 474330083 507067249 82255681 393645717 993460909 183863524 535007251 98058104 782492083 780516424 202863457 9184903 15643152 613325788 366433794 908709502 96651823 340457109 414686586 976152120 830106496 481875477 14047499 359205546 953940096 321858013 463322991 133300065 381360701 814148963 624818719 619517 599909053 464269100 822424108 151490669 222448759 505449389 746339880 75654077 251505856 63591131 28686503 184486143 302200028 72365094 290142773 82666244 828466112 321182657 885220384 549230323 770149700 942986148 282314849 566266432 696990681 995231768 355023792 254116428 543459320 20215526 612442236 780542085 154367333 454192281 461711863 113863024 633792571 199537134 216013537 94108321 42176265 960327832 408768924 824068014 717856294 361196175 121139798 368263897 885398903 290843915 643158158 91503498 912527338 265179507 314766038 355779650 83594391 805725019 975099641 833142474 631061538 319900664 818466920 644382950 343068834 405713950 718019394 347122008 7927280 668924912 347339595 349848943 146664575 263839563 215223467 151131795 364254775 262232977 280912460 695543674 638190689 126306077 180188557 649809826 437246285 782042740 223327617 245450523 24365863 266374178 391942831 840017546 751816522 411582357 876199700 351655639 792943574 461182282 517167083 635297983 25214248 93148869 213180880 306811529 585901748 754948513 800898493 617384390 675926495 407771777 612251904 657598988 693253443 475733570 449859548 568370803 181069349 751741855 222664019 580239177 487734349 919024258 301835431 997807335 286707547 935102606 112153798 770571747 444130942 310244373 596427114 21800279 991595290 752993717 777348218 454216640 927016820 453313222 821875877 643260012 13278294 178269785 829947620 218162295 219431381 443983740 662440860 33283595 628582098 546533974 415175761 793526499 190385200 289429444 643011170 649230969 717082572 925503583 499579303 301962498 625897055 72023570 247775204 40697416 662646053 121091983 156511761 981453483 220669754 893783837 988167053 728455347 566508852 681156710 166094100 388284438 415417052 183226388 597418647 463744100 525331675 462071287 418166001 779758086 47208002 149811699 274938909 60811704 598970694 900646029 173239813 237788851 118657009 289687713 555176123 473912077 442272675 151429691 494893890 674209478 250371805 75399178 438123740 131581654 523046639 78092847 241016847 830582731 128348930 21695851 118716729 244342634 608385847 212223397 762421688 164734508 560421177 291110730 915719975 391152154 671685927 284900858 594065866 915557194 406381383 252599655 924775148 829101871 475253617 154272832 359949360 765115758 558549322 45483171 410161241 715167456 598017028 510897145 432463204 821577309 591184685 403821822 332634129 899045175 525795828 514782140 4053493 499694870 457146790 364872436 875199221 523708733 114121053 483906359 329226947 634332055 880772982 527094417 131395390 466601338 649762629 818140278 325106325 534560271 387302616 108284057 119180646 636468548 453958470 228917413 720737710 73823220 557532312 701076477 738449632 872072689 939811464 208446163 435975749 911562315 923507155 964952693 493258721 117403379 317540466 197652842 943823394 175520062 56969111 863821576 893278791 244866175 212016491 757211797 277486414 127042653 779788915 990236536 950987715 627947977 685719235 650350600 523390093 8685138 171110273 536900653 535466825 336996927 566356944 720715194 816507511 874871430 956160625 474822499 578325893 627104706 314510048 591510831 83364302 176237422 186484161 503727829 324040062 204408505 456888321 748754362 107652218 732386219 957201307 651189877 217670873 303064736 419911872 496957172 672660395 349836232 467645900 396216915 283537853 548918623 591621464 955450632 463553308 578264621 530997223 104171422 297410614 915457899 349442153 329912510 139723457 368543077 779480995 420618018 912008114 962309159 136343837 687270326 894168604 547146432 497640762 206148897 838712009 676024401 637566757 582596708 36173715 838804464 758014875 82195146 22855699 141135654 328802890 43925872 393825653 219295376 963763784 258596278 427440132 66097922 38069748 348137916 395586199 442487536 778507492 71729543 261649451 409412097 69540304 602386727 927115709 971430845 920321052 395258703 276679648 155415337 369768171 503637659 706378125 969971265 390832626 272019092 209162653 727000582 512898806 998461733 167657699 434913128 871200909 352891638 989816363 219313866 830660055 758149381 877021350 691117071 484051997 527876035 110064007 864224489 943624250 974110506 28832860 799016792 478619766 553408836 525144247 642347180 956132468 510595012 594347188 48408823 447685987 833899734 504910892 831981983 979620039 189673667 849616725 398589136 740937437 811227623 372261612 565883450 18938800 892252008 99738011 601546724 749167430 192030555 258161893 487417196 243587771 539686770 47762197 622644962 69507271 162104810 884472866 374971724 398123141 603060858 885917434 472971147 792078488 711211798 639468299 84837032 373051252 150763738 694062599 702167962 948416715 799195989 631753848 426128364 901997615 188008358 314131699 652061006 161981059 893535456 506682851 867271671 563344541 203356831 779048231 82246359 258387406 593186660 638216285 195592201 998302617 514112252 640008066 647779979 159848783 245822062 225977901 364062258 403839971 600710281 457744009 149694558 544277423 798414137 465470837 399118126 777206423 763298259 92411725 94793721 55236961 50899314 152796180 828108551 965070245 163162442 47865523 233717351 325016205 655689082 168953639 64727997 933653547 644623049 759163065 519454628 257887486 750227187 211798249 666519508 634385955 85766895 171075276 350193685 614713478 673822551 732486676 252164553 460475792 710225934 156981005 613796402 244299865 418921545 388275633 37943281 989475818 631815056 127331474 807581129 133017856 436963501 633616769 265724193 516295696 148907762 691534452 653357206 81479837 40012308 293415419 477374346 911103254 533619731 42637284 630806053 177909600 656304034 971259290 229278748 881728677 472585029 432887780 439873264 204476371 770977473 789970857 863942810 70360676 395392466 550016160 824356143 851357708 928387087 144777894 514142429 690333429 52201183 177051652 727148154 372592155 140854126 901886829 250843574 194203279 84747815 703276870 541046541 5374464 127459311 492734127 403752457 48231024 619965717 56002059 359359948 604969180 499949631 854900053 199276484 204823574 360399234 509740926 453254643 820686067 387480187 272106235 213821791 250054965 541571026 723525804 794829089 907255387 425368108 337611751 814478567 240825087 607757750 638221803 551653467 246237101 358398139 659232181 302367730 517671579 68147961 227671242 786155877 655738984 932156905 400619502 793643279 208970278 565738768 575180996 169018222 30842582 272929991 162248380 195127256 714996526 398343121 674038834 188063758 240045280 138353542 965274821 942269086 613231754 257735399 869948039 348149247 115169482 481285702 597537840 774595331 253704739 207730476 824624780 258767729 30693682 335979805 280326547 121001957 735477108 138533487 311116802 28179275 691030769 359367043 434398510 240447094 218874699 838177950 775342253 506184732 296810026 841622734 713071788 583799365 101378754 54951204 270253143 764392246 86174108 863076367 5336814 102456375 409504386 43201081 676810280 646686925 243276743 446593917 137324516 970030328 564215106 596559818 147647641 601172797 42554455 139888834 731975077 743894788 381147147 964773699 583546501 79860308 530247256 580048322 503639314 539918964 250501187 837813715 561007892 912220528 142507041 608263908 825131974 732462822 99045092 99366628 104134271 317770079 769791185 880661442 106122673 835290799 386592348 50199417 5843355 123485863 344740967 108251825 533128117 494508512 111780114 812212997 425503963 926635456 13595130 81213964 696937459 789957875 211320142 123552302 150669719 806946211 294917448 120406873 40287949 429174340 789279513 422326761 770252172 300854749 80729283 417460854 200753454 917215513 977464878 829467192 222296663 257975782 195263076 494525462 808959838 713853011 100283301 775542666 954438946 20291615 557705741 883989725 653112599 686109607 50082716 838312871 486435333 342276998 446744952 690028921 212171775 1229903 307407992 718285588 718773959 657231825 681691263 944427386 290757384 490219474 238888195 986952976 488747563 289985352 570533583 190251108 245595591 606878625 133849169 426559837 250603818 543271415 37598470 990005942 272601021 771556284 101205037 999068509 594473546 641802945 101511056 702499791 880457504 962247179 933351732 146990237 126319178 77231274 937888548 168268933 78341206 306609193 980586909 118373137 401094275 625653528 357800394 445164004 294408337 232141829 79844538 129954063 771204515 2261512 481016919 759247373 897444801 100501242 302596654 70542592 884962648 506215305 521270199 413627634 331463159 82917468 935731984 736417111 156581148 156746063 455439144 814842923 829337699 911132129 388069168 105047707 947924196 731138221 18420009 897956710 701126080 705286370 111166884 735880613 146885736 959321192 391960894 494619773 864925548 791537927 249660034 812892864 391901100 491784915 89681981 85271055 462142981 326266747 12391717 666963435 880436216 587717986 841544772 263252078 474471096 50214525 197964396 411566615 463245159 177991318 627812189 426778495 982363652 860519418 17837434 620648895 416371755 539407312 638899756 799019612 872151685 395655108 6788082 84529638 656788840 28163815 289800117 632046551 175788442 142592802 770982216 952617489 390899773 958097892 994768625 116343797 82680105 814413185 575324463 340666032 242381197 882515107 291324882 424117365 853411707 901073125 108815664 864099603 115162475 622993115 605052345 362236315 430945308 69087054 973854005 196799210 958712425 5050088 886328506 942303239 268891543 321500786 578586137 875684543 265299169 950883207 927825611 123517290 124551524 507651299 232637260 737067260 705878910 16226522 354242944 215517067 496187254 965631053 631410657 582367961 225328504 566911728 349367621 288880753 646900114 626488918 502562932 962846957 687372735 519643191 381732656 754796338 151751678 468292330 447448318 448084606 13964130 797686700 683399286 829109117 175678537 717099236 203364904 703459653 849225903 329698105 132277322 241663577 103851098 836054674 632090235 927577008 213661443 589052704 982258181 439887420 183293587 214445960 162432271 622651562 309678774 339075598 466608256 21827979 117601297 479734989 229352219 338656618 954132611 987990258 29208335 42909592 513679746 447180094 706057633 319852959 237502980 706270547 871235748 868870651 696874145 703563262 460985879 961942182 240796221 667728293 100030654 567418858 91816716 136345867 162849357 341506673 982340404 218682951 725280335 491972317 969929493 684231576 704333115 228824814 583206984 211402260 280467279 241021520 437970471 69448638 397038619 791873155 800011585 572553830 253671643 457769514 142147483 339911887 982249680 214295572 313528456 526459304 836122541 7114851 464238586 612974364 246435878 484952764 277228624 51628058 973225656 651642198 711659675 415963929 343521958 430425705 241017905 289352598 240077385 528068950 692105555 213038668 705846639 126148200 895174681 876203249 151852283 818397168 282666373 408022704 6847781 182386950 467920442 747898070 214425683 143843476 364906199 71171029 458837021 685898787 756591250 985342461 479052250 336638090 925659408 839372360 73308079 407052448 353228192 904901661 672427587 490811925 437056919 308392647 62530809 990724360 449357252 359489131 632925377 13248121 159065666 42986696 277217042 240135350 639588670 768032362 585781606 522528191 534132479 42224087 105062627 926456524 340073828 310357698 893035871 131052715 547412423 810896717 914672253 751391946 10648975 85629964 436505015 18961125 106069649 811813928 919895961 955039506 94171991 387925891 155685584 994848774 32450261 759410589 1228828 432363376 211731081 500181552 636832946 96120728 250089281 419861649 530993372 769315369 314859951 853339346 570451534 551023792 392263119 760282236 493963835 469439899 512315429 867375446 939659070 592719558 949263969 898655926 644618408 234959617 62392225 783046409 222514891 817828502 189233177 83499362 472261309 359754525 300280686 344413232 107727691 125545900 874914592 971194465 905577172 163268309 61816500 548532816 533874248 364750956 347403726 206330996 273214258 941476208 366503726 596671963 917265371 967867870 791993934 343757449 432215433 594122056 322988333 292495863 307995036 591873449 58423647 677066220 479865957 3014743 650843601 283383698 425953782 343552343 470112194 85136554 931807316 923898311 6995625 33385104 249276218 91257251 73361604 676693851 206323534 722298424 641443407 534927510 143849337 174905776 278642089 745654316 883049441 519623434 139809344 105289644 876127810 278917237 674605856 389547114 973546214 674587659 84662752 282624205 187494255 239627595 968206054 435974924 271346855 919019116 107219779 759283600 26507940 394792176 873568916 371534741 737933999 959052474 610329932 647086460 584551687 289449810 473427147 636047652 354629413 631080249 844828219 721588756 439077251 153998603 283950088 619445102 128796876 287125745 448456420 22487570 380970460 592267978 75584415 259747975 216356060 726873552 648447865 207824258 585296503 101100015 525059035 465292041 53368398 801421408 943578868 974681480 848613358 251757121 268154170 905411197 420008721 738491769 315555348 356505161 259797519 250383715 339507252 843329468 3528947 42555898 614929092 462928814 106517556 933929460 592896363 918658964 537116297 34572926 739782086 55761170 924236264 88347436 798081546 918632795 475294588 778919375 501997117 365369453 397405675 888595922 891880536 821281665 282474787 902021554 425036560 584392280 421907351 720323853 470053032 328387387 482629162 915074234 577769808 409680053 79448930 243027013 756102582 190190418 325282008 613850856 155718387 703405173 127900637 519698535 684116645 766519229 280387930 860953168 743549627 822514554 345605840 119950365 127470898 675967748 819265511 786519098 970827367 760432224 914539913 499016192 580503888 325090936 172993450 732541799 617534785 912672504 627439974 800622957 244932752 948030403 379522318 174660687 72533137 85492122 939954309 929666360 556726166 498174088 281400106 144750476 877571987 427399319 281503893 810297609 493576124 810487704 111255440 153073961 641247784 677306795 878982326 361037957 741223037 695301696 794857063 195519552 189984322 21554957 518288172 744765043 640102453 208363155 805487056 268648643 153013598 455195659 46459857 222141020 630088209 641172673 40499603 719383651 679676733 368237543 1140043 157041347 1536665 336079428 36252251 716503109 519296102 850793570 302276710 726090860 429823151 365427349 952844454 574381790 763867950 422945371 756999915 648073938 604205810 405595694 565976878 5518925 859682943 464487592 243717883 386094345 224967610 394829509 67854112 876440665 826644072 517144827 53789120 924245235 852351137 945522464 864094294 948523573 839671016 275499165 648208061 428203224 878061668 894265795 414813985 149628161 147254553 579827687 442293711 60900904 785707275 973269583 270343852 318840932 607333802 146235844 394271660 980701853 446378502 233933803 730127080 567416279 609581576 563860990 413181987 79847186 77117963 188829558 931359295 757867101 281372729 85634383 490985257 989764984 738752522 236852923 942497593 567845699 400171345 465807613 494043045 821242812 484576813