2093 79865933 16438762 589724821 969479767 169908317 629482438 742169349 366026224 822422950 97844608 364180875 402399778 104390083 500977771 260695113 870562518 387857619 507486639 786327903 24310604 562199485 517511435 735650403 935484661 944949589 953100255 860097621 834743604 654325010 9940939 598664242 637310195 649969605 633055449 994737338 622516164 383975268 176188855 511708177 747352721 288620800 615298560 969263405 688034187 852957462 600455259 660474159 651342526 44310574 519327420 521021195 807962698 332563803 389451309 805035509 579868774 104591562 164726282 924909259 193406360 330260369 627608165 991577299 393295113 965619026 714782929 262527294 86981309 96384962 137689900 986467822 180007198 779987832 782737260 2582435 428958737 640084781 999136904 546464626 168236660 280853937 580481171 127667934 917266624 900229988 57205755 206358991 577601405 971879672 328956096 908687637 163376722 61374441 244385701 943640601 165833730 655515252 738155492 17187849 967487730 55301386 672221543 943765054 378399769 878345195 373631473 818827843 179259585 847203462 742106136 725160198 233111613 75794269 625073533 926559122 951719646 31635262 2173681 856230097 59813719 501303023 267715607 140845080 979001423 24215753 357719131 972132052 232756286 523640364 244596545 201946428 516374690 964387183 910861951 997940982 291861902 171600813 884399827 863482841 73556996 527995401 387313661 601086289 848590741 114871319 294119263 628351730 905175562 182571331 993275995 240798606 659203174 154571711 841973916 857466879 184905760 634425737 767271007 395721782 500302572 178573962 421512648 483342689 604171356 928463750 874860139 56249600 389357020 114716775 815800283 174406512 204647419 382016504 100027872 870764372 390012185 66719494 296103182 583985025 325014637 837005871 956347868 272673886 574229421 610065631 937586735 663651735 228464066 75639598 801976799 188121328 533834063 987069783 731924794 699865171 334430319 281398378 127314834 808033995 364168938 956213546 69150103 877572655 810968907 362796818 152133218 687123272 675451830 220093741 39299575 7513037 378536565 783075020 885562467 989728569 919586201 780217685 972897202 814833079 375053670 397878089 438488076 483119086 175438922 877509470 892205161 225156978 6290439 850915440 990229483 74192880 775277646 824899383 882396524 491839306 409271134 927827907 843722303 613199853 173197401 615618960 56966033 149883573 274582059 785565485 668534288 145682518 394163895 109095065 935159165 233438731 641334477 487053923 489507214 287065775 370222998 596992560 80553783 119239876 458288775 858476715 378895661 109261727 822076605 665409276 573780765 226211806 255625798 464949847 255144259 364036984 946726451 272392608 805386888 930750848 707882199 870602667 654528877 892358471 67902282 964199027 6474653 448423381 507843745 561615348 641358637 661426753 18087268 326808288 877748317 270837017 103885425 107348453 867440888 718892513 268654317 407713365 12484472 863853519 119624663 191876127 617250578 12779057 553201731 476923456 4826344 346901617 902013299 398693902 530293558 749230401 88751883 937403054 567137309 724599034 244197477 393617731 635152632 162966471 231979961 956056651 191700346 665918969 542570756 519338306 867369014 985531134 392948906 408195103 498790089 410441222 322720660 877263871 139291975 596078712 332564226 683600835 782429707 515111838 148913226 121976984 657561615 678982383 176634539 38364062 314638 394765183 525652689 130118288 981119199 66864215 913645386 769917686 608815674 924789905 994934945 232587488 138686883 438077303 994121015 877974756 207113224 590521159 113499812 756824034 256210932 854888726 162985590 599876876 605111767 111443395 818562442 938619296 295545667 893964211 608998951 617939604 114046286 477538738 222963713 389742846 108589098 148795426 316110877 606485757 516326614 226501256 767664852 270952781 554949584 251328903 228090580 940856949 478799124 681359233 403146104 356218524 877201512 179034624 175815003 366679888 509752237 193411725 542763041 730811252 835582038 305205882 496564557 884056741 469620928 68771518 316066079 440218306 451153440 686952904 476648238 764972592 60124247 666846584 623669646 466717432 636277976 805993024 263646899 883838359 21744018 238417059 817527487 513353827 194185604 607613656 340754457 79381655 857239322 280658698 297806585 503975603 92775672 38855561 329055124 301070377 974095581 428074859 288118327 109159562 39206708 772510604 498206921 962074580 245794361 790772712 860442483 347795660 744362395 423108633 449015418 227842743 379608559 899620792 116664747 864497233 474132514 688626869 87157409 707149007 501952339 588631518 212906245 518526279 980861799 402951532 594358391 347646409 687270333 41567436 153649226 87189389 598292839 819651273 643726886 148010068 674667382 971056810 122332405 991685549 814666759 798021043 424580945 269126652 897425686 244635249 808070402 236952505 704848372 761022048 369741770 329693446 990846903 337701477 699433205 285929608 706168872 787741504 816828031 994601990 720022669 575567561 218150228 44948209 23340162 743384960 990233831 791729686 382073506 209795624 953790723 67600509 987897705 103443497 40206658 353826716 376861695 854359605 650013290 299121176 128294009 231115260 258366052 434422093 644532848 692277271 975752503 912650099 182855863 652819711 89647040 420074173 547076048 367231988 997395856 129061694 167750736 849777424 716174142 264339724 64285657 216386207 593763643 121482071 177113363 675408991 558518171 860645112 157178365 280447813 330342300 421613813 930947514 116778824 884330432 610944548 316033633 4147163 674580802 302292029 497508803 867378375 765598077 901115429 952231028 494358694 805718033 835854696 474959370 416145219 773885441 805453411 418551466 391303621 838672149 452117798 138837738 646129071 138424506 732087404 542237373 928477930 904439128 477915036 336078195 625950602 884689677 199776534 909235573 543748161 218558797 9139698 395062642 86168493 845650979 483490137 568529638 752617410 611631908 919573617 791368637 586913017 344022510 225434637 466805455 864819630 106336200 434467195 786759584 771404620 827523804 959622370 781950711 515917886 54035885 184615839 168153199 615007458 131080091 765436919 426616394 156185063 327942271 100142083 893860539 689734124 941362926 991750486 950328581 2208388 946321429 925981097 501061176 190066686 128375807 291340979 834089457 967371341 450446452 391270546 719065043 572696797 520618655 849718378 679260592 618902990 930975745 347429319 960471197 636700087 570289690 152965750 478443138 440360395 661428897 129974609 310448600 207322153 794239678 684193560 781035386 530250451 269105895 94294747 363637607 38965589 787523148 440617748 602640738 933982031 214897892 518127314 433958029 954453899 191209514 462040331 486676763 933123557 616442955 96239245 24429464 561295637 94416950 768973971 782703237 349997244 627585334 149390294 229538705 486820328 43072749 868094328 584650967 440854216 144208670 846060954 65233135 218586470 739352783 844239423 225906664 695822226 971085773 464165660 153472007 840323602 27880121 834088877 244367758 193923920 228715104 987193307 370060847 81247034 280875043 257636966 617093452 417912510 754101253 298220142 338059123 434120191 38182624 187952504 358083240 10678688 534814303 748789842 150544861 513021654 486172907 521276177 891820739 39689736 310041953 42272192 503713300 954656607 296560599 666107963 725113524 54897706 788244891 656524116 137575023 294898844 34098501 444689737 304122763 166475604 267271698 69162147 11620370 836614039 33601142 439380932 867538670 132342119 311492070 358102021 510325906 607695607 268772589 839601458 195193126 207978463 324387461 329319619 846847765 582338064 830228109 730603661 78986763 175583173 511176735 788055732 709218895 729056391 931676927 896473278 776012622 277225550 972283036 521348541 529889010 745360380 272881295 172910660 509052635 491502516 963808431 192389272 889276891 203586861 493556064 411362319 595492676 351970164 507405177 221206457 58793351 875902282 866626520 998678752 47773980 109104308 759945623 944522103 248121042 927023516 53761305 654318829 132155968 632877509 550262067 764537641 945621218 381242628 737226384 556654156 834789223 578295934 852914646 413084402 406659604 270061684 874035955 457270953 868109606 892451250 851744495 465292121 730645415 362932269 732991022 292742532 426445722 906851148 770458506 925601355 727927542 482969023 788885121 945046566 746257227 977012417 724585563 836386737 266949787 950817761 484011333 64834159 284016920 549665778 260594045 872401562 299885701 894879790 756009269 806551318 188786648 61190499 218804279 916652518 368482001 559146735 509838555 986848334 689421911 26386813 400593364 457038208 488204652 124575422 66908838 571191341 473475638 702081145 572173889 7029711 529273716 156424673 690836722 852976876 758336416 388011774 454826151 525630172 124106519 475074244 117074728 827002477 388103974 467814803 263857431 27246035 985257590 701951739 710205661 406065255 851814108 156328600 578476912 542305159 701067789 66698339 463628054 382212675 689207086 190894361 187867203 764705061 6652662 519989016 24005629 520675474 87273947 852442975 985478977 109591145 269763303 911851786 267150711 348725552 355326716 447019173 525674259 744104739 997300327 659503329 889870434 158975155 136002555 140641967 339859987 979789293 182041669 827770692 590652620 653092972 939005512 203803810 207985795 231155825 65613651 675647940 124679544 530328978 775456725 368565574 534257611 419135515 920056141 567279617 886598227 941944247 229104897 20900640 586853378 860777467 499535489 340089518 891534695 125579418 161202231 171716657 928918064 37144975 850788907 894145775 822286443 988884797 436033177 775586264 286829373 609070649 281254604 1408461 597353525 205777965 172922865 103264519 813457522 691522868 22321310 525229737 431336343 637512992 282351607 624711621 694238187 638002909 749206760 68048542 962794851 580354349 957015308 986680391 784061537 169062662 795232281 5337210 373692859 893364876 302070380 715658523 858701139 418422357 359492368 709267698 660492970 351538986 398135280 152648096 706821137 225919461 694657973 953638811 140195511 742088786 538225571 832305971 996738262 235256287 296014056 61985687 369949429 286666049 211418562 441329178 509795382 493845225 539664083 844770722 677830892 64484390 388228717 819346667 743161457 101806644 293665403 913846003 837422911 403659139 110702931 192384614 261142833 206451391 721332542 600976757 648528323 339850917 213078523 967978384 502421143 731684583 128945549 83205684 222858453 492551632 355001736 324306582 851233602 193611706 765807824 276461608 405528668 738728246 526410473 921672219 236401059 288598805 784112754 899382535 560707967 376891376 619393342 49896887 351185420 431938668 936819967 900298176 864460081 63285884 409457517 583753302 261430215 976887418 941733079 299790042 622559670 928205386 680318696 447194927 439105693 39335085 985492252 503572025 893344635 289948685 889849839 888377495 282765029 875755239 241558560 163603087 550838583 188371381 678417491 722774496 159089551 908872145 801256967 469272292 540200403 382414762 149428058 333818834 924638670 681891502 101006972 825854637 262067347 862963346 960887619 633763444 201335269 524064081 272574576 389533125 636405267 145881663 778063700 692181952 82891012 482276152 336665581 341844673 486237590 857455412 576413746 997594317 625638852 267813464 901282843 265288159 406816385 816966577 629440319 375162262 694034235 677047955 52987694 590393082 75925505 518011047 611721732 148329067 246356185 47442065 623216466 841828274 776360310 498793438 866025930 671440130 914658071 415223279 450259000 884454063 250628549 270385288 691453167 6761297 864809143 168979526 681140526 474512778 608909288 259384795 939356189 697487687 723261229 215785131 345026456 961548951 915354267 683691329 846853145 765019559 369295954 511069196 160329687 252641768 120387151 531839190 235097370 715223167 277525148 648171632 56133020 3734645 415295456 535079756 726739705 155887344 20159699 193332789 137365327 834961822 713271216 79200617 622221739 983384167 313029404 70138442 478704402 848469495 654706157 82952643 117915614 866122484 290525407 675774699 889655867 288924928 217486561 791991176 222267364 62419092 348300873 584864821 40055821 773771269 124287986 562958947 334743576 447381166 993056400 974505057 295196766 823232920 972851610 699855326 591447024 305311278 283441564 170687571 68390046 306854915 629945947 494526253 918090233 536640212 984557359 127714321 365487653 365653645 801607178 250754381 901107912 173218437 351736638 691361495 916425015 327126881 616048120 847618354 781984042 449805653 769998984 629198730 355691107 298149840 629082869 534273844 562673524 80065744 103172167 852474001 160908855 650894506 65106990 572957348 549612406 146891938 656823340 399570765 30399312 227024806 913587389 804887496 175523481 796326912 59590139 318174478 55955027 640180975 553586521 361559781 398353608 66828517 705312620 789239061 986312797 931624993 605204634 38901439 213792209 968293765 692463723 514713948 112489382 672206166 40730382 394877893 27009963 674699319 485535238 408856507 370812447 511197682 31380067 863331150 393325139 923917208 401977408 116959651 562266150 104270893 182005323 365032630 83675995 674157575 482857124 476450273 648543985 820306513 672098360 117315327 409820467 799219921 784942091 886156119 890469543 355924173 226608562 234810242 485351675 279748798 103740761 367041449 874963589 914681259 979642142 15175421 874490863 413932496 988833351 407750378 76605096 729176336 923155898 550705414 119070861 210492307 238497344 624472433 484604872 826765398 907566471 42483923 77567726 3661923 366424490 293406343 593475736 766805686 688953975 429963228 345894424 880935851 577650599 193954394 342329225 731902217 335767009 312022966 926358164 860943078 723643229 178432907 430534522 50055027 637889875 982859013 105246829 749509550 25095409 709823742 36767950 677783767 978641628 464318406 802782696 827154783 87395820 118782606 867953337 343443026 322182561 740493584 790858934 154128209 749549745 991329054 53524111 398472325 868731274 133328908 618730248 826129542 905883911 626561061 730440350 594422908 928906372 472178192 25617485 501717534 5227198 720005811 749563569 694721977 730931743 568992257 873063120 136431711 942619796 121804395 510196317 23444250 930209406 651121426 703464484 83954514 200403309 9233723 117576948 685365540 232004616 114179814 145402380 41508771 128371703 550126806 994479988 411672759 431672283 823701806 422482249 62964355 573394376 321301980 31765698 407305739 610967818 512435209 598666599 752976196 367134539 392224274 738244006 375663792 924686746 259856246 75705254 338258657 175480694 547642015 242815730 838302866 63931237 708654693 921634034 26242864 467332046 24654536 105816669 597451433 574694432 5278062 53363346 609559632 544307953 9890491 731764381 879656874 355378997 2489539 97088343 112483799 746073481 270619303 549202603 941875876 397679443 267514873 271926565 932430342 252945484 290478341 174117500 354473089 649264215 425498331 871071439 279638503 256122858 764906756 482572973 649714243 745034021 944207132 832423504 320186894 965204037 479881926 582490052 576094511 980069292 885728120 496586036 918327288 638336968 506861934 676433218 772492409 790795320 702396154 76888343 184270494 561629200 890146823 776653080 929689801 893380949 113521256 555348485 106115398 146748671 395485138 925887153 894871913 386470440 819323185 975975365 785047540 654715695 678216269 875008345 71447081 648987670 771600306 345187451 959386205 758519852 257920330 110171899 503701070 785342645 447914844 283653896 539717551 999173283 862202638 80005529 637275407 805270655 98205189 56674932 794313582 252434137 159619303 908241776 155647401 773464601 460662325 285291390 712247601 725134458 376059953 425933727 538730424 261908670 731331555 65200588 85334992 747379870 196759702 247316660 147349259 718713733 33187067 666838646 169309638 319398876 796659821 938311428 111039177 912406411 315224611 836480012 694562677 278679125 347688058 362864745 29013282 737204629 860724611 389747298 891123791 802238810 244719699 492119360 743845314 627565437 787442016 92246670 557274591 594169199 338487767 969694781 873111102 230411060 659883567 894245503 131712761 906090599 120715966 57839426 269904793 332012085 501515659 532447606 489701321 272231834 790933748 472348137 434834159 472439056 36296104 213902718 216165630 570777666 345067461 447599780 305032212 861061920 990437886 269715123 17745299 291203186 932395593 823599699 486372414 609618473 612307740 990105353 431859809 404327648 79708232 76429347 992756792 253774777 408047117 606280111 245510587 766604481 313585413 571399178 661504446 187619918 906880186 263109378 465789779 569243925 180907934 615298548 491075483 164390871 940565944 180101588 258439168 833493209 580773023 194471240 471720297 601104927 447507432 54256816 721644126 540181566 258815075 283563889 421526320 850335076 801967003 364521086 91113010 383142835 123719653 539826237 357108348 968615594 420174727 189644863 840801916 362572164 966172079 89220231 371705302 504154419 654168997 999041371 992175476 482644046 162564494 986565586 31761877 715327098 195506707 654642768 293597020 393909114 79279495 713992468 667414598 604713361 129348836 182414496 65645382 729725194 716891657 585917142 872373514 564196061 889850762 250693410 351142925 276419341 528799802 54817589 128845417 909488889 429034475 101768834 779214533 582970719 538065345 459353829 560867400 131966504 388700713 363509639 728921250 370455753 613992860 969382030 55033489 179353026 823670387 101370962 19108898 269550184 622552225 320782912 852819826 761600799 421997443 696220977 822149630 276713084 575818953 295573481 661007778 606794922 61202398 994969851 549188493 110982174 690920004 178883620 788346 606425971 646102064 482807790 385775687 365117791 967375822 191963308 503440890 160308277 805855577 814567319 129633050 61752486 312966214 24223068 721340502 191175217 217651082 393912439 833436906 412861554 469562322 589568609 990516884 48080169 824565753 751392599 84280905 941967337 763618769 538756694 422202532 648263419 642004922 353872861 879183098 859197491 453954230 675240848 230661818 820950401 573952024 347341511 703345219 772758181 285488729 466587030 854420687 417196469 643809030 872818 279878201 940504821 654871515 518591757 7599834 515604901 774591994 959585401 826202718 726180008 956474519 555841676 597904206 407415566 219052097 514986328 338110500 57313441 136310427 119022522 279914708 861379150 334053100 153763484 687946468 206368878 344273946 212568213 80417737 164856863 973217261 540070749 401686542 856709235 364214226 673282910 972211510 165510409 986285527 955587427 57333122 354334210 32297960 994514861 267582196 855339889 599929843 576520718 746592940 377958154 392914516 560639123 824120069 956767923 915514750 988408389 610829648 373873870 722675596 136222713 145274817 303377913 621279636 353651364 206566964 38000028 380673047 674925200 514745391 889489174 578651859 46892697 519200603 856437839 504597948 397973419 791041405 483744708 563309836 999777839 732375358 201307328 536574816 28927830 903408495 999424657 138494462 509830121 933675423 232755997 291488376 96259540 989688542 241965544 815491079 888465994 697006114 700374004 408419224 208715164 653244488 694538845 767717208 482962748 540229692 523693119 509264032 334195652 329804619 723729092 822329044 628413415 361388387 990715119 741873783 999381970 232045935 383114077 888535224 530949792 874448816 970539459 288616506 347291930 918287554 300707204 878687206 477550379 484134602 652459107 563895241 76973746 391894839 892158052 945091219 792536564 327847298 152297603 177617624 716580577 254953922 995940989 787908397 102386169 40244072 548724749 927562831 909083958 715915517 419263059 41442910 904060945 981927680 916668026 904741637 911763702 638730754 355581805 817974985 311701260 452911311 469763949 591674264 655834628 34898420 3844988 419087870 906286745 272029581 547151088 164349372 905792161 134197554 681046353 94607124 344626645 178086303 614793571 144045251 958682644 572069503 562738165 330514306 747003577 911508188 218583659 385023640 271292443 685508416 674981498 741228656 336025672 662246104 30410962 685954926 299503348 859975308 435689602 585837193 855174803 388173139 981067935 68066220 618069160 241255078 316659407 664611777 893580324 259880480 89707739 719589551 86264186 701981040 94469179 902592232 430011025 1166325 52234905 810516239 207861350 250857637 897041038 224916477 803867704 750012330 333097225 487763219 769609202 651657619 459990019 610441072 301721553 400614987 50318519 794439384 978587522 122389000 41276250 713094253 366109870 878860704 913183433 579197762 718503242 239744949 420644316 67999366 692485988 615414893 566743808 623415247 156501306 335014911 530067029 764237983 95904045 316069355 533778421 86238575 731202791 432716106 189260180 241259256 103491450 22932909 14092615 839423734 421939895 891293487 424823645 932869641 165948698 958430502 141799780 966748653 662755873 459230944 118771469 240581375 734727827 957653822 42070045 222009761 682458886 524075526 647094196 645849015 406823651 645677768 175213302 929851953 195444818 663629295 663538722 868586062 218022533 59770169 931431243 906393145 192685309 678932819 598019778 243729140 9592940 860212902 485973513 5762605 934075781 657833426 846145749 197659491 537869200 311997274 267201283 12633966 31234296 409232336 655456561 346299380 487704932 552924791 378035160 175073870 146388064 533094926 430015254 582584379 296706633 655294466 590080616 825754709 898627877 238068727 119587296 798561000 215794015 163181489 490672969 875855217 145836083 112808226 116618412 271064579 27425449 94366360 306016067 603721313 558137112 217760796 621036599 917874988 664674407 973220752 204237568 561452487 528601666 256236605 488430820 371622908 141309833 468817315 427210030 727660991 926818752 498174223 620079615 356813067 135872754 184438463 934743335 362308527 222115067 101652009 938021465 217022887 55612349 218547979 271459377 996087047 473287092 375488646 978202543 724373356 432602912 429776223 330984158 748026296 988736524 6032701 318679491 785205149 842291711 290573105 276122152 768656164 307139002 50973908 458367372 679871662 269441132 222246297 986925539 274792904 155491976 677914669 202743609 922029034 911888609 178733524 201670768 941325915 310892898 893525352 726187444 654296743 248369066 451396873 347646754 355714164 134783229 105789236 802884056 777714998 497761509 447178020 723939801 300165482 20391728 971242297 546252483 944011219 590414328 613169068 436654940 835029279 767669995 223805541 13428113 234969239 853212561 101146749 731226378 827357813 402071226 436552303 924959728 582774734 233613016 636078672 562721306 19265962 950858329 951941540 358335890 607980738 34098025 774753984 824959381 683156200 326360534 265578795 253083996 990172747 702974596 67975356 915139416 906647989 899131018 707400313 922089978 466083605 715990002 181111410 752167436 356465902 583297095 823144543 470396251 300932595 390565343 469012829 154675471 903561536 850413718 235393656 755485838 402622656 585579746 111078896 637589040 574521261 279878713 554822865 256604964 422320557 5656109 3749957 738797154 833601784 594360646 985219699 174587213 112555201 512438385 825713447 982755980 668260758 690927034 311749890 790346335 393550993 356944434 350079619 952538957 577228933 86243499 130613833 120591548 447308790 649302513 706278456 723247992 937661191 218084081 184927862 731845693 899780953 560149721 883344001 685824047 611808680 541143009 553519933 981806623 17534308 727367447 998111545 579121198 655780887 689869836 895781405 553059114 567920989 9098804 607674214 94527312 872863858 388450280 219593299 453208462 996780499 679789360 126467864 855953756 859013218 337056026 285506083 213807716 169725459 765755188 700030449 442120591 4425640 118824539 488928129 21846224 786929331 195250234 442593343 455528646 368163364 112342897 581984396 623674076 415826587 305544618 597994922 386335080 247663799 711121907 110441009 851957785 10597933 381288359 43796106 953877447 979465628 75972937 451756457 369245511 560393273 498637059 853293664 273017601 360805142 771134024 413484054 570073537 415288695 257536859 447618352 957730328 834698963 395289530 957593890 604743355 790195762 762115578 524427432 40958112 781701725 988634867 706688490 130345110 855923095 272275351 247268058 544571406 371620628 881095295 511705478 21910822 917743939 454673909 147326709 654074097 610048118 606610191 187352731 635714486 184466555 236933326 737738269 134308442 794472025 810906755 585780988 465933381 101083731 997838663 810479914 67325338 592292111 495579239 43711638 488087629 511127633 182044255 476659436 710273600 216654998 766643298 136314575 903973560 749148582 439129621 801419276 914436069 949952785 973844668 650733062 941297947 138458631 936208775 732548352 638674137 714201992 277185689 607429168 205779691 724706260 565633052 421547098 447625039 261991400 299529909 145621325 387087230 896172015 40856352 834602774 229705607 493415333 313682788 189700308 283189205 641886797 778330497 38041166 719778450 493391602 832500462 695337103 666722870 70779959 303715594 226548522 484237282 27761298 703053218 318957851 751769341 453915808 96471838 444544738 810076109 669072200 160876205 738572103 870874319 307627804 95578118 424914066 860666063 885481158 592069747 858703289 639759277 787842973 990195394 817146856 385671647 146718452 630685978 404517665 212836689 422357745 165684324 434729492 44613084 488974844 139770184 57594826 914374320 474790326 477525720 350800822 777116072 753554516 981178375 216600544 212119055 687572571 395132511 428645741 440854990 410885230 863874896 926477253 787413190 233603976 541923258 216091475 893334700 501620916 892917233 40644063 94764928 959720189 609137051 91967019 818421919 785473538 168960624 11677802 727295885 408855332 921081007 796018135 505092623 282238915 731587975 158929115 845626844 700130854 405919196 594020792 711903173 787509228 193778476 822534629 839544400 23305113 19620834 410208670 501488365 719330105 589955969 226215160 346021724 209952753 593775774 917808457 264853178 931187561 876894652 298520764 872938679 634286894 893251253 289918091 301954241 560376078 131636741 894479779 544458014 598795909 977449742 239632445 347672017 384221631 978588587 668764477 703185981 196792960 479060391 851903157 147865284 627653978 220992811 214774053 105454968 374504632 843483798 8392508 899394097 107484621 609070429 236402658 588570575 597409810 616243099 441873779 690532368 2396268 278423870 698468423 776380779 202351326 49771812 476370453 231242718 712932551 298735287 68068624 942144623 853222734 651250997 7862559 497712865 49212311 714066571 481572978 559889571 855618826 152991104 796045755 559138942 923660869 563818670 373663283 942633416 400721580 276920483 529554152 998893660 159427529 842284851 518437768 905299843 2128321 891131483 123583497 531051629 122081647 894262007 983146335 706946566 643462621 236482754 864019006 434935862 887044870 459043962 659393085 805388583 651456743 945337475 806150004 662932391 785244024 855983671 86822676 484914765 215288046 579732540 257817073 679738999 394708965 160213564 889922656 214255989 171594000 295456138 857886358 578156329 673782534 31782913 698014077 721571284 922828457 195232140 673517753 633150049 984873473 957874122 251393273 688795061 91824179 244158196 759406102 505696190 729779080 204220498 512432387 533667583 655808065 257576885 793408946 912661188 748774012 11781490 339498826 543730520 531075997 748983485 185501213 838718950 523334319 220487058 848986874 720172435 215361951 442360746 577876019 619039583 392213936 245501171 151070842 239798593 971720387 179618074 695656515 813055730 29197681 692366758 606404686 54731781 292398755 59570376 21449158 14020340 255631887 242837248 309310410 859886811 482063347 752270668 497987995 108512883 841844959 27889616 593964044 898282116 409425870 815184734 220541458 340150475 254851622 714910990 796958805 100625058 265650998 971664527 742703150 559442733 212680300 436793753 835463467 410909511 160544346 2791465 345842960 832034719 587317379 460624122 332855552 20320027 762778314 362941481 751807248 169798006 30677485 573553996 293522887 806141097 887080172 435546820 659354460 936148253 195857033 455678243 840426272 644065632 178001215 268218333 790990838 557854339 425962495 486644695 445405520 542931775 548042829 210214775 649825804 206637198 235209647 57440222 54122250 874765038 740993826 533025925 474307524 286271131 994821938 638541651 743590035 961177025 296579197 594108063 976967055 674032492 123493289 568615356 920874725 692284143 533247824 595525861 384884238 103615941 427289594 620390663 90948141 586770561 338442877 250526234 226005532 783061229 760803157 639686672 692605590 935662695 250133204 911095571 364901465 519541829 684783024 557770857 645710458 629970636 611218320 602497704 821194954 535058273 793342317 581338657 490371753 401574144 975875018 225129077 507611100 915047975 359464132 637767799 360098461 26313034 174509139 230383725 740560970 2016237 721144479 199203594 212146257 979573344 194934316 804351602 735196660 628269747 177372691 92979903 732784210 832546073 470690717 478630646 783339693 969999235 698725016 882499255 525689241 662867994 200952889 702065762 575665492 17887894 591105607 749381001 463522605 807915551 941751894 91895035 770514967 812932251 693720505 440063360 231255526 388949576 144239349 190673362 922207619 730799958 208566404 186355795 578512934 427867335 133318817 339872573 739249719 393933482 206780188 172123679 502959217 235964674 972151233 324258587 1066640 585777126 819045300 300009572 772014992 798888455 69434079 850353342 901233433 420411253 590089051 650585167 853477259 645198405 60369037 294649499 720897417 663357408 575828686 698207734 850532433 325290540 25620114 698806864 288043434 334531667 145232709 382765716 317072940 338570744 28247743 750874374 691999240 559639074 214938648 879693786 275786650 515805461 477751802 149691811 768806436 475353515 678342259 333251828 16108794 569798384 940197529 732926597 313416336 952728414 372200419 177066806 299858789 156782277 868294360 361915866 886823264 611184077 450088912 748139521 976173255 678008552 574428928 558598503 631578145 28127613 563670769 276084491 47198689 93667128 589412796 822137512 525823523 508568214 835953238 392160154 3373327 700659309 119205119 761672602 624680854 494210446 692969413 270443283 790336903 858180653 565813987 306697153 365445117 654322795 419329323 897682462 790260725 533529363 904538310 538014806 634749993 784684906 420538236 905053354 663561300 309773170 12936050 999147895 173619304 290062258 913680586 315645853 364508431 303829 718328669 991952346 708342807 757776537 129265925 311411131 393268391 622538224 946460049 914268111 703738505 974255430 818064523 363243669 725877090 181490520 329573788 654398083 51700734 11162328 700951716 815420603 313907102 90975158 546498307 546477747 301983986 594135538 726542252 573206674 911510858 161533063 896870685 165302116 889022969 709954513 349928401 588090841 334668539 290339945 308808905 467252390 540598131 230455764 26052170 85126924 815511544 384010771 591018583 814276433 804895356 546475674 237575057 459480752 157728820 826395077 202314710 699495491 531920484 270553173 614480959 345632705 921973102 723430084 988422926 618084909 995960405 963875333 951495285 710366310 828729077 569315317 377476519 707170257 617308664 127075518 802547917 276937252 327356117 483087663 230508955 426393258 694118273 572338117 324876241 692446200 718331187 497577272 573003922 784325316 894715494 242584933 737273693 909147490 74590577 536671708 495426225 93036396 581643078 22749130 602598574 228442490 869830078 931457654 298121289 980071495 97880235 856693545 440966607 221289092 386097598 746723852 228564192 426737109 908837231 866868983 211134919 955979933 692643889 337574022 263921403 540301334 959534268 294806246 879681952 589159502 759095625 116828159 547759056 541844716 606326689 399882726 692480434 715233386 591629414 936779713 274548438 923913401 841886130 11049997 417573059 889938959 903430962 657579137 591558370 511212623 539108726 391573264 141519892 914768247 145319014 228973567 477322443 38270114 463665194 263293929 602048856 643832347 908430090 415296228 683134331 557172886 514358639 128932448 519274589 741146255 496781073 717712667 423854081 214760303 843058553 229699166 887132330 73563377 324871878 169501971 728109500 299587249 144128700 893561996 220078733 564541865 533425444 294342847 570418972 23183332 874857989 152464302 814695484 799429481 827285799 783861941 683380395 805896318 838303872 121475370 939972129 50808427 249663799 399965190 710922862 952335675 251037035 242772132 480329149 934949192 951746078 324156017 650161331 213143772 654378904 115253489 539031191 425484029 817845377 625043762 764264994 927935865 67569326 618978172 669993107 718051650 521276496 15022488 778404816 759978813 121074116 985048309 750518722 311796382 529712789 776029820 260009103 698866063 143898339 996856970 553330553 222328689 776813438 113978376 868055391 878809750 676656869 975476854 104846041 937986113 890555026 263695063 399982087 494861250 717060253 567835635 40602368 155517040 885071005 247069309 400036532 563713873 611583048 233528019 780272421 23474255 773791906 18521530 702864423 611039386 722554181 430022931 196619948 944967781 28095841 342547273 247952603 606835191 968591605 857307045 684109189 828492904 62806749 788406844 5884976 85027094 756500401 189412740 16626329 739607967 604051988 995118876 880395933 385203486 20946646 580755233 461833983 150818007 334310609 718697101 315587013 895087850 678742684 675454576 13107201 664403916 387006452 971355860 755812589 175582861 641462302 869389647 832757727 730498726 465097553 926194980 26824360 659015875 344145292 110865628 241642309 220947217 140060641 698402279 20820647 644399928 270006745 197248991 246255067 424056354 691953903 335920738 810147117 285872429 684180261 388469478 547101731 680265798 490542856 599369554 75402436 972765744 972955711 773456206 266511455 35810612 161788024 436097323 758131494 675156822 246549217 390926167 4525290 655973106 70939604 89180336 659060265 678131230 915411922 419634906 2307947 245107654 242055565 680991987 61318828 312094837 88874470 929481749 266124343 655271313 557157260 270653720 997652682 406655757 78483591 509977245 298040989 491349453 422841746 472902309 959326802 304731441 466663926 26372172 456392514 230729823 700558508 594312498 144022970 597988538 822576593 441136269 236474801 11303951 647672562 605496837 222153671 868705987 691231980 746795467 248423594 622821938 296714007 401076026 532846438 515558753 744126921 100824053 352413601 99199228 756685599 767102564 383149433 774851394 473446121 264121090 36975220 367377304 170381697 509919520 235834594 133804037 192994236 714915644 553565792 768457845 364681564 199703940 628905734 318986953 1660231 368786045 807363424 740080013 365092230 549339328 232946846 271426916 413472971 624592053 147691432 319810756 865695547 338358270 924213095 832457097 719957494 258921789 364471718 642456244 281706774 405254251 280446500 653217689 283668658 784935360 726417294 992219475 473727000 59153653 488780149 781736066 573364007 894932599 139098417 638461614 173031744 118469919 862472192 273436368 587100385 903840200 273156494 453607183 337205402 773695944 325172926 463049582 647100795 412795188 176533645 541785547 490709356 568634861 55213019 459952888 411910169 967151189 343499050 156670087 257854369 341375295 556776452 453835539 937522239 258345494 749265894 223862791 681329935 420597548 615789041 482483122 282360473 562949557 97549989 485238140 861867629 955036579 187100186 54094204 19602582 75719733 44369507 410043675 655745177 116542154 274424383 241783621 208702516 917579672 10452314 631747113 725876044 334473858 85446610 411178309 91163897 495615475 6926366 628926695 801035078 217278687 744425678 782607943 489367191 962386943 119284548 370848204 526200253 635107093 898433915 195950797 261327697 192799767 246633836 71906763 163471395 240116343 464663975 986638117 620421324 419904274 984867826 689580386 244661050 264476943 677441228 729281455 596305008 231223330 985705987 69897213 757344083 717423563 902922759 885581579 93437454 711294645 769459922 884637829 284946843 999387367 331924294 61450065 947043725 224891447 299474305 30296070 705341717 943187023 453657474 404623805 875638220 501823961 772087926 64309092 257502569 309747486 690985444 689343426 569874132 853536469 778393327 845540632 5300124 461315348 825073974 572394449 634166824 382393035 156151897 382072428 283217373 493693568 915049860 207968115 299431622 829709857 894168390 973311907 245584524 955910393 481211342 522594457 616542478 202183868 329862883 39831640 492082129 20716218 91684744 248052710 98454559 319966708 278889371 818971465 464976677 561939375 215950320 207546547 797946917 405574404 77227355 957105595 781743561 198613269 98617255 118645861 969088744 540127753 660849628 904059018 537040648 134076377 216145978 889153306 597805718 917546048 187165993 923145434 633751818 650132145 230621564 750929972 925939291 171702878 950914260 886087212 497385176 927457218 40590589 946506036 54916163 197414580 586131663 796640507 786102118 211194159 555671920 913529722 524505671 678711117 120928862 447250238 485447637 893341999 478398989 239274315 257058903 885128560 62348137 604614212 312927845 519185582 96984748 467877610 84779866 9857225 15648044 327072928 680056692 461640583 244046249 536818833 93753111 228848464 443150912 772868961 148765275 725207865 716134808 390161519 219950111 338953246 905328817 709218758 519274422 42081179 815438702 157896611 822455148 847537631 628188472 770971187 729758080 812172255 292296877 809040624 503623774 359993302 661120825 709632170 876449811 936332947 352103327 659545558 567074102 304759284 447527665 699834355 986432124 333742409 215166261 163976161 391961306 809866878 816897240 229175020 492248984 323583011 86842751 699306983 689446561 699425170 421308946 504256956 507701007 362318482 878473120 417599277 369641170 951868256 234601828 167085225 779639000 963508186 426772572 901653482 949503298 923037281 272783205 886886707 476935076 777197751 88780026 866077382 187001508 252522359 725397995 811440316 887304520 434737033 153821100 732761410 490228031 553659131 552449064 871882660 968954488 787278277 931897986 774252338 29924062 845783528 329488661 191215533 548783949 893362995 456166763 79588986 687443636 416889602 89597685 731813459 831879532 940517348 604853542 102904058 463229773 94598237 183964530 854501720 843872364 787777869 414782841 880311358 943129607 304756865 924860481 315169726 146759905 226075713 759464133 328355969 838574017 947531671 496758048 161419674 397543234 71126115 550057022 940428983 926082740 708763733 685964882 118055751 730160397 743495357 361769759 791609394 588802744 28586210 610971066 654311459 681421379 631246604 41783402 758580165 313512190 884877512 328527406 371482431 31034257 407253093 111870759 16971944 492390667 771247532 508720720 476562766 930439269 275000004 118379270 488303240 898816247 678109901 711117109 817802909 113134328 879805719 376213562 375164810 79495304 246585746 637042642 150327332 350647587 17800641 347504904 662624276 43229610 636273228 533429639 703374211 50461947 799995957 587516294 260595878 935264445 207206567 977054766 324110604 809396553 378197699 98009727 539513079 367844266 867517219 953301545 605904842 701203337 155154004 223583670 589596161 122790208 53664580 789071022 928677464 233527329 707499996 148797566 693432888 970526191 482461317 966282587 727789005 165176746 776037485 240267494 874631218 576519937 108218446 576947784 632545363 645884797 262660230 513392705 938916967 743517502 87482292 888085573 931926430 429094268 808653869 59905267 562851942 530250800 914718003 548941315 128863431 321162415 664162414 268337718 872684646 559969113 935224121 381961744 848056951 679468845 596655397 753486338 793138785 169952809 857038918 425519773 909282206 83118430 726805853 872796311 693501617 811145270 808448967 262628489 87222427 656027791 529128287 947224026 269510427 173100081 464255769 604247150 930732057 50558117 295897097 913587279 793805879 750216856 354449592 164681795 204541316 110461724 551316539 823584204 867832247 340049475 166875053 744622326 396517382 132750256 361650646 124274301 834810356 570118499 401340511 332629209 339910241 238824448 140864228 128753533 785266638 227091016 187320185 140452763 539784524 612446704 749356280 332039841 441562205 679795454 680931691 998461183 911055573 961603538 682845348 35782227 71760116 438991934 824551644 29568431 150490693 910116060 51081750 288811806 15660721 670952813 906251896 113351984 936480565 516324635 385875534 753187055 645090512 402004404 997215312 885835546 393117469 847582232 964424428 989528575 78143669 25561764 844348926 328358475 73248083 172147526 841302252 58796905 257864566 809364831 226608128 877785719 970689454 920285397 344936221 20444389 643888855 301490843 590564029 365280916 777756508 374660350 420304669 334674301 528935901 729050032 741453404 753442787 590415449 468840554 534990597 938379463 998481691 616714829 743396603 461241954 545297691 694930422 928546916 598142111 498514941 135105091 185411174 789786037 411633624 270192495 684006741 723527340 776780820 257345215 715155784 463580884 194903511 180221412 167629962 55000974 978085851 162111256 534218606 449461793 745078812 473208780 150621436 520310518 299610076 600965644 937938726 744697648 226206175 629065180 452323930 745120113 859637058 907116753 604168139 130220125 322682631 495970632 453719971 17868669 974920150 421803575 636959389 113371448 79887796 425132922 785944015 637014183 7920883 544484189 411623282 104605091 231903846 463597463 700064803 742823181 708723280 861494721 155008945 45511044 776121995 536159110 366790019 761530182 665525867 850117579 736601408 172441888 963651153 469887820 978829491 721301231 634954959 713101071 763643369 329601220 183459919 414848740 20968592 782536982 220349461 140953230 589958379 218108537 607278535 138476169 334132697 85058206 231506558 338088881 941394690 256924286 890386944 900937023 466342658 647208268 470595953 880883795 115581551 208136618 85302148 568936716 727968048 560075070 12121368 9056340 174319558 418041265 281708014 242506018 296109027 173781747 994452835 128525119 451348364 820601775 152217433 95513314 278310440 311101681 655729527 544910744 805974616 196101965 281508181 898419971 650409503 392231251 817533725 459791601 386799765 619415140 279499223 23987884 909899828 415478988 512430625 853100660 138938999 980501803 349371909 132093413 447750161 939352158 882210649 783442733 165600473 329223420 606893977 153146680 913517749 935047055 91151768 984121595 913057936 457183773 300350743 700334683 667804283 261928079 433678794 524628934 51840301 447138896 172412577 610846391 231102402 733479755 87858441 250206486 914318532 211787851 176441555 338099353 566440610 842557755 13205481 824539732 231816662 432311139 676755740 991312518 788631063 415430055 46782840 457498865 459306040 283167580 321224649 354842864 666409843 856440678 690514583 545926572 621047304 363534872 615192092 809559517 246125130 469554666 513065792 480769326 785102326 938096907 141357470 19176203 400839199 242924128 332327527 703969242 64496909 678499593 41516689 673007975 87464514 433508107 133957369 964716913 521654476 415473677 27674925 27406541 379067855 729424439 519982368 581384794 540793236 107654643 471981477 989406664 9553176 184280076 615445875 962901512 813192253 220390869 925619379 540382670 803467928 280233018 994117627 880430654 22933531 915224909 812473911 489494737 963906940 500220145 22198429 507877329 874874587 647726035 760303744 245251988 293434435 281669412 540600133 199577749 997634995 969968087 20744557 677799808 704209219 518249539 110310379 193324926 390140345 991778841 244427951 956624442 644694878 224885307 964249785 406354486 876936585 861610509 346232236 676509280 447471507 147840422 762350535 899313003 420958384 186704996 524535554 561661112 769373478 202174932 741782430 298305044 713793581 285576499 398213241 487749376 460657010 626574797 247893694 87036582 758178179 14668083 986557274 173635001 164611562 619376561 404390661 537593094 587923574 559817771 563806748 828245505 167670157 532395745 264814400 436882860 90874991 376463741 479871720 442787021 598067892 784130429 636990803 521278904 576008099 770441884 575594448 499795129 367278239 777274820 117535884 743573694 21507583 604147824 732180310 277559171 532983212 364515690 46863222 136649786 334058921 6903104 236285819 214367597 764544196 541377787 702773222 934218378 635294 518998157 37692092 966410977 832912048 86162538 656100915 540034896 438290493 51816032 38406231 235332649 627806004 114380085 156827321 271963493 336098637 371751419 203196001 971667299 630713117 520388983 187536337 270642773 313973737 63447722 781591233 128943424 221852718 809192839 858670333 748337235 707789808 172799294 576985942 339332696 198005298 566832231 295435951 231975554 24276538 996770484 251356864 89537977 419314062 578593188 489866808 97895452 789235881 744419624 294583324 99834243 127766299 550315893 849797064 319841166 361854615 354869671 654498805 678759600 316645693 478900136 832204226 938577997 794395620 794768978 975519596 464869522 687171108 175903683 957578489 214528738 585391601 429685343 554293279 647724184 515951434 427355060 22182770 638578147 332489473 265982611 69813818 545294414 786597835 384846747 720199942 98681667 321996177 913490659 255259223 220825206 328618949 726127004 654428572 720060342 263206613 58756380 469562243 363107691 398660234 941026510 909031305 137256673 365430224 792880593 63640408 191883632 875700855 607298703 957239824 333087389 166016204 236793668 626472959 519182723 34247619 587403757 296635440 151562525 240284209 95926879 831068136 114279179 837527794 401811922 705873450 765959734 101086974 854984346 83837276 735482378 375299814 408371308 284466697 300422868 97105381 442217017 110594199 230200977 681835389 519515770 142501530 832799409 784054135 798945308 836220423 699952753 490364035 407541486 103974553 284033758 193475999 320188047 176854441 393967974 324036257 109941654 122376966 403538924 753769437 832372626 54903761 383189629 208017870 192902730 161724097 916535298 855049932 618529997 434165064 618169239 104730279 835024528 678069494 82286754 869868386 30371847 622772654 58257226 521831219 361054646 918824484 617175235 963644654 699736881 671558083 308814538 686346549 645121866 969421919 212359499 16081947 441573810 294627916 383036288 748591215 588994198 664421670 465900096 83216010 123520131 195943152 725736964 757243626 723497412 708161659 858331201 642188993 50391714 528619755 844998061 86759066 778865159 418472061 773119434 201077055 957337763 913659780 227703448 12884840 897174294 658298313 747475100 953379394 423342980 339720965 106774711 407928301 161668425 858030680 101532718 598133546 462217967 967087549 527054510 871068586 215907414 868554185 860234558 896632528 149441789 117860924 819743836 249464150 79124893 751447882 719873545 428550040 276516126 422378919 452680850 412858087 958067002 544877802 970510205 425269969 169020376 994356367 96835051 989835469 359381699 664433850 778538931 423189698 131544495 557980491 963662110 606074498 532838038 908821711 778507347 28254590 219301029 554265767 557060277 303310664 844907806 261384773 960935017 58590257 634005466 35375173 632572535 460402648 844401935 721455895 527017483 685788529 681460071 229063568 59089281 405018639 574081250 388215470 915056517 366169130 59647213 437671070 457716500 439625327 93764098 572616463 804120607 354151882 42315446 611862713 672698702 106895416 296534464 338141140 900853961 446256032 418600312 343577169 570922838 389278254 839599309 114883953 569992788 334067181 230098945 100381263 986213018 467115964 131051551 327350297 576608809 126552158 364421082 878878585 477457904 501041524 409746522 785052300 71714060 563775879 250288097 586065767 805158992 832996971 477842583 57562558 255297183 803880137 421075345 637740309 389579590 663647827 64803638 732223152 732509347 928314421 363752154 471530359 233256753 300448322 871521237 841068124 279656518 767571399 848283616 52859360 360050383 184221111 750556407 28832952 984017287 898956649 196262142 829045372 393841349 517540332 356180315 210781012 369556707 695049272 423927023 824670907 768034709 735139199 938939475 143309298 714330443 956195903 245591623 120968162 892658356 840686673 429344974 342796138 46278737 991181190 550297499 228932269 633295657 820002781 741174949 600043619 719012867 799243971 99002011 243696283 320994014 649938453 223638355 607763719 647074738 498278582 976134597 593324752 92322583 763634163 638485887 519115823 321455943 913700608 340479058 637511940 112571456 301473273 476041702 755064189 156094932 352810706 835332354 256823786 217936436 291228858 15225108 191948400 266837963 564169352 649445850 225446312 403395084 990405016 89585987 86432391 545767466 455031122 467657211 406842016 566680517 967920711 644789278 587754464 451791631 420295411 275708471 682275424 630089268 199966800 376908665 502568476 582840133 153291999 95782338 930402964 686083448 2040236 404423649 44412641 843973906 6650744 596073013 14850715 246718964 905652479 586620718 528035100 148575272 694318769 134918564 353816515 723998588 467584555 442622807 507280983 146581242 965264866 152744703 834593123 61872726 721137757 36715036 985653606 297428278 644626456 351011390 998842593 899675619 452777802 81891188 341947152 293198188 174020034 150906210 323139625 421058247 158072234 493712053 512859887 759862510 719498541 365001092 758302997 976922512 780900386 20205657 501184355 517660031 194063729 397790044 170702373 304631193 855006348 49779753 882325891 612644400 886938461 219290764 445869855 587468359 947287214 292442616 920705668 88326236 357566748 735203636 835170479 7950935 153178681 599119590 535709845 24156071 485188943 323769044 253474712 331102384 963698721 784867043 887389833 801005192 820213534 698412379 884415023 807313900 746864022 657707988 518281362 66997323 420091940 662731521 635574582 175247148 551397847 481444777 473226749 409347812 204550385 54083506 453697714 854640692 311752793 372670478 75550622 633913982 495237855 874545653 317687687 456153427 17897683 299413754 528527502 419849744 523114518 344449806 710968662 7851474 16171101 657315063 597001232 427495566 30777323 981011674 633000408 527978753 445791530 964360443 778684088 636990973 942521147 636463737 167081954 52835016 2745802 546731501 445833793 89526481 930181981 983376002 88887763 775374444 559096292 352192342 407970694 269776462 907377105 840433842 924350071 143701032 739717870 819937627 208770636 857972437 696040025 297492831 799340239 625395290 898227726 235125789 299727113 176219240 260778554 660165176 651589700 351432033 375666005 142753025 246760303 746159979 60132757 419592896 885641081 354797383 879194087 583851802 192313988 309099236 217754205 657566081 659400444 285485131 213820950 81444334 381922744 678386674 49302278 855958675 429845521 891733786 444135185 195272197 703067685 915137119 323329386 228357778 532573925 216372837 327302603 89951172 758865291 946243 503462121 447068470 517129972 314602595 745660373 602297704 761287090 470900709 307704705 158263073 314240297 555619193 828914427 793054491 879790291 365362050 603909324 175354592 715267320 89162034 851364103 188464243 992296692 723990430 725805875 619561749 633101989 75109027 349800770 67922128 696715707 3816370 791334894 18841187 726810291 584064327 844605325 508628640 811743377 981786584 384473438 56048047 65059039 898620479 307577480 171031833 105681619 831081959 419455896 337312302 171776640 136106995 491472057 379920854 551631603 122205115 841341859 227980453 900511352 715555247 611464307 76212991 590243568 732098598 243562245 41651479 610706388 679077964 522381081 24416668 247726303 809244439 437271522 198337301 628350479 453774703 282018549 558840344 446730997 27842086 458730709 629085029 723488948 510723402 297544906 684382744 265171382 45333237 119350564 192701545 94565178 380776400 720727942 912482146 252006935 600877377 179191393 713116514 35180299 187806927 969278229 630348300 527965867 969654151 955479989 377211440 922124522 441903505 686267379 788685563 737788076 449763114 963326781 599901329 841352594 800142218 335360574 150735586 576796303 382656810 955996610 461302891 622359489 699883840 584202182 588412345 123510650 527271065 441670726 654966699 305181305 599623186 82614923 941395804 943779571 384432957 100241751 240318264 177737338 700567012 520037229 794924199 191978173 305225110 651336831 882155930 73730196 700245019 95390991 452096209 86489605 476123753 274881715 639213662 120966007 270288782 941557317 400887260 500753283 398640844 260515699 26234253 734752132 814936930 107252682 850256581 741356753 668411326 378619267 542935840 978644406 49346747 522655203 132531710 187665767 638371464 12605807 24379136 85768655 572674348 696446488 978644009 773319611 509226199 362800718 372153440 99207433 607861467 615949005 969902410 980539471 459468449 953229287 125585854 26824975 631986162 516668522 760889558 89790278 552753316 813487983 995222434 178296032 112979205 755925399 887824400 219513848 604719917 854876507 245153205 33400476 595106069 342532610 767471974 221563221 65787163 885033324 964522897 566507036 116585398 398999862 68206242 121264341 732783619 366124044 149349568 658910860 207519007 697113822 734725423 757401419 349449739 670056570 465453817 182305243 232435682 377515118 166138221 152319703 541160412 285134412 346957230 710643718 586500652 458544750 598770388 522073384 871957605 121403425 210494168 917182879 2654643 883768940 500563759 15109535 117911205 737971300 764669047 615113607 274477533 230810676 789483343 786463881 726757523 646266454 41660922 307547888 566285243 51956914 807262921 195587544 708179431 623485524 637560923 654057057 153319992 593255883 262365216 979192631 558848693 637773317 205203551 631980578 606242600 857200427 356052679 198270543 703627979 159665461 549274818 819328923 294254890 392495082 434552220 482113075 869609083 669857993 668867415 223622553 468273827 590772995 639199379 507578796 463398452 792590209 358603060 323775934 728609966 114459228 729009889 37406988 676864567 465248760 869287881 609232474 806636668 329059959 420385696 763128934 259175088 419246136 743879433 900698534 826846463 629501465 44204167 875346994 442129970 920618030 978149031 235120342 282019106 123210741 657167328 322258463 922057671 108378917 438294994 845794216 370384138 138338396 132870820 922199856 136437566 827955235 942312592 79894530 888602050 177017142 391338696 435925720 658064231 236516986 744691437 255825845 506701668 66443923 281993874 743402113 846062543 906470360 438245223 577176887 535406099 967390360 458887526 881202772 850590936 135436606 389821144 372726785 923289255 68501231 459975053 523903937 602787435 29464570 469811228 932458925 869374909 401893956 591136448 651797725 358361100 995167160 150145966 797201005 14415264 472416289 66699608 885264871 61597438 718361522 66033073 647052111 681774743 781880932 780566437 834737698 516983588 472958142 383412281 595882553 189382437 533399851 505362580 559322788 612784090 925632653 683315627 751889465 904432366 736233557 775604478 934128076 394158455 369809426 2270526 154000129 182229588 651293673 692117767 359810526 5165690 529253264 730812158 885859345 259599060 957628446 836687995 81398844 964086706 386990979 200836405 396041227 24584785 873361516 500081869 329160017 241163619 347543232 288432562 606364276 323850510 135067478 332040582 742449024 33710438 236733816 606595179 412418723 518924548 537809391 960606627 633533132 462514273 59974098 509779889 599456648 943226970 788972579 153722532 734932372 29155130 954178935 300914791 429849088 479440390 677449090 833610836 820004649 540912668 154860654 914655565 245430198 215769033 804080420 301338004 544065005 389120904 72605652 797798747 595097695 997343332 769795840 582777339 533490634 481735584 408641854 822061186 530451775 772874923 907337319 653705426 686041388 212670024 501006251 806852446 893353579 305270667 109010860 773891049 710042768 844576064 548374565 233881781 880258374 50338354 392574762 971998205 9765249 884970434 122920478 225241136 638362180 302391610 422104805 813085429 28704008 681460752 903006037 534050093 518008229 864462259 655876384 536720862 898855757 369619318 307520321 31319139 53420511 134073179 375173328 41300937 78721935 159585744 650303050 58001685 739047074 253418165 113026736 375592970 732660831 530530788 370935275 447672503 969672980 723052710 68083559 316220268 399164091 907875050 217516016 588587620 71584587 660849068 958353510 632411098 201068755 296566018 545223392 540712259 578584101 345290106 720104445 868293482 843668336 334981343 46021723 606214321 413670717 631661558 972491247 341516189 738992636 116751093 67349607 891981570 436382251 250014218 534895054 200762788 481616178 321312047 349320305 904904642 839359967 601610858 657178323 368095589 172829089 483598238 774713743 158558191 13025492 381329496 51895985 985028331 435612589 323517753 435315515 856462021 522551662 228711131 345713809 750755065 629348031 877068312 346128910 828750793 915625425 614619181 462750737 573583991 483277608 252619286 256841223 417013498 709749198 97315201 317772478 466652812 971015870 319658297 61575210 771380621 444782940 436511251 657918030 157718 695095813 954689266 785281926 903739217 22445115 589265197 459272434 819190833 810550888 632578507 390867924 364757261 801001559 572765567 271785898 907211025 530844880 539007585 410056130 668552279 40596750 238339199 977495612 679000550 830249259 635339336 638980216 786866619 993633988 268391332 366949446 491472876 148171261 980613594 915078761 856789791 425033436 920823874 610960360 472308608 886001789 774724649 189553429 152685148 467835722 144568999 589571851 72523187 740594125 466697203 145669050 649386619 190576292 73648002 621613214 582854282 187745898 519112278 271269667 768178161 927312404 237975303 563032756 211299922 720728036 590293271 754258333 326211574 173167583 582989772 535446959 660861921 580484607 664966412 756287409 132408020 688327263 581000218 475367067 916731466 282911924 85024873 890163833 406457409 70263657 222338604 555794 726721541 66820264 690527647 70946529 198291710 475421740 455880387 13399277 431511450 285062852 622670569 431873402 48139999 226401305 125438519 625882740 452809192 28776140 205570625 28603052 931642886 648501586 617918544 69409859 882765857 310836800 4550162 545513980 523809427 157088243 152325067 837029777 44075285 925715294 879597544 210443266 196290162 473806529 552689147 904359319 760319447 724217197 562248450 439680142 339128924 140984912 92064117 315732945 876940321 588385767 133395166 557826916 999906938 694979650 915636283 681514004 928526432 800658883 610112977 643819322 873719884 753352104 9307004 412024369 45447296 290738975 445111169 939333272 175954502 488969605 753801310 534941206 546879780 755292240 299375497 25653511 988169010 558528379 905389545 194142062 972071540 400467722 630923055 926669028 1544732 208700359 540534147 350696697 915265193 719114987 585506544 724775160 959836169 240304920 421594032 484112928 123412299 415615337 597603280 786697725 764355209 641616712 301706191 522364789 320223513 549478993 233122981 18348915 400012480 460211969 821432650 26219375 953456835 196620178 292715216 644473502 99376862 757228426 695431733 819723838 123741500 459570905 200062093 474818869 166648373 493662143 784824569 531073722 49878396 20307819 221698435 754936990 528018508 379685909 230531093 795310327 100256667 133829772 992197074 477732076 106085808 845909763 14018829 760201770 493174769 33005260 811510032 669117233 790195423 804210637 597472647 223129016 566621479 323797603 294796697 571072517 287813145 400906127 275011650 303826279 800128136 882316584 159498682 358929364 320528911 281297404 427782159 377348590 937604385 82315609 713995694 693100230 728667359 833192257 876673106 384983357 828096299 360540939 514503679 633958631 320883465 851517237 400115419 211060771 561187912 511870556 424122283 908456419 549224270 1471679 974226895 686400458 188597020 428780465 551166806 115933189 436508968 987717408 849883348 70181845 679733241 468311696 372072308 54776943 490167846 544675457 639895587 826185165 826394421 707722049 541456752 957012891 485808531 279295641 94277926 289314711 844096959 307404027 594214204 343821608 71116624 144973160 990831881 576386588 214872458 219534651 935295698 587050313 572553713 542415907 233090596 484427908 246859198 899260174 411594757 786786487 741972441 288742347 468203448 685763197 912046632 455139434 64733876 948505359 943195223 781684513 310763035 187603125 73503202 127715279 324431661 265837211 318112101 502402842 599626936 482425443 61975944 468095146 383421160 309547577 169788003 991172384 936853753 741937965 468102200 336948343 123162771 32987222 949632606 124192085 510109530 759951984 485102953 995469516 81489969 7005478 316621464 459773123 850229125 280611865 996176034 864783987 154247948 33815486 660532147 554512889 520554555 241038497 657612760 509908699 400963217 54725906 780998379 391383066 282701652 929618714 345914050 947793471 737668241 802173131 107701647 695309680 418961561 968870200 769674321 713394824 800347719 359773908 510668740 261587705 907795261 657329716 443109347 488740019 594942001 719942507 674368300 580725251 897736043 86760454 71297530 848883751 136770521 64270906 527532624 150880146 262543720 278537393 441726508 576619553 354256803 805324772 548584231 87004401 525344479 367196621 50640837 10622416 424594481 655900818 741471047 169778281 141787250 945681067 405134983 646440824 315315146 268350924 413912881 783099862 634238569 522348040 101515282 929346882 307823697 636349701 412901431 313001377 677361393 771108302 617421589 699805902 44294790 559137348 681301907 74282757 884640707 542601974 950851974 623320442 23383353 321142772 70855929 749226879 586215374 799898356 6775287 661324714 653810845 319839831 6899133 826637691 314965730 777685835 306134887 403734897 74273817 472053282 694617311 992346481 181632053 50511952 613554782 856189519 834297853 669836229 243821912 648775978 304177253 873530065 482425716 267154091 381081429 935575564 925217032 638374379 289748052 931422280 768389168 412944742 41340695 463143882 991097573 323605572 40959338 970658778 917678690 201652684 920289371 384212736 32176300 479716656 518761991 875097415 806660057 329321200 630932340 616462419 341133636 396057550 750384778 666205832 222157491 806605209 415031650 816520609 340850304 460132653 418198659 191295446 943820209 211380092 790774309 76852534 944096495 737135192 45337580 24798951 750294950 732320063 487166167 887853832 966739629 129851596 716475817 967752462 532307560 204078809 299395346 216183500 988010467 327691996 954263066 498149323 433822412 216477850 767473436 838517547 356541354 132722792 138211818 274019451 45331049 258527796 967161001 806265196 728363301 553295104 101670717 966562055 149061712 488048980 557618210 216962781 879892251 47434234 463998086 877968539 339215835 558775171 194776994 194902260 831173251 78119043 670644276 964922744 714891209 964968641 480787313 146127255 547862013 85687727 738798703 967596133 523163478 71821437 21363724 357648589 36852523 265600313 510742760 115930994 2858255 662243429 345870168 701387592 821155220 541141331 127501246 944556644 359169577 571075461 75751539 15429973 978982060 659654774 189321878 75010211 229074237 387456049 610949713 952785978 584964580 4424845 360634162 314135907 296991511 182379517 77039464 994084139 635115696 693265253 911150034 812832888 988636435 141957952 79618867 105914104 978713204 413661100 107066156 693003443 3745150 653912532 954799559 743771818 153973657 991409661 475768453 415484541 732547868 611839935 555590298 618507511 990553952 180302381 572565557 112536778 935375703 430594945 461586460 593858250 2430100 183752031 812642646 750537289 139423182 648926990 740891460 316082218 386746070 492665118 976324771 288632567 906049801 128965910 289614313 454249444 548154339 311289390 928823668 375148589 140753306 778561846 34360647 536301037 381841794 68290719 288286239 857067174 611617032 267588938 440941905 963611857 996669813 699392218 975522615 763072441 543271226 549233944 518662461 602581049 607703326 85345006 526627131 260720060 401517677 977170929 541617774 663248256 449228002 294265777 846703568 341198176 406656211 281054175 158464655 54550682 396302014 803875277 259416506 395898787 919861288 652741616 830325069 444208210 722346695 710745814 3237087 670919142 355700092 497284863 138249537 431473872 281925684 390188035 851644526 896352671 849131657 352876661 635628743 630030513 782876750 682648981 37601934 461029472 308135395 868414802 208268653 320734571 234423092 778515832 385230341 214268391 877692488 726711547 774305101 584099905 945915138 803176024 479748336 949564913 793429028 446311120 783545817 592239184 37049174 259793465 654780514 908150218 219725585 116016145 206607338 951743274 633156619 345554829 997248026 634138694 294457153 774700280 543811469 171767018 218166960 186602492 585691920 638107407 619091209 615526277 588654933 865813815 783313093 652386481 153864920 571821609 109587711 191572836 875516871 707279347 902713923 366518122 418573779 951503741 659457230 872842171 247824741 688546572 715931509 785721459 939638115 140568433 745518531 661736230 689496656 653636301 773516046 42443644 73182878 420839315 705889161 556027636 861921017 619575191 520295214 106979064 522193743 257005558 213362432 954522658 903738433 896049171 452663814 255038441 407546899 108547805 784629303 410010411 863368676 471378784 706237663 831314230 668049348 54575171 212186500 387371391 18905275 837598363 439547543 99449625 25801888 293832867 515406897 987052878 399634205 564617140 573740117 403538572 69176203 252343334 677967750 610009599 372226991 690750559 784870067 409629140 133026552 932461053 665915770 344376376 342051042 15443543 624230914 272783234 999647537 399172412 761722236 370892577 307401855 428995888 830008361 826345562 91883917 955031841 610968742 26346200 117059981 721140268 507977469 840795546 550810964 405308634 59438800 72654814 521903999 601718211 300608265 928339225 990670003 309823860 413736846 640579692 981080460 407296706 22720341 844712586 821183935 735073232 294487217 33015823 66241574 983171988 193313401 665314441 238325046 507322101 406227383 669253018 426962277 328658473 67503755 101142129 20525570 802737963 79041177 859747894 70804423 40577469 694144175 157914986 224686600 928294938 997070524 655699800 950597734 87790717 649478118 335717155 244714114 732962034 775703569 543953007 836953876 465947359 992068998 911260669 15066280 785177331 595786355 477785286 371776768 386165880 693624097 516651627 281727905 574766483 720811102 912351489 754307337 727570310 196933816 125933794 622369067 630610755 444299286 198726576 691768828 175458834 339175018 711304020 955107328 324176858 413212785 20901779 732363312 129527390 259094841 65762685 527866706 403675043 397626935 370343533 453889281 118506180 299828120 881011869 697350746 10783638 472965303 866941022 359298383 780790739 556207831 813786668 924697515 534011069 952205714 319994348 66618126 218286069 252942265 719039959 912639600 416817285 678774938 76733375 120419581 901946086 628566431 894188901 546574031 358554285 796414323 456996931 474814216 633509424 81907998 746483368 645082478 614743084 149222744 578213812 734562229 58685185 905306981 472794441 12388466 611695372 427363768 55867094 903711753 102185911 471816011 206795000 449018463 507369291 324398652 963052588 650901026 944515897 74902701 153596286 626311600 557481244 404369919 702352972 157702772 942729816 785327526 319923456 881073136 917834370 420716165 785104176 28070813 636878503 195540180 112953927 260677946 489888579 478413508 571529873 756702440 411178005 824881243 216071569 149935500 979416046 810884415 505893625 801093725 144345676 80858629 833351512 523928437 739207168 429462727 238112094 465533961 5864301 363770050 950687480 412409970 54744722 35880219 499716219 936616609 340848240 431518047 875130341 67414040 713635635 844609591 890521332 124922103 266687026 755419624 499012585 816876166 181485986 844351092 77567723 914799489 262178530 576311891 113204410 946650917 502283648 309585936 454053546 868095945 228526076 193128349 682430699 729066251 495818780 693135674 367733554 178885031 476332846 404331075 391240750 570764946 687104379 263114908 469048006 144323654 810766167 37092666 151485362 807976293 84092129 960038934 253575447 148879938 572050271 261576540 172060334 660092406 756039086 289543417 242076802 513319462 704096275 984921754 272191668 644768072 196239399 614127681 77705892 187158189 183010618 432682220 594007933 66002728 944427559 72561118 782540612 451345282 195982977 243777943 685256438 817257800 906730388 641880082 735451020 628175352 387490889 489053148 986558789 957172457 71813476 612995839 260171709 729008502 168661718 808112852 578328245 298401330 566613433 524304797 814882965 20982353 390110692 987471585 508807217 93021340 375354090 853935110 887701272 154098164 157844950 57436878 350970515 477782648 271361227 951546241 244474812 691953768 979964473 874711617 103957748 560047828 52285337 534744857 90235822 46718842 27406990 399261203 401980995 467620385 127629638 214587342 377534804 731989199 595960339 934613143 91110448 256136904 339662665 265861795 685390696 358792374 228796134 103826777 815940519 54042730 608153658 854174919 51620305 788113988 249073388 397868522 426260533 707874102 310369615 497508086 681001432 628600312 741195935 120905829 918593945 708472507 356675499 486449755 782431702 48474441 939702401 68652692 30594472 238524403 731516865 932840652 944591859 826405183 387394492 42720758 668361770 787978517 335089267 634202993 295934228 601348160 58310705 358303197 925797380 469825747 264906540 772515174 346016365 141107163 654885320 275916063 431751128 534082384 582145801 341489445 94311104 301821370 861091342 736708180 112263629 917309415 805574486 194482482 442821213 726468202 107011687 139101682 838815589 195581165 697159799 341705415 886444751 353604368 255922585 970482673 445479617 907361357 259257980 951240923 237893305 647362675 6262125 909173 249320563 117239621 849909067 327225438 588983233 921657485 698614885 587453358 706334835 792922556 559912913 975330056 695165267 415224193 918124120 939461564 478296954 688269537 325560540 525028365 933230986 297233580 873870807 155548917 112061828 325022108 957143709 671364709 513487163 613545608 941570491 34232719 718847659 380952057 878188128 970704554 180133198 828064723 671847321 6414726 415025623 352128099 379676270 880162426 26494242 444374466 375599051 717585765 911358359 383829632 597827730 993030872 702397318 807005745 514969370 940856741 544547508 698253694 166892675 499594549 32584431 452482723 241224178 914909366 102636287 95819482 375280938 307941295 780249499 845363739 693505406 717899398 766307230 376309505 517981285 115144252 606705758 673392376 989711935 356646808 789621192 903348307 266923058 544895726 303430297 654060702 279001124 989673196 942432679 226533718 197246826 324760305 323586510 662474782 978261562 834845020 630453484 407846371 794310762 452349298 646582140 597561529 400718486 337906202 127550861 689244879 343228408 281456715 735417957 108137879 876783630 710795986 791183287 606354881 824834472 445537409 626212813 144480428 408004728 840087367 241345648 858208143 337068706 601902115 752288766 646561673 322490543 901125488 34600604 415981893 920682487 925922599 264746075 307845773 108972747 352021132 779975339 740142008 802401750 584441122 962498100 372841237 748478536 676631737 13807137 278797376 622668870 32561277 355213746 657071667 84579906 888814407 512763221 328582495 83000296 945285540 921486634 682676746 254739432 311222060 441733060 654166619 143358408 96941924 404955438 117298047 448550543 872697870 370386316 411138848 766036017 112690292 630038891 981818926 611489259 978458167 91362060 582667594 31021930 919977979 541407643 484019264 474813485 905743416 243174660 226976256 537449880 393133198 114597748 18239453 687668504 654116605 39342879 422735137 216268287 564771716 836831665 758586614 591471805 275333277 474787890 215227195 263864354 821655509 11586744 177879340 806194225 846147506 333623138 508917749 285604564 505355192 660076701 606735228 552757441 804366662 435747189 465063981 686326314 646269590 140749372 246777869 210750227 80425101 141876214 167600668 898344838 79741395 589573235 386933101 405238284 59060058 922598022 20664855 99523908 846917764 82034169 899362663 914938825 682799894 614402123 94155614 777069001 391186167 266909353 888603908 904388795 660662073 162928980 662780817 213790369 68419360 705355593 231367538 712665158 963396391 524180482 907978153 383828351 899195020 609579243 59692032 528460458 967323264 34983076 645551306 673721439 487730594 255578116 545070099 529414953 320340000 739094518 713580033 658397135 463728952 458082710 511201853 415939238 95080439 158743438 342436954 101191325 943334841 347236241 498268920 919938573 947807692 981685690 848111917 422033616 731099517 854584630 430598331 321697387 819606631 8312588 958279245 726539600 804886970 683449251 463523939 415966255 8470580 181512892 154025019 124031023 143721127 956196483 969822201 555618311 980219700 595596298 957086035 543119097 770202509 284715378 77918679 162622107 74725832 844788333 927068009 754705637 409989411 983419995 262686584 687208776 886123022 594844819 351201245 27949995 751545840 783278297 362412325 658325445 773022189 649958763 18734475 297017391 5836553 398281198 717297425 458648032 633804988 607730425 363175212 377406915 992613302 65773678 985611152 781590045 118349861 208269600 902713718 189226538 383282144 753136958 713688184 793607113 733597262 494436030 947646093 74333507 457346151 370560408 836243683 796555343 355590975 351139101 883873507 279025838 797980359 295947211 9142417 372698363 592569303 938002738 841503545 334745804 565254939 343166267 634487364 716527007 169808235 377079414 805480922 781027756 318918534 455963792 8187071 177459179 32226559 230611153 31832690 395097117 927849840 391052578 193071293 964629656 570413856 918500768 481843387 816290352 7056812 605352849 263619030 306311282 666350475 326781194 813795349 123008150 154247825 858911136 361103322 134171640 949613078 469248516 374482047 688728228 851651458 750751950 530546092 900009472 932839770 861107907 738678235 62146738 980188911 18979969 166039123 968912214 324791091 81251540 837771822 146795520 190347009 588901905 165354138 988631319 505192907 844684571 329941079 691756736 130303523 166706510 207348617 586958806 687763744 567116389 920015621 701225873 260283113 792373306 348372261 12074073 519339529 356111441 216980042 801202589 365394559 691397488 788446863 728475015 232704823 37269901 946504648 264450808 33631051 715708435 190021879 778149276 966510689 257455796 917531004 93502530 711990996 808945022 6877959 481463554 958897939 820847993 138839258 409921104 456506046 932369526 248431555 474039468 555253179 885822957 869172850 857074704 353518805 167609411 277670406 931503629 32625212 66609272 695497926 847384809 136856838 888698458 185590231 77746511 134724861 213360777 252003318 716296355 764034488 943753940 988757560 87878869 124423580 939768288 576857818 975664535 372733691 898472896 460361531 26687612 813124388 216463086 112670957 309672001 14832791 187166555 685004727 513734450 545222255 584486641 427395143 440305851 503076315 820284765 622690743 808672725 136547088 139793799 542447758 624738353 503738935 132479962 892168223 59965518 579336642 457456860 15231205 37551687 301580901 621055803 862875476 437470556 866573814 595802057 478494142 665357640 367530033 656978776 533700326 10248861 89857782 132682508 532060014 678552254 542594932 360674776 673011346 661686684 33142500 547192224 336048982 422402126 913772144 504308275 523331412 383495264 757673188 721988201 99283898 138264802 15777662 137427348 383464302 511154428 762334509 881834869 758122389 173355689 495014915 165817597 235392945 914695683 80405039 926081268 646029750 213383871 13192385 501636073 600627977 565241417 593238863 824030917 578551215 515860150 505694667 716848402 817036851 453008048 442724898 233986339 45334868 602807958 521621455 496157502 669775712 880612932 727008778 423847993 344757445 913631367 12069321 660524614 563251719 222500044 920700621 895570111 822527003 688974349 585545112 343062360 22770533 36071682 661380423 67714093 55747918 766674328 298741317 174780509 362114253 109346755 980587958 746500321 585134734 250026617 336144969 985270334 99740528 610258708 880977292 743325245 545335420 162502639 615293638 621114724 839460484 266456315 267087358 300746197 442971956 140091572 288517634 920977836 696071842 540905043 370529321 307136549 516204371 682323770 363602817 736091094 887703678 173240652 383330189 604622997 195183876 300506063 570513878 651917087 472826466 891725525 539074501 985626126 187379555 252001228 925817093 75726895 483866494 196466044 440029621 714639608 248536822 470474059 811523197 432986115 151398149 531479884 798460863 28733011 191850119 507445715 268898078 449353456 181892480 561380397 368500198 300091532 912358722 547656685 832658362 380197656 391610054 171026743 769369349 134547613 859620948 378799943 428053063 969912792 941728096 81282611 969923313 957842510 296314302 189180639 514967572 935117637 326933425 178259768 534559183 478329766 858431095 253977181 501313305 617053103 551120973 855234363 941306683 747180473 745179325 925277002 685920745 564981283 331359032 518543713 92122646 404355810 940541603 825141782 866399174 457716606 42900514 361715230 233664023 790583151 576768716 376343050 853089282 84238203 662393298 184839169 293907085 878526298 989761931 283147568 792651178 543370164 653758666 401058164 520158654 482566699 419024276 677595031 309416543 628138620 735437907 815851107 573123694 606602183 689955607 295190775 110105110 527400658 40796372 778709646 603766941 960151242 904059635 691576002 994866926 432218177 951976957 904321212 525910814 945145926 296481524 790491253 682831673 952201775 356721341 665545940 248923603 604726988 255322461 769506331 33115240 914555270 235935179 139875617 89580690 884409152 777057282 117511550 155651297 394990945 107984016 46227849 418757587 910689177 281435833 574792342 693225481 263225666 676814245 461372881 605319537 840644604 983908255 533857592 328027114 571039336 89237660 713549478 845557292 358229136 668633925 643901458 806514700 384768378 604390582 909402170 563751917 164737200 595355361 342431235 490123956 116993853 760407919 533931703 842575667 204886367 536821483 641042431 352307541 499788095 536861738 240142148 363497765 232455822 475724681 327526994 368011784 497559056 281000797 484701331 315797132 283530743 760187558 875287284 106926711 161149504 996063873 280368534 262460474 825891412 450889451 190129986 646523878 216876556 244590657 527872152 948592248 153867068 84371972 153581909 348825998 482815184 379388432 464743195 121788703 938744711 100735047 265566284 877532629 235578609 790815296 614741764 883612500 763600850 648455091 686780031 163761169 12082343 423243790 398436854 61759122 171623761 574191258 803315022 284961962 470607472 355168685 525538346 899217171 872548451 144569354 531090571 940695895 429397744 173802594 956414793 413395605 509383678 380194565 249755266 803748120 313781306 343321290 970899320 687442045 240640864 622704804 425263324 484649579 532294729 476773187 641301882 575067967 98548759 890847189 599125081 277489342 340806909 468838836 405164950 258500477 340571977 378456072 523687977 636076251 100763224 879257012 291563503 821822321 925039622 17112325 269939072 411542610 985515519 650640021 743542087 719432190 94958212 819417707 942287241 673358221 488775156 67767046 65434815 175681377 660200464 172288416 58539822 143619512 176315322 950116940 119147976 630291531 898905675 454119755 103874324 378781351 28282405 745995376 539293922 940101852 48041075 83344736 689531755 833620073 439001157 31838016 88454052 970905572 11878946 472105735 652034016 676071268 916100090 737427580 64370307 615584895 512089681 150833098 184991253 980638948 553242774 408659466 337113674 473229570 844310753 805082240 182337300 447733819 530775638 887333447 897230707 134840625 505335912 697918083 464230188 84061058 917652521 762407901 247077414 745778983 780072305 192205310 211668629 790905845 518140882 47303608 384150950 571740873 617878797 163509856 397941304 972628052 525665076 868095494 907142279 99698833 399038338 858287717 759482706 875169623 199135359 889602916 859830454 238818923 617581267 371842779 257105603 935201949 263236519 498810003 77724147 129953048 526185214 583654563 362078428 130824613 465987642 719681803 105354672 278842391 885639234 437267441 682040963 135223862 683517962 231363563 903325065 69795809 445298695 519620891 766329631 504961911 100566161 721441788 64872187 869995440 811949372 637320366 81097108 271376366 837240875 511601176 6789797 339982656 353596683 559371762 253945360 32367413 811571168 940000242 859272792 348463692 168212730 444069221 648611041 837981544 121726710 559142534 752147346 754435969 409363266 735687071 937477014 655555622 757871801 865147738 188955954 451569852 97687177 271978210 741441393 166338968 908933260 565604756 765125184 86128373 363811679 604885511 222622203 908989528 283396142 143910754 908719975 484897755 369494949 473050363 887620311 800687911 372639290 458372635 541754241 284719604 385281714 965899110 194800554 751322179 93198858 272168850 471792219 121319521 451870125 798773474 779872866 722137690 522920291 170844483 844698030 447279367 113285538 929624896 448102413 96904200 857907510 923031590 220650116 437522390 241067311 590887275 817920163 5453454 228018529 594881800 684705573 801646546 118265337 927682281 927842120 347676327 356589769 143660504 586955708 735898999 316591343 422675033 799569490 723994345 727436849 702303851 86401897 301533881 818901970 27493491 520716398 384843159 541259367 674052574 362880826 19536776 592618447 192689626 495327055 851289045 376681522 483430938 681313489 862608875 480195062 642669963 178100271 756428660 190659458 905409147 821868259 835230978 952480617 166141917 670158211 325992754 20979702 155775183 46069317 732442985 812471360 768063470 250142532 199556262 119551280 741256430 917233210 836996402 317440000 280243555 821676063 993996837 838666483 548815426 414754746 198630557 75539342 469460623 729231030 404947112 986062434 707001837 592534001 432440097 366535398 669248613 339508011 399494378 145705261 980859989 669907663 39237028 392673069 927972312 443083281 793202587 383892981 661393783 280423890 125358195 673550718 966638136 105795262 505520845 490812850 821587040 249155207 726691892 245998846 663748697 847417586 152614608 586178049 30597619 670581320 273872605 801824069 936925139 248479969 462365424 9302769 9877455 150997462 640635207 366095712 622484211 140904854 11525739 961195298 899043306 361078791 375488164 713980137 783782778 377589066 193821750 817407054 678096246 548240391 28879752 779918547 468205042 630179732 285504291 517381843 534941439 845898455 291782143 181402762 889975367 218460721 838419768 710921626 101387923 326507168 502747531 650920413 824332548 876738958 802592058 319242292 73730975 7027375 652988638 3306856 145161193 666682871 849755618 251755318 135247857 53054977 338780765 30846594 703709269 325909454 298039191 216032853 747366100 123134859 433455675 829653789 385699394 624295355 19118081 306040926 634757826 207575921 923096575 548990949 290680893 812328401 805471719 115857622 942678543 519745671 868212749 24990452 54743639 157087008 541957348 29802004 747912194 720440178 342671249 79034951 345221627 518852724 778485247 800816254 443264094 73593447 576819116 778092098 145904857 165626195 798845706 78476655 802908977 951768595 576769980 616465242 162050223 959298598 896613292 334332897 628503865 926071417 353333652 841833135 113067819 342908087 321204833 878713032 302675462 877681187 5072519 709786937 864681437 287675298 438509742 923916588 173858783 524158702 279950432 864766926 234859700 598951243 312400798 574964783 708701649 982265408 213792822 513260083 37968169 877482878 793008411 391101598 788148957 946048215 449110914 358118213 813262579 40295154 412435586 696293730 916157356 773766737 77834180 816609982 611993852 52848174 79308646 569013415 760314312 434363364 326094788 117069898 291928423 420548207 313574622 713938560 946618620 649758992 560408899 467126583 973901258 715826237 533798580 282082642 990426754 186188885 621682710 560985592 264365666 783398569 738565671 937879477 449325895 728726506 464265847 557973955 440905227 386341387 477456006 316642595 737446075 278897166 987794434 985657057 651401350 824984408 153275970 586080160 880454393 181296 437909222 869495591 582661071 413722214 658788902 470212269 866247681 336444306 868280607 249373128 921710611 637323937 515057743 574344931 741080917 335726768 92856347 750940416 656364807 180672609 288140498 345806237 786006843 384175750 90298812 622616768 890726473 827276495 762763384 172400903 651490323 501685559 532324921 362202326 702190598 261755536 988747004 662525213 732173625 135639853 698024878 657375438 884837691 294815181 123379123 335981955 249929389 479799607 433639568 178409183 217886720 283882325 557469399 710372333 841225286 972964183 245958123 98922699 178296965 402582677 830964668 74796977 204975434 449107023 914421534 914588771 828798234 970942938 489247538 417977283 85009596 152635757 20822603 172044575 683288647 432474289 731177958 583278471 987191204 178638468 491738134 665028915 109472810 280928273 440106716 863612487 974312860 92669975 582864525 184080363 690903016 882818531 383920739 730761415 792487115 28695100 876792387 47087447 97731230 503082455 591802867 973455160 401729193 849210148 743046887 997952823 221557375 805712766 638034085 33998578 790052303 20849043 132010134 925396359 600434818 503987525 100399584 795101981 42826617 711444487 779414781 20578030 711162765 446145375 192181792 280666429 345803303 749164065 523196020 928358452 932731550 803790570 103667047 418853245 810604873 72457868 61629362 22384417 574462590 558049724 793534151 560881051 844514142 619402478 574051628 988684916 866982257 971512633 517424829 978593095 27411132 642775254 706564262 262062198 997097651 458370927 857452216 686262819 709683903 84753441 480454880 335024556 386320454 938430899 196863397 112236524 270568353 885239583 765331225 329456672 523808481 721159990 875034027 913395609 275512341 342987724 16175207 422032377 512112637 586140764 47395285 868257198 356078037 671441656 290295261 133436723 631151779 631528267 421185560 180772397 687504248 129093419 391423978 34481253 969792576 207289252 810885636 908017238 209509863 609759777 863201155 988605620 405871993 460588287 23151024 905370749 121355563 769746810 908224140 241588435 220917055 593613706 182269873 973038139 436556725 878806820 271882406 257410722 540684599 734353017 537383663 852656325 70586656 325355461 743697472 932321588 504410416 62364357 65006105 210018015 85447638 677209790 650105619 570959126 284323764 872606639 502005548 134728986 792780871 106950756 258860126 703179005 495519846 314046359 63620646 409714252 754954438 370424618 605953128 924276750 336961060 958238249 141091411 314659205 364561023 706047104 42630502 720221980 972638516 922030329 604606600 194194351 950350988 499182933 801721851 30052559 985557043 385274162 948477215 297828298 842564926 162595517 129570373 532062696 971648992 381158535 310598512 724120648 802857183 532913641 299831807 782022742 665509338 258444991 691337341 594856543 892579034 34200597 208345458 859870274 951853982 822341608 989420887 25322430 234563239 883273490 54570076 552380531 58530217 490147816 304920770 109372117 323776640 98755079 873619246 184885668 804796705 275788274 795945527 191484232 616509780 98738092 359348317 647194724 22732069 921407040 836421849 896256236 563214480 765576020 971211295 301518223 100554850 692477288 988889985 284297404 253170050 95764991 499849603 642973409 670320823 539394647 694744655 268287761 219268584 641913551 446662849 574639646 157660407 111814477 249642740 398143647 967105709 957361241 667523253 649610970 139008174 476207068 519500481 641610465 480268754 592483668 795136299 223509229 216191132 317029856 739170462 981710300 113153259 655205266 385746989 256972664 329964301 108307597 224325516 295924947 568937499 353740592 748624875 899313496 481492487 753875823 179521030 284957065 369953723 692175660 74344651 781252256 304663760 909971077 355171893 331485567 3232649 114209805 76900663 761851544 155407968 343312246 393903651 314403178 10488989 466644144 658160396 392989778 588758839 929641781 282739072 637207722 633526799 667779315 316189828 316726514 325786326 479935493 357036351 784690525 951065883 301239324 114987039 596258939 853339748 468977333 695325318 896034826 947802589 413252802 768603295 763451891 756056437 396441549 183286478 486012495 451552531 94645482 855237875 138606400 627707650 181526903 853644125 137108098 375882571 645549162 101086915 518707864 764727049 4450785 763958341 971194583 844825815 494387509 62039260 756207853 943496240 920918633 181111922 828485706 466934776 320459077 229018219 963177762 154075935 350771856 475273643 991883258 641858277 179901838 952446788 634708602 299718167 946301919 321337262 252435422 402899017 805251018 41695348 561588413 537249862 341272503 126382725 979512563 201374470 455940348 45382659 736882386 35796178 985685045 38581362 742845208 719348061 571169168 28645724 290378895 674235003 806612088 413796639 534305206 703605640 989837811 537018823 117900243 986833620 645272114 637258749 133185543 382813220 167406544 576678433 957816137 390235837 496304490 202261920 721223332 936760384 111259745 467326484 464618048 402842047 197681799 143438470 431991132 119827771 240955161 293926856 777827339 212093618 28874305 869821354 410800213 238558076 865514132 952592607 242787637 905475117 407524091 369389379 494802837 772572695 956451426 764146270 168524008 773799704 554745906 871763465 72637920 926791426 493204633 723516002 726383805 341436277 653892284 336976969 612552639 733982980 41255602 264209231 973313021 252998366 459757723 519573529 600164056 602652483 160323376 688479004 825244608 852803043 363716978 819616979 282238703 859814185 389646726 914678563 367996218 920278448 176930727 551634477 517300958 366038979 247972664 801137029 466835475 52933421 333060197 818406017 613406463 910289373 9316070 633054863 292142343 522379477 232857621 252492249 224929409 969448221 83605252 511080063 15389199 956146218 879714992 81902818 501023087 514388622 624342888 515268592 523490321 920399427 803536842 427769874 176982477 708371403 52544430 112047652 248860763 819604362 155729277 484763909 365898955 734706375 741837289 916754676 392280113 146857206 429971002 635842735 919706954 701175244 210444492 223948323 564367470 449989609 506941133 917745234 885680949 754420451 66078339 438864555 287278990 562581027 95755983 218384756 143970337 444409315 471073920 12400046 808574638 667979790 573258995 940364722 165386104 715007466 414899830 199969368 573549390 31989873 672140387 981999658 504028106 42011136 105795062 236591027 819978518 382808239 145507308 186228062 618598955 299009077 121633222 572777869 225662943 141125713 256239559 673438980 548545532 34373588 925887015 581399159 110362777 410977077 84847041 502784352 508233071 66951865 461101456 207251990 61201088 572184482 748601286 29386053 645854609 595731910 571309253 227873020 869628185 530980785 517465732 189334123 681017957 803941310 57487776 868023366 987907761 399772923 975832519 490411382 230376003 429275113 4975454 657421736 78593229 922311232 942867440 312681689 113324128 670989000 906304740 869992033 675972665 293428829 515356228 571157209 337958532 202483488 981467237 491417138 832026862 933719873 313845999 860505159 770656116 309525085 484491815 909945693 10941415 683297134 851420256 540815650 936802392 906629506 776245468 957117165 912214064 267284841 599836250 69937331 606810363 513901346 348602630 120867135 731506075 360622978 326837958 686337769 334836907 186495715 746883731 157727159 610683192 856802244 904005589 691486579 613318331 189772402 961154307 6264358 91501479 430663953 296355512 467634580 644979652 730772783 202322043 594310513 207699191 405231141 441369085 500228809 199041088 10010192 671238214 677010255 804971859 660440860 598563383 569108406 180324784 729582148 591498967 352123425 484560252 271522592 300849815 113974668 691390831 15412655 749166049 271105432 23761858 163361945 302519326 998346209 109247722 216942620 791136753 285714051 800996044 593584490 405248844 184277414 753992320 937658107 328760151 76343951 845088758 144904582 625601191 139273548 428258307 652755131 724930965 798619069 177838769 79481649 712523262 262866169 399420494 924562239 503385236 908256963 727377946 887845513 212990532 672961029 242306114 911482013 834237328 852550412 880312472 571547472 853433324 105634680 346324645 9727209 210710285 361327942 13686965 17096092 904373163 722589668 762937094 898550872 411748860 793632967 853652113 542873268 350070029 822569752 774628919 345551640 365507322 709453884 835007787 460912334 109819325 88682865 329264536 633574403 919650237 264129110 271101442 8291163 351708132 456362559 786511305 820254843 318723585 354419072 884070682 949783717 605923750 644905786 972740929 591343573 743556576 659863344 679489487 663655775 411640552 422093953 22969286 308384152 111635679 787475922 48970835 706106580 10187331 452550876 680781665 451825467 809433091 475415052 9567006 607908227 627160060 460704689 114088931 100761235 648917881 975583718 384819037 665635353 11558176 298966423 365797199 458136894 348739432 188175060 422271696 182241719 596879254 875571317 544581341 348177148 245049881 131299140 674467000 221066870 612491779 375707457 40464126 860047301 572440264 443214775 635249870 65608986 599750747 187852306 831927639 533794136 573979104 805942293 31064314 831812095 480015466 956208323 960648071 26932940 177253208 427090380 737116351 235902584 374494206 127220936 384796222 424702240 551498009 907593587 615581516 404969191 302328812 888669368 400597205 685588954 305885667 694786153 733952348 104671506 217947139 95057254 714049284 361166182 926360355 418445916 307634377 410952592 830169213 25965111 214764756 786486384 852169401 727118897 650697471 556847828 446291547 151629409 578597696 818820193 181581474 773722986 264999720 558355720 762375519 726664426 243249338 102761032 521682158 742011249 823274404 854617635 35698125 949750490 132147873 309279916 918407674 225488700 612715581 634219391 139163897 884810932 824375132 52160654 367370979 214914038 687821601 18506523 500762184 295144664 364020568 586344150 30963520 703551559 46896439 641175714 518693701 549984268 120627623 467318013 142160291 605509353 95834909 329376877 537760735 517054668 438937269 275099614 638433468 379432079 838205788 744897356 742500724 538939263 864109141 559150377 438112501 657072013 791388099 361213139 777155086 431156769 154576974 716047918 151560334 679289745 816838199 200385515 167370805 535956360 679770229 766686007 209160022 154720292 38814441 856235965 789289749 909344937 675500277 729967187 737669158 622734709 962934972 33975834 18271978 414252174 334889408 356971040 520768384 375329645 15611723 77453414 82110007 357496722 10726883 17708305 247169454 761820469 553739839 483205015 165172625 573362059 87957628 275356179 267612895 548828669 491114582 739091584 58555835 922753391 339914777 159660192 645428997 273747511 774867283 800969585 833670157 530997611 521033242 537480042 625480788 775280505 719914443 938326219 683401763 898089910 464101874 100382793 385403077 904858545 207493113 511182107 918501149 151596393 879666285 668962859 763148943 901198066 804915987 291617065 931347162 282195924 244918459 509510803 37701495 394254602 877690322 984961081 938949195 494736574 325362966 603914111 436560441 131705293 540385651 18149076 643459127 648131705 604534107 241133503 225524557 502572577 5180186 206009855 594516344 381081645 964880740 794838648 650659488 643603567 285328668 844890182 186820583 811073501 57755940 599275196 396267493 557290931 991590839 983509367 207823019 517757978 372993099 493995476 294936286 911407523 320899891 23233867 939926225 779287272 936349011 236416499 277889184 26359697 854035226 244890746 558160188 979632062 134058377 700717962 439083769 897620806 994011709 469609511 195065936 63868903 10296585 821551978 901641852 166748169 887923617 311791766 547957901 116011813 22907503 202058758 446620188 264858127 207157233 944332624 737551155 832829794 135410775 18847978 300080091 975411871 169732202 240589522 85364030 865782115 166024998 919971986 675545512 784479744 53447289 477683569 412043741 622094743 710406726 826474249 54709531 767115568 239658912 696920549 25752459 318384362 114283849 51529073 38019561 971983942 891618523 6024018 661946805 536437606 54385744 106854513 869687291 741362025 72428281 560396461 189920362 356419982 40708294 979073374 910490083 944147503 454341375 52934993 553005533 496587069 359500441 751095364 644524398 665541740 530821157 824251957 342714693 813126377 185465058 209707813 159765371 463061684 872795972 210022912 410321638 901991961 169319013 768067333 799859831 82192197 718189265 449303834 701876032 244907758 274942484 546045976 601003416 751273469 211644658 139988457 556131568 385093925 214685956 187760401 13027671 436427120 195419214 992116889 300197422 215055338 701670789 272862354 217210690 148273646 818571315 732309329 526930806 627763992 241491182 272035652 140717983 184666577 602827503 836863059 170990722 671260933 494668962 330791038 296173475 617145587 128881820 221777508 364022192 874876935 801232314 390671248 152789067 822139493 184936283 645096509 392052567 734393103 781570384 495401137 576800851 328051309 552939184 205653510 19909125 873671531 88159280 639868867 835789029 672364134 463633239 872391791 118915220 594318702 72794441 459015569 451235484 718558197 12339953 689111181 834525923 591865047 937743504 752687862 977545845 289802993 698971641 458438257 569126847 115094875 465247661 425005074 270002835 977426803 416632547 771085899 149297946 697475276 82861830 47976717 220365207 552319377 246215239 889393600 592565268 533759955 803259109 677780701 382687735 54389509 561521964 55235416 135271726 223709214 201584517 551504853 407030302 850127597 738927804 394804836 623894410 718609506 445121979 91914935 39079915 731687142 785254747 163532166 101937702 789001390 943662167 897997749 42634534 648767193 258244238 311046258 609591266 664416563 891774414 487311936 716395854 56688555 377164381 158730401 161818160 461643919 893431505 963025831 286826174 604436763 459258903 648814978 365102962 472947355 547141136 917251838 779546472 301722267 703988040 298471520 512434044 892156322 744157470 990870020 964524069 554926270 56032681 741338171 642916822 624742483 278135749 365439598 5579032 659865771 84859229 320896034 278043329 261922562 342144352 743383625 792757688 189643904 443522639 647512128 790904989 485796560 363527648 545368090 555194431 234369108 722886491 951209214 514540082 65947761 297878803 944288549 669886450 81676799 326634607 219124355 584729128 909094779 99760937 247250460 602659307 598004200 523874329 79037976 86689210 166776390 386750712 252562558 215943331 24379813 343064732 358434619 475084195 825895580 316954106 986512513 588741203 770153707 383361516 479443361 73014505 528229191 420349087 90546220 11214300 165660545 719325594 462708544 322491938 595177570 332640435 655622437 630044838 353350996 63325520 342761822 666097120 549738640 222255619 78941630 285006986 938304476 882877188 274821296 544421314 368848547 617778027 98644339 217406079 621636201 775269935 677052000 327079927 276767696 571326598 98121447 581952280 643591771 393467108 976602441 394569646 427155065 999733597 863208801 788597685 391078804 27168923 851098901 645133653 688072299 797316024 662445466 933063679 958254939 1055223 386116840 411972673 411784099 217452212 157403393 640068346 764925892 696692409 806978471 651493293 893582714 998692974 522727318 386882907 744265267 376104182 636427138 358126416 469104993 987126888 988735677 443460834 830336309 211037067 610226807 489580792 962159081 917600155 45320233 941710280 694187047 269255041 476732037 924742003 949386565 760692361 164567326 492054983 633894930 742687593 573360547 434468618 624060585 846138838 65073609 769768376 658757735 31478586 869317402 739109686 476795020 349248059 215645710 561361471 385759106 362498752 888710322 887498691 629804799 290537729 647494137 153865417 87570217 933887175 748952799 78666936 909869852 663843017 580175376 97109292 519983751 916572659 625741365 395611050 306485703 830055119 565378227 13506622 334570202 222681526 159011320 826368730 724807576 998730995 789693858 567742903 730351125 190476667 789079042 689236835 460663238 639347331 736759628 581266583 431815255 639738786 502951914 656705253 793559890 249822328 516985146 781311293 936017650 187405314 211605212 262867979 229872221 900054496 196808117 219150011 173485698 106590603 705847380 197473304 612073803 972166425 406674149 962901758 490575638 230832954 388290008 611195702 513691933 116802903 33510179 643370441 704039158 93050264 199440568 122037210 483841668 364747605 638412646 629772997 478745136 414422486 990650774 443879639 841287545 293024025 387701128 432485785 406724423 771193053 716912416 659604867 520066929 689488099 416681369 50683434 296950578 33613186 641062331 478243700 824376810 191558130 925744110 989309464 76896808 409995901 677099007 702275726 44655157 408083938 516770802 402222223 847914220 350956583 784124147 504431956 48959814 837740969 2598932 115341039 331177013 201617215 458922604 148897807 984535863 498322434 983244883 170187852 233767591 320090438 848052507 399706525 28934663 102476543 689413708 539049962 503064409 619002883 952656417 314391543 86461054 656676545 808960696 143632261 794510827 381245315 687117628 906203065 291402769 924742964 306805803 477283631 272883268 212707058 979418215 142404272 992902818 248019436 769119950 183755232 613130159 773581734 893494685 911062802 108725165 659876963 583990822 681274310 65075615 341359207 721935553 934204905 258061114 293967692 103020994 307760312 103537233 197335663 313748887 999137250 319047724 249699258 574592948 824279321 109818670 788093750 14097528 176327655 474344033 489724433 483793779 240596219 771199382 530186257 326442287 112199904 232011399 650093072 192192786 795099046 711069514 285281708 346655903 402547145 919082416 384296292 719305909 343467213 445715212 251877239 223588054 518934784 524237868 883909828 441315099 116827213 999525147 359354469 121466001 249207383 864790719 286881246 125303695 152970669 687629849 821690377 772880088 913222795 537371485 800786718 860269878 908978770 342618004 45101384 841705278 454771535 236769200 880494144 845907237 345319016 846460881 478636406 348328970 84263891 568588141 685062313 18823172 669176970 951622023 806916247 316732261 654360004 654155956 52310356 400252148 420850238 147278898 647487867 915161070 21543050 411912668 46613615 731809501 143894847 173263658 346177443 428839975 824887933 808628849 534522698 395917801 672490390 678638580 351494522 820159449 175853671 258000749 279077237 306773064 204364347 764157690 365533102 178244498 590851346 225466586 702115217 410793014 895254428 132070180 285325860 521726625 246578961 796732194 605483297 119130393 639577952 241946492 979606465 637580239 485526495 958778247 831607395 917002974 796859970 852686765 739320615 671016206 364079422 56048886 971388827 172179867 173141325 839200289 318190860 343577815 621752874 41621556 817779803 369617011 348331226 256136036 51430075 220689319 343892881 716264556 758302492 812092318 618352856 311170778 984278427 661580638 382602655 681495382 245579474 927102560 512550886 210221559 213583772 753691998 387575333 407252155 845842079 271511850 139996088 951951778 371900090 295673534 357979479 128725297 681156608 472482166 384542878 490496513 155643085 637698222 474061655 777017674 931796808 463498828 545880676 736001766 799985108 398145258 558607020 62281112 41709077 346034721 534000638 1165684 835028646 264642344 384733923 129788086 584288148 190607782 426875172 434646893 803910157 645454026 80975023 746684562 446052341 52427435 16795537 516100076 347941907 907663887 279088017 366988205 118712783 373252306 928159687 850283758 217893990 708953765 727387657 492300882 591106414 209032432 790405134 51873052 856014575 850063428 395579783 78291664 323287700 157297876 656384431 244636274 342286857 237377737 573437927 362216055 679434253 541146088 409407542 916541564 716543277 248884862 538091608 325262270 392436673 500047064 280826471 421937231 425546720 589188531 809492992 316656523 528086231 820606720 665630964 689697527 931903703 972486562 419230259 324493420 355207222 703223063 736443792 330356281 283091936 499388077 43407868 792711961 120545276 40268871 675385752 178888840 643009564 1961716 24348223 115681680 398027610 89459334 512572639 175814272 709607592 818033679 937736992 979157732 667637801 464004789 271353088 888803776 430320595 955965781 900796792 947132199 726866766 85689169 847161238 545256175 579568447 207277186 461028944 235156809 219346350 714983462 936944517 558924581 860622495 891441942 361412873 530748507 665303361 835062386 92493777 767906364 554144719 720757315 110664840 636200096 993746391 597711768 394583444 373026580 730271193 45458758 800094352 943721540 527189518 632639998 467976958 601194396 853865730 970953931 630067109 588287872 458308283 859518023 281287708 586184917 951371921 256121712 290919851 916449993 22628232 732874431 700090633 128188208 134389237 417050720 744412289 437420416 596020065 545193068 184824155 103554250 173383041 516863005 239388890 80645951 884090489 653273278 573451120 43967006 83681399 647015290 289466146 239750442 996834893 993294865 332136628 470017459 350594699 264924568 111675291 356523795 938936893 111757267 776249325 433983725 161760602 745019268 605251030 190227503 745186564 365330328 20332777 219813250 322348903 989569149 161534571 969082394 756970635 49913720 416671513 701583584 470201090 623433791 945748729 716063130 639057864 906883323 168286853 970457302 572648185 502954469 384805452 3161235 325720204 721931862 542216349 777855035 761289325 206402880 919972836 912122828 584422719 950998892 640622105 343607430 438752608 912739496 8622421 510701384 698330180 654827228 541565276 636294291 167675755 155215366 442690780 520561377 329890235 908157046 240645975 24955525 571878665 886093955 928878318 29848811 408126281 293013848 795256719 889874796 961510673 113122269 878007478 432496735 247088507 503752515 688349051 779818996 56152063 759386786 375877992 804189818 812535638 219319875 198457653 735365968 789191089 14486853 27533387 619238953 514267153 702554936 17486121 425468330 934282299 36456585 107117330 28455308 372669466 772269732 111054518 978917764 396410597 60938142 489208535 745271928 517491093 515588280 5438367 34592106 601860623 408914919 631841219 53389470 59557765 612772624 690867703 169453410 161298037 292162802 596667424 703756504 382497510 565736442 434567400 893158254 274833346 42156005 81306926 298065196 321648850 60289412 395910112 660146094 507856160 499998982 564224762 289994041 956409801 626579745 328080868 203071882 983325393 928917208 711197861 510922051 752125156 151625035 500309671 881964119 888680819 176651200 271569657 686120119 269094695 259961409 493154497 583319188 242643746 441914797 621349332 458995681 31389810 316390194 999575532 571648158 535598753 354229460 768846637 74773797 473771908 953918635 251973590 116761831 463472457 663775501 48597903 692715352 347102767 715941401 67424715 14328644 623350217 802659816 558703154 237026243 681302879 421065902 379645004 880482351 107781032 176300136 821234126 892727294 202025261 234361034 726136646 521712250 672618060 784033104 826632898 7969462 134405448 899984712 360299331 503656460 746980345 127461458 778788480 287650690 782451337 666482236 816120260 266425314 742836201 842767052 366614058 861492660 485741107 475419243 131295548 543495799 717885135 462372413 485257365 678539810 107507624 462132515 30884095 104181275 919290262 232390236 81144245 638061770 323795214 85615872 887917583 743588205 835963652 528217700 407159909 898780446 295396747 985886323 341001790 51079399 447200501 482850827 790029403 594117048 26996210 798111044 640708168 208126052 595007587 229546404 45019525 529383021 881015014 763876798 142308868 31041349 165098933 775991050 161725738 425782301 297272019 726823687 525769210 638204328 69571415 522981518 660972469 919573305 236312912 18082818 939674322 789915783 54821795 401596417 440669309 666153145 721118180 376485496 505530588 221528019 374819569 246738016 121647763 809624307 121097550 914854921 684622039 557588489 715759912 775459288 793489436 613191144 946642979 803852321 662816860 418837839 56735989 450137646 608203350 659070672 733268669 589925155 228912354 815201872 279398383 669291937 631610413 361230932 940184264 634654737 93459376 223461573 621164340 757842711 769667928 605001738 937967059 316691155 825682773 996120971 751276792 910536621 886217913 669243531 884893760 578781146 482104811 787119251 31137021 45045129 903749946 86285834 360406174 206265968 79780369 161546028 177764980 229539027 541638091 968259042 136730871 155292680 340798754 855942864 807053492 732752809 45304126 175303751 682403511 566448020 753894133 656668049 594437072 603350165 725797950 958755148 580271306 766675674 685348346 924510040 336182755 829610998 608762572 519052624 143884301 513227325 731895849 500191416 67118544 200217934 980812893 344148564 996041626 395211860 17813902 864202579 155338911 34719160 306890714 683341144 240159881 954514909 36282259 734349285 503209307 727020317 540649211 26902963 509080525 180087109 265627910 739034780 790425266 386862181 488057331 624528886 970409912 170580970 869455694 78537938 37660389 643067402 733395673 468722895 533579047 990794867 286667685 980506291 360680763 405685658 404110723 823384586 578770725 467664886 887004849 466428947 694235040 422562948 45880436 188959534 792701279 648323570 378521729 594094500 392689336 377559415 842837336 947545516 254024426 744478694 771493376 611849769 423874617 648671756 69099457 458130699 365464694 980873679 950366763 746191956 491588509 533804466 346425922 295439551 300348524 124506192 419207770 774925189 328714200 182839380 734323540 822200312 428277124 385054198 306944036 932471740 585905268 16198118 497191308 628848504 629460737 609915941 45048253 309757443 227330090 82174972 318976734 426528520 953265554 307294325 793423761 779811441 457174818 784366068 765268251 869266865 513049871 318202006 780358275 623163568 953748538 286747618 97703187 461521941 768023613 534373534 613731852 728903490 876333693 600240198 206575690 778876954 485580205 127502535 757732130 844245548 295479306 94600674 417220300 912762654 517100284 785082296 285475386 34646594 27077780 138476385 795214033 572549077 310470372 998928527 642487790 439046374 187160717 511067511 74324180 94549261 711618443 805445784 924051565 412378831 458600501 997690610 957043905 418802930 108231525 432016917 605355663 406800918 582662923 35916500 176620631 518390275 850457803 964970569 432796896 104223665 940993672 662645340 56562063 64991055 967694110 76253214 527476773 132308247 654720722 749246688 884703155 509058074 39253711 109516746 883816234 414709845 781517914 690186384 813869363 707595148 145764864 624475437 498515565 739706746 755439093 436903888 994493800 35647523 673359866 28804630 546135377 969405518 130451216 659329508 315339330 48498010 60067451 378633227 143424611 972714470 476334050 773400569 42118059 450927397 2387015 586669197 568324538 239838084 295976732 130009124 956251401 374815889 485480206 607785133 967752311 282615337 638980780 715399618 931997632 656579985 62466366 677238305 9893817 114723920 150856715 991255302 414178641 657208710 814631572 837417726 270839184 113180789 236242132 868991709 174450523 269856541 470171180 320286477 895656230 88119640 321185826 555553464 742251788 973279773 46870718 364133396 979726552 433386457 167492498 263395620 229538731 723535996 711118921 246181228 767319489 450875789 245534072 360598319 706411405 482291669 704675314 886166134 436773139 683950205 310921075 666582215 318967657 368799526 772650710 709997655 214815015 831222334 988554484 491767410 593063723 365574293 221708653 452463027 368876004 664609210 299324086 327689911 4471825 699187546 677817466 478607657 982317449 357075305 583870808 859180704 859948830 206745470 219236920 305541052 525495565 492599954 940815233 345749287 629360849 717246107 272289867 404799791 336892795 885413758 157714846 335387249 347604697 61909828 37522435 90616910 690979963 918653646 469802773 482244053 684455607 409008126 448890539 113839144 745776114 894300136 839745032 300397664 506888227 251952696 615838117 995564962 69123337 535910213 809809934 420079450 774865729 995390307 876516577 989327393 179130637 723872416 386473811 311044950 405418639 692392711 760736035 2563133 829080643 724291607 139257809 64471665 110061462 394108972 371946423 242230329 853015783 118557361 948989073 550260198 927744377 985076701 284456780 327122573 682691767 182364185 106299410 110998024 736775374 982852877 904093847 930681539 858768133 155127316 716263865 75089910 261371031 103960305 67114182 987963255 273366398 498439666 244188393 388378308 310069375 505725001 285379972 257891805 48360332 590801305 594469681 35051843 38927717 940242591 517451843 515461112 276345478 916722396 751079655 591846106 584424278 578297311 558544831 561345821 135467250 915529511 221005877 417961458 276094622 46397596 15784616 423783624 352293101 993501218 460951475 657827585 798609355 77968389 354764814 404479754 205344340 879510873 572419461 160860720 732049196 169622907 277493149 178650139 285856342 194131436 335351056 186261119 882639890 140225082 419788581 588924942 580021559 144116431 733141237 946633543 133325474 274480995 248953415 78941940 485661043 983910222 2917422 93577483 853423594 692820562 554822063 657391530 857713556 198937138 112338593 653375916 90398175 958308891 977821550 791314051 178637618 396515303 662360751 184242440 20910713 402258625 973589635 555614763 605821351 172569835 695332136 856910398 335202421 69348715 121691837 205156556 603751206 929798131 554925058 986161187 720479290 693207665 173896657 174408755 652182322 562080953 910805030 492896746 820230319 859991099 359793727 12042534 840956473 829160393 416306472 513784003 91899111 783235994 876455456 396083688 978952024 63818788 896928894 225771290 269547686 604575457 590970295 954182987 938668598 756452820 909771851 791495152 263928552 417162804 665118101 860450613 535219357 804981129 940798854 958316630 116571349 360940592 342391217 411990136 611802705 506262842 94200494 390793606 574734498 970768486 361288711 185765536 258882346 74241894 663540703 666670135 142126843 409960593 291899445 806856097 887025800 716010542 669915556 547493238 914327016 697830331 987621199 606798004 254922152 545678957 135658392 286032319 306972594 383575195 401178098 301581452 884794643 417677877 951044831 25124594 300648446 425497200 438622062 998635897 345411208 373539806 472237307 74752416 228501012 176466842 380820079 406885687 775312926 825929087 643327271 546390833 262079681 429201318 231826534 191472160 276972889 856981566 119194250 767704060 456160566 935186214 906162960 731966156 892248462 148603866 537404754 957352416 976871834 178395808 663461546 614390784 457786481 599162891 587389997 876507752 334006913 97017877 967479157 141335355 176740806 557486496 286017597 790261295 665063139 459935930 755760340 494478130 995086649 23482630 837184959 187819543 348015037 473521612 413987617 298689533 683615870 733782944 271946524 81384558 650856242 142068923 117554137 110951135 74458132 176736979 336790012 93518449 943567247 866060190 450092790 396248807 568446625 860991598 539779127 902844741 732088743 510285549 549133489 859831428 449928031 44970245 889324152 469607280 738853666 941244049 912812916 109526130 15994014 14845966 720057204 120536956 243138386 216173714 86204941 75816035 662775537 682180645 968389108 730197104 797527455 880585964 963386864 200280430 922450056 127537287 493593308 716217713 390630965 379303441 119482937 281455285 792352942 453115157 74517775 651543154 974242553 67705199 59833709 800946982 397226515 675221796 538736046 19112855 935819691 837027155 561726578 763672583 386250667 151370380 764653200 217448968 432603280 340075875 356165206 804704998 428931849 47877265 13941164 355927625 26133785 323467013 678225971 758393680 361925825 76619440 622255698 435325477 667263915 197550598 916548324 170201956 809777100 3696839 907552788 861946233 210488042 956188694 822475599 43777501 458022382 991737744 940389544 248184577 577279380 9620105 739038259 171537365 842509226 465462792 796072826 147683331 208204314 667481856 380124605 186964616 104366827 590182680 566412335 214222525 550754960 402633736 183465398 565073034 355923050 842290551 323188784 829623494 897951632 210025067 225264410 122106208 7895416 240126730 498379033 781431683 551487257 312868409 745420018 724105610 836731133 602465671 80089352 792826819 451306911 448004190 629292915 563576969 341323340 370024625 330279276 769129076 803444416 251944271 134584952 357677282 713930333 148852798 711721120 81118766 516838163 562840110 828925246 165248027 191990922 955172552 131546996 435139807 347869456 739901275 996926240 528756832 970653071 305053095 906872908 892435453 775563399 786782452 210489765 166075149 774127623 293076287 388128059 259513963 586881157 538761800 275034933 934941973 848284200 924434581 848217965 469055312 132307194 546124743 120514398 111020965 772377188 965701499 534926570 354148437 557214218 186861298 182823965 547408389 75607794 224048908 232990109 110667010 424934626 526351422 624580096 966519197 254892394 85133918 480156976 64056733 738955635 209934322 537460010 891203017 4426498 701114160 752760019 687667969 932339576 713202832 989225082 994241851 585879710 49610497 24022007 405966732 306351745 23412020 427593369 563390821 160108159 848732264 891820881 443918392 63363583 244337592 425912722 941323157 30380263 761092886 973950204 449186738 472828521 117503920 223169413 110544034 970398237 411878034 192285193 15344358 358530703 471470629 751838090 763249710 339191857 253990899 269184876 258597714 955300461 571492623 771117308 179259316 372463519 680366610 48040850 211365999 542031042 708232929 4859517 377492537 229128845 613814372 816270460 871104532 994202674 507551953 679941879 547258297 223771135 928872795 480655702 211948361 428582762 97253693 426857738 344123040 180211625 597437402 710411261 302867821 306372350 138531525 529828593 405499243 404731877 125474153 169990561 295265093 860575463 615451552 271159130 269504214 344906417 313873074 229069228 518464128 227303501 436759880 15532075 563204019 650881313 542001838 894218673 779490637 657922075 749697245 480212355 583226328 980420503 325377690 899778684 580049940 286305150 224665310 55865873 794421006 309240138 787136991 893306335 913749530 481739003 225804387 248323052 284313865 338022904 148632069 787219211 758185016 839179254 805349896 431328263 865477336 554084205 285238328 794533920 715957314 582130646 297798498 991685533 786768157 526985635 724294400 957517454 905688535 597496742 882081157 323076873 274811639 757609226 464611623 936902387 721684537 625405491 710431427 221512365 364362015 677700899 329011040 782678974 10416347 370093793 320521524 429313691 639938856 217264325 427957372 426175634 906250686 797133797 227573913 278339623 158597733 118607470 827907978 273404333 192364963 180535227 239224096 709776964 51700694 536034068 881173175 452361613 454122194 128786169 972804985 271542361 800872831 553564651 90029776 843088533 990511726 768285037 900884539 814846686 395396740 448699359 369088278 184438902 775651319 800605984 118077333 835136151 287372264 6293075 920239234 185509912 955110144 705614700 924095387 594854900 286835348 108142610 848896635 86512147 724769579 351722020 864426010 285292308 406297626 364701565 256361538 435560248 306037434 77638111 871168797 471390747 402439538 982688258 986367190 767295120 245017665 691305183 96750907 113024854 99577871 990053712 426655582 95719416 500900670 894281079 403361148 490501073 255061055 752991410 312113044 860123334 249845236 663018811 365026204 223822578 734883633 607390244 64276507 125021651 913299407 555094106 499723430 777581511 513583871 507694428 294137264 299512027 23155192 211714363 595907684 610162873 697218220 72844423 359325802 59778708 216029069 935655606 446181710 668962185 330969732 202446774 326691778 300020241 728763982 150893963 182934229 496964463 111964278 243429339 377117489 378569151 31383367 847226256 890968897 953105856 117795497 964013551 693071033 538907115 847126324 98007966 656552494 280732347 526647018 277824320 953138633 244786939 804748383 198782294 661392361 117214549 175591348 135441338 52814203 355010135 557321320 91433122 269647145 151767008 640686361 482547174 93808113 305853022 490700151 330994766 80972416 272612254 464214552 228368021 318377959 553128642 622559634 712568821 421638567 340921568 674775545 380939596 11455394 871554876 299043304 933189457 819002490 397418254 597325907 590125962 92898598 697693753 44555703 604083521 908967114 614251605 392848021 19470142 983766233 936888707 917629404 299559440 665415392 155993979 783191951 940586948 470972202 323554344 915344780 587656973 251546754 784693401 388738621 450639941 54566439 440767052 856227760 649317481 258361340 765866237 569585781 768809378 294206019 589262223 307415192 771417665 94372252 840704857 971472538 767774455 543134616 620893606 548720625 245960732 162098356 59417014 187231222 851318977 768131253 277913667 160458839 97687806 411435865 682301167 120007859 955490682 690583105 546782192 318277029 346990671 346283342 377302960 558956783 544381903 858825420 731292249 870315541 834262412 841418104 516284565 984372471 21007067 586844255 863256418 729341104 245769185 130869788 298742923 272201796 325164862 191754831 161744438 271471299 884311820 895450609 332505112 811446268 984871214 826530011 127642208 213370736 306876536 199825362 709334936 24349560 749274906 747434082 548666330 250353769 737381231 711015300 188234122 448063310 590685703 894008798 871898909 946150484 270370949 861857906 141407913 9540086 204666725 345779620 208349543 306060201 742156055 477717735 984940166 621148227 368969296 331326194 122172040 783667654 563128581 27473916 270342892 590910184 139909242 302909332 109045717 264710351 494050780 674604099 561057947 673261438 325566196 790006494 128777732 689330391 762001042 954916476 541037211 322171121 640368877 83508010 346616969 525126276 580225243 253965462 581004648 767920434 504192832 464507858 763679457 493710275 727308478 395727863 199470714 500669769 102220485 761521633 842992121 505207015 37643637 218641109 688595809 216594992 75319851 709357146 696647140 821348028 319185707 535894050 318341319 852054597 96585380 301933671 909672264 314354700 241036350 348095044 765962495 950746133 437490400 312532626 878756558 555847113 621876359 902116047 963689381 656706024 554774324 125481174 869997094 883011933 628173774 643263789 12592192 739346592 237498119 379756626 177445827 931344111 634504427 524646489 671293380 653039745 136305137 75091117 40308000 229651064 985255834 419420745 395777210 731830722 34718053 445140487 683009640 706059530 249094148 377849812 424130104 994653114 940222247 202990785 46269347 112940343 729659966 827135902 68900955 767494348 812035474 39033157 989218167 127327306 321761346 725112537 260304512 107031247 343314036 854375494 769261838 589131529 816746758 943609360 902326461 52009156 525667935 177285462 767642734 824113546 827449701 451953269 217675770 67912786 752828338 23977812 844963474 861339993 237757375 280646131 950642138 631490078 545633241 528323811 738983276 338245084 449398030 449459735 643337571 286058552 351242487 70325811 319068437 891448243 420982551 677286631 812091224 560451339 286911487 719022131 197245815 189722200 515960132 728383033 119822579 899743233 743567167 738066192 349629002 877210415 388080198 91638388 844067191 835733735 863772467 575524690 456275978 823803218 73973541 200099742 685997636 287851969 299787138 856241797 355110279 793705546 82594763 743875239 111741735 301644823 586541279 956977289 702011285 656247219 943943310 312538985 675263457 448539218 612389806 646105525 476292524 212819793 496890425 73420608 123068715 218770048 395312306 323990316 434337499 260790711 434841248 645660830 207025479 707783342 219787880 18351101 467941060 985073949 25372912 975798045 328079956 23743913 471380833 952953616 173542036 497267844 723624187 733889084 191051112 242881621 216566484 898315893 799145984 788313905 92097120 138545179 390582187 632295096 271099805 267113656 706083411 587321649 334961662 373239092 56917288 461065544 990323394 439877121 780731308 954699733 975009425 647118004 81539717 662489459 680911243 709562621 743685350 61157410 74246051 301004892 154151326 916249420 622350706 739770048 763747938 302043935 619438889 830324359 181447867 490942233 968528438 366059630 921293172 412966659 365027854 358355782 888296070 208657787 406494387 336959446 217136456 466412452 728780840 151572471 928291216 977129813 133267338 554602703 914722564 261068250 190273172 98660994 372594010 504226136 189129757 459447016 615569135 663269698 178744860 345870490 967922018 531332632 549700702 411251953 357617043 74114179 29627736 63502452 582584238 680083774 526635022 642600235 605941167 855772467 863410521 451733607 250100808 746716437 44954472 174814373 966059337 6508232 96167082 531918840 931975578 519434208 72717008 949315380 554918678 137281201 72658702 577119655 818685587 467930169 542481879 589210009 417495830 26806491 845984812 53915360 838706017 244865397 123011674 124197010 982488941 285520472 740573136 519070287 640899555 848178993 669898869 664274576 756158994 345159551 608966304 174053312 428386688 31761272 978494001 159302381 238985441 924181249 951753988 665285440 914953605 129283129 969897845 790138196 566960325 537928415 652753755 570638856 769606954 832068211 373846473 192668880 299952909 716172969 204351550 54304120 309386190 153678762 265408425 175383117 340514316 852382245 373362962 984325537 795723436 85800589 974027759 877854749 121830908 914944457 463220074 373601116 232843623 9227263 488687370 977799877 808765188 560646869 115877828 42321927 166597844 653997861 455995661 713782263 845449068 95407977 711206245 522172408 725099606 83248032 134393316 221862019 604464470 407349926 555292922 765921863 100794224 935989269 37079071 238704008 112734942 364758636 990588748 844161138 328077306 85007485 187819041 962490146 949968775 330080925 979726849 362813687 275290934 159706603 24707094 623080019 446158113 170635391 255902751 189149030 278219911 545958888 322406505 106127149 252041796 383208026 151265465 754441454 764607575 882664763 252141637 916839338 958168940 911337880 55963628 131879804 407770141 2310185 982307774 953432230 544323426 74887202 677257590 148394617 196237168 592926990 562944348 941489698 286198863 553179935 790721870 741026071 867140216 570999663 123543053 216284055 782747831 292674611 156855163 829443837 236213315 925424333 870839384 223284374 172093482 435271170 925209142 931094948 588177082 949061385 179825288 56668069 510646847 962010988 556754923 759725638 582923160 408159946 694439447 502544149 681801067 478534311 145178400 651576631 176153195 968691199 540778446 405592470 972353236 676449999 393226527 550975063 529434560 39516232 101452772 548465648 393680748 605320771 676639372 221222914 576608656 869708286 776569887 857293737 482477596 104580128 243575770 572979109 342493855 693495672 268391146 882417676 454519264 11474625 548909210 7027757 131820482 239319242 832112531 476357638 674731068 929958400 92427634 179912946 447448425 660833185 708113222 337116322 846533720 733856003 28360782 195006425 195459878 954001244 315090044 175129871 692791834 271521542 548928747 819671172 797645660 274704504 803999636 505853553 116120032 439516807 539447361 681195593 921351353 281326516 54531929 692370334 56026476 451012031 320547800 885118933 851662118 462229426 917732486 535411518 190011824 633656894 649741415 236188789 50284415 502933691 844004060 572418973 692667841 787560936 299090194 101959384 324652536 121028630 886327967 829398424 576592585 528739077 280256061 470570081 824251049 953383445 510181467 800749960 527626682 710075258 573258251 177379559 432159193 946546229 222506093 391714603 37408014 261190652 649301441 292193218 415347772 607664421 456965595 735663893 279950031 559242231 491095591 78407028 258933552 191420987 709000163 513815670 99690854 263972620 786106935 487559547 282460450 41192230 649833259 251244276 410669835 678299182 876045529 107735302 617780542 710416419 104096381 909298718 832045508 362677035 370695670 524335511 672885910 179508781 808767396 359658227 140988796 233459718 140321328 145214086 610365591 494862599 668163303 983733733 920114268 373063307 644432527 539265756 842358605 149544973 815389077 754933720 317342855 697154170 35112503 735795494 750869354 978319520 337823016 16640175 545907019 668447575 116777032 244488235 550933307 121664433 827336654 874919819 658788114 79276598 570857244 4326254 209684552 455269069 931439537 50790611 253216567 95173485 595779236 627191365 102750845 305479931 835649787 592403842 362785973 896065706 732831226 779568892 803192134 457638335 710335365 799961372 622083261 498895860 491096395 605174752 103357381 129715672 980738057 590416307 816596035 858034480 75559133 554710059 942595400 824968500 917695019 80161824 466800866 152507564 525989661 947694550 683657472 694302528 953203245 543692855 592393794 700082588 685822829 227615234 990125125 445421420 673685652 694084488 392355451 991253203 332533808 685818094 399979528 679820734 10208471 933116065 143837658 678445782 721596846 292260439 920286722 439029550 150209546 45253706 728430530 750079596 919379190 677155434 656905188 812090624 271990006 850504239 964261963 244675265 671403516 432767516 551839446 267787209 55814155 299118018 148426231 183324021 509806693 910534184 533902396 232363811 506412785 406728299 323262824 532132155 737447161 426967354 57676866 268142990 342745599 181618378 996327913 837022585 510776971 866060321 191507684 605694453 654620828 215661174 914360038 613541951 62519001 259623437 503888563 468248994 864134223 801920976 749615510 86085761 808087379 219592423 355876690 110053546 311345288 376421785 53292596 819004167 506631153 7260027 258901220 257956399 689933144 941579210 228725474 339002498 270081176 292839336 974884088 166188250 648858406 331348370 116504824 239343104 46200570 58002824 101802179 965941309 458076016 344879474 481435411 163677357 469565370 376007629 328396344 258706158 465824750 361219126 436402315 130793725 100189556 983440862 178863686 904267 566631165 722009284 701743486 852967935 346520106 102303694 658994043 271759027 375511791 464818713 125896305 956012062 533700204 861074555 228751596 7346016 595399208 880217915 39207268 641901263 58736503 934873791 463057605 196839300 48937876 175527037 560707640 542017451 598321400 748419416 706578376 843467699 560009784 943491366 520028328 853994443 657686181 459404147 659136874 218756339 600916319 108945377 292748980 994160672 451933366 662787222 59825098 976184429 738853937 917390139 457046888 769447998 676137571 43011030 510838217 565837861 500688409 694189336 874848389 477498989 511921137 774183401 423324142 338300171 239052016 718224528 331364623 156491203 720022494 951243939 758070787 933679757 760319697 535377426 506253330 272739573 35019578 305598673 901241966 372372026 721665684 197874824 596950493 243940889 215136833 88650604 868648051 956913769 106650766 786348473 88114353 835568197 889773603 716455508 334136168 170699178 824892388 184645632 760669994 499325777 413635469 644289741 421744068 19728274 780180259 410992717 38297228 194280681 597365789 854704344 44692980 431485619 754044105 424143464 343978380 466349884 334534665 952377463 271648927 647418603 491641348 663605245 508540757 604876475 796946801 336585474 404141773 322269452 518136410 884115341 667738993 225950719 924724843 264851350 195565207 793998515 516672082 557108423 880013589 813763224 495322861 931380256 820840716 504916357 804027975 953035192 412938144 761679084 867106722 773530742 459119535 954593880 372122392 523033066 362220488 273022506 764497386 618018540 893943984 214134155 977200988 17530602 147612998 548341005 476515591 210786878 395814812 643708839 120434632 124980702 155112890 110623995 962164419 872781731 849871629 45638554 361687468 413953994 598720205 144886980 992490514 280368132 85018613 184879850 49385710 370415510 535676169 314279687 904997788 871876718 537054375 667799948 681644537 469608116 946589976 795362957 201650130 283294926 277418843 72134284 79492176 61433830 555464112 907742265 824573806 931868835 7981145 573378581 472261495 284871791 443352084 243429042 421844454 788726372 781277921 993876749 30111337 590110295 499233620 672849881 94299703 9088553 977034852 470796366 712257 700526017 689678379 970058372 623971679 129974001 696370298 163763449 694980543 717547196 870714065 42231189 730001315 8311013 646236389 593081576 509677021 158792021 750715066 59466836 452844974 112173145 111767158 213200654 467975626 80906468 522747492 697725766 842116172 503410339 271026722 977336572 349642607 112327652 627273814 467707049 21846366 846158999 104948095 759801582 903728533 587801883 750152560 201644608 939450386 981741578 343878997 725885293 64048282 865950306 62991018 800527212 859604854 665108546 496683698 370796920 10282424 636571089 307696090 981179502 406997866 832985212 407801677 347850606 369818841 100806048 406550741 861556569 486259474 800455366 714271915 33710500 367147214 707626359 639371138 202267495 477659066 38512893 82063891 376543845 175753209 222421006 178101550 787809398 919687433 188919955 962790924 109017645 436562896 218435270 456526574 210458121 967990778 489049062 950876902 630094382 751574006 539497678 522262011 185381027 657809610 589287241 910064702 987908815 603291527 298795628 141294611 164076004 768219970 442712723 926247268 904763939 15030811 196710338 182391848 709233613 307985819 952592971 645588258 523510171 468516964 525918517 114286329 569811688 974410710 855112088 425792739 295856225 788042167 416034341 128329421 382648478 577261420 281723024 173786886 553993977 444650183 556810497 338894724 587760797 737554031 240370116 869690298 869870545 47575439 472253301 717305871 954135784 808351024 937195581 35748766 491712170 887036906 850444817 11306931 68883413 528993212 470645300 285742604 102295000 70091796 348428502 35893316 244537811 984760443 547261071 641474782 438162376 707500190 831266020 749390573 451743863 94202643 865844542 484189898 66169969 125180675 332620696 546132406 573850936 581338072 771659164 183571754 531098706 628958535 465135019 352326640 485893101 519635720 390877112 626413393 682838073 518506153 236741588 705820115 680272233 569916899 264235804 986328609 435121386 515071753 58123251 756763555 821672707 353711190 35838996 405031929 506135232 641180829 111939898 699286344 643932437 719012211 705880122 229274195 284595892 427876669 485991437 361803463 873335821 710373873 636701636 579327158 635280760 34710962 265103173 695924414 898695928 695144183 661975560 892527597 98982261 764911431 531717426 606242504 509684143 826081441 170243967 844193348 251979260 449481576 348622797 402867502 471582630 162353418 298882793 144733820 276088023 680532282 433405390 793855271 65968436 623237261 126436725 922717241 744742959 396928287 927179682 740489769 609548685 131249220 502925843 62705655 861443222 95444261 934691164 218030187 535482288 506272293 648120108 182809815 249398450 32692851 676909901 934042031 994258692 750229459 845932598 675994158 420733178 164658203 824805190 281583083 347473066 870930514 549873972 281519606 8140918 612744771 291375650 600969182 284924442 869311740 903082170 587947073 99508252 136547485 235410061 930997066 463331025 495913083 513436685 134975041 258094984 484608456 573701066 665767929 915853017 264250861 406772678 247396103 703655502 723208018 924107893 60303391 527990217 59572979 119151103 981042793 977177577 160948400 408929605 676365262 44462243 733883596 107414279 438714850 562620689 875568054 435294356 344859525 653438284 765639137 448671263 804580322 743736391 875388848 382893448 535059917 824074997 71357988 442137560 678651628 983343182 666495993 933070003 334616414 412140855 137023377 762162868 896043932 764628970 409147589 907023988 827054798 770359028 801283727 636940388 69885664 776896919 666125678 173920041 697097860 13231402 103001206 187359521 747404384 135182869 421602577 842968280 226977953 477165169 759434639 834388540 872608967 424823606 609596509 969455000 490458088 616223602 77505384 811238622 314078526 342811317 681662623 979116326 217691404 272879401 100752670 143877382 84197876 536497630 89140484 343300285 625435947 967377854 985780217 526707940 726110446 307181025 66825899 831261915 150363498 142773499 319279847 173796822 260436192 570994760 807549498 476279598 735658358 372410251 6905607 85869773 961537225 62064786 99631101 300199840 800932597 940759975 779508540 694276224 140304341 182362320 578314028 682914607 83812328 617704179 779763915 58043772 521338335 706901088 548233241 308145515 306301619 966216789 876898652 670569740 317538191 801286854 622383808 747584514 676548081 375836867 516250985 588039917 123842343 281825526 47207847 458433180 667807856 670853952 122177636 285039430 878199599 708434519 362990578 104325070 567751665 73928924 289530935 89195686 158918996 58903104 82848922 318404018 659631250 217888834 891396970 930380506 671954533 471186483 256508117 120085981 380417910 375188023 565504246 33052772 8308161 314625542 627761425 656239280 263645975 829672218 209045295 555897284 570152453 115980556 273594757 88638554 910367683 376078068 260136120 503092371 498745883 702190294 696982894 405500067 281873275 565673596 32924214 96824214 767654549 101173423 775682360 501952068 993364116 511025017 744310190 102860371 785413114 624039729 529397497 302911738 540156055 159244564 737644114 819749274 212900485 441987129 803508218 245140657 981258353 302507627 383362501 149703259 370742358 866364422 601132187 812251539 618598588 258586665 108602727 409256780 470706042 130589478 181604234 898755976 521287813 168088609 844911299 501902135 259632196 167226931 802870174 136693830 397905044 104816331 970014215 887540054 322940126 366703575 890613649 800196948 170649560 835613237 327698995 738514653 856177137 57859243 946011711 151075134 172066181 486363922 78552577 925356873 29497901 925204424 352827676 86346570 779476905 836270271 172044872 706364290 80752634 790108525 257722741 806336128 87794089 555666110 756929683 473920294 450118968 780795595 545430051 296204174 464491380 388887088 902097203 171899183 256833331 932046235 255902354 37783832 710355076 496781434 810687895 253761072 103303667 814111307 43960562 92438021 827541942 827634765 729585737 496072943 558296337 824936046 870754085 767071183 689089967 760087036 729603718 529393941 978724438 199845695 771656520 878838790 919156152 842876692 709911008 30043390 237057225 514971888 603114279 105688196 233788003 124022351 247714729 218789862 418180803 752827603 734496019 234655873 893266852 539073051 926904276 529617434 692073094 330185043 265775431 93737967 999941186 849086772 381235469 689719791 877895307 528766017 857969660 296956582 639494844 712578895 942407122 811452147 82494294 879425195 403333930 836667447 242034081 941085891 520853906 28061943 444146543 989857781 101419770 339930117 562407299 820672707 940487528 121754754 630479353 18311893 825171414 643911505 512433339 972928979 678741737 911221888 617354203 409534131 582341636 434507822 928168121 212539265 557345730 142116858 376852537 871550162 222889223 149312629 734719786 111970168 579818684 611123074 170092232 863717849 609932002 307579493 919738552 249145442 528939166 473665017 387385708 36254486 181155992 471528533 361928357 782954603 290683700 358323092 469357037 437102509 885684877 867608593 424381854 359759186 658373707 512344492 11431797 878851474 736460773 673450063 961779588 446165961 912018858 154645422 123794071 166989085 720322983 338749611 592910029 725734053 494205068 375582687 272792036 75331033 515844721 560139285 20175134 626574593 488449108 716140427 113613460 823134117 720645700 639004808 622800976 404462288 77726917 579091865 727342060 5313755 453087515 884966528 123679321 24593536 70052923 430275522 383083070 264113789 899501467 365658049 878032843 798895892 844611971 84652135 840082704 195011082 632062249 537945848 375779910 963391921 880264722 114633309 140754690 789780830 833353380 965825096 716813683 161855886 157260686 963864392 389034537 366111094 95338552 236756980 563810075 345792451 749731161 977782643 513226077 840125050 854885233 205855940 386632524 128508793 400583474 452625036 958876657 212620747 65036345 686092969 441378271 18216412 99439244 501835793 107104178 428999927 69515284 950380543 363182059 828669539 135977523 658409715 493668355 318030581 534750830 425612495 837521278 768628004 285736174 102834491 46495887 506469296 353077161 106795466 84349691 222048529 484092732 570946884 414505152 956253118 570457033 896749269 610739585 121806156 640173116 374023679 752234583 94740530 759100979 125707498 998192347 173159781 486263436 577101068 887510370 650914843 367374672 778565654 651021739 61519953 794036236 793188021 196644275 152927849 258517460 685899978 863862276 468385660 938879715 760522791 410832308 805780837 50762942 786571277 334117817 547655001 57983868 5199969 786182766 497041489 424873158 721051749 130253657 469948845 493005360 739029972 101607453 363174874 509193122 741507902 855915534 67441359 857124743 848567292 336362817 730557124 481152901 119675335 421508435 682745861 901136450 482121611 826503844 998111709 814721108 632489962 928104692 46137416 223322626 325386740 35733201 642480310 670383155 315227771 360195318 330478113 369139397 562990819 628077935 724159249 173749148 519325334 847601386 24542079 325895612 636083436 283234962 740911611 295552228 773823616 591425655 174884210 35552086 705972075 624042169 866615091 76092245 877173572 349167342 544011618 723287686 20596235 147835554 525369854 100020923 945098560 703045986 601966090 178455163 852946474 498820831 187239203 725018689 401129410 623646625 997083571 997587176 93785554 40967361 429311542 950632752 160004 694414011 967997726 774547226 370748129 942257212 607406883 182959072 916610928 286704497 730344778 282329829 90326074 708767640 58485999 276573697 245702696 579654408 215206179 961611045 25331103 210081545 569782416 57776377 954195024 58470406 838031781 836359615 920541731 187252018 852896751 601484256 601750303 276814857 339247344 169593441 345005811 381744518 635968533 329602157 680264573 115435843 240953460 985694233 348582491 661432252 200939551 875948660 416531317 82653528 632747917 529463011 490233350 974953183 10425711 221064269 801411119 788631100 739243490 325675378 64882401 269304573 432032044 631536548 362261429 769298428 417373128 587244020 252533207 603910728 708988463 282950797 572686034 585860394 985414797 799064493 328915275 673726745 946939191 795848419 360596622 853771944 682532693 535096998 235333648 419455862 427458901 565068652 731507814 322004511 89576445 557602896 590264341 946932418 372027526 23434011 269935584 572121160 247531853 505152670 474002437 734072901 444171311 329041006 203958826 689501044 887549336 81759432 263926716 252295935 969393906 800191358 958230952 710505549 612538343 424837597 753378415 811590278 519657420 530934708 550073968 824808652 177315637 133651818 783746446 93987522 373495950 314130384 840798359 363475284 600098858 587617997 873237197 368627765 847181820 361207295 634979644 519131821 112110794 556019329 63776066 179966681 861062107 406730650 793846822 202590853 999543182 924305809 182646914 843341017 367549029 621641074 301002525 171892298 80704632 610940691 883671245 214109643 88011675 149586416 652872465 689124810 649316507 351196200 582537509 222415186 983618573 461963669 770650972 688732705 887324928 758782534 636208221 668198771 793924103 626139716 814256225 707465780 582518673 962288931 730578478 428901656 180280422 157210556 972663276 895792158 161778150 408861111 427259088 258316322 222504494 880900538 514017188 63200951 996364774 826387982 578698673 156887181 80064679 216670782 617548712 580367632 136597761 340672787 712358461 592191937 395731230 488764645 656808629 7879438 26240872 558827492 415652629 619382780 772732993 643202984 323953763 413809095 44291038 34836599 859842505 361858471 175980487 342244964 890121271 243468523 712667915 587660699 216305030 354393884 332026054 158804796 922099648 256032726 959920209 186804911 575047626 299171278 267429386 137972161 227393559 672282073 24279618 17717320 503852974 41949768 543260859 620770184 653133390 748233339 337336195 607894346 426577534 323656841 321390279 435134398 175104446 380146943 387498078 644002419 782187107 735590729 465306485 682208124 43956294 51320097 798671622 964876016 172720897 106237307 327352609 989758220 181763037 426963145 450526276 116198123 41093261 403541975 107344465 86395469 823879534 712920174 132302139 492800578 791567516 202538121 229970284 21683088 947377062 258732408 897850192 796583671 100841796 949865351 789358503 480413705 446644908 99400041 251210913 167420323 591162993 72634259 658108804 998710803 358862559 483097322 124687970 187498076 536522145 844146337 890607253 187313936 434547459 719451009 156078211 714768698 9116247 789337132 102495463 167854515 62158878 920143397 186945825 22906283 962277153 19897531 188175214 560003069 229038316 484603367 734621087 148455248 589017275 766598711 110091052 502069005 173230885 643348885 60964462 161362150 24457318 71254743 428702659 739891478 80797743 108669894 694825943 446310310 647547020 573228442 706605214 162481862 467235425 649947379 334851631 487224539 177554114 688977573 758829797 571952491 975957202 248507185 379800032 923771902 489495841 693857706 42229828 284782672 810114888 918472403 600773435 104651340 394382519 930607056 951652207 158569826 789608989 516412063 827965896 504888456 715530560 195326030 593725594 416134034 793125708 615028433 800409500 790371271 697440548 48889202 465247830 179814470 441120422 135472985 761577665 467512489 857350470 791077120 954313412 728247134 313484649 826421231 976169623 334067807 263382400 909163183 215883471 798407176 850542040 984829169 482133200 303944508 867350458 385176862 289608643 712075273 359212975 6596907 417631138 143584511 800467423 87875780 771005624 358060528 331561311 747390801 132590060 710036717 157664011 771168082 212997699 354040459 978233783 408093583 914258195 735495238 714768909 918409815 234160643 941067365 252892623 625291264 176788451 142745993 241674404 218925744 820598330 345854870 538173816 856153225 944576197 586154637 689833279 448557300 629145894 163000593 794616579 775295182 745215942 923304103 307803095 902658777 396244897 220535038 494168387 133224052 991402536 766187943 848501638 313441661 356020586 550071043 14602530 677223613 171979245 397446204 455019160 717015492 773241227 163397634 591221117 622186422 71786134 543863414 342564734 461460142 856233314 808857141 502491059 226615083 39439532 853915750 488489339 963432416 714825767 904237268 488982783 912026352 738691833 140966686 20338001 429608852 708959626 705431647 292339606 355195021 203122089 82786853 971971766 912305423 568918402 45052579 158157592 298608810 967489885 851569095 864791820 994599932 727804461 642752691 479573361 932546708 838275060 218103420 755561426 943612358 219288553 988931021 611378343 588637974 777040952 970016480 405968945 253349876 171204896 955516943 807735506 28259281 190612749 256511424 118245274 916118778 809489270 145704469 613560061 358217673 188181547 118867086 839172858 116013921 949454908 9461075 314696180 27076082 721117038 7668442 969466093 802309172 426186709 788113040 366390893 390848943 299709040 724107841 276488069 476994825 543578456 9637733 804132938 271956330 144528081 270129139 542228993 506341384 151990260 590542891 154104355 361504545 71174896 825138317 28874685 388204822 583338804 524224822 93708821 520076652 811964330 913406343 396877926 228166943 810066106 309648009 587869402 871788563 264005397 983482898 989764385 953443198 938229694 36106804 355461059 92857727 631409019 822618936 284848806 495989424 198254151 589185289 441933230 984407389 752887607 30262987 44185298 255851510 134703688 805740189 151211641 547800617 427054587 267876925 762020618 418012398 379346625 966715542 753296014 489391744 256937510 623198892 355703230 975127779 980446472 119825649 96785859 721281962 23512003 837437636 275021488 952450245 403323712 93026566 8500657 322352351 985899208 168618689 823876623 299509295 980413311 257919694 244914787 483882624 268949446 401365141 753372726 731301183 414077997 311939697 721792776 138055514 372402994 536453675 841732269 943329709 854212450 990278150 993420792 712827357 189791433 658894458 135276672 136312599 566322832 36882383 796778326 718072895 620569727 457955430 103642781 253507019 148140762 959346512 226693008 74018530 407211377 463489151 271909479 579867130 722703084 739349460 191104327 925954798 638428930 405703161 978182532 475297118 229343673 618868733 529838194 195046768 177518248 964427879 211657873 36804901 475838876 995573349 115359824 521661336 442440356 565110647 457682889 45473160 474934452 360358928 867607930 527315736 35848346 955745907 455673354 915553251 895553664 871819126 973140804 393262088 185308360 740566145 811689175 265067797 831371484 644949401 455136850 333945981 211152676 283200034 539983334 817837535 208252165 993770457 686021690 542076344 754850341 224781767 246073777 368426483 129173708 174084194 176662405 953989294 444050553 246824590 269400218 853408520 458290469 338970948 664003536 283167500 680207689 529993279 807068774 845301564 489720442 485132462 274046296 552860692 474838129 13657635 688032205 522019171 179195090 399903381 711999048 343023249 836316350 641631513 929521088 808156636 373405386 93555068 636302951 776476754 699624382 776191869 925740018 225546862 582430534 639314782 83904187 65577605 441101089 718486360 933076924 518490615 733548798 56846784 224909914 882180661 190130195 236374861 890231067 819131402 578780534 331479101 398526704 135668446 342778578 735945198 759939117 929933702 798014722 632839550 779428494 685779717 331778414 806158939 384613042 481807273 731512536 831358396 414166065 798404969 308859377 108291319 131295202 561077902 415252000 268458411 826071377 137541738 160032022 660203687 45269761 421511177 303474962 392065820 826346631 582523625 21519940 541306321 215519006 218558134 945537874 344287686 649351352 85271596 766384612 505244261 386611756 720511018 537563482 216258987 699991629 493156405 261974055 364905306 824737836 282152941 856479966 842840425 192958117 395621105 694194443 822904610 990877019 839349599 385797215 45697537 712380760 185380919 383999666 609898454 219404300 277049680 198440161 275702867 365235535 227843902 610127475 505500863 305422436 111836089 372003660 214250559 662404037 121317870 980608080 799254925 351274568 146268704 206840127 822639574 741028159 507754042 615964079 928641640 763889267 854846878 898238788 709754645 70104821 761606382 25340289 958951185 689752809 828987115 396950438 294425502 497479755 634222210 310601951 580600409 982047194 765377239 148630270 257876032 230113950 663781184 46543695 886800414 897396027 30480575 77957391 908149550 14484716 362798328 313738703 331563767 202036087 274833039 892792319 135039288 262206149 773995419 368238682 446054429 422604409 132406224 956413847 88949273 873974291 216173888 40914423 153585653 930027394 60467385 61979889 947820991 886034158 890522457 362047821 799211160 834580569 896124287 494354989 264638213 839796699 972284744 695722790 480968389 307918825 822167810 276599066 27727795 966755015 357733159 17201938 176124386 2049380 373711015 454492065 224594341 973266867 293263760 21536309 720702687 961223576 599978877 908147584 25860554 62296059 882683946 320075312 985215917 81321117 647659574 568039938 322416586 653930068 370949846 800689708 661029129 786575871 894899553 271332471 957204369 610977068 824278036 283048535 202222626 751199156 807748083 61739689 162462803 799563941 634226070 237043498 924542474 281416878 663684498 608759023 135118935 358709077 99107603 916575416 891464157 357072013 734801350 17773887 3353061 633737905 405720727 89241097 506013534 909435975 369064975 655422206 570631251 190006078 723264151 208640188 93900012 366575516 651055624 548382433 102272384 110607914 848415655 257201344 869951429 219747745 433910145 74794764 563583789 891373274 101060870 610575109 967897015 748102258 147066640 376131921 280718097 175891823 28115310 643098132 264229092 209084302 55879951 148000265 931343423 395030214 593637835 825967537 335148370 911234255 267671510 716900391 666341009 21639723 894140584 128812501 123811803 601617467 927444936 455228260 73193356 868248438 705675672 584074261 777886206 635648795 35176500 647117867 429251698 894203065 324947388 112791410 617745208 481841174 418073610 999311940 149520948 871687613 765478255 465806829 173299544 749023654 164597841 422404846 280745056 748055638 555675784 269145224 200617482 18815465 111789084 733518229 231222847 800949273 742472379 84474216 774747540 692249142 580653768 813568751 366869764 301050211 112783912 788150870 994247842 950482152 783219401 24510446 800037050 620392164 950395826 804980445 285326682 441641315 157193785 563243714 841216112 441572648 256547412 786135039 613120794 148000883 336194567 562675463 988692698 298986246 181675142 996307551 152957302 333658981 88346862 577752109 698476346 402619262 941172090 842116621 986617055 588163742 713286191 348722210 175133590 124199643 596254913 242073478 212059661 753083495 705712074 191735330 323426462 102997098 531724124 3163149 710236766 138619295 139261563 479568589 403920029 391715388 180181216 970717245 313731784 327220892 70731821 111956552 143255129 801584235 926095153 240819263 272908351 334199262 649060210 714945997 812742961 312760469 110888963 953396635 159252183 747968797 423430447 113774940 878953200 783380618 896009369 599871256 670882358 667286582 803225454 871581543 586262120 65507001 857603150 587304244 680690875 476545454 482993234 98497883 971176788 470419718 842362093 621822932 504786861 38712588 667764607 80302029 434670684 603833412 383139510 567185523 486098814 364104187 329146754 646473997 437165783 81800698 656836216 600085591 424092401 229489069 852194760 777206238 575116309 186170996 245531511 96081805 819162412 490091714 497656550 82148366 380609748 204080973 691335315 359200916 63938423 576355865 958600745 9302943 820470426 436057928 171969248 753962398 336534349 189687224 506075320 862811582 446562469 496199579 378210639 287944959 569661857 741829407 442548501 612043611 741810734 242265473 189548564 631297064 1431031 911742399 4833507 455770383 62920271 282508396 473474413 117143938 702215285 795018141 760019453 670000101 986977618 35085816 105754093 615714208 727967113 439752706 204579707 89788992 283049744 708370088 103220071 290972545 631102114 410344268 773091421 966442906 459800089 638815880 922525095 104847274 272386601 165026984 710516180 104242153 374417988 219114304 796501874 356413056 511948283 425255445 232972339 771081788 73288592 95633099 588104765 761491335 411153118 15441939 650439344 802936236 166361311 341110903 672527789 529615496 95930556 833349639 173877847 103184226 280953976 609609472 371562296 657752205 19654753 50427344 689776385 311664267 930758200 938429448 621340583 92561513 874411712 987451080 860048867 403994291 197058605 921834266 595180831 970301592 865421010 562441473 75089393 443395501 612117476 597553351 19793015 963136405 885626469 49179318 652493978 461908724 514778940 858408656 527266505 561534306 608727850 734308069 969715938 770892004 462365092 978394995 791623921 654762507 101053770 317769800 414325396 997251224 732651827 972713904 642154393 847191973 898293318 495510183 366724265 629609544 445951130 816198223 865362360 728558595 538154543 134121845 713757138 691589303 931601627 840586295 995499628 640552464 144127662 512273869 566587140 544602012 387378376 588174174 729479972 837166753 855703125 666093425 469114212 34033800 995929647 495585658 71144617 10956666 118575303 764004750 170291259 223353001 362469024 719754167 526946813 152636789 821830578 721699658 153262112 315378878 437223366 856226379 449607469 366150905 911357682 716223193 562730508 48559827 870973820 252024609 133074434 722556636 41816534 12453113 886210670 848564674 55087658 797533330 155876454 249829590 978024312 369168495 923522879 669513948 919202093 413151192 954332640 473697243 454442093 625575894 439801430 577542869 853101971 43010855 421122343 817425535 501915194 943597412 55995990 184924300 51018918 379225275 706831321 273249134 508358534 284866904 613819587 80157830 189097817 84599641 346535414 719244131 62446268 891147691 71530255 237320455 280600963 989426595 796362533 409605206 111250836 332332431 134911373 193608975 34760490 748677940 585090391 698118715 927640829 782173522 538859355 377156920 742860196 457319657 949942378 360797977 937299093 251622385 19760942 35919569 995051169 4355061 13916287 756391982 868616383 422387002 635805116 38022207 140983986 307176525 147886252 322945076 342407384 634949345 174435878 608925427 333330070 274046914 330633898 467566243 224870262 789376151 651187384 971370672 237527931 81972755 276202460 275639699 108367351 838319390 296481057 262197375 180515717 965666829 173093310 124913805 628619494 110242127 778299603 742968449 76477437 160336799 221231455 773736813 273800903 379600933 426632859 91136928 825283755 474919489 716509114 894932045 463585934 253959965 403660705 78224808 926308277 799969916 140830448 762687476 851903256 164827940 397964483 76309557 724683787 691531058 548066313 442940860 166560308 69634470 721906805 740822119 510498930 374718920 644219877 630050062 356399450 765061139 288149633 534380732 188288514 260740133 264576586 487102550 663808111 116796480 44641700 110405013 205909376 514851163 606514316 733146347 29730072 410746115 874656725 473125159 982197245 429836245 271956498 123322329 878956416 922593317 339554923 342992606 165948559 346270749 744299470 363838665 443685157 394828167 33996191 54147815 273802643 9904360 97765868 237291181 744320213 694049373 22435734 26478548 856476227 218809199 585728516 444201612 413365457 717186789 104522657 345160673 172734008 405670031 612325369 592727635 412367147 627871915 24227907 110833461 539964437 418118267 54004130 931017662 982022974 909451048 601562852 398687488 299226973 783740294 861299637 166888604 998380406 18368196 875290823 785059774 520147234 254947642 972802793 642620050 225515046 356839175 405747342 230105273 399486389 275066378 67908688 495271438 543850172 56973888 843884350 520687611 195323146 721131314 366929946 989936300 196300333 853841313 960802291 317597584 76217262 78918148 480469006 943228599 151874424 803467743 974561803 11039932 383105467 67659235 388814450 632574043 201325394 541365816 185421967 632148104 774309570 10648945 391595670 727708977 902205133 288277620 560604848 814815092 197030286 616926389 112933903 160099615 13587631 894572645 602419638 997813384 21684379 133063112 552840567 239906151 699330927 116413244 971882478 34350333 239763740 364157716 197780804 489163785 138295977 642721239 933883344 730298914 643635430 763830305 175681221 491869542 764654958 899690849 861832141 827663619 863506624 490999612 245536257 131588 587120360 179061919 483970036 968003161 165466313 849295957 925318959 601605958 174892587 426887195 669244382 373893479 324579807 874528150 334305470 169505213 21303344 838227252 113165628 527326192 881740318 94744833 82263490 241033655 712157825 500264967 925399134 561666313 132116706 982944643 447833599 296609477 773854246 910537218 374681345 849787314 35371172 209783547 589107882 306925699 289695551 482327732 672563410 83451658 858238450 98909401 534455449 300451062 565461508 47993127 748493467 100266125 276055145 960037234 853008014 793533530 666155286 178373684 997606041 510466304 911619001 374894289 529644870 750348517 237054452 52431123 669228623 613586144 926638332 30045760 607226623 593262245 139067792 400345024 563487398 337378862 229007165 545372499 678487501 817885279 342946138 715531433 775642747 618840020 83333283 585894606 382461453 157769603 408419168 733488183 875433977 42571090 746365919 420579837 799617060 363474233 326281349 509312871 797172056 830524320 425471640 470783849 779481510 717302655 781565478 850677875 52632602 732950742 420368979 616209964 198815667 142175770 919655289 453709239 735140989 540923495 620258188 305763159 596231018 616794204 28001346 754358907 889226869 798395922 763612657 659838231 422765086 130841624 90303400 75844890 698780177 421610681 268477916 976592480 218467565 773319972 200421279 532549889 991330641 979389503 321385272 174109237 822223564 191698446 673952534 204615566 130018304 883335829 439361911 467113256 474821066 965598387 103125495 172545337 967984774 903027989 684125328 221117439 120609910 515592894 998906933 512841984 491530585 190483985 856961320 27313580 839205129 802708597 638811705 769827601 184363682 112608484 341854644 325559947 715828696 847382401 956530194 618423114 975828647 317787368 166850793 670577138 836299019 860381479 879153290 773763786 234395737 867187640 451837701 664378034 888630548 529891135 912089467 188496649 448293947 104812046 970333027 225119994 998136254 427165690 218738836 744991162 878414115 443125268 31329743 427233001 822225861 379668866 998793236 912609206 345475055 875759220 584519697 574020918 791748709 456496674 833063370 133626450 337922269 22714470 522764493 52170661 789738050 207059639 999736654 261631224 486445472 304591632 611122271 668521256 55762383 450375657 452011330 363003097 747420100 119763635 99024884 992035032 417837972 37482246 247739886 326268139 632510410 183017625 151180784 167990033 354632921 265282344 596363442 965547411 576154276 39996831 787590286 961401775 587333682 602370171 199023329 549524221 102732797 692438648 819161444 897953252 991734686 88981646 331217797 709984994 459409463 761449117 122945349 616030593 371082928 45153729 260655272 215602543 917476915 654902731 636444564 650871867 352128558 483462601 825842629 844076211 525697808 134147502 723168936 175845996 174064981 998849906 249310151 115842870 410448119 241277699 79750152 378902527 818725041 308894485 542009788 210150347 261479033 55995538 160026163 307797758 261267720 152951796 263589372 738881846 229096600 505202264 603955928 59774200 735748181 173372372 88549389 782046942 172502440 601305702 225370573 969206271 61346488 87412524 593655673 771342032 585092145 95092989 153631204 164227026 579839583 588011463 970679371 691274768 38731855 570803253 977831662 141410347 302500638 829609471 440143964 335547682 435027680 340223653 462755317 610967472 272465333 440105102 211938 531981966 463971541 761793716 662777689 358611906 89073454 573421623 170880126 415327382 846384406 456584149 183165755 569894516 381799711 601018662 648820675 7726969 751637877 25068588 42087813 506271092 883483053 387738660 729582879 6811446 276097174 550307233 8483178 258135317 955638768 794072959 851238551 97454867 442912679 771094802 800508925 546606225 390328011 777354416 478263375 980807550 246814366 723233574 909871275 538377788 501181420 980293847 814149096 805399922 794840787 282495820 442844631 634254722 307814384 185935501 437287451 873917190 744385153 450666243 349890409 143838776 703606433 648835625 665778628 357279565 827537243 932028824 894595676 569218378 12089501 457647238 182180107 579183148 674963843 773441434 249967110 989131465 161989463 136012939 5477624 33081788 477134871 839348643 64774319 486335092 403513342 418829779 707291456 157099352 44712339 775980714 63674326 591538598 884681907 789749869 148823200 892040189 440599769 484198755 337869948 864808050 245300543 530429684 721793154 247335030 644711271 284181821 572720444 867629802 403823086 116093121 672268075 629285662 130875699 464617346 83228791 669199475 987652535 856189108 368621998 55580075 525830975 533544088 9564676 396429185 187579290 444678917 965033682 215554896 601013145 26914792 474367755 824876118 460776068 812572397 36698050 980802092 270795494 189343230 40261783 837214549 681465556 252034456 575820886 241845932 400858187 385890090 806101467 89900331 985170092 950216384 297675454 430691611 452998310 787108687 425653401 731533400 703875113 285350674 775617983 870914 759245166 927235118 29254518 161525866 677995449 696226568 463469327 870071725 261965118 595476539 427295597 67395295 435381188 371752573 583454078 573844993 341429943 590448316 20942865 564063181 425867311 442961514 390365838 321865582 719873891 763020947 625917946 615274499 787021833 716464415 875602093 650698632 450098797 688923531 38822246 232149647 732430225 408512839 460195876 310586278 17810736 904474711 331154004 466176305 249637460 645297972 593200458 119534885 647419345 826400058 623491614 2785884 155414445 467495096 999330714 518295215 967236693 184169708 232328636 3643926 356478213 206011924 877128436 31760742 106858808 942288826 81580594 294729239 733362540 619729076 768997410 952775792 379876855 95289648 82996989 80515507 234438854 130202171 336008076 677137429 576283875 447400996 712630464 507133382 915001331 562076874 453338918 552766893 382275424 597529946 42637899 792726086 357876019 885232159 643429293 537218494 298934653 941637596 321643189 28079738 550245447 337817629 189135642 578589767 409548834 574716176 313143634 220300258 750616569 511563682 415788444 477430300 914125351 589181353 733554658 216864889 739314791 954720795 859775741 139221171 714107435 525281511 45484870 724846682 339123682 748595622 358829084 677869234 155475940 875012047 650805734 802890476 531256073 942393823 62235141 887557991 113340151 185422115 670259295 450505618 395303558 370024900 786933084 366170525 212022595 996064789 883410736 972999159 331781740 607792937 126151128 139614978 898482127 999765410 705393219 248380209 766915045 880360351 349291113 318462612 297305671 853150991 187999079 503186781 687778433 771012642 348643075 575270067 192478597 291596518 782033105 237409838 590679179 306227352 469741484 752484006 294665697 529206735 175126898 806766354 907275478 148854061 580975686 812282956 11929323 839993544 455181029 279607529 779829127 392393464 411158899 170898217 611616213 107551658 864146496 435920945 399986402 750816724 672993291 168270242 445936902 995649998 276292187 277427216 382005585 635340184 143772117 666296667 418890389 99314997 700115255 130481130 651431102 140689701 553139307 76363785 24244888 951210266 952418082 663655574 854252456 668535292 301738752 34818205 80030960 147336040 501661774 299555492 303349400 352741105 891436977 945589880 414276774 67451768 67447705 418238194 393188210 17285361 218508814 939918111 593040533 24642096 16327473 540027523 31918467 504891845 567414044 569923071 326372828 223892690 787319327 860302904 769443126 241652223 887007224 382721139 129284506 609287864 470741643 420574831 837967851 124563663 69521139 718083574 821248563 585310758 741307570 337365543 629218087 836648907 431458258 498720164 472682119 428723599 815565933 307038777 388570049 819197802 894462939 892535643 898866161 596408959 647555939 939957615 352120016 458965375 871331027 751908926 48073949 264840096 524106187 710069539 47398177 407009495 196492958 454005528 220648254 703828760 22387033 657143138 85064715 748235566 577734640 685374804 506828244 906851079 79038416 862216276 362486185 607279379 487024968 261276595 676909950 474213022 595469519 947905942 521136223 978616297 413269788 428901740 5353037 934780576 969300351 590739121 235535304 234303039 369784884 26413001 809273259 773200289 466358151 963720679 66271166 234199164 166865518 489011778 786477279 392919655 285508937 760872805 757368061 841816588 295774417 710359015 323308369 595054874 848308559 239891056 72010209 892331216 97052900 229306998 888308400 496666336 143504612 553654912 742880511 245559085 716514928 273924019 61858973 156479660 85342403 654523168 110576033 715129042 840551530 931638318 67855192 394997558 85151953 414814515 270211702 109142327 986713358 861708406 7515918 224408474 16539509 905810531 384915207 61191793 873929254 996115602 664179231 755096722 243205496 119519409 50415269 667843188 869303573 177444885 29333348 271394316 27008228 677752185 518078075 220602034 362263592 591701818 206209368 811344189 988916298 977372178 660596356 990094420 428812692 778099280 854173459 393867332 308842077 84439390 938127208 862601017 970956741 44647902 153781714 724008618 179044468 14346328 962045882 456959327 445687069 946445286 495141672 716913816 757355374 451883020 351549851 954372929 668952628 527158821 510688643 450530404 375327873 890129068 373845323 105495757 245445602 703238009 808843940 110316012 717136297 882767080 41039804 637645776 699294880 239908121 355627474 581697107 594108480 592815577 937984219 369929564 479441967 390740648 394475408 450415005 269407075 822709645 671705541 256227350 544536439 215741534 120144332 250353778 869769492 678926882 354219470 250128870 9951344 845982474 351541730 565947008 626883272 357959127 687616636 43988815 492258570 213076074 855094196 990615523 927121957 423002752 652505107 775864341 634496869 927019011 577777551 396701432 455499997 543079843 412708294 443716276 43232527 253822848 868330738 358752236 56120393 436135708 65112301 713438777 175525580 216550156 620735224 253693422 954308719 768788617 399104600 240912949 410937617 763484113 597361187 672724320 414528510 652121040 542765438 95667635 479162429 761580592 179511047 837577702 585474394 666497669 559063171 999395944 964069262 749510624 467937128 659223111 239382433 464335011 254040635 719202161 155866641 589498566 409181129 355762097 318796040 71184878 564836641 204919947 337299119 33295059 182198784 20421967 48342235 2301828 924951849 202234387 468278216 541927396 319237109 901505680 809116219 862602800 520784806 618665683 181708332 234299331 204041762 197726761 691653381 953427843 601862001 639051672 265765913 340221235 679989140 652737242 317334822 308194004 517908991 891115692 565820568 558997884 470713732 373555613 887933167 950341404 481297657 34183475 19069682 322324995 427077164 694118730 335869531 683648021 155866963 582481959 646859061 34528865 102060426 800990066 789768507 483541575 647600632 76944649 263849374 635092039 41634610 593117737 507430830 598560641 102683434 740507191 573870806 108688841 895722264 157517320 815647715 562754144 934539880 540171687 116093689 127880272 454830919 493170659 400365441 386591769 888198572 191387490 596526028 544020825 74782114 87475635 996609668 504009831 640806172 539588096 975775056 945199963 961707467 762765134 832861954 250837358 120113502 400179254 227470242 908954067 737163714 394064290 742011890 965958138 880954423 908831023 694365283 27878694 931590630 716487462 442906345 305530530 791458083 532222910 349158205 410324004 522776534 236205763 515042688 941403927 417116941 717866481 149854985 144618885 354336948 569540758 601446906 276312238 968374487 253429347 874216999 427128713 710530832 571922607 927235082 366192682 266536049 146763963 492659478 452126113 632875234 759692456 770221628 455156530 590494818 482921712 592338638 239104885 282815133 969182125 744820138 612850114 147966416 213786150 21484624 146880000 345956144 222075111 8372741 765587101 980635082 299602278 980838129 364219645 421281216 218396943 456963827 935785035 923080058 317023647 34837310 793144195 745609197 869982347 636244858 361307753 815869583 139586515 568006001 864351360 436960834 747092546 793893098 415615085 216225952 258802084 854971358 842777864 971301864 775026396 632441213 102497823 164217741 575701535 672920896 221730537 973398017 354505813 123527923 11175896 805387597 588113445 997424113 119672127 943740984 717888739 306087025 386809830 592683001 148165961 905555008 187709799 177365844 610166258 821829053 116147691 356363207 591479721 824190420 558251862 48235777 751696715 965580708 65206326 676558708 938228080 6423444 307145366 651168604 139122636 457391422 975734346 617339552 470465912 695189490 823051004 137569046 477048299 803460014 619110981 163131567 984596314 821030557 374234074 554445330 109105526 104021465 228374423 421225856 195642640 881660578 173568515 77215395 285208599 654505732 972153553 962722589 657175479 887493095 351818725 437579037 284288174 700870766 448391732 6704041 753031340 940812204 79353324 365512154 389788256 604570823 909031245 79453057 749447737 458073318 191705658 417369176 69875669 23124016 1300775 422779573 805218023 614280082 602293691 764849141 108852677 69205067 146807251 898409111 332899802 928927692 232749029 245423419 89145733 403998147 101782234 109236597 272842959 701945309 437660151 374390692 932299996 73112545 74087757 156974510 514947989 286555463 582120523 38732200 851624508 594405857 502845825 975812901 14708505 615471744 880037932 515077392 819480991 241555322 61305170 149714230 604559250 938085288 163297508 94719095 167470729 211253606 39068741 999322448 879665489 279907130 711774111 430994999 452038870 888647207 812236354 505097305 711936079 277486911 236866151 916854956 131288160 705693990 892777130 84603615 257529587 761246569 615562860 560006771 522019662 761197265 334110662 581282878 519502406 728185247 205494032 916752098 534096598 503256288 683695301 176022339 358911829 217884394 469413788 540956254 92867689 479526909 65062459 696264196 482839452 228504742 485336875 597276658 907381753 170012449 73983925 131535642 927963375 338381603 608526630 400096225 376998188 792639440 136810522 791092852 451209171 628358637 981314261 388414630 77202279 218930655 214220188 874418332 488505704 450718074 383997849 530574739 767750374 637583120 349468761 879293473 382751605 205915995 13138545 416716898 459632467 928279489 326290728 827927158 719545204 894896629 320698058 497855089 313736548 286013196 106947963 455373241 288292237 681687831 780758591 151490005 350932165 250605852 669245237 482434461 95932495 248385163 780884727 985695432 97027716 478353153 300419504 643150994 653179800 120182451 158533968 66061544 893907418 481509906 468380518 249654938 613262003 857075655 506032867 900893000 5026629 75413289 261931693 685379935 649202761 800008498 476489237 495165710 104922633 162668823 73563825 529999810 968213026 595418265 776605208 501883487 587409386 819347211 633029865 423324094 719839891 383365250 616544423 336251542 259788166 64378032 280108151 719785524 275706553 948335117 943563677 940009256 621550273 200329284 573321084 419429220 833978439 134337484 805131544 980283670 694370264 469489879 49807457 841334397 687452017 925595896 863146555 464363694 985067639 395530466 785772704 597956680 794059964 831163093 999189949 600379799 975337108 189059728 743549107 391095176 662645052 903375111 165647942 673994994 272777209 628891667 723909375 184550447 952540411 275971462 181360845 747720562 638602259 640602189 289462723 204345536 633309145 716386803 884398085 73622691 989059597 909645457 512563240 388172731 339390570 725439361 905052762 208646660 604890488 965054691 536635216 188816683 183166690 367218093 954605712 173712529 940929871 996929825 428157163 460894040 100320747 464517892 300545733 105905719 276310096 153418316 726146568 422875180 417041578 83625923 964610852 547506089 182931122 997727151 174824833 164750944 423603969 235601059 975000260 849100206 759848054 309771965 667487398 705298684 437118429 876783404 286529602 118249402 826982439 905325803 149431778 661258238 96646858 531094933 991198009 176087617 238856496 148306270 694877304 469696465 511053185 117343795 935610413 773862214 273171130 857110000 3489302 576822274 912117729 518240344 868397192 407800059 335755267 415308421 730403284 85711764 164546768 641769003 641456273 53759451 819875499 506198397 807007748 437074463 891470453 207242236 396285028 985947079 177898259 39589369 303290692 950098851 840451491 911746918 5462786 553216844 926054811 715441423 518831341 132262206 383580052 918731888 531696900 655429695 42003609 369954063 444372955 173074987 600015260 24997373 48380981 432865499 198699956 51642701 637869066 892848507 302338484 750570626 391567693 388815679 476945261 631844324 884306819 473598021 544700145 668979561 159861425 848508143 178735367 277513600 276988760 481513419 936767725 562649166 67221708 735680424 979579738 308498388 972539219 204461093 872460841 64363740 570481444 593503091 268879303 47547070 810157131 858729604 397084362 691534807 5006915 763730336 980582728 223356093 887903143 627991795 135943870 957859197 557117922 685120730 733502541 251169519 666931437 414190666 331255347 879039564 923859843 278091744 988105148 920193809 970650644 364175861 229956895 119833788 698079511 434373607 151715241 472762335 950461797 820727662 824215299 67433302 815163980 121883772 287262661 619627487 97258352 196933150 573874451 898129492 203057571 611406234 856785370 37881250 394178005 125437601 624597671 331178150 905496905 846722417 93996872 173204822 705450444 231198017 667722259 646929223 160024634 719319142 30031087 753454665 835998980 539542511 369996337 429391967 441793392 111414202 885758609 976547280 847473610 257363937 642744906 282216349 818887462 682924477 400972634 421947284 932395924 118369666 480348489 193204097 301485123 543094626 980487492 530789006 599602144 148398206 674299320 242145290 414493937 23936443 496597524 468619418 503871970 731855040 831679279 464828306 316883928 518783266 370859160 128937143 424842264 908009020 191494586 211370952 627962096 982540287 403115606 312919285 318447225 120870452 728949004 721466845 587097391 892265387 917723671 447044979 995070256 985554037 763613058 927897380 370821837 702782313 32514731 386747929 219906717 99141612 486765387 344636287 213656153 118810662 717898604 107909416 342065900 236575803 253696877 146426058 132397769 578425286 467502147 906153010 403566024 384541706 679551983 526635904 789004145 216035769 102709062 52159555 855581099 331708465 749539089 285111762 609089887 94299398 322000989 73741162 867624445 236804045 964432657 643838461 218732047 952159370 722415920 540715873 372090976 659212126 801916833 852969233 967110337 392766328 448432251 706411057 676868180 544855854 593322861 73788102 155657598 728830515 85789849 665681116 71533976 12397066 50730081 412873055 886702447 176061977 491355589 527774684 200128642 999705856 903721218 807045959 31101994 19913930 21267460 414368423 649791446 873690284 657298481 828107897 792950535 807434304 264140149 444716580 40740062 613391585 228787200 956234913 702166112 886588733 600782951 626732174 523641531 369178616 359346049 627600624 461422919 589484261 192105399 204064949 532444976 732817651 498215316 510803636 999449892 280359633 500269829 303268853 498243943 890308862 412740481 985656675 625472422 429792454 858095455 637475540 437374827 356822842 347869434 112172584 634420058 305742494 404599844 7124601 862180929 293454729 658564653 242422319 674860183 800648414 863564200 74007387 61369556 903392696 412979047 36489615 826005465 174087475 122904445 734780553 128343835 397777213 730031307 504243837 877121543 113615910 769720755 721218517 594069847 129275464 889986603 193506846 733494092 463942504 130242958 269750611 568640963 256999012 845832362 266727868 134007535 100922526 803162361 221287866 752542589 974264504 219648664 159102650 564797321 981742418 361463369 542729699 632662196 42435881 814965363 340269628 549443313 919765677 430429325 139910925 56016397 647777035 699633162 723128603 894012194 34447195 886013112 868520920 246562024 471400246 919351478 460835685 565506053 63905923 8820810 593922330 450766925 701016929 317957306 576183303 633925991 999854444 425027867 429426436 311362385 535275967 617798652 915623136 568934391 629536024 102019502 641076561 293348657 922820401 210001252 799469538 670546672 434113491 70236664 669934177 573353256 280253584 103450193 109058324 557212736 882303978 340480541 147511706 456067207 578631738 121649744 543953506 306606942 343101796 708556596 926593688 327424339 942636248 430443648 589962563 986402422 473501327 386510464 606780391 237732322 422691348 689073249 498154244 720809828 480647904 753123036 428643223 844784165 907673740 666496511 825067836 966682561 184823736 99266028 469374047 758299315 960947340 940595359 429087177 389961985 988042084 330676766 85022549 500706970 369807690 859004914 99163104 464098487 92116103 64506859 236841850 292114312 300811838 173464382 359643514 362967069 99070498 723464522 682733752 609944331 265135982 287892817 793853974 191155652 694958631 3829157 231350163 707593261 713568532 138743655 472854193 740352191 717700387 410124371 452962734 305166383 913879677 987738946 533136044 994983201 824257297 119661298 56118564 91721265 411267756 629305102 843560386 389949904 489307729 32233241 257374891 280212919 387982352 48383140 359201784 277074613 275616905 212074810 747393321 376075475 871058663 51677044 969880972 638325855 131388972 15130222 983142931 222217812 283426341 51929100 871786403 534985082 719427613 633727406 79218426 613876217 573426523 341446667 338141734 801649846 177744486 613305737 689217956 395706920 105613230 965927893 547553500 640835500 143394328 861497682 683565370 875403887 858367121 187512457 514769638 81315660 388472986 205378218 730844056 523196672 544472688 450031813 136639958 695345198 274637447 776772594 827894576 195370221 638838242 544229163 648226533 601060353 122048126 415115573 476251603 460285993 953688405 460072636 137947571 477460024 808831485 865953662 680142309 624659395 702660327 726172082 733899996 234732461 994806174 51396642 394889202 846117114 435489543 681948957 499258768 95747621 55683835 43932461 331922525 158399537 79117391 405781365 234858206 892219963 833925895 767564059 371211953 829541439 996955387 321956979 945141990 519781272 435624737 325807741 169915284 943148102 43665458 317465539 442994055 902470079 907076155 696851598 800101035 122004990 966451027 738823946 903109454 20651436 275473819 885985739 598045107 682788237 684888260 1457523 572790727 196451791 710186417 962800780 575924538 27731918 376743518 146517976 738824388 432724147 622705243 434071817 832479088 243971226 810683192 929399014 109009748 863724952 137365640 892533987 174124219 458381884 452012081 288655960 819609913 298515922 547764542 737956620 677212467 145994998 504955935 140529935 513808650 537598775 176541373 418799374 945752609 462686084 864304814 639809044 374620720 118019724 765160377 697055678 196345825 323817128 2474095 531125708 994568586 474112165 577533465 222369990 18046184 815434456 899229972 305361906 369199849 81930313 849738160 333662729 283465980 299407361 641975715 891856750 115176462 308472327 640033823 285915864 696237659 678701758 663373183 43841876 239992475 968864992 681350480 349121652 647988802 730472044 530779302 342720253 564229868 221972553 548854297 234523799 82555490 853674056 279451841 516771180 273542680 402928766 703890918 852517860 523445974 753651761 822662868 584486876 439655453 498162169 269158735 26318624 924286020 166264120 109090857 347379767 280820167 801987487 329874445 825843439 150726848 908399658 164715114 963500273 860093015 866290044 445507694 257002793 234082252 330568299 860495817 934431949 82773073 380476656 201679345 693340575 794390236 815834546 942546241 183593250 649368203 444087802 371320187 659191210 271418528 103804168 278251310 565905912 310619897 749263697 40720809 9434451 54693141 262439206 163316343 619525279 975624249 275883323 638359921 467891751 347654348 311052553 530092925 421358048 266111854 677177838 41808414 800587370 134548539 940020597 843638239 797544791 519569204 393510566 539957143 443973496 952737557 807073120 682613447 560987862 455120210 897626119 715437195 398893747 309318764 472349196 105026608 141697252 946677783 890590491 75298068 493224977 788933620 36875953 765244741 630299088 860572112 902190844 466573617 30154169 829637376 220338356 146953929 912709803 903166714 127217947 661353392 245666135 823796518 214704545 965831739 557642560 714796498 928444517 201955914 216543312 92897853 643735508 764771325 701580341 834703461 366579304 89184243 381098372 436737871 282575077 259213814 784554282 933760815 687331035 649859532 440823642 789708933 874928671 342795282 432196285 422864346 290834070 716168495 837493297 783075277 692089308 740766512 155249661 337369146 320789377 661999735 572942545 798315684 390023259 13664599 169117123 321818119 404102463 576999919 503364764 805634374 578178867 661475594 876063024 387209420 329574490 455787414 682666365 85690716 425457 479338114 773897447 998967028 844846904 159569941 39141347 830527660 80830919 735688495 630536132 271896344 288510871 96694340 847466626 107074966 268388201 146040072 660716521 336198011 211268189 830750759 838128476 42863465 223557795 326983247 876326740 303534979 498114252 47719591 584245041 833287686 705082421 77705415 346361045 600501453 886447639 468969686 791723408 878446952 493332098 853388774 948549796 424647673 164901473 110058661 128143309 536443550 524919190 809235991 407364126 502247201 218256918 160275284 712979782 921373020 949383802 993938271 573850895 121118545 604023697 315242253 763249641 700989675 400591584 408978598 509491133 677609392 108921110 781525995 271476250 260421732 525215565 392907405 573843175 400277118 33738869 677319781 876873049 182535183 546472870 17458274 31085405 748989647 598277574 967668070 988274303 271792005 231991234 290085284 104703337 11528163 573788325 393229665 173514700 452040322 15685331 684603203 55862041 266660243 754549688 585336060 91333158 798239327 350583685 217107783 176658555 507201560 707352057 666739016 404038888 514952106 530957283 572020880 913144981 898572849 991346600 880439471 3924739 152227895 927690385 462727061 35014064 501420433 483436580 220248060 197695699 980785601 460202086 747888715 723772899 626141414 159434776 965471016 563588984 151310668 464807956 909213119 529968369 830842968 575380148 431875783 282682170 224607401 87372293 986574660 856177297 422617201 87798965 741293334 817504399 344533389 357204018 527981190 345330750 866388891 897284718 57503634 613537101 737957370 160183508 684012385 248187696 696785571 238363904 528858816 543652511 641229989 771265111 259546067 589364434 404980438 639157319 382616709 587760899 435197299 599061068 567978980 479106551 915918560 649039148 487302963 540894372 299225898 365137505 75959318 559971345 676438836 461004182 942847157 34594743 369836231 702341653 211683219 3835391 327254267 174474207 117275806 839998157 448172461 298922200 418779351 67625708 459274332 172052707 99593594 972739845 838404201 20354160 172907567 134797716 977941286 721658833 273663966 343375083 425838719 177522366 760642376 951686511 917878387 680733342 495862775 472904466 627011419 642707780 600917223 650230427 624384441 314849904 654454560 407390389 900313626 662160165 629213367 135320690 352654034 159980882 698332600 869783898 14850952 360348462 944425827 959567529 907797362 117436146 619237148 780919533 990629347 961471240 772772840 618148887 749303243 378447290 507062232 389285211 911850372 81410505 417133125 904394802 169476889 868292363 690819797 449423515 257007764 192425716 41532014 727265891 252099136 114221670 82635604 693724476 858054554 706423733 407503621 825274166 791841499 700877976 129156047 165691611 54423698 850082735 533032908 213334309 92161656 616514588 4214367 584742366 22441613 611794462 173070971 759088469 584530617 920316529 849204484 802023651 563023655 294980532 683485644 16670703 851252635 333236095 839797928 922027845 867963067 424515237 144786141 577925954 24788755 286442833 993640685 326891936 763195930 190766620 666174251 644204949 721084388 543528796 675710717 794600465 744917483 747229427 721494818 123585756 239680466 316840280 904857448 330088757 600646659 500289830 911084732 221090809 632740941 797485760 545335726 717613849 643261259 605988974 649799525 660528787 666984607 650211479 949709798 132186339 506526345 542898923 26743630 193257551 767783087 56097076 224038701 61084807 452884284 290240616 873261667 226915836 794508948 108789556 983776511 880166062 85236675 188681999 42102714 377992171 384445576 595970436 366686600 972928480 351314312 767371706 479713062 557322376 497567640 146116008 607528895 253275021 770687960 403841104 178681715 679930929 490212996 371362327 162684355 339079202 8588035 850480607 350389073 982038745 400438254 594438888 899052651 340039260 26949335 684691149 283220199 434764721 822863196 754411633 210054658 69411581 402300762 976783595 20966553 39543473 506409100 398386234 484021508 141930932 305856559 281890563 717723664 888461747 572118756 921599644 628771246 47305006 934950842 794091598 91254096 405877480 461623139 469130022 333303161 839111896 784277929 864486390 905696847 7927209 754335786 445417359 81703023 140227607 785239911 102504030 163372733 370300899 388860147 625787267 155185601 742013639 342441950 796191015 916611871 963270599 782567796 889884857 410520500 712842087 753783954 541926116 865771526 828790313 705768609 346454637 751373718 260949232 502470153 212060868 127154837 773532578 566679294 602507124 155028364 115529194 447279403 925128023 10558315 763412851 329960671 399648888 986835733 710770031 922487142 398362159 788846632 439580663 213998801 33163686 928032519 769914168 328171205 965222324 481410293 889341919 119891827 211877827 909505048 983941137 180227810 994953766 239002904 166074568 353792986 146470943 687660178 738848918 845599164 554881405 823699394 983449073 169024045 45652903 125461255 963589424 663131323 816105297 261538539 874575097 459190600 474211145 406074925 897774919 11292584 977600007 242674810 714123012 596341046 62140209 351594427 800704800 470880113 918620340 180274401 707034229 218327582 480731727 662706343 621764113 764229661 448794257 141176480 506217896 10063525 482107095 472311156 486577640 730388697 896589984 73729411 454224908 961969911 827628809 178880994 423536777 798427521 613101032 414429205 868603463 856174374 554626056 388222110 299328393 998983604 34900506 277614421 571864159 329167266 385318428 70216738 110365638 974790448 630198219 631216477 136259685 273797752 423054201 800876967 652929452 835821484 838643996 952576146 771528027 629999118 101228866 870577233 773808881 990165041 325107193 298889460 999616229 927528630 796467708 984689373 861636384 372355580 786987658 793849986 177671726 230455869 454655699 198665376 400654147 590941214 420626960 165886831 273262301 149997735 377351080 936392595 386490234 831054027 288303792 77876420 252546182 596645121 815730469 962385384 933225463 424786601 858005332 704980405 378076042 650209316 119387652 40862800 991346966 260327465 880820501 395480503 611648138 651851748 207613151 237747702 488573587 845569702 890052898 333170393 448135132 36349940 818714434 447338947 650737507 848080272 516321404 422728921 76312869 475367937 60876043 503415376 277547710 209275986 833430969 667421914 153702298 72353614 968412680 11398213 245571954 27803221 519794182 979657534 637410745 716589833 156892399 502169948 15013172 63777464 979061939 551490258 217445642 615722295 760579357 335171961 136920937 608170856 800299267 366326385 733132264 383563505 937489268 156992804 360976364 891576502 386431353 676666456 386951413 141777304 697580308 889780257 985290924 478419512 229405959 563406971 802216585 292799534 826941596 964297652 313801392 116175432 714271335 967647114 601942447 122604103 130660139 193141021 542227602 674965851 655653326 49992319 543462788 89695976 554474225 622605848 905461316 436948118 17538224 464642897 534315003 191322654 555827766 801453127 970400559 813890972 126046328 785868472 154458726 526204272 510743733 623103837 362559550 887900156 195821393 443320839 700216329 499038942 595298826 878695663 347955344 732896284 120948063 251052880 892657595 613194708 726506400 294424608 527505437 66777094 24155301 235147164 10134762 587266940 144129782 704425964 759740937 439083935 68928563 248053470 470951026 473858041 768602923 390208595 695517012 317321021 785943385 576588254 349645343 714980468 415013359 990801207 465123426 250467069 991709152 462024780 220996204 309792118 392278095 580862786 503898860 8323659 40230928 104908077 820350835 590171013 407869119 513585118 978090718 506589034 57283542 853986656 126426128 937959616 415031444 871451068 393592324 728872117 887249200 347882258 166604960 391304061 490161909 840222610 441379007 403432198 133752891 463936801 984141830 954017584 536956849 967369666 402813759 102494282 490208909 844741480 493802815 888601258 335863411 485829537 141865490 694383174 509657060 666187497 854701217 310094227 715146773 898571661 816947319 168892489 574600822 25385950 388992660 149371917 807991284 299497819 164078382 620143887 808155699 787804295 164119730 651159416 9632354 839700869 304538169 395066517 91337172 145629370 535933591 744227844 366742957 19168071 172220873 161971115 774722586 359757447 999455262 163110079 958648931 457516125 669755349 989168347 580263372 794609136 843584316 587700511 921073612 209219537 788774519 926242604 11567524 956721204 421359473 521900827 252790253 995796273 67680016 576348482 941516683 847393004 949802978 551234229 633514448 763369694 736534939 17792193 86436490 896155380 126058692 487891783 87560346 767675926 512266263 552281126 917824771 521631844 841749882 967066132 328255644 607843940 341197613 679096920 864847502 978858083 946220142 924703539 656887010 156677170 185400823 281871458 37300716 396491741 103301461 436598598 225616805 625118616 181737669 330041622 920056585 822972235 325946253 676651772 487122943 689829786 73128419 190152524 180316344 375750527 578261282 349686923 807732974 181286111 397087275 198178821 844872867 1048726 543119061 66277556 293575883 876921006 668260162 901667411 368528982 388978986 744110478 235685190 902954953 140006443 845608311 116448334 785288290 856562010 444466851 749388678 666692135 579215148 39369225 819962996 353414398 635092018 587446655 467197371 114343188 474263262 91614999 625491447 426042885 566513079 227128111 306749879 247984465 648275293 168164713 612015457 269605301 442648441 739234582 374702510 933660213 961464563 361533012 615245889 84378236 352390580 291152861 966906608 307514494 56509948 840964226 649401828 443058427 438831972 420053812 274123457 632424391 23604490 244969476 419660631 276893201 397988853 994280131 613991000 358908591 989998889 716117560 501676790 248518347 299236385 421846638 306492548 289541897 633763457 400528454 76066405 460397910 708653106 662730746 857712344 628173543 659934312 362701894 652770796 128224840 760470290 111129423 855774216 916477434 660973080 335188286 970178856 530418837 432169591 428889564 652737331 422457506 178550266 550269297 346866715 252422380 607809656 738492185 247084248 585506983 600765428 175550390 40756614 256535642 297674900 113820526 605819455 460835144 23728588 477959641 876553355 914030347 964128194 897219861 27622149 628923592 423795701 525727570 410864992 905063551 314165317 234490682 602423588 225591836 50869671 343040172 606104605 9116624 981348309 299363003 295182814 955816300 526269059 86961614 882040586 504104279 169703957 358028613 395806501 674338336 337339498 452248633 914113710 439951970 321555056 433230704 643640388 73543641 14399860 947717572 546246648 178740946 265073459 885846577 562072503 958813339 568464987 922343777 668912069 828814631 275804608 51429057 466634616 173640378 660407433 833143869 814021553 158934928 356371354 717425623 582232849 695356610 159478607 813046901 111234442 600608070 417686593 844923744 211698533 829528470 966525382 91208778 986964162 815675574 634392318 196884879 611995121 98742762 991498922 659783494 269229345 748411810 945338325 757173893 108296112 65010953 453476329 387849067 485639661 131395979 754093592 751703580 447875698 857274242 928043428 157089262 852003456 939136740 793097567 960849403 78138910 687398262 766685323 43587835 623545563 752771718 843131619 535037115 543685370 779611635 558420953 601503629 719448985 571115423 331929722 706876712 869776946 142477434 545556829 139949567 158961072 719478166 473922266 122424933 928202656 651104069 824544231 285670771 354706885 234912996 890827341 923892727 326105555 623645455 850864488 570367677 583855171 697028432 206970573 604960602 693998518 99049381 345629747 152793322 223802598 212697516 126724313 440221920 379294651 856071268 294098824 815418623 528133508 535357563 526050606 459446309 111647088 138242378 608850956 987393609 777252518 338784199 696153725 888185549 875231125 842766825 827858781 44322982 930358006 548412474 76627791 30749920 757417825 544846308 811090828 133209583 585146559 703443300 737247939 333608333 651887711 199505600 626699942 545681618 29116589 143465204 315718353 142929922 504904027 568698269 249416246 455274571 191421930 861707139 331445226 127233482 623874106 894594713 808575903 493626398 930154996 486625317 55680916 639653104 87451813 668861667 885488102 281278264 927246161 526431516 739084783 327336907 611018895 106534294 813056000 13695098 227521555 614048723 237942437 94346903 580078158 834451536 64104915 134263815 284951126 383429460 656824874 418747552 482352976 363230213 972655563 585107329 642876554 207160607 818833190 8715012 249172072 847682639 802309716 235236648 980971024 663103219 143529608 341328783 414915057 789884123 686544292 926969884 724497733 46128520 666497941 444559786 728323756 310638506 180605052 629736167 650089095 194629253 976156953 996249486 17635115 383064392 666098674 382175392 363240252 675443527 245221146 565244928 198388794 905271981 964159604 81246454 92661569 490168956 331178561 145303481 930222334 344435091 663447544 382022769 339893278 942570931 795133215 559860457 118777709 592929546 192222190 749350456 790346823 669762603 111291553 4413290 910315002 907787467 294047713 895471801 599056014 222873504 817703985 10367183 136633747 350871858 143014607 612484974 488461708 422548397 988726731 174514789 306454247 792414387 115245386 237376587 901691510 55323401 143879506 637229173 373610655 101875862 645761065 916174928 484353294 197305290 328465129 483447558 667925685 342259741 997091753 912584024 87535739 166460414 853240685 490552970 488557482 97692098 554977932 892725857 353639190 48732412 236156132 197443123 258518858 223051940 844061374 256210519 467886594 561947009 839972793 300063888 894574728 965026813 730882632 361348561 475349794 356907922 850106211 89203517 660303187 481833740 44230592 788007573 581306512 435458489 521335531 728319351 89610929 86703656 660729969 530040214 740409953 171780929 450218925 48979138 137034074 158816226 960475100 190600368 537660712 172201765 107864284 424726373 478064108 962364823 13736688 933619119 823920466 258012343 135091842 974124222 574553380 187703307 165550881 976967206 668521551 742817535 222751540 214297341 694744823 327710938 3902580 715229021 407323992 932291151 794145846 105792922 457547071 72228925 109418209 448745090 5856073 652853833 651198893 808604092 312230088 759063531 392951503 673896481 709887305 638754587 115310020 199477337 852482789 794283367 737786092 993113209 137822222 712858441 563458619 2197971 785749662 163321488 954541776 620785994 510123037 651594954 227673973 280756009 59179332 969284700 899106933 750624883 989748637 323942508 682140134 321656500 277905068 787363826 404637250 572767233 759688249 469663007 823588585 421471187 740728399 716315975 891431886 444220158 373244556 821706965 304972874 298000250 826770561 848440057 783527523 181695241 576020780 352864194 379682803 93540053 849903347 589443940 623144546 920814396 538838664 765195878 884842400 86734726 964778054 53858856 615225541 893919897 517506049 100586010 430337192 520032536 806950051 557774697 942240317 928699578 331341074 183039435 356439193 811574904 562551393 300397014 852466439 267839363 242535238 960493302 606954472 171822161 147966086 505461546 618579882 812638111 726946600 894530571 360895941 843473532 872520684 869209254 664898374 415807793 460897040 637932892 964093485 368649854 118378407 63189472 440986211 774030786 87127889 182067050 288982745 706521252 132088019 200520019 669336247 586988351 316365370 42377563 43940171 675370679 164783874 576112764 639856575 994041669 918457851 153409034 612875504 391625043 527143586 970783561 795921040 214960298 443334982 966247022 726623179 875757212 759590263 735986197 30451712 195456291 627309357 937692751 538532329 538449471 466604365 683649396 625033606 953554926 308786027 829383242 450175110 623093122 360502930 855560672 446649768 504124811 14142553 56602320 384004299 825683381 339717663 249420254 47834086 148307872 311240531 775932076 332392340 382191697 313738338 955497130 637512891 20137987 335269077 957745066 448872543 977120967 146276230 225559649 143818297 228699074 233059506 183753913 320256804 155384224 331824446 881628044 792034259 547138546 383068756 427208008 932335287 902269515 313061628 699572340 166784935 580672295 633012453 739438419 626142095 971296008 305831547 223969052 86183388 760732474 963409558 689422110 977329072 75212369 710823898 516607611 547726983 930418729 234393178 437527276 18832652 250306535 819624901 662284007 731215485 512954438 539564727 267107283 682549425 905869089 848460301 204362220 468188137 345917710 658008432 91729899 924456186 442107490 25176053 319293715 853403426 560830283 616980990 567460138 796645651 50880558 338311798 717743653 185469604 411388803 479984783 337436677 144361774 335658777 201320098 381663455 71754573 847779274 631605337 794802025 775647895 223373093 520504223 761377376 145888205 626935496 968957072 326168990 314001634 19572065 680336276 602015874 263920128 660718530 454012021 996111343 274285855 687546248 957502029 924256828 681196192 535818535 43416786 775123130 265074646 892281654 145692028 417618168 729438197 148621725 437687419 109446477 287995329 433730702 784138121 954646160 888231897 440337639 182480263 595304276 113331707 662315570 33393626 987171725 293193644 42005835 697024172 110992975 689223080 301092865 702221251 749795920 75299333 485794881 273944143 334036100 236757403 903147826 792704820 303026994 387722167 475597469 828895052 626096983 842400415 926625906 387051936 613227792 693437897 765590688 589371061 295698748 288609995 107628145 217891652 973268510 556243941 517379588 859250251 46465715 134958549 500839664 653984612 962528355 937478546 554863010 379949924 292823937 985883260 184051549 675058275 444581083 543375872 889420941 531601612 454012547 152082392 454471699 264978030 50462172 271504099 620870881 920401716 329839781 145787518 646456810 732429612 142097932 116974213 610617308 649011667 730704322 59225733 482910387 953879212 790856027 102080215 910959231 719455575 489823279 660793466 465812993 675913138 822821873 790685078 409457204 596663838 603640683 366215787 209792964 44493804 234720182 824271382 653623093 869705928 79144996 10227160 933658118 776764672 946821400 823293484 126218372 382794687 602138648 785824198 119477881 979590267 214142083 309444932 322947946 959584759 19839842 286033523 892537353 113934705 394237193 480958274 992769552 104191897 290570098 993586679 278895535 765566935 41103035 842253091 190839234 21709625 722657987 903302659 390563809 47115775 378146593 567479262 130041897 270512983 595229655 726333746 268652930 286753477 581272291 867618038 681842494 649479794 520202967 24768849 836388237 602090289 284426022 266866708 466161228 309069871 484942776 435624735 746886748 440411708 378056118 732125328 217130746 22886066 33568043 389529292 571768080 411351417 216011140 315797459 869578361 374748609 936998416 181311385 55828796 123623071 620998685 688414852 242665435 649614022 629145174 465875661 412430194 296873043 107806894 177127516 9590653 844949911 226114339 792616713 308249842 123279037 653938253 324209639 904163849 743070042 954887479 652932703 566361584 610242633 24516890 547337856 324138153 857169549 337795291 695761624 974398521 480561352 659931452 130113091 507223979 750467394 886683179 103712312 536548319 938142126 631541307 481989474 57742860 175034024 781509072 372047149 228315898 973263023 869014891 362021327 267353203 618341149 300166062 38956649 143953195 676951474 154608384 768701109 877395307 76428195 301760722 236193272 925202880 66296451 961093764 829417830 979871319 631596336 226706982 274500480 526977704 142826271 794535357 523384512 436958506 688053952 549541374 170523615 285920829 856456357 23371782 172789195 738991269 118732339 144559307 968802050 100583231 913662967 552315851 926827473 785319278 741384383 823112184 860562867 559651325 286104701 822269513 27509438 580230326 322904369 961742077 781755870 105327779 714966817 280706643 788800476 6539571 502001238 580155493 627642872 337058345 27981185 631158526 75301620 37207145 723275731 701011876 823738663 849897079 310141803 360582880 822857894 539959713 541005234 610328292 346457770 380224872 756151506 690799464 229724348 472809349 388260858 358502653 25629532 494732931 179817965 646060725 86093938 817280450 155360582 498100970 527150586 483808280 705810101 678974671 418722288 103473626 471094742 298187615 570321050 877003556 675626381 898486366 619780702 97653335 60143198 836098921 784982481 199585838 462738907 59549266 890278868 108330099 859448246 673010617 758419336 187304148 355992862 766664305 208228592 717598750 795107922 551463808 490715601 125679425 402970361 398242173 869140187 539378449 990847453 810121598 464438378 564062981 592675962 370102327 579040568 95744450 500892150 738620912 881722088 860760496 160015070 531944806 802714793 522211080 808912062 247098010 534736374 700530402 861756839 93351862 697113319 246496358 355850117 345685202 743910988 454934206 491046946 510720287 911677074 600275200 227341782 177979866 667721455 221732351 957023262 168665356 335763679 777649127 109640076 766485160 46763151 981269199 431380052 557191132 504987168 912067004 433617267 206008094 939187378 737149136 49496786 820243043 223746897 381182924 355215613 296363232 470308393 187621887 286391609 721281296 679950832 886965671 766648303 509672820 962684871 36418628 306993309 888316778 842345663 832355864 269088958 761816182 37697523 682397427 308077295 633354238 536067454 708957935 978488248 948594248 103389829 336245811 41877589 444641017 972477166 543926337 345307786 331304381 622684632 501178421 20122555 84573242 258969995 813908572 11135873 482495200 421543009 374483418 751291913 835866335 48841320 802032862 859389069 270746939 119830394 109582141 501187084 897185049 408444063 717557772 683581243 544987104 774530967 467626412 207454442 768629696 104805824 271974260 552726819 883214897 558093730 502446372 669291573 273819688 808981878 524218963 201105933 100312972 747788947 64700253 146974960 770645141 160325449 944466240 628643162 733824063 287911538 89311492 295659731 797229074 498326492 221566655 659002597 548802583 732868428 596497186 695691965 851814927 45168054 638149426 701370664 572555896 683980876 477919121 965759225 772381738 138001776 878117395 689997764 219931986 213860675 793261931 863884292 837425777 185190491 813315090 960187587 453334470 195416845 350171662 79419735 111088145 41463059 890903970 560647556 277454208 14853479 220468266 254750832 580836583 199495166 357116907 50868411 651709561 588848798 47021212 782917534 254783868 833740388 846069422 194363423 265727424 883164576 884081334 10530554 764080786 428523585 430862718 918987978 659970768 156135325 78102994 394283355 389832709 398710992 752911175 140641729 165925873 184255128 871027056 702751937 631530832 7235629 83286995 202985496 795413406 858680906 337276337 84414502 321368558 972902930 725384565 773080838 461362852 64128714 335205494 475729721 975410659 767174561 2019465 385644102 937391564 469775906 451954730 302041459 69734286 791023529 599706767 701886156 49269680 229457385 209897822 671923207 19976341 497316029 196076180 454441414 731217750 934193571 113828199 310494640 848301489 471641796 593719538 183412707 539998401 676594381 743112057 637837295 940900107 469130268 589544197 426175044 243424859 356181699 291870421 88058236 13610364 185299905 176406352 269191850 615889584 161228679 200203881 369129883 376946593 25304232 560263096 217036589 169298588 204413373 854271991 749715314 709227588 456477883 317079898 879313822 131956866 812987006 103593259 685155130 562093871 591807545 21817204 499762204 221788739 290933483 519633812 956553658 457983976 579319410 879764614 21839703 876245081 467050907 907436486 740704277 436900733 926033098 335004893 642774681 127151857 359968125 550823444 92075282 31346304 186119396 216694830 993237737 634172050 164245670 639676024 482562403 754815000 578947610 431662636 431729483 448066245 64559419 219889743 63609887 393571092 469488033 446921510 953461905 764123394 82612587 392804288 146375075 277385498 660314575 964809625 653908301 869332596 103063814 300245780 994772732 44669122 802540966 247729168 596967393 861383626 370071745 858057795 520553077 961761298 7955366 509973525 594438394 253570950 857483655 967210008 899379146 449380521 41136244 596993818 702698561 548569216 548363999 945589856 780523481 140337046 932986634 669218696 401819924 456936084 388281616 676304210 671751588 934643723 616273913 362668648 694948111 183615296 514663267 893781074 646094166 533105658 94632527 335482466 950398135 999252696 764446432 896144384 14444731 301140626 383589948 702781338 132569021 102110913 156920259 443827728 296545119 54236709 964326616 819141050 961184649 975291102 611381440 870476337 617510905 436843498 695364874 29369893 330299515 82826133 549815129 989222747 125481460 851397294 166592900 832862708 617928883 907612870 932716325 803643765 269841826 854246959 984155118 11603744 554429347 148354856 44196743 181113189 583886317 681816814 500186669 248185143 618274647 345773071 394650659 308843744 887131718 265829097 110192064 459591194 994753246 953409581 702782653 883040334 349686483 139508835 105122091 858727878 673483705 714497969 112679291 519803896 842316949 329438782 306372951 411636712 351122333 191711862 624235042 946566263 266490050 661861080 165938799 289940609 544075232 495621595 367465389 383822600 537968878 801918081 370367210 399297771 951341610 489278764 341111921 981314160 939328375 854355638 611249011 794160997 68811999 853238917 784647169 246159111 523442455 941371111 231540447 86550187 252356425 558788115 440274412 44640486 124486781 359042696 744464196 327880946 917705538 77116261 820084156 489919878 672271653 680119439 602527285 997747675 643483116 503346274 369319821 891063058 406111825 493459371 626486115 836123340 603555791 794139597 654180951 292367025 388729691 930568302 231210562 685539973 303496168 822748926 870930505 588751624 345986274 638452350 900191579 259179893 893798401 797935456 528800900 442612946 143455098 460196333 765824703 309677459 817283598 687399584 290679177 522806646 38073227 692309832 329451747 154450516 404074924 25290242 683130088 281271993 975425923 11826176 640862461 79884254 302209072 49998860 163769162 872286671 47140746 642780770 977381621 965892918 307429629 4637178 601436673 927478816 925200155 186092270 916944466 952058510 287274030 797425728 795689554 361282908 735852261 126548597 796277647 445057421 991697119 907624543 122605380 128472386 847367581 142436010 624187950 385248281 106248548 198497878 303815956 495481848 44913149 61629216 619485584 230016727 550474324 256535446 278674637 165997580 831372126 879120113 328903175 107180913 199375804 424824855 340160866 698642769 640702314 471413461 839224518 713945721 945603521 232391695 366750576 864445717 856860130 440272435 835038478 116398386 905664086 476703466 545162018 455341796 66226656 886222225 856256380 402573681 40188070 530287723 47853708 93233459 841411543 186725228 802305479 427168329 848867574 508042020 739689572 994082165 368565540 194311732 663041914 973130918 845309905 436763460 305312181 553791540 898102216 639875290 862827983 41792521 299244054 923965335 891338150 673592473 500780071 397173640 665796937 787094444 168446410 433503446 395452121 100465168 140952290 265357084 257608231 271321639 338845669 303917490 861393438 778512588 225722515 686616493 347022922 443466526 408578474 586321653 224742602 439533589 494578154 373521148 737575768 198503758 145471918 365622154 845248161 830449772 22237906 490434084 163238346 406007379 936316392 698623984 249736149 583379017 907345433 269123232 586478690 607599824 832716753 656795762 851454675 578022261 309654701 467598912 44211598 142892260 197389041 554693356 808817035 598576752 468510821 966979614 862608214 782573137 979190456 794054446 277251149 394319701 245112298 912592604 209749149 474407075 59754008 742859402 914306739 607825361 703585229 506974740 296882084 891937221 902075706 452634675 729700906 655068926 534354332 419962349 36027812 690325614 861037340 94348900 644658332 313117015 385704680 616988895 387699155 796131693 400218381 424203789 910988309 584309198 237801464 161151389 988969160 267073949 523079678 306846832 176212922 839635204 271721348 950949672 905501004 273536885 954960664 651395324 540146002 943953482 262277316 615444334 610464000 649595549 870955035 970873535 453746448 437415798 768706898 501003742 563218872 167753481 98566587 888210351 295733159 164601785 409949460 499941859 985286221 991114164 984113106 701614003 951566327 357062233 671694556 545477472 78932166 778419126 124315134 756616850 192825176 232192737 474513015 632187903 839756493 842885327 264465407 244374285 281440290 2233449 522214285 156807141 79775333 665673985 647774063 342051439 150291119 420933142 854852976 726832480 44706157 825123236 659636418 17655048 398364904 731125730 531252012 570353208 266787745 202960365 535351356 907503882 801194644 560131553 617371264 700341799 820366324 91097475 424688744 399117815 209033786 830326808 907421690 218969073 349787476 2412820 600355932 664413583 433025916 836685367 679278977 479847789 743511484 501771876 260110320 276052161 687155695 945116928 213601904 633382410 512307308 468760746 815280092 551531037 320265399 448831194 783502895 617353273 990435806 257820433 275804839 589167430 750558499 606989110 240676236 234437529 770169835 550220578 414244987 969309236 346184008 544417452 78455721 477519363 416781329 411765766 452861537 768424450 109595672 37541696 23789550 95672599 587072666 99146614 148061728 830531385 183111902 450533161 115534887 228289916 856393850 881594424 622688177 473549073 283041494 227313780 3898110 11214982 892550817 501163984 320141625 428097332 598410051 688807321 819480067 691964362 63913900 770142155 58682807 784609499 879577414 292481912 236349434 758388957 929235322 246192679 808362354 601852022 875944307 798637907 227316210 861334062 787093892 602675872 127582368 699381942 339874723 322684515 936114368 803867933 509916172 55901386 522796883 263387112 76528203 124940005 347397346 853714687 585335936 47131072 616051005 940490612 60878237 487009865 885870848 519778397 416960909 409232974 812676155 713906264 571151859 174476827 328294701 241371704 783667358 888677155 175439974 378071277 190127001 125006645 776369004 274381676 571425175 253114463 306960116 201494477 859044174 616061813 406578700 215593775 468457926 656856051 192427065 915813481 584527391 257340855 919998049 68953897 503421332 160658929 787317433 40234202 731080146 212686308 422813338 75386008 338576244 664892001 913301807 588739826 269336354 154911661 782308684 184404525 76677974 605557391 376765793 426631413 438121876 309764127 395800250 366665968 309530223 147919337 932384569 512982435 963082594 115131857 315066049 858584090 684374180 5210786 908423157 222127568 532643107 380564869 512422306 904008851 326038979 227779651 243716889 370045118 365422289 242987931 467940692 22854232 463347162 255034823 452492960 1638498 796394295 250339215 931289943 64055698 292943917 897501432 891286825 898421854 687953172 373877946 336678226 760916467 700486842 645688375 167270645 354965747 994912472 420536651 754838396 953848135 816060446 883903069 322332221 53230622 839454583 719789393 727345667 862894470 760937706 116827043 659077562 794866540 756097261 790161382 213744404 693623816 850748608 428612349 772422814 655123413 455362402 940165162 77709042 575126552 650548258 924061037 862078184 380438 658131808 999059762 718523987 969055038 719295354 14668219 916714981 680305183 686258699 929044528 615838506 507947256 886566696 617598411 595728239 310290469 283380859 486423703 328224730 92475412 788805840 118269314 239060446 978167446 787935564 237664702 885294547 975991479 137263749 543453444 236355883 649715309 286435756 396888416 368842949 676732231 511986253 454999604 290897165 477733519 443181966 158095677 140289516 379259223 448124336 290021108 914737076 763418939 502804021 678536367 426255389 936404475 582039926 438969213 74743253 152716347 466739929 212343768 638701045 656555332 262821476 284486430 59508919 351116969 554544877 569340704 592072028 217757328 939879752 460326143 158523354 169176529 103165144 166710314 21011839 178941916 64012623 792740162 697588888 918742314 457207369 347588517 391840418 308088701 228238164 183335503 626530031 697061138 93301260 443785997 639500331 290503120 268645053 851504835 793891696 846059146 161813465 399481746 111035988 433745465 354801526 146908389 550883270 403844906 480187167 647523009 261196185 655932408 355268440 43664053 260803819 263116459 37039301 464230543 966388178 65719357 128061176 328032291 479772993 700378247 302042405 397501393 552235962 582325718 386144137 114343556 368990610 16627348 71712247 579706665 164442200 617958497 778190332 145677397 21295317 997115468 753288219 133569614 904946630 629582557 16132013 974910209 700423730 595398144 557616817 519115530 499232258 216713344 24004750 818491979 479194807 482359071 503335001 647447050 733788996 33533720 401065375 270897070 134371838 157271379 240112107 393833381 184230345 57059300 606387882 565024533 678702970 318554437 574023217 378349569 733081007 596144389 483122730 263693689 292975190 470014760 263811125 360927571 53877119 33941298 713778799 689314910 607290491 804601137 206811859 490191418 403308390 383565775 179257142 978084372 993053157 455156440 278560824 959443713 696848848 449476651 912636060 630613851 241577263 81186910 624864744 890672245 112240168 547177936 462347023 471824126 906835724 179684294 358944894 622596315 127452446 58050680 539992199 675274740 925398231 153848211 508218734 84406226 321077726 266231470 187013506 382562795 543306274 262961946 630046281 815295324 253540424 896829291 186166591 859675961 278764174 322527391 336063406 904936517 264487518 541534078 700767602 187382128 243969035 400224262 953271548 184912167 206304571 572901460 19339527 714147855 737612547 65994626 170129757 172787373 159637492 694097478 390168759 797638730 215575619 214982610 119272681 113112004 62299752 866764707 537071992 295981445 367694169 372249942 638815928 884719233 244295322 687500589 175687671 489567654 788443458 865948456 712020177 671091117 774372746 972512149 284261928 543967298 424301390 559649013 29677258 124502452 268400745 838474778 327319928 245862016 327434943 986552723 722569743 795289130 334655350 45804638 292126555 496584437 334429542 332103578 761960257 902785892 302880061 68919978 921525127 227982491 997642029 383582464 739528721 814803779 23012354 351553010 645080980 127128889 931960655 589341419 978481989 337396244 264215513 220777119 963809425 714747530 689829331 663692661 18268200 147391756 925382833 553272645 525362524 41187963 308468074 613857968 606899427 235096048 489591120 549904278 27162353 100438304 728883503 215099356 32034367 487522678 396473950 847475657 533530170 344996029 565214159 958668419 355229946 959361310 210512006 759241885 744863671 497402908 168574011 347404588 22908164 568370583 769483236 430171923 392137763 930451725 568551875 263057034 633662071 514100653 501867540 324380102 9831392 881049234 922722971 450204923 293758280 387634031 543736811 135524646 325763889 933529692 539426691 874117976 739380317 960139350 104134326 329646399 116070607 940024094 270141676 959208987 788677668 945420064 509952548 742752568 379545501 237971673 594750719 218803361 337434189 326780343 478626004 291706388 883395442 667888954 634866101 434766339 744149259 985079287 979867208 764150082 698829647 982107104 724922044 152734114 655589051 411390523 339668205 63161787 398402551 66761056 409666038 470402035 265709110 805359339 634294515 857179313 869814655 53303690 230453673 837843091 404286765 987122865 159851669 10218197 240675388 676506940 710810941 138203577 525593364 3547606 137373542 529637200 394383461 932312375 153101729 815897397 127539427 48096912 245466307 750143875 839519268 184523645 140950107 330113146 938276024 564292318 932944889 360390394 22442685 164957937 55436447 549992934 776463504 322258851 89227292 203511907 905209566 155962368 330752271 718684027 898680036 282455468 959227446 134813619 615209044 717419544 91069738 152259280 326374422 923245989 920685160 154021170 779126067 875528656 482926580 610493273 531070050 226998703 560885955 947663502 159529229 253518981 902839676 419747814 67776651 410236036 19552361 478787831 125468163 957957713 955465380 727637090 893480081 100739446 862117761 684158405 58847766 629575678 601800707 618986626 80380208 435871359 824746038 174053222 179540848 545531006 336346658 642527799 371059081 956377632 779906432 762268127 366492954 510508645 542929801 587884688 131862948 820955950 721329427 140411541 410356911 791999864 21292946 590444701 235334295 136959006 406768788 854036814 617566986 616826735 249607609 269914623 436157410 713290383 634200603 28147859 8071289 709546682 522156325 944445392 762371135 5424651 320001558 349965369 359025727 154257103 999058861 186657346 911766085 958853136 177871238 610281575 43213777 333698805 818986580 725653253 610953466 858785797 633753258 961898557 769293513 548096458 305556669 293688367 214574516 126115116 660708365 607078030 106878018 259785687 154790645 374738530 555884690 152793055 685402234 639081957 213117556 507133973 24138969 873978314 748471813 885787643 693107607 628627278 616392174 638886162 620290987 569412220 394082556 430844397 471075211 845778117 664546308 201489670 488784493 572464938 89999370 781859475 886458646 544483615 301083596 746137856 588911998 104938732 623798600 199120067 835674535 359084678 843258431 533124578 38357348 148871420 24734203 472621286 788012709 237004471 76379398 189350443 996609160 445848264 969452590 833256896 52224687 171383411 626451754 916078102 435388641 593297120 724621614 647685261 57358113 998922671 778265282 468031625 924369584 442142201 417821408 979208756 162710961 770895835 756458587 706119444 557118787 668847923 373840829 145661404 237612914 174302754 503047860 451718651 287779148 780931996 980834883 600015344 118424997 919583143 52024024 95046091 482911751 875566592 104157730 798031727 387352614 27243696 297752438 159462154 784351138 273069252 4963499 910713544 904966664 182474259 12772095 349655406 688361040 320734352 808338412 17307421 735146680 415641048 69785238 33879267 803171899 475364925 75185710 845054842 244304961 758965600 553925091 329456652 314635398 581319606 333251086 174538517 381147752 287266163 367925619 950487335 222297302 548604432 667240042 652025129 838001308 315337632 360594742 614711012 543916867 95664842 111816666 682754732 863497872 851704345 458417161 886479442 657258748 30525675 440757559 22238252 231604196 896733070 307967372 747560619 951671975 532702895 817522956 306877951 674310833 721667180 142641886 791526592 285334904 109713518 241464408 609566401 132816347 869720284 851848877 492055041 399486372 97401426 922322350 67770929 883564962 542853652 543095685 655211168 437566426 581094196 290700529 921874738 761691073 355701611 339613042 63330854 662983059 138227902 161000787 624588619 570009599 938068158 610938639 873813629 978010865 396176181 445124480 553055208 318741823 152879226 206708446 635968475 988044933 25291358 197155358 935526712 575988556 342057919 495223059 617440787 237660322 395181036 306542791 743966651 813439289 731577865 685487834 17553947 661884979 988398347 897945906 508291957 465914129 237904790 990462791 687634695 700938929 912916841 678599267 7406143 966509327 231118055 899773917 765630291 728044035 500029455 616146318 231160025 165866174 278821894 520615944 428590094 37432884 654788718 786250477 50958530 541707385 626132001 835797259 633214457 97841348 829975408 773250712 301314092 126688429 402972374 408489485 896790983 961880299 780896738 824715999 78875001 779051638 372231576 949178405 767271178 947767622 346713836 693679170 46481860 202480672 240023259 188653700 795640023 604316125 689042804 94793407 774489586 49376675 467643670 36688301 130409244 917406427 854029714 364393040 466277472 422642901 963664056 30368 10000789 440791772 230441372 471875395 564697985 154670106 184965776 456448016 655523490 868953878 746181763 553377251 386178739 711717144 839238642 747298014 911658446 522832101 986023674 255964515 558856309 121756574 690097472 273359146 843902190 539734164 804134529 213228308 466281807 290119260 179620665 322824738 535538633 172052086 427867186 858705186 399859084 93373339 175009885 670121979 562452849 286063400 366748887 55269768 987400925 153824283 510446049 418952144 179565818 785273430 320668875 451781105 940054522 526085799 577255125 142243993 395481084 881834146 585780824 202761982 656120313 197208668 855829885 743449842 607337717 59876719 977239947 162889196 148533059 989789756 5682909 842743655 364745320 23024689 948648904 106852346 180828493 268564505 787662774 621478432 687927745 175855050 661976897 675351220 290768324 373039713 28871633 914482437 119592936 318517631 459272337 948146421 127318120 337461440 597587783 224745174 923233513 484358413 932831056 969763240 192979747 125658745 456803866 804285644 525977566 605752887 321251663 817888101 659845549 648499992 510948728 827144761 556647968 197511441 527311621 849723115 687519926 792155651 758637084 675646549 756362649 65907225 497657091 302276246 164206403 942989365 229888911 598224839 655859853 162201747 935127865 92266715 975836631 129808381 133505703 164747753 900850293 633671581 462049060 294985127 152143246 462390390 791616042 815241154 940062291 562425739 582797838 666427867 543574298 455423733 194005168 879408084 661762092 935038056 314432044 112219059 306522887 973347336 778197229 425665367 939419414 69987269 768323242 922577003 773198860 914682949 128114808 554652727 30676350 940327409 734099970 11707799 714850896 228342370 918977585 279664798 578588776 93354584 883389376 273101807 96781867 344101371 118895689 232375659 561331486 661379001 69321939 971504734 111399023 586131173 446090580 106830160 185803261 523388648 179554965 789517000 908479601 576733543 316007501 371479414 509179732 725431040 157704717 981789793 15064563 326689084 506424031 844639130 645537370 330523681 855551196 242467026 849075716 276114582 393917353 566355319 165368390 415447850 86345342 518897376 784440687 435421831 749275516 946517868 354260420 871425304 209125241 993971089 440079353 667222432 707030061 473573170 258394128 359368435 159860214 410513427 9651346 164864483 832184315 228389560 618150247 771665670 953771599 676744363 393616379 805123942 586145394 687019003 407816217 783948115 806880686 980216339 24402562 572066824 876775407 442270447 874039816 942713128 475396435 785059847 645610406 146195814 381767883 499854799 205815171 105068715 67058309 406987744 974505168 819833462 306245206 764646393 249468003 581372475 855394707 364334878 341510463