13
603569295 841119850 864906375 544113669 648358445 379890237 716067245 148107050 915642001 424158105 325307000 121599677 69618057 564413422 97486569 819709917 697793700 818223927 7295071 779131225 162672546 155165448 436290748 23890164 182937051 113929107 230709767 69783899 243511135 35200975 561174874 847080430 728837191 278597608 243710459 229711995 511004211 959777704 230335411 279162572 236452169 555642412 400762249 306070226 972572200 498248819 125780137 522882260 168989105 133075208 302013478 331661651 288240657 590820592 208068181 323694074 704749699 438777948 245994339 800777200 326495289 807169214 500373990 55332473 938283188 744084449 137560834 449287393 556378512 367896246 728449965 792830681 776055024 981728580 98900901 748627217 332493758 77197404 124025836 501482863 62788978 426039314 833144514 351029635 16859899 41212688 674723709 574125964 332507003 920718049 227419524 659002292 580403622 727793514 566851132 371203169 324394322 704411966 820490562 880772834 924824578 401456886 526119875 700879595 235701826 477537142 302023172 568195584 407250912 426049008 69678441 470039890 704604689 755339321 821069526 573980954 649068376 348309594 623278 981575379 121544002 228042802 640577664 554463990 955836316 59945155 925667160 280230631 764357122 598674081 13519824 541698059 130961 392156065 95094014 88349153 869693207 397117186 656544737 129460478 675682560 726223178 599500369 380287242 334078859 273086254 954268197 983147235 621395848 954891475 964722607 595456217 35450636 457816630 149920200 991286952 517761786 75587353 124033942 134635267 526777801 137553766 676333326 379425128 529709832 771427340 467774281 251919398 21060885 124319011 381379877 696743446 703058556 980880246 929547054 37137408 106482859 736331610 20284636 727878707 543739444 837523609 175851283 579190080 147856598 325771484 570477025 518134750 253875203 694510967 652770017 780653004 684581100 181619703 12594491 66807291 805563409 480368772 318726689 826624295 604687784 552622932 375884100 160262699 386019537 157947513 197400107 492502396 894279124 70201109 72897463 438018561 760241084 248748746 17208635 908097682 574520230 440202026 278748792 680911800 987229360 931518809 314081163 671810453 965654878 326675655 738617744 771218281 807044427 909860799 450358935 264248570 462483725 678759401 424511269 848503262 836706914 621911376 193522018 730986031 544628851 266419481 21520952 304869928 515168227 891245960 65483970 89688451 183964345 344232762 623116617 171193698 128267930 937197780 695520517 93922802 263873428 286654620 717657449 70917849 196515413 20532743 187682785 511515504 699292144 612194055 212535125 388515417 86621790 406057143 119501442 631250642 672476624 993538767 936120570 187644845 884784720 854120906 129849662 68749058 50870027 752966279 92459123 179137958 542680418 787979640 125577126 806553847 74634254 695750941 729988062 123666033 716283684 917670847 635181537 268092187 382381261 847716662 656607604 469003052 106290165 628625412 100253687 778766789 474680538 888890623 966411634 211981617 743011523 948777662 133247042 793881550 554260300 225706165 825535874 96940712 866202171 951113000 756010925 793352791 499380300 338515346 917018824 68180343 108702552 404716720 336272530 491083814 104949742 845396501 960086866 211239907 326538272 60340546 990006696 801218811 801747535 808934690 13200421 397275417 610228711 146447463 43673327 164489005 224669994 869209201 113946083 90872159 672838561 869957008 884224950 172218854 208472347 653760134 240399198 317174899 910993220 429188094 808258713 15942955 274584588 620861938 79699228 601122861 533718850 922222291 254858031 335466379 583673340 268058452 732741796 193902044 267022282 776415123 210907415 491692276 498140684 324853498 582564435 170979238 194810499 319305745 195714458 255799212 825582245 436113656 572974112 736575458 865301751 233749184 605034780 992402705 854611123 537250374 446041925 240846332 459472658 700899956 576312711 43145991 968958409 161570867 89564402 88497050 790502356 300471817 580189326 288643033 625325316 15270121 312138637 672652181 334575866 507853096 928451394 12674470 943966752 353941865 749249928 661784862 587691049 206801067 506703927 294818531 744051442 952745852 535664864 56040459 653645802 964493941 951702824 475120570 126064801 41267219 563617620 769083524 194255402 143806939 57726550 672097084 11593426 222381554 344749259 346169292 730234650 125717012 358843762 526717761 479658877 960610057 41018983 67349919 19927483 547722910 214684817 763978925 500468755 602866047 672535751 6630916 567359981 624238568 334267852 545941149 518022153 897885472 167541032 564793921 894208778 77783948 236890999 905802204 300165502 434156624 104487856 30400145 559873636 315847984 557117907 39532506 276458034 598136890 959398798 296385518 145859793 26599974 912880809 498844914 629466021 585416553 357992197 49342362 62171480 692260049 595283511 432709999 442661881 762824543 997503921 189387018 840608491 86911279 95189215 140773987 521067903 52193437 23690498 80941532 368041422 433324771 120474038 497015822 31461654 932389202 793401340 29837813 958989177 558798509 381199094 588455191 144215055 739191291 637797553 58902902 283967699 85597423 491612901 726629580 700938332 341633181 916016598 394063183 428544460 863722180 387353536 949612363 915915617 411044034 30553888 136473398 844368806 3544292 633489221 728346826 788449861 279406920 610701006 747439031 838205429 844416466 188410581 834936851 436124116 678724501 746356119 720091815 764321924 90485379 446721389 317776616 432118561 215254346 711839799 860663021 78976519 99193328 810275378 847408503 362753728 693345632 983881901 59638893 549406291 469887481 787985720 190372511 601810768 251203085 937811542 292532556 95619544 978738489 127469400 384260026 657462983 726341885 104351834 274301267 816827265 403589589 592077883 248945819 618843936 156434041 109608833 697820455 255627369 772400577 397745317 618381097 318262569 234143578 678019991 720185226 704031059 318522070 910557737 158358186 422241521 700885638 450890743 370377431 679624120 430876509 754637457 189603463 157218388 858989291 316421096 974045653 115095240 908498979 75507831 733939176 64933013 37633030 284275990 173076748 662549974 682021308 643974211 980812543 916164886 174510561 553514128 472712304 493032631 464071858 631070491 915274152 17473855 81961227 138167942 697097975 512837736 892805399 739217804 522572490 604311050 55638893 349134502 719406290 816654238 424642333 453345459 734103617 314791730 737621449 907180365 977341704 272159116 403670936 810670606 188323995 578181497 364184727 661036300 71214122 680772951 144623150 839004640 698246806 226584377 977172583 247861140 591938479 722494341 987078945 114510963 326805384 42717831 463645465 46211667 711888436 740804165 352073492 445992046 55595888 942211308 205688771 32937585 214370417 609359707 696124557 255210779 40057563 60309277 916247079 111271685 593598594 60870222 802792692 291845393 139970965 632481634 539706533 731909444 207492334 379301837 698936773 534297719 274536035 15098598 433025752 986424471 755902763 637615611 284932876 811498651 579826912 490621647 696952602 646713695 952497720 245593518 901924474 992555284 158419161 670687912 956343335 752017755 584074500 611652386 43863141 724045465 96650379 436086040 308471269 304142714 815387878 7408035 838440433 89923906 22506633 123982544 928864743 630925762 761598155 213797612 294940772 193941426 556935626 991893374 840655122 509433339 90003251 595095955 354504982 248422412 265783861 310848311 440160 849858361 922500697 896819674 426420186 19151070 185422074 587407821 175810150 809945 447332222 14250576 943250224 322355222 990749493 724631326 953280984 604864008 938428938 248221750 798805434 347880923 92631483 491976915 857314263 182634735 87072864 64335604 431057147 205373091 375183915 284013674 907747818 150200972 180833341 186684363 21868408 366255415 774092184 197678558 219581726 221424400 64445500 15348309 543779622 55194986 739979635 349576965 512575360 530924933 597798715 163897154 878805856 542946565 655874069 588636478 725581300 595463299 652972083 9154806 653352756 880672364 293168480 561100568 30873329 326518188 747784931 905258110 692773603 374393475 102936661 764871696 595817875 19898527 780220005 992113863 927609887 372716000 341690821 440185240 756157299 792005903 604082394 487479514 334952461 112472823 76115986 913050127 560452488 581604435 922204933 213805238 314793158 67889773 627422172 198182854 394407961 227723462 103440957 939697930 602116937 58893985 704569619 50451171 78792512 337305984 42565027 858918765 562538350 236772215 151620365 318695642 28778111 755702759 806175156 216246938 720691948 734807508 129297058 281144430 168928302 904018357 347466034 483721461 971908130 974888206 681904315 218832450 202611661 637861638 11046740 804728599 696755623 715616359 855179770 628064502 905438709 750261164 339499626 467977052 987033379 491119991 639189060 15811483 99339110 297880576 84574787 820031058 32688077 213871845 101175481 54132746 117890195 301157881 390370573 942314692 276046080 72274881 13663501 331174108 562652885 24710241 135902700 111924868 592842967 843598836 739989370 498281669 446376359 79488989 818775088 433409731 423125347 457964141 301737580 522464457 755844717 386312367 342495508 641049161 452700578 296187356 547698273 423107140 597345237 938068846 217938191 725907684 862860093 231601692 57081785 425512971 108828300 45500851 537437839 701671267 741616053 129943568 52469295 187992406 61948924 871244383 473918503 485074271 181724884 775656084 7538721 937569601 14484810 202550595 431135121 467185389 351254317 978833394 890292529 948599555 769418599 108230713 527023598 632278685 192348771 584105383 910308023 301177071 482122600 300262221 2848331 223738646 430205790 55317627 264247418 344671080 779078376 738165922 829745351 960803260 366338365 689800438 750889221 380823175 744867399 34540701 700524930 96121710 13374089 443333818 897237631 635309054 404080897 424261222 120104099 596429669 860882971 30412115 750123106 343005564 330674336 605487804 419260576 613396492 513321797 683507995 958067572 292400166 421673910 640329282 105719786 788012275 182646079 856609007 21351809 927513479 891149708 721876740 23635182 757040163 17726917 773389179 392349211 421807815 50166760 512453310 18237477 911049731 395381791 620876949 106571654 726056127 226364746 525832230 191968979 739686543 209340218 150036544 884603076 483530494 790365827 990322862 124059128 973011906 846931862 145410938 753041744 590597929 719804044 629193292 347638086 737530961 402582464 592503663 159338769 452749224 104956966 30092612 216315314 352855123 650969562 322886968 78911243 729850674 848719199 123396588 322053577 58059410 273433133 206656646 394106271 916315326 49495867 518165399 741843591 896427729 663576337 494885329 339542017 235896740 124078614 687180103 973427702 379177445 132200125 132766464 684443035 89673457 15375443 900758350 442528580 518861371 223645311 373956190 248712038 72364503 497352778 570765615 982940287 770785911 629938627 229562917 539617596 679434494 747728316 281461181 428378582 263821013 628862876 767920600 499717753 605457856 307617062 473145448 984635301 439817188 458428279 521594696 529490645 326320088 422353039 972019226 845181459 498514716 345975409 93893490 423395586 843328187 517175472 258852232 466630458 147114092 488415149 6248047 679064953 236143458 140225594 107443528 499964471 769088470 875364128 999682225 227062686 35497550 325344032 64214346 475314738 636288677 585809042 4805376 962608765 8162074 976824602 807790217 359193157 175316370 754200074 782588743 871160924 123891905 41440968 190307741 123522363 529856117 49072154 802587316 618515941 189297749 762547211 118480406 810902585 490427698 970678997 37965264 525925248 148539388 102179611 1239979 784828066 687988653 6045356 599953190 548667094 835386324 260259767 907860251 863219061 14459834 542965353 734379978 990868112 584406321 924687719 114390468 966778804 973759873 769494151 585294738 15573981 384557721 556291510 826476567 874985419 379486866 716958197 400910661 380542621 819137808 254667006 17887046 359642821 113228728 617840236 760826281 948615053 878100003 521202891 664350473 745076203 64168237 251246810 735944308 501090924 28450888 702851143 467869721 2210754 324861653 905680825 870301109 709419374 314488695 549294035 436921152 693975561 266252225 837831813 74518175 937906400 92498813 92405221 150065580 58243907 562761824 910891861 6858953 440861820 432094745 523725792 38454383 348779348 774972602 774398691 849870272 803423490 329766193 170256352 658150611 507144212 75937170 528451713 69079945 390425865 77745741 506001098 936917793 196514332 196349270 863952334 134420725 141364449 808873922 137002671 199608357 371635739 47894525 58983676 665013925 332505636 582709469 703468308 681284984 357682064 330383359 531155249 13621914 660149552 701411601 671772525 19810124 629865138 52740597 88890069 20290996 130486338 594891167 809725155 179517036 791240438 673677483 166454128 932604887 335067764 303456799 132213237 706703503 203867691 191196914 224233787 536373327 773906383 927702096 217658305 984104813 258085448 601329920 997726727 770751366 155257881 669499245 790561490 785123019 722239842 879451560 657930381 705242546 474342720 467655530 737275949 118099517 993849379 903730077 50704398 328917136 59703235 35434001 888137005 263570926 226630915 112370785 799944254 853053664 40072874 870118925 837158471 150674688 471448838 687401557 921426055 626706719 209417162 564503904 264346097 931657004 443955457 922276479 489415910 770814544 242448368 79208218 888914061 236297740 982938295 939618459 417731242 895157896 975052461 305868240 11245182 54199735 270755391 811189436 907253400 163344632 533824720 596928230 314019320 5273551 136846146 87961734 484496637 346263308 652465639 748842734 130436672 948937462 523635572 619852582 719751999 766083940 699060800 461182420 2381673 534515454 253317238 272629281 282189709 80886058 578497521 293434891 135085794 849252913 104624320 894855560 12597538 490965406 344300149 179133224 348755324 481146295 119611325 833251961 827409604 772076964 434611054 957846276 573530785 958246627 430215217 145799144 576846926 129276010 606981564 431744966 516307830 860298802 704374247 798497539 941184861 135388128 91932424 76270648 984641041 49073110 823642574 849754945 392554883 167942716 881404535 741310207 649089011 1015853 427078527 329014974 625609183 861689581 286861243 199139962 672452567 717076460 344939106 101815853 698868836 951920670 533560819 67693025 664735831 237935059 718706931 605920685 373323187 663155721 534707699 210480587 564745197 210866632 912751898 957300080 378809348 794156427 698610280 880414726 647688646 125688800 209429693 273297823 839894748 348807303 324954151 364863674 65883756 669893257 466679527 617268959 474330286 240339 537478350 139066110 90691765 256185274 597503162 316531318 919340995 984727227 527011906 336602552 195593853 292280163 293902625 426919567 86436583 845029272 307334286 586641596 823234438 369280346 859939419 515645545 718087649 37409929 880509220 636487771 707303186 199705106 106273089 34149831 52461812 643751440 25732307 143153577 899936714 475751835 312201261 671794069 460479056 839213167 8396614 508589275 131493324 154815605 935508842 70446273 999844877 95359488 509604235 675595675 464639834 222060013 191241213 182727476 259469942 924266799 819215247 966773128 123971899 925488337 853439325 28950077 421756136 879171633 24620020 174209209 207439827 336821281 846003278 667918883 28550808 706916258 29024517 12560498 714248230 964533360 935523144 566609466 59892841 445127373 242205134 524532675 667187386 285962714 559776517 926657329 210229506 231508123 745946816 186717771 9512819 451902501 68184214 431268955 183590493 92804234 605478165 391030320 282141882 303997802 58949197 310692690 10914054 87973714 175769554 577678650 905023440 111292691 144288109 964916281 408936430 239009610 341965315 76123810 524972324 901741832 855297505 735201830 133249949 453760680 774435968 142762768 905663181 842620182 426548090 89253667 935424417 32026248 332800354 70082658 336024050 244265917 380775348 199454470 184755997 556544902 777133120 89779431 520353959 773937596 907212078 929290390 12947199 101693753 857930566 537919523 3435578 565744430 125637712 989201900 19505103 900073680 984481035 777684651 595210222 263545484 719454684 383150998 295571732 52255031 453233656 484112148 149037314 834009004 683566619 333793312 243070265 313216098 423572743 763424224 87153687 183301180 545230973 952617259 284994933 403161532 343053141 140946878 968905962 468690854 130148771 840927432 221280893 967146172 471128442 816491115 83208015 43099485 52158472 378779747 947870890 505392128 862891896 96908197 191917491 398974874 430701509 434987756 564707338 706790618 50928340 504377392 890091799 596159313 456994644 175086725 851837212 800047786 316033603 673259533 121254999 298698741 366703324 195052258 118361272 837831766 11543367 201569288 733447618 63701839 432865401 681318501 421610334 148273656 630743064 613527825 547248530 61444567 48515575 111955862 620751551 951960288 468849620 510843343 400635960 925844264 538446435 252473165 578408409 854480038 925732699 552179774 5695138 144952382 747232033 124056411 982784149 611291766 178142065 568748126 527509971 611007466 102582986 949120305 759281123 733326050 562648124 159046012 647286983 463680065 123518240 268038528 268156712 592367860 631398237 668792672 370728484 169844665 921265838 801653259 876841070 699514896 353833027 882536208 844467278 101065053 859108985 679767786 564873185 889767416 101032271 92383149 353291242 203615257 41503448 112572358 936941308 456667938 124134736 584228284 772864369 100169343 704783178 41021074 692537203 336181409 709813746 915782053 358542440 483595943 717435306 235383503 35627198 923784699 970436078 732610843 877366118 682061422 264894988 442239296 571828832 365927260 387138811 925120074 569542517 281158625 890208798 506483818 737826563 866859900 943228469 363207291 967029243 648011640 404228365 512082806 836709415 966558478 427864852 195251849 302670780 997816524 283151718 338297979 921601216 253587789 70908815 651483693 935649212 188320169 93722982 359994403 554247429 333378160 137630836 123789940 614536785 880356000 482790124 204879708 747215893 426018586 568086999 566761496 926546593 972315365 78844295 763256001 791390202 359225513 811024216 94060975 357042031 94175928 284875320 131159606 200280083 208300501 782643300 135929288 396620671 728882648 348440057 950868100 62260801 338587259 74658033 529313953 218943252 409964524 734193661 818675512 835983110 302280653 385437001 615046062 127112377 316797662 230818423 918502579 676023175 41842632 865079921 33065199 136018560 149955234 16741172 188815010 358255736 651900838 177260664 754876407 233299845 525700722 558260866 148077013 864287981 485435266 677390966 935747600 895399790 411584620 754423105 583899259 566381639 992376472 198945315 693494017 309174127 429763738 464512955 985197302 324122736 182109235 870778868 312657663 332064470 740036406 501472673 542836572 391937237 678733337 150229338 625237082 56950418 708490204 773314095 921238400 193925463 303221420 709502359 89325246 714806040 316441823 525740872 133704039 308818288 724686187 827198056 470508781 6966284 144227370 308222442 331089020 326336606 31517669 643746683 510917442 771554075 145219349 53754007 16007671 676469053 203983345 641244754 733419471 912473549 267075208 507174230 958915379 570296629 216676582 900756991 137619028 533118405 426497856 271323067 694453059 3700402 951037489 164961833 10666686 95264853 473184276 194272073 274117825 504701945 690535122 785035267 128772380 688270838 691305640 144780051 364739884 895288985 786024805 98159348 660278893 905616380 457849945 471710631 328429368 674526527 372467616 466048396 60161292 651481838 589887830 754614351 655182241 540925312 772092551 518365293 488706531 97793186 565153732 615340722 602495131 255688848 252892348 731267511 943959686 944197988 876047563 161215929 692003332 514588727 111891643 204798585 272721466 569741588 676509216 601150834 96784475 48976825 67199224 9462133 552975030 509603420 764076484 60673630 50528725 388685394 579038923 391751623 486478580 144192649 7092338 88973705 252397863 112501053 672757582 48873908 56699034 401321504 62606203 748702367 768426598 174497846 953500952 41148057 596755801 482526527 642298892 693540276 384019719 562014482 703002409 936994749 71617895 319595252 997668379 974662993 708280647 429223661 218930975 47275586 425932676 78539680 136249291 678330539 191040733 661523240 579720813 100256133 915361110 642327016 848958500 683787701 816824863 654975811 577452125 266097023 137502332 72267376 959637299 374038417 634281858 515156067 311033159 558416119 687267685 161217897 385595471 248064691 590441558 457042813 295340278 16374228 535582493 284105935 547221133 579139592 945629175 126941940 679395725 713506645 769268956 380870585 249810705 438610178 35846389 827262830 704707201 25865087 899530206 516860859 252419870 386328423 884533292 563453029 944744542 571800971 724670926 182856373 819865662 167628844 639899186 115205933 184003072 27998038 251828235 731224205 607137630 49973769 710682511 139049714 763480414 332467827 519920299 13291113 771078005 408283055 840553943 328301566 286664508 592600509 697678791 539084379 978928932 582212077 102537401 776189834 6529407 679724694 959046207 678911435 847353538 451461752 646633735 883872976 331976156 898461970 467613540 939113786 948435739 178296045 78163493 711916147 510763872 450600159 577723626 134358236 858883214 270793928 315176168 145547715 863394437 12854953 684632094 842323363 447583396 639685862 471029556 454112803 171926915 282592122 133024231 871796819 734053874 632174332 755669788 66030023 530636295 75799687 857660175 331588394 254095732 788340034 43504534 617375970 91456552 473744526 751734207 950339766 744538454 66910368 95887475 607932885 932281694 633035935 302772607 379865083 125238156 773802163 686494252 149681437 56394278 672034850 21478249 642964518 304209175 629664403 561510907 687361837 705464091 271687441 18950224 959559823 912543841 914971131 429452153 4000387 388715650 33702719 954340153 133254097 100613087 902743994 593703348 885411148 388296289 748992321 117792590 366050811 375310843 804286843 515732249 284221487 476321686 537210498 927186005 633047227 19391261 341213271 320409057 724855352 465417078 191875647 536931534 377960913 106846771 966383687 234477666 348078787 86399 41334178 333849251 953215860 944078173 927552599 838627001 184890821 529061280 956419591 550941632 904372123 613222793 66673874 188593604 89544472 456400739 968295975 575108066 475792000 162025606 895517123 53163711 627442684 87392764 590095245 5403590 46755901 556478926 92397622 394834689 409081691 133731801 728683940 362297544 77809967 508752898 53440904 115217154 37814171 862376862 518675152 794702661 475599648 437865393 983296265 417660487 894266132 804108599 992768553 222574491 966134205 740802035 275738202 593576883 680711165 865833447 451496839 579983433 274828732 543894462 974818122 683910424 677626263 556018421 898724334 607952596 917287685 952165239 575686116 807618223 667058460 94361261 602320877 142658101 532226654 438133501 412834954 279009145 94758459 258119866 354100002 60892658 851438268 629838204 506985907 384665792 348188011 958482746 964649225 475533109 354893567 791983706 11959892 885036196 200518486 910684227 345505151 117806165 715365825 921191267 925424388 382424278 15552522 380261624 377598745 400295542 670911491 642950066 531821054 765669950 901069932 885921056 826562608 605024559 368275620 186064874 989690352 716463631 144547614 954339570 44513099 351957547 598839636 56472992 89510103 799358122 967157219 435015254 917164287 682523037 356206515 695105034 917463681 224275403 927883024 147578785 477087311 598794508 790528851 8908358 216980818 544115143 894829415 43543419 149139695 115621394 82124660 138830040 832085025 79188640 945685977 876598124 431146187 397041972 933071116 520656290 196400087 752744694 955671545 966080741 287784090 164394419 513702134 205247764 241186188 441585152 352826550 718273499 892896026 143355394 727181858 109876837 539986903 474527632 5936623 689126599 590149026 88061283 680473005 274750410 167249923 478675341 3864893 450912476 875717313 789452376 971568767 924633767 542197063 779756671 890714501 829981154 796667456 256932994 887745284 37853637 698518146 93088193 756127136 443930532 88959954 335825353 553807369 628946857 662869351 412260358 170589815 105534736 500321641 851062821 380285146 520087930 182254521 236666406 971000407 910488201 26118775 795085533 835121961 420832204 427358563 578352821 103329717 224026012 835285815 991075002 114396015 386320321 84163188 870523151 830250853 173123142 58864864 236574581 802070000 721734215 648834940 972659815 827268952 1672940 676238995 60070457 521760871 711009883 296736863 345277637 621498077 175372004 140363163 309136397 596204209 567721726 740005584 699533926 644264104 427807758 690608921 758660119 814128079 627288476 481699629 496895291 800411618 540564493 585986239 454997977 114815068 87337538 280174152 794600386 89010478 808929513 854670843 463287715 519939389 3924066 808565352 993953832 179296070 948928515 155606588 775500279 369166600 895612172 327550565 13430697 323419924 18159479 624607182 990064369 497964321 106306805 339476020 150892299 499387664 925462259 605890276 614202732 12799790 738580794 261319477 101810268 547510301 115990314 417614350 919966056 972430753 226179695 913919882 4243182 27624570 69526463 779743462 249307536 817655002 107294020 115254600 141074919 977969872 739861782 983655654 328450553 846168587 323131667 479342852 198072611 101110285 85233121 812275343 113910075 676330282 73594814 68236710 76356942 42101494 485851060 996322998 867048613 564547121 762759239 871291795 592171691 684802069 503551616 841479228 502457064 463362002 956733828 496048349 293848234 549111969 332220362 622298787 247796916 655352030 101641632 445869527 756462315 39391119 110661229 722888757 715721401 36772409 791125467 792078343 78873903 129492886 640917701 798438882 694040007 403676933 669730671 138728058 88478995 25798646 832723652 443452425 489160649 641973839 792017140 783008883 191085801 124237496 405307663 438882717 632105892 359465661 884752244 241084566 398856780 995413474 963973323 967094548 32185876 607615149 611689250 963576153 737108035 252606944 614531394 283664402 508800244 136778424 274908826 449795605 162577071 107632471 893248031 651737720 749606310 537781530 434746596 793208477 662019026 692570625 84607554 146641277 52036279 969359798 387725844 303409425 817289631 351699160 270503966 701991874 959314310 882193217 518084386 548938704 987316527 132615773 685119472 496116764 121910564 960028298 945912370 284487635 67660762 691676760 936225355 669783438 81974649 223488310 315508275 743993676 916058935 400115829 890634953 968095214 221991986 130877156 124020998 39281611 482576317 394524965 593789851 294406986 129234541 964390603 695862056 116551061 949522742 380981522 465184192 71433299 193526179 263612921 355920934 113703308 807806047 144662648 783486746 889780696 368150958 98995014 486290731 284209886 351627209 229442044 104821459 573619196 360319200 228842458 465417173 842895517 475883789 59207017 989818869 605118330 876113986 685680919 574185757 825636721 919178807 891886315 749586387 112704979 8015595 105507314 226408287 815821642 102686329 862411400 705602332 470837287 813922780 44409422 755047174 165549983 273851466 712384999 739169179 634170667 941227457 57102711 329582543 269627605 116309728 319401406 874745935 844940080 857598691 301448052 523093160 776777491 45850726 272679540 741998836 53866322 230703221 968407124 869687964 333389550 683334883 427806655 804226837 497257656 472216078 411790370 515324005 746067544 124175363 107009543 380238204 917919186 164112254 709820748 40063151 132938348 881738520 914809086 977878428 739337204 68773497 500971582 368631054 114624224 626167488 110629883 168490546 856870709 931553373 38178503 42776618 467404615 318501525 699519822 964662272 790717603 111310185 332502636 536785140 88001914 439512180 769539711 858437467 603624434 331876818 898500618 736562783 213615331 665826063 714441204 805468901 587115927 67929145 26616314 701740151 694096634 137246197 722747063 403483702 921315937 613441932 298776687 241236911 931943457 998296509 58415542 722661053 962123060 390918179 111962553 902641341 830430359 881502264 613595167 434054786 65895441 364612144 23133928 279510772 30438200 737575133 84979666 470070493 658020644 111595980 24327003 204633637 101358543 747074066 608117340 875190846 360515992 906894027 116427751 144975808 757706895 27359659 867636862 719829948 418277838 832115781 474987648 248708190 566134404 88582808 535279343 632029845 453194952 558413271 911540617 336149519 148504763 849036649 806220012 806525408 813148995 830547016 11159038 767023904 430137441 471792744 494731110 790653433 231203130 463675227 935629242 988910025 491034886 655782463 561256333 909312725 340414603 36243974 10537274 906549007 124826783 545816617 538578845 430538101 104229882 302635821 619203986 105251011 4188829 277940358 911776419 669854190 108487367 922935458 289394453 391141174 247244561 784125563 34310967 478447692 100317149 969940209 467357710 443868402 478239031 28614036 205697486 818653634 917374384 216234760 577719000 894717533 614567744 116297838 177771993 571313992 271450025 796975980 676565003 128155220 74916331 588341416 798009410 35920064 363793233 87403856 427061238 611037794 724045786 461372205 89485479 824362935 283828773 409359556 120747696 614584170 290489958 326445182 285754163 60380701 542679943 863473163 955098234 9764046 832287367 132870221 581078038 103737385 929846201 257643034 84408971 857278898 698500816 882418381 893198962 62294042 969822238 172776559 525848203 546384383 486665131 467850048 223263677 770493904 729725970 344011374 237594434 20215922 670456556 523348597 80596623 65652858 386821754 888211224 75416904 71625480 21081438 656494942 27879232 803444005 914137977 112288203 513239262 465155152 994706585 258954583 379965561 817045182 431731142 905813764 363429558 918396273 226180171 586693235 541406537 955906142 930704609 779000971 828638430 453677525 154865927 761751419 519330383 541687681 502479002 594747288 613313162 376076806 251242223 641192394 32037170 17896559 753480597 545276432 483051712 600703541 804231015 863017273 417748716 88478517 621347396 633694640 6874783 700043933 72904235 400797686 508466434 3608837 32315016 189621223 309802728 187180944 951372643 829133112 581384991 306368004 423880393 47214512 682444811 527638982 688406906 714481981 545535542 294403863 259758407 881103620 895107404 63989415 596637252 165372480 4984298 70501007 799067120 11859082 770544940 871971355 265173134 279011368 728096559 150004517 468632591 37899280 337185461 272521593 719548758 918570452 578889598 143429144 965784965 113850768 523584493 506708230 828332749 69120028 653628459 88091149 802740014 401252223 4596931 399377259 566624703 9581229 469878266 218208182 873956684 92939565 942695904 991646185 371950933 523308822 141650695 693099891 413724468 331352522 965621484 133273220 102439333 397027441 129218730 68224291 510878209 652803223 427448888 191727318 574439617 81077340 132334833 229695990 334845929 136931764 629073249 901470632 999029367 951467881 972195181 725502410 44407440 914891078 569664954 268874739 290716259 711315649 961974630 704440727 42668164 780112474 837713947 145107498 29656274 819449044 65848155 540534484 324768626 345813409 732261802 899208244 279407116 864596635 128904227 614253045 854044766 610493843 368240037 705590492 414478083 192951577 283609261 458885523 107842648 853274216 727760263 251075273 417106224 542251252 955516000 312290755 322363719 645746307 309914619 352019994 465195344 228279140 745070844 789963970 426608916 329849005 541688573 706016032 46961999 523109167 172785436 901006765 986119376 393541839 459113616 400597452 586493416 595239244 711999342 546852430 301029819 292275964 797927703 718136043 834527216 753443697 882943164 9407295 251706363 45374142 361427289 716901707 273653283 106498126 359382036 700262199 288863497 753586976 258794590 335825496 129212502 284096392 89348621 115331871 677638232 548462237 368445689 264131641 143701474 80445024 810984072 297247659 372720988 461428134 15383696 59764564 67388190 750843226 69171859 319094553 796217369 430599148 35996253 69870645 389613640 247894656 622649210 678477137 1481625 733960166 14302626 130694127 18056551 103651247 98542364 695694783 504629851 466988053 812342791 500847691 399949444 475843222 798095351 772670432 937271356 665995413 832434996 4659540 269354998 901606855 323754093 65572360 184722362 212266713 987959378 426852368 312677735 463124947 105329498 166675726 197085106 972148498 149886219 67658024 928316111 248428583 763352807 285462321 567933002 428211957 638826379 967882446 904055179 289438089 593069238 841326529 955433502 278020593 698502435 77304859 32143808 22256521 142877220 216866170 87039600 130836591 643718539 399717335 446477905 601564403 566393061 643563011 426229260 716279280 711221035 207061731 817224229 327090202 345040418 385157225 755302159 983866797 205556030 511873698 273304879 798625268 205716586 81254740 76645855 904219021 158559600 108789663 778991908 153953186 178172199 866031509 137306143 821890738 118265203 583784048 275971501 537174631 79863419 554717127 105970270 791084454 761778858 923194500 970691022 106819270 160868084 578509541 943202433 366424114 90383232 69023672 165049376 296099818 150278412 94211597 52835198 161354378 203001260 831827106 315307564 381173459 550374974 452613708 55580557 668640178 36397749 184068424 58331168 116261168 738785551 164301438 759861989 353080769 87495931 730553004 312416405 248364015 161578904 255618831 614788130 251962136 324642503 632353872 400578320 327437282 726565469 453413518 488791660 929566729 285240618 804099225 163256547 835615592 256712926 71353470 356772129 145627041 255421894 415103297 261888210 994207446 579404736 21750192 347288208 519417033 604819562 659704613 767781049 766398467 767839810 235085538 870876969 92482307 867439410 271455283 272435955 446521238 724868801 761227615 228604326 862625785 565326833 391860873 550757737 674556125 463214344 907529866 820183167 718636238 175149523 82071370 565360043 607070625 956337935 912648251 126487651 413673856 424869223 746785066 32588682 45225393 981870604 903465652 137707700 701826373 27437294 262660021 863970 604822461 23887629 229468296 467448240 441730829 621329170 18205970 116286947 937059880 778252202 936470114 508212477 805918091 871057850 73572514 412988709 679912144 838737131 391992727 946102367 116122714 138777786 978691049 161348107 973164757 734673060 151572173 527507489 614626720 414232194 528371460 219449175 438119823 757839756 539413781 879850652 231685285 410136117 848653966 168745158 40904678 637640439 676957636 846822770 361214649 603046516 112327838 41126786 441783640 504320565 839745519 557906354 643098352 670952928 719254461 468779468 258142347 870826634 996286957 872769068 137575187 524658410 92218236 575695011 135014526 484148383 308062022 366699811 894284500 9232347 535444970 935189178 646872787 64918965 782011941 8087429 667965481 894339780 901730588 962265487 251176704 741476101 372688201 894275056 264945388 91942655 215570883 523087735 815285656 211857834 395856796 952860843 589032610 340591398 381072213 724047136 824739781 541650602 90746941 571540640 550882949 478708277 506729812 197755729 543627242 141258112 58359524 64109082 888114258 960090113 26374562 139290956 554082573 251579129 886082378 819027961 196038151 101653255 342115689 11323800 166027455 590488852 816701009 755060065 931080250 50289582 479107195 608336391 591940184 422370502 32393390 142823126 901078779 539123202 193095222 297222380 532897681 251454746 361331462 421011932 64061218 240222390 412819254 618143791 491801520 298901626 437171745 687839671 253071247 631803801 551679837 419098702 222292646 220897205 174158760 5889255 123703153 505782321 466742012 715643337 928152823 499135403 710982830 829231595 38258598 756594418 126453968 423672645 8049157 340301796 844684578 72110376 433040553 110020191 542770533 924842073 408921817 979942279 465198103 661993064 464262439 869394306 81091759 686555085 90291504 107766886 544960706 66511024 613549207 11702712 782154361 394218390 510838115 345653550 75966344 401613079 102247961 54936679 825285725 962813492 395238475 522486662 887440234 828279028 632506853 282727126 605637460 893945037 115185764 923351929 408454460 579448203 792746228 342062586 118519647 735554099 449829472 663480354 802065123 915895045 675183066 436735843 310113428 38537540 634905760 386079773 292666985 589670087 441016452 117952703 404999938 688771293 492955731 144956531 369566681 977978951 427683658 975204141 871923981 542869422 751072430 132894800 122317619 396335017 474957386 240837266 131889109 924786858 904317620 786470598 693198263 432017045 75722801 3311684 323070951 710628561 241907823 615737937 152815007 535440641 586207006 557814946 224211928 79162731 702771477 593778609 909658048 130455128 421499109 634098388 673324551 25087898 766993188 648158536 421422916 241950568 888995802 405828391 19253785 645829782 44815349 712452048 930363193 120538150 568280099 253434138 683683077 662704288 869172075 836498084 198144923 307895440 394313023 274873217 239574537 97084494 868651826 149232578 80055988 142667294 783330966 605896905 167755193 402840514 254055434 589178109 644791082 995567603 995006500 516561233 493913744 39821842 81529641 424276930 12876358 649809740 530227434 696559435 165030387 251915868 385573879 363175310 559811309 779886902 638048527 799385846 729487762 359216712 948618425 662060117 354400373 584465750 267957015 522155566 987306264 374528816 963850041 484613705 370096412 811372900 1174932 864010156 703711109 82704573 140803445 716587467 585030679 671030880 265663262 750061066 922946748 651237141 965752743 335274416 283640402 456317629 134660256 865644531 815534342 935795047 527704641 22451074 372777156 648178022 544606640 212599780 22706831 360973040 697213485 245319609 172345933 550904783 109329758 876057042 486125722 102649570 445160869 923672767 626196816 563340497 526250193 401659923 67093997 492002929 736934340 350734399 948320558 871594596 68895289 616371259 659906002 596599930 638822333 32683151 97294312 35945332 245282931 120001143 396918372 795012783 365320753 421780672 198433925 327166877 150354073 684559648 282332813 595514942 460748774 908529629 11371798 986998967 310189546 78465795 331518255 47123879 429200195 132355173 771234841 498095484 748726432 283657202 947211781 240065125 316340353 44506086 128526823 414139651 17023595 525445196 209152427 382344348 947225868 407586352 562027592 97579934 944662366 844360405 545611243 405411134 752890028 556983041 244926460 915595940 635448837 576444716 815236185 917165398 708799889 438987385 267777241 310042680 722644587 214989015 550107805 38984933 112011467 678634629 305640950 129035063 56596184 514793377 511379411 856338418 774896096 73406996 806434718 719558455 770283768 204562320 977485955 375690155 761545362 222412409 291286088 249510558 798857125 106522266 19192315 360173373 398026017 286969556 670216053 120670597 501958572 72840218 12171896 613970039 751474847 317812847 743005102 660587397 685122590 106900873 516925808 460018679 32824235 175876885 32093494 803108003 380439206 9579442 31314517 141984561 84508217 322600605 244011485 735881708 281639237 263203800 96055074 679665254 550173356 766271128 652852217 904648294 839111346 665024114 371134693 443102552 835353327 114139788 103689942 520475910 73557027 473132116 833010956 106381263 649009001 865104450 762005632 29448200 727200258 793320150 23949127 664224842 968437121 120476978 400106543 102592718 236197144 348677984 782257972 786370501 114949105 287626549 543535154 806576817 952650663 914669847 102195728 640520349 881326002 58402036 13512618 954883029 384050518 846523574 913780658 33059512 564144383 528302650 915024086 143861001 174139159 791489579 808085843 142576273 764482924 60708745 97685357 680061 409386729 879943330 639566928 376852200 20086238 183102076 35945376 972736901 97771916 138141104 465773609 831614284 49059506 479286227 639013673 433110024 325809795 405310690 318685903 889954178 933613340 86226348 33815172 960268865 877715927 694417381 955361505 494715210 755126127 53046855 495395272 164512849 785506551 134962193 541365050 805592789 170580635 577310426 630846049 120868918 567967897 96619651 952483202 617027403 575905879 444013234 50137421 754232040 849323925 368823324 496702577 635453624 455049672 383034116 595722483 185281958 77451490 403600347 679997169 832577617 456647202 27908800 849606833 94670113 15387359 243488242 900262902 38484361 820798668 531108945 159353279 241282924 480244962 964352847 858310328 56150834 408366075 908447749 662899240 110206359 129787432 159601811 745659983 437353470 542635927 193898825 622635428 472603783 597499172 155148956 157697760 54146368 35574122 7304586 1332847 50961482 250792828 901595749 89445843 924107862 285221053 101315488 165390780 765466016 65668328 23701101 674133216 326550769 784665216 337032450 436757128 766969014 349150627 182417105 204322477 891786554 376315930 679474271 216906696 973815103 834623228 374604456 880477837 870197350 381909042 881810684 773675198 485218236 635922792 863121041 409326092 921143846 964436529 427233238 686609855 882621224 303450705 213259430 209171986 88115914 550291880 645929115 707601294 899442507 680862586 911923771 643745420 57178509 443914401 860652117 883509978 131053988 87772932 616504174 1251332 469681975 350831217 627442896 954900211 986754010 343080297 216742662 760414215 160033185 643975900 299540429 42654402 947426605 512799859 104342755 888058885 63091733 750271870 448176538 815050606 283650815 212616668 311312386 193345690 656531070 24480862 76855662 787585058 112253794 545876202 641352756 434452135 749223786 268795646 241868706 588494155 611875943 458611368 348908363 771909128 955103635 648448792 667079897 755046599 13765010 771422652 495621844 76856743 374210881 943798382 744423716 657861696 156415044 908252468 851207386 812946114 932733330 780579414 453047531 897503490 178971976 94400281 331955619 928195762 215712293 573824325 516689910 827588236 884952059 718114639 452013723 840055687 219079790 119093613 447618646 232844800 743032631 943240490 162217910 117243505 887038865 906641626 775105201 895970275 667410453 478828947 561432748 452660142 259408354 14480273 350163625 438380330 108880554 534635610 219092451 177109213 108459928 735782361 4697442 845928354 306413359 309227531 538500400 525493149 280837511 986119046 758337950 23870135 929359529 920555860 993630014 668914754 679713845 621251574 417401388 347124291 100080514 978834137 799784433 212005235 993314410 2464417 650385565 954711330 537100028 869478017 131820536 498076322 457776737 989034351 196521035 764190097 150778241 735021436 142199605 284132118 721140475 900537555 160518620 503016364 821093408 154148627 24447477 353323612 775400201 441848865 700447903 727997082 273199361 352748695 940002317 119030130 207729479 442904241 73741453 744829507 164898617 58078355 95422188 622675355 899629072 291943224 239381811 902923680 26964653 381581416 187055791 600621494 134635331 347574411 956154224 955728739 354239404 980601701 161568711 129639599 274966926 862016614 710153047 548166287 67281669 650155357 667196418 275011148 93059591 593454237 872357021 110474575 504048959 967779209 733149930 256194390 112238792 825048107 11634429 991719818 59145882 198690221 444857672 193781213 398780998 401011889 2026312 753020403 234129950 163595023 735176368 361613242 25611630 445329408 909779529 945409672 948001131 429492306 72937179 893577088 875462910 945294200 4051656 232028228 765589769 589717952 488222618 877828561 414766052 499857048 722064739 473911935 551063635 166922404 667693148 949844633 420450659 669719460 702865029 654580609 833314483 290557756 16193844 711442480 735887164 778489740 509368511 536404654 60498405 582305691 429981736 935961315 527599884 286549758 20505902 145706012 876267711 508728521 23534567 143550122 861101935 598115672 617462057 412165563 765038076 137671565 214526555 38005094 659907391 917391585 692585704 345738234 60465700 561295914 57180707 796352865 192302013 419065584 185273878 105316785 1371268 615255614 41278093 381487519 901805373 61783996 527193531 630589443 423028883 403244464 774139565 136647177 1360129 244117982 548812740 618914571 381789547 763339295 656919666 41696931 533247239 202021729 239951531 593712940 763317643 149648604 242582164 808136023 568714189 427856042 913452808 570085457 895628023 807247267 951572976 649949755 721547629 331282867 280539191 144576505 734527331 54678749 133740048 735887461 151313097 682552788 207318391 533102644 298408443 864238057 427315942 684172048 66259779 667267473 130401347 682093789 816916078 372983511 490229805 238146626 653355920 256198972 808232083 548983936 63446232 612321419 51450050 784993862 943604286 331989241 782086733 530647976 239184356 915826782 119051796 390497454 450895929 326370188 776116464 601820738 190608238 55948765 285992780 109384384 723216239 416394127 791478173 392648676 641894005 134224337 630795302 295249918 390423309 291543744 696750220 453869541 756381529 748200270 91379762 552502174 80189504 725982862 83150144 171890226 494326003 202201940 414904046 945221932 528572128 191020504 399559030 571696733 246969269 685551810 681081117 822701874 954462303 472559283 67866909 596356301 606783620 698662211 744122585 997206929 842722322 440872798 303592829 599103844 41589427 247488958 4122378 121778931 973471820 87272522 146185524 467797816 141990828 561089570 265536107 670562957 604626440 665095137 94776049 851595710 203163306 775857166 526813943 10141969 100932808 594680853 606498270 707716428 145859423 203137215 557439716 988581745 644010013 713548911 440201949 685599441 961037869 444324327 659894738 934509682 531596849 658596628 254823857 673587677 72202558 372876331 196666993 676828998 37971461 291443042 380941067 93651134 67300201 907755011 103793103 20749375 502435857 562807739 728465803 648295280 765944954 138421878 489393385 262471327 851970790 929595334 948070768 665525018 373919654 460481865 452551060 758032869 119078487 707374917 284136905 43797411 80251241 480803899 720626409 970739076 624763307 101567470 916906576 544579875 9322474 20699672 565329250 364274697 436023777 146311413 865086343 201968725 284733291 354479721 464440052 989220447 136591414 265027179 654745459 510511068 578025410 107296512 121060296 549620263 667187795 405197202 593417674 599955403 886001101 314044077 423210838 363280767 268127913 192633773 907860642 129966753 65849811 473189886 494241450 501873588 619501299 211844152 703842313 756750956 566323874 20798724 745971397 702915288 138342269 253233215 65942716 716367680 213046093 187003012 265987936 732750254 592200214 859405611 185222016 330717674 25966047 608432854 693998442 294093960 801066627 454375443 424060713 866916438 927565329 770818529 221306386 399582987 982662681 925148699 8850303 401502914 798463790 754821700 104418196 936806059 860571281 22877278 653173732 73617367 62396656 771678035 658883987 654596871 483600005 844106004 837830911 509566052 305055217 384345712 656176378 106121838 838721156 80237084 825554642 618802844 703571979 46861021 18385825 686234653 824526087 27236128 87737561 475506236 634574194 44672123 412312288 347661834 920065774 918002387 273795567 982462430 689680415 932679554 489575660 25796779 776785551 327406565 535362831 81840762 711752277 44055568 40478966 402989792 124292652 718549974 21792630 680380997 617927362 892694828 219132009 294969808 772447322 159385936 770476044 259537875 56574425 35304691 607199709 976640199 953307078 880995276 959102623 495503852 813674823 301194642 521300631 442976734 628601207 909179828 377333862 192869844 953235396 270329194 595859636 930044414 841395534 470168632 610425404 311839255 362863453 829557414 606809063 135310768 988943350 229801466 247365009 45517769 117622524 854564718 874674334 70929595 735559987 686293316 418949814 401751170 987487959 792766811 697244270 468605525 701946633 74578125 661475369 507698388 197423685 109851365 437742796 38819212 580019997 900684566 203174834 795399817 582758339 809983897 783226951 424218049 892301730 30591954 322252184 9924247 885156672 196926511 933370215 473233019 883219828 204836388 727500555 723224146 997603200 424744818 191829664 552066192 351839309 705821400 59764573 401779360 815672765 350023735 293114938 248209121 250708295 496289772 43608931 833466634 158790029 679352249 110201042 51091752 709944203 432453226 61015999 447617234 629379738 846902580 773366619 365115925 51738962 500867167 88340064 49342155 778128351 132686094 453924713 129967653 838507494 513689286 384263379 506696618 863713022 677378318 607422106 966937683 173668083 503547403 652920676 332458112 182899645 763121719 236066230 745360214 195574938 149598595 45493808 677471042 996501176 818860427 42586960 48240131 172243954 983443397 950098659 950372305 968645858 256539731 932856325 659669711 770229017 317119697 18882689 486458398 994498015 626304795 305912440 20682458 129852191 958833117 205656936 165268203 721954829 441723167 910628417 770046133 591321762 956122225 447517169 587822931 774982646 342620495 488579428 947226600 178580252 291194446 750115264 147226103 547734177 682971582 659412180 170479554 852607646 678294869 509454318 699622020 304599657 815366759 720304478 286968215 774199869 925961415 452236418 348671057 220200941 362864828 118717183 811522703 171503413 418750718 251861994 946486059 613887580 740441422 746229018 792467832 884152235 348860641 792210301 284402771 31832217 304138840 454882325 736956229 982433710 964336644 436578242 139549726 632219762 9399080 426517941 258935990 787876861 878754359 607607047 8077795 94135547 578840596 819600498 265638960 850107681 71462485 64641378 463995254 664420274 810870396 108979445 401088868 12247396 753706112 685491639 44079613 57844945 140373958 633552208 40278648 957226968 70130444 32344741 441963089 932045897 458862682 700899079 719922751 337617035 161022485 580516912 431752582 739863081 252633769 697391542 442487121 176612621 762032920 906482375 841032895 425419675 867978186 94638122 437667071 621684291 780129761 334263051 532045603 773020085 967815259 424840617 582763412 890462069 457185358 24726494 675024325 916048041 725625573 247463435 106181435 886648058 827980347 537934017 479027499 80614110 87841918 921514620 257226731 702391204 680513355 950775992 127810872 401007900 45414107 417994309 22692185 825543868 604773726 407254154 451080313 425105345 832094771 33843718 168083773 289280123 58570213 843108099 57844523 636712152 90571527 164025958 375876570 918551875 701959975 707420435 851682351 642318259 481451414 108909075 344709456 14481128 912201433 325036694 415489029 957615540 595547369 290697580 635675767 200321089 697951734 86756073 625426434 530046498 973116165 793510207 671842987 884202744 489134665 729687510 373431255 579706193 893713468 749307825 350774427 448189802 309244619 54973137 90508054 790696034 16398578 287733876 805177162 928600011 612770570 220666184 738731910 60834299 511363764 226924036 261155388 61831857 166196476 739098188 591878356 139312634 385124754 116237702 23515371 874259420 845925213 249462992 306481972 739638674 998770818 657256399 40344836 160531796 712229536 130852890 951227830 728628114 418586767 756404986 509744484 883873703 829587536 248476387 944708002 193467660 475400423 58379749 255299517 641596899 797477937 847177873 633425899 182602685 963415576 509457636 56862098 661857148 758920629 215860436 254012181 610207806 873116835 294357017 770739602 437862730 425209908 721967426 19007203 696313041 330888771 528751687 580186737 12992666 629744440 377411099 206460326 105144856 435790848 461759844 599258122 233268779 161454076 85200380 268387830 124869645 594658017 177766294 639243159 353578639 393626730 893255341 963786445 119259924 187612351 587042406 557122654 465338625 161526191 428646223 161651659 492414962 957397910 594354763 505407629 439658709 971765862 711867955 397319931 407556703 26144158 996578053 493341848 187598235 81778427 761729678 164984246 528952810 939495972 804227406 882531449 333122695 697482740 698834253 452382619 737611457 138393018 862021639 202950076 299919210 290667855 217118101 792334172 100582124 811472864 150258160 540240833 783238719 714642482 937560765 43311782 740786640 786655177 536653630 928384875 720949970 150899668 93369115 102419139 90395633 897596521 984950588 276034695 447595620 536301200 728417314 37723436 674694219 442955313 240673512 974613429 733623168 457791614 619463960 686721659 121780837 622238487 79478851 905019557 336880962 17039609 800847705 77667595 656211153 190017694 858568837 229677482 340917362 951937952 332096622 431312996 702050832 169563569 707347691 2162811 558381136 288281364 39886247 85591714 731236677 133076126 60205136 317376205 590867740 532185462 4097857 712648577 6940308 83576708 470184493 343821270 953132691 123548557 274005232 461860203 313566252 132574062 544054051 654483614 937028380 876150673 85796603 491595571 898230609 645660660 346274748 456611738 786458391 386160995 542203452 370211427 519237121 454924954 687587632 962621227 839626782 544201855 527786164 846567091 480294930 997970657 42904720 285943980 121519208 316909952 600320549 287601826 302000380 144374593 942085440 91545119 873041633 880398410 435657056 771272235 378575429 781931804 80400332 165033813 20609159 475120150 535245241 539846280 930045104 75349232 354983867 622188245 472067454 882770031 468755329 952362384 733257047 511660050 90822723 707292621 681086368 691143272 994894447 983086749 688034231 936979881 927148234 561075857 669894650 362805284 184864451 48470072 144737081 117781149 66020252 17862606 592901299 601265493 557708887 375462762 529131091 912692754 997651008 1198538 647979144 318922696 806077288 381236184 830582746 896900011 88528799 364185474 440559642 935939612 199788582 128593867 725435852 126936809 542186090 395330495 342258459 579566908 296316934 339511907 697348057 362337186 357374513 290249350 963602679 915083400 665712112 345250129 680292513 515879479 346448668 180788016 834802176 5042315 562024201 517901281 901942327 503069366 882086755 195018328 291525337 81875330 176128561 16961183 61328506 570831018 264808044 403586965 150397919 561124978 743098872 847745976 923462164 100473379 990511692 739581202 868073145 508740164 84831325 400882018 24619636 283796359 581670034 859421812 288838674 143694228 229839453 43297360 499279960 111926201 238315689 790805298 46317898 266960616 660282847 107646404 837791634 925090891 511233369 988189553 486215863 254332235 688451889 262194386 207321980 531479940 1775582 75395118 40220097 86606907 476277136 64839734 222919632 57947164 776777912 511758306 54157758 6617358 555055667 405954085 971059933 793371356 49275742 17377824 60331965 709558589 125024228 750639966 487165839 636257597 591345878 973381702 743106198 132314126 88092448 950428178 663794067 89868030 25823290 704014164 28991303 354616792 621370264 251910935 265080322 250664536 763669241 171754447 109798260 171241267 430224898 80858186 964612623 479500640 950752383 877460955 41575588 75776604 480617280 528741427 564550568 71963151 354639489 160173125 204277278 442731937 110601297 868071345 385116333 988940960 424601868 414107636 196074111 898488499 518534937 461154434 1669394 134720537 485425247 111467654 305961805 915650145 44842207 123090787 247667144 995594590 551735 289242732 923887561 333685381 670500525 340954488 405648533 25140007 501127613 462442177 320388310 464245276 183029881 705504643 453186229 607631749 972128645 649260341 358636607 490663575 962931141 360306001 625384113 448356381 471773656 931345918 216522885 369132229 54436698 464190029 217243178 907504807 753432761 141130732 93706547 276449645 334601586 499355080 154106019 688245566 961797257 474494329 152490835 144827131 32515332 458193431 604975247 4643970 107453765 963611854 347823912 922901272 176434215 825724391 223774012 648207871 609586668 440296897 17340093 516539732 904486926 87099637 276560898 510436046 80746736 370267446 786885691 415348322 869622526 940991710 103593881 683936143 268002399 108601083 681279640 300517731 566794514 138771246 157678067 526764645 954899467 358018345 302182276 131333675 183742729 525956288 632057912 793329397 966253185 501914371 162385489 870740104 589014008 438946387 233692509 669760744 809213833 20578193 85109060 531352719 961569904 41219307 67805221 82088662 2336756 749084861 382606393 421647636 740372474 392800826 948412281 695271934 750819172 103110916 679121975 934561901 629067204 311179880 580407658 595320382 813094251 742793147 318576845 254624618 34255893 552269354 924385363 843469727 425363914 862010789 374822439 239450177 755746462 442627660 321538839 758083219 44228880 704145232 32247214 784601354 96946051 980659496 332389647 700281589 83770405 11511615 487359850 565353976 175207861 67767501 13190717 840818478 663077014 331767563 95443090 697332907 736553283 19828446 393318993 161917190 734355601 768141432 401367367 490102056 63285451 722906206 100701634 107514332 279567797 132948849 744632052 229030215 966124711 929538066 929311804 902411482 793566047 269188013 467765451 968773909 189471880 480956169 662108746 852548894 665240098 757551836 402398161 401793374 629896648 795717154 416226931 216768608 416374946 817594298 706870665 332176763 393016864 660088665 292207461 525101027 793037514 36839507 754131242 611678584 818893939 535959406 514090060 612459979 805147419 834371877 433750247 994619300 167844405 95858987 699684553 833084503 705927189 954599080 87394237 188340197 602832594 503621168 405108805 19207533 173731825 964495836 203900662 566748689 624584495 496108124 91849710 270138368 385463997 698497318 881816953 204357929 86973083 248423372 669334274 744636869 82795242 103084515 591772528 103156014 51459868 143973440 936240517 609903423 98572514 23634747 650759986 701405108 527255915 55868785 573129007 700987741 872880987 777029669 120252789 349981841 125654152 64618865 620120210 511118149 615632550 354453522 715476078 702605633 455393260 237326712 299758861 390704868 192927593 891531389 493860882 96903827 35504823 430101393 706807250 134077337 306252506 210083596 687998811 833508422 118468747 113644177 387012522 991349734 743190212 359781677 341331569 868844365 424400543 813968145 379962507 40033086 20938026 947954952 595155085 476331286 185281657 894913947 867036154 378209250 638961695 360897030 475113077 674466518 643514789 34436686 661060221 949767295 244520282 201575391 635792076 362989029 167735934 22804591 206855123 910926147 235102635 548186692 779770505 659503178 214671196 12249371 552052630 235609222 960204323 999724081 711940508 998002346 747154387 578976655 228727955 386116076 792390051 703841032 913098960 435904833 590794085 426675541 238188488 835314367 628250932 873980564 50819756 795986867 749301522 257674879 559429373 984404157 658377937 191716237 496423694 873049133 203965608 48476317 108658348 16686291 900716764 820598856 14688630 647871145 252091870 95932952 886503587 44481915 799773984 799602540 332903114 243084428 78794440 571091602 78398789 707045373 297588526 981734918 355548599 46890041 91926156 914977972 31294191 750304093 106694202 380234251 623353219 163176176 281226934 584527933 32378833 181943691 257643148 47067464 682331202 509735018 143000416 568834782 406733299 795290766 220953682 592152780 38375188 299748122 15760741 969290350 859309861 313349267 803541627 67374819 360239308 895467783 982352791 244049865 645771869 941563359 624284116 121641447 957255902 905511050 706169380 989634735 939971108 963812528 889218565 622302303 326063905 884735347 43653445 585313571 532542473 117123493 177466344 423434027 416871615 193227085 245240736 128697836 506576353 48782356 196072655 719332027 944250139 30941806 963381893 442538367 972505165 440182368 416696180 782277426 198209778 122865553 771912155 138180879 939194447 513647079 612999548 117774711 398382420 509169359 703088282 930924893 626292852 733070992 206875279 43164461 926298078 452116015 24378663 285390790 500898371 220451318 4722810 297664869 251393124 820621069 592719602 76414649 113319797 9415775 858692075 164045941 984797701 483120589 154743186 776508507 996767669 767742734 894283218 247666448 129428453 449887860 31107700 755721305 35475211 237982979 651402132 961773289 690098994 675780795 99680438 43513724 896232114 956919622 341178593 147625231 630057050 933898195 224039880 743376847 795830336 82731949 907422788 780628030 418368904 62165967 409652896 415136566 682425068 156452473 662803014 811853521 606340333 693910714 420091185 641815545 931893693 71493311 456105193 474509046 747274106 408301998 518022770 496022579 365221613 859201363 643647811 995278663 645615917 720204057 591171870 293962612 655452372 351111017 74590635 73821270 265793351 336759897 341474202 800734785 493212371 4277210 465104665 99552697 550704290 885195850 593884608 335114343 956689161 902506168 809623389 556479627 310808159 180162519 52502199 528546138 39363875 548666376 376341160 537496159 121386793 967513030 831458771 776839165 171140407 758565773 850660435 289450124 95325663 44650997 90184902 441054400 48928207 555289567 393123464 452148863 293001776 987008072 639779572 102207297 742030599 301919321 658686924 52838751 482081840 563705489 433901255 373962081 964888232 810242416 911458240 86275018 630271805 595433371 863114183 801412212 206515503 566290978 90862329 154357532 610941975 33563597 595411933 512386548 441369530 988535397 817051777 734371307 828059828 456831343 836578604 422606787 758750664 347781887 327961904 93348863 911487376 761863160 467310944 728891967 572105569 231285544 815166985 54893733 826718915 530797528 856305946 885750784 949604872 799684641 40108309 413063206 685764605 488036608 925449754 127134128 329088364 595017890 861505435 9664552 51849226 550600398 432271339 663116256 898382285 760233243 756465119 662386021 374612762 76292423 391277981 946718331 307577967 58961326 1612058 134296875 442275220 710434370 872564025 391880085 362635370 765188700 804943291 48399968 105741668 582909404 28050463 434830032 30443653 742072264 297010950 82292880 292672656 729282289 597925502 43571300 342031892 206906981 705957321 716644654 283199404 97235296 515879345 590777371 8712988 370007769 577590612 450988208 932958505 302670996 695384659 148110234 67859689 352844309 49026569 173601357 935753713 77077032 460947756 966197366 819149296 757958706 901006612 964338318 339757355 351448474 7909612 681789247 410871821 713866933 250950260 694071225 663618595 619345971 137364955 524847949 989353740 567471933 975836157 774828604 870142929 523737175 922938839 938002618 876581484 971965408 964120342 664851556 49042433 425068091 483565282 720708095 35543156 237088253 537562773 375300511 588536727 545472385 57089751 999408548 111855677 160556378 545996132 627990639 779902349 535877453 152838581 621772449 103349379 981191105 249117412 973492308 504928273 172056244 764011286 234026117 144021645 580647987 898877673 45580444 5716071 382442948 618804906 41259227 619531202 8884038 269076105 60584288 554356423 178682222 912509203 518728466 339238600 311021694 146719098 971657316 846899148 152074046 445946124 950248527 133265144 695063536 776257195 490709783 867119781 392784840 724735900 863657792 973432827 623613567 761754603 831665264 858572881 233075868 725440857 330620442 241959906 994516962 391204731 648832695 25715544 156230293 167561154 364954144 467251987 166796619 189127819 314151128 318870665 635073943 116916015 452135809 330137473 745689576 942845592 49773613 138474409 520097852 765947771 964423602 143711412 380218733 648605225 854800659 613294601 226562441 185421095 707770873 73595763 429142192 356603561 99311307 585372485 376681082 316781817 52624465 543477701 505909637 219291960 862348366 140983573 336207975 167000534 323637412 81897544 109846119 373411025 72888319 482460337 139358790 889828287 478688115 372093889 390949871 333488768 985388491 470028678 371426229 545675723 543624441 800568421 902279285 495452114 385940899 131476726 812233932 291081730 674954427 318143562 510373690 537302786 311643501 846581665 704303320 635280914 780995575 666665805 8691932 706400260 1642502 567088 448744906 480330617 225177344 692211143 813819385 63082194 162239815 37761973 608757917 558380622 838330394 363553561 53832730 76787652 495030287 866066662 367869383 169984707 36726583 878243073 559803859 348370084 577341098 116623538 983650998 210853032 783289344 844859297 917253293 784931846 697942751 218514558 117778822 923120095 910725702 931598208 986202289 925481883 969360181 447476566 483862498 660206935 811030127 390211594 736994587 306060408 108794615 104863963 328561481 145521198 983107037 888365341 346407649 412964494 4988872 182575006 623817526 640794582 27434296 393587178 278242787 577893414 612101737 396021610 353529868 375343798 180136177 192248517 153342040 2012717 639725083 637204538 662219652 303271569 27416126 399214233 609331977 136210741 356594562 937893459 134248306 192217958 678775159 480655955 605182452 683764031 663230961 228999972 177074973 543181624 622587150 455317760 973591404 87205246 851339370 179637631 315065410 31475540 371886148 468407450 33488258 864127597 105611982 695707910 167399160 985544481 947438509 629247503 974271588 304033065 419657321 961036260 496251023 98432473 294208574 101433469 634712871 957439536 182949807 811787844 353137519 658053323 267105597 179245282 745258570 118444961 358882913 60323973 2436867 730769062 381247790 35925125 447413018 339376138 584149402 614812178 177436978 384104270 96576041 4224925 688137335 516233362 965261186 36904718 614665836 259469753 990854560 101895066 69425648 26320726 913682910 275079533 684374049 33304866 454324815 282148978 4266193 813207729 194989318 6703061 396493150 576237108 895144559 843906168 915613246 331810320 311234706 93050217 715914591 407810747 97275142 256568285 924044109 62536321 293473003 391226304 174522441 136843922 493121370 96464455 163164648 406804273 371543989 847538698 440109140 825868804 129687669 444375333 639076526 324676987 303594760 35569669 900914095 198739313 731992204 669043700 530549633 43226903 762093917 98980583 451037650 711885426 355548869 227598118 626938113 649021872 618824423 801460554 785865795 111945786 897925010 949030443 371266426 121985358 649085500 811375566 947854162 778773170 108267258 439447048 955966523 411862019 327533083 709396978 463117698 59525280 378440671 993667331 102752183 993050955 92647908 406306199 704936374 300713143 633904318 184390846 949735015 105245100 985851401 588117169 217190886 736292770 389663972 588457312 858278128 38749465 252349237 658648649 670039001 213132862 98095690 478521884 624994881 425628774 187918855 88112572 337670420 418875892 934296269 292938970 411926840 879460543 699245169 969379580 32690045 185665846 153770420 982425061 290910946 992138187 423058589 360618199 580947316 665238927 949075511 291741803 556504759 53941108 950390452 79060119 267073970 48486136 557582003 744585217 326631276 745500858 685214155 664301696 16893110 472026783 957240666 428819950 204003686 509002195 250715890 236693731 547184407 404486310 71635151 838095354 249140856 494693741 51229912 830088172 12449027 305416 121829968 568953786 906762897 72220413 648013906 26353226 973222922 205595902 770938443 152370557 803613127 456152591 669188620 820506237 928179375 478945645 101842546 132183054 987947840 352558436 221393151 387648607 757044746 293028303 78260320 6185595 787722044 129490232 688790133 800171071 129795648 810620101 221641217 889074912 735356881 869655123 915428138 561096162 75251018 686366575 565983086 731380511 995035532 235171699 551886741 775731266 714117344 653729288 760430686 554581544 6287717 981823838 942230151 615848830 274852134 20490464 474550791 915090544 2497062 15857284 567777974 132292710 826477385 789419191 873883988 414350625 659074307 789312120 827963154 586841692 328195054 393946233 170738562 175746945 481634298 722625304 951478212 48268001 228870951 711908891 602849545 87675034 546249088 397596055 556040230 821101222 270602885 30591015 588708125 273099947 46448299 156486093 257909024 725442050 945905284 131793005 992309042 457495951 773621491 820272189 896854009 954332911 66734781 67592564 130079850 548369079 642734234 81558055 596637080 871605185 645983312 52002985 811796586 44748760 302115406 367836809 865849982 572718292 250944190 307074467 698334605 149908855 463560560 956243629 727867272 261982203 940553001 720176307 571994520 566690851 392964855 468848522 373540122 312216002 388957453 503619972 860585081 31691680 437694393 309738520 755813232 936194071 214257871 567609811 980942831 516373278 787962986 699309173 89091563 38907170 6383633 639942534 41332391 322460559 448702523 769199663 584442762 241771883 341892329 8953642 808462734 587373550 477802164 34519215 899589552 866759617 538139187 612690992 750967664 828349946 922429513 506780889 764544011 136687377 926907066 598003201 505577021 714870045 297312367 447184950 606293581 156212366 87127478 500142339 478672925 535830001 121858361 63115681 777601884 463750691 72069323 438580977 51124234 402387853 473100193 803230153 121663830 863755746 415921138 872631494 692105686 190867010 231928742 309166056 180070754 11352167 907169257 685647775 726222212 56997984 132832719 185032153 213210350 72476563 685174492 691883276 460822930 807032853 607515323 90941173 123299903 532101012 529522150 26940504 787005231 855138709 830170657 908669061 718894449 98608154 633816914 263516494 141991531 718262022 425198916 322062285 729614189 184884532 860226426 308352761 241882516 845575511 493384914 307609233 918052074 31075765 999492509 231391363 690624984 459524191 322332536 813924888 844141569 851854687 693381758 631146793 559509755 376068774 392332214 130920563 474676928 878665494 394437057 616668459 596927510 819635973 791247110 179058058 4520499 651473530 487410819 98919381 349565400 980795733 406528614 120133834 864387864 258537482 351525197 555012842 570578039 673857734 221454089 414719601 378228780 914835847 898382761 937738535 143420980 143231334 68659092 618097908 21896821 315612515 87282727 471340697 135248482 878529837 650398756 992285354 382519726 137809568 943721101 732085127 971121668 202766075 852218961 835509525 461303557 56260517 243038726 31881590 730118251 317009181 299117557 108347024 84361387 50016677 46085553 227782367 193248011 967261018 845880276 215144833 282873526 785679369 686485530 270638374 516725565 189400645 115440087 899245292 327210214 59161182 483846778 150848241 114443623 188582098 986357766 575747180 244842615 81912852 460145136 974960867 398922033 611779060 935824257 483283421 661795737 834426176 711065788 855043749 801687187 409462423 70188575 937077080 47658151 609190471 60231813 564383717 798591117 175671901 316145368 978317697 87349449 799992146 129165931 201793072 841090610 968040063 630056618 85933218 49952908 90201748 913410451 301391308 554497174 701751068 637191095 216292904 536177237 200773242 71336646 190380784 610235666 994041594 127457857 657893817 455748425 40206036 74793893 106855901 215877937 390939261 85173591 155743752 43447766 66855888 357536824 884538376 34895944 987593443 822987961 937365226 930311557 588914771 91272893 337325090 290665832 728463988 553617994 679359436 929237230 477471007 869740220 391989255 324028960 849714443 902399439 632293751 889920479 977193332 739149652 958314783 368132587 676839609 114058528 411580353 596211863 324111719 148635089 483624174 164221521 971623050 273505759 94533071 560537814 364778652 284374527 703720013 945759006 837992521 383079442 727512595 167979887 105336021 119501844 344525214 807566830 874417649 976818965 550003668 851610974 568484977 508318444 72259920 97840945 474893339 336356640 694052809 799005058 484991729 177676976 963226579 456614772 451182735 910276016 869668952 668477753 194650536 573388958 614236752 885159423 808984766 194265706 53139304 914320787 166283916 250180884 574403976 40701558 226999842 124407638 744828899 795484819 485242448 817088819 893325765 960135787 5961818 439894933 759140838 490953547 617571909 574883776 947568319 921271010 485159785 669753631 589748756 532326687 95658948 56501867 417486104 904643715 250767573 323141774 671480861 417051490 573322658 245884831 310269414 652838866 222808835 55098306 300840045 708051283 724703492 46682169 668187064 730665310 486577102 279844261 221618851 104149004 854728038 21703529 877936380 192404182 691457160 320201495 724730870 787116109 376703362 994733340 544276183 479987301 170391473 215757037 897038791 743714131 314158234 59824565 249069356 536967069 114922871 549909401 245018346 839626363 596591570 765721776 422808033 83168665 45566030 644426884 39834035 752810434 518646779 917770415 797730983 62620299 90488269 374978212 849736408 467191631 369711545 246528950 947178933 540103018 462285987 696734083 136333508 776444222 756558648 385402864 165927650 723997886 935312266 410945996 416140608 384420195 29184131 838948641 467588861 74750162 335891884 359939262 680076962 854538664 130226037 330324304 917158963 220714306 705302516 619411730 687905938 75014054 865940680 487601230 467633438 180743026 36851672 456483312 957187248 645926687 841886177 123114892 369924566 629714802 386577254 786065174 14134990 415761386 477530175 334240217 343027914 813422059 694179480 875621242 667960716 824405517 205945540 437636038 45119816 911248056 57047761 585542120 838778477 922988441 925659716 158928274 103731461 962511389 615411587 913435075 460954435 309814123 889066333 830879001 792045291 128159947 469460534 658696647 396437699 946990709 992936865 739465613 612929128 539632704 467603214 133406203 216554580 673548754 571042242 114190762 437313170 628090003 552249249 128608006 403594804 477908958 140052646 359842631 292936706 755464233 125794065 753891141 917794722 867376765 437286501 709840006 995536712 759263402 221053013 244490770 558770470 66506237 983956383 171699591 606138941 304075956 305105795 675209887 977624711 876148037 789400649 267454240 356754399 194166257 248578612 612865569 672075216 388631258 972708200 817528288 144095485 951018632 423935789 914406573 818395390 861222290 476762939 666448461 473002051 697815952 910939231 31772515 764322189 747411973 55988472 222977489 51487922 361094267 898187376 881628999 89758663 540104384 1599598 299029429 734270642 250178210 911894998 258862217 638809469 737119558 76390498 635421320 688138183 500326287 402344252 359049932 214064937 879107191 878014759 687066988 576923136 641470349 571355869 193761684 241398681 627344342 416739173 145402969 988438609 314926542 27031962 930713639 855030927 881147933 229743061 441817928 131326137 141638052 700680145 622651972 731273976 777070643 110589651 271928518 129913290 512933903 630978450 196494593 244557454 361509568 883561581 821480590 2979910 307433810 15242268 244378591 934778152 284497807 389781561 775733120 599424350 269329889 706446752 306971636 2994181 788706179 748789564 134320318 782860598 301986068 609488656 514134567 79056704 572594673 786063086 61486360 85528570 269557895 257980953 182602390 631067464 994058901 4082973 486563740 301492704 871841614 730942332 88787215 8855781 973240259 864520335 608280131 95086507 423483447 767768133 98080688 212189619 369074056 84917373 995050217 671060124 694406029 361701144 602633194 119517062 280589 664119555 57561998 122354850 774616874 240164388 753422314 768675768 96763727 92502414 922684838 968605342 823444746 11472046 977461123 649201364 875992382 438257613 744287871 151992188 58542105 842368559 364181807 427616161 927285932 211748384 98676278 474208321 425965894 701309472 593725383 426246483 217945386 651287381 548601333 992562261 891451769 154540007 613754388 988215496 247042421 388955586 809337197 923003533 400427632 639314679 572204890 128936373 77572285 169009120 280928561 136114390 11377672 497626735 416246917 938663605 709375119 514923195 265388285 135341006 68749027 859113668 414103855 139210779 510401042 815221554 131773033 254369170 969761561 598043788 242584659 69320341 986999374 51921850 992323874 239943365 543752895 417045123 221396105 473841547 586054243 502324666 462472303 449948282 999951401 878719221 241128246 561842879 246158775 506516531 549700251 314907802 365630192 816320472 454118582 728547600 631542020 438407981 982916770 453819940 888968135 78017788 375656648 728483868 129939638 220496881 968427234 526208900 637542005 42339698 50440 76112607 544664364 462522743 526060889 397132125 193758323 767189135 811491370 439917099 126222025 213707981 754824901 491852217 30028446 61459842 72916176 514086832 352384190 55832939 967906773 241352318 133850728 196079780 969836187 116306732 416576661 790779780 642515632 54118659 833119478 495082438 982747640 230300201 957605182 361324888 479948692 3879864 128514017 291440056 443796963 107252408 505148037 51138224 599104626 387692849 112598066 672020802 901779682 464982256 580370108 722202814 558850941 714220836 918282594 381203487 683043934 334859248 24499626 178075926 241494274 857619104 673158364 76758273 940435671 483279905 438083161 420384357 487159770 419113544 564340779 930956733 526365953 69488809 982094957 125470572 309698024 94693017 650007740 211477699 412191639 82894207 933680513 971042580 797115043 704479466 204762426 332675337 39338708 229262052 510751263 133349348 86881149 183909620 210107621 879833187 667189526 648190782 152733903 6865655 67304320 717074682 937822388 446186639 639079857 919917339 424173577 948777881 867126722 74181310 12771940 131834720 9591884 946452453 955393667 806706927 503448279 160156086 139382257 395303353 389418139 502649886 528652701 328815654 686559507 591276688 61165200 206265392 91983829 213899103 213131047 11804515 930973785 3469794 457991154 570053635 923387133 882164731 371347876 643030214 808862408 384119816 627381301 818454292 183088628 582774961 477677578 686536907 595447413 469576202 81840253 984865552 972226088 463009320 166197566 511301954 54286001 227362766 717567346 146269831 441261870 783214759 158074346 224752014 786684554 616065501 794805650 562588046 350746591 18669885 58134620 159608992 402789701 685515921 978063284 585878329 120807241 308257222 272415230 716254654 777833424 206771849 553636566 750059505 669781170 719834132 113877819 724067171 799713264 831445165 722853368 93491493 467176284 880927715 318243508 253860831 349509575 113049151 816448877 700256166 131719036 874583497 712381525 387025103 412615777 542961168 972903432 533423018 851218390 97835021 249677666 629051807 304606871 803314232 231627672 974388041 375664723 345505491 550971571 27894346 29467015 273824933 121385840 496643299 7269007 439629348 603020496 209294948 405194865 271985733 909551114 389430267 146569223 474448998 776455370 411701367 17410160 749358795 945124385 868628550 847193817 47318410 350196717 4317047 850632642 434340755 978705088 78813724 779846246 529676652 106708071 661829627 656017951 228093911 10989286 663286958 667723259 614009782 872581906 72918117 885995515 634649380 314864750 885081105 109098371 91320113 296782465 979024904 693195274 94423209 700169814 392905450 141741620 50366524 397222497 992374262 337223645 375927578 923704353 117069884 758120597 30412417 631415877 414138541 111022694 642405163 929941866 631262319 256414939 655040131 556696802 142410447 142205870 871561552 880007918 103820608 962881665 29306742 82845505 508593298 123729952 783015319 901498749 265471572 685898209 298721239 110362193 23121847 527165184 34066539 992708104 285285774 916995329 476640341 551940681 28018016 119045497 481882540 511796701 227976802 136922665 68493496 222903616 131644901 940055048 102911527 235465509 755453072 132218270 318311015 116562730 255948222 953842700 18061472 521419794 492257269 169299077 631781987 367895482 696464261 518364893 213119946 981750035 435360215 689760287 386207076 315894598 808805784 868089616 827691299 36782580 857528647 748701162 112202562 989173549 541272569 215114089 77155417 149242001 199848725 395466432 265804731 455796947 201825492 283866203 829733107 694082761 453165280 314031454 61978236 2145901 832396347 275098182 983895936 120272921 964858469 222619371 436167519 626180613 90708981 116375178 515479559 800753994 865076340 627682121 642443902 258865268 695312576 719599320 408107269 895161302 967582118 673912000 203474608 169407603 957778203 33207709 863490364 263459843 347239163 777984967 265605744 32151869 53083142 102018039 152424790 870457978 324637411 588592310 349154950 267862758 557483854 717150875 921133118 275076553 197349355 416093380 533941821 892661931 135692693 942049091 787823226 955791177 615961084 
991297835 125198774 426255647 877021910 841205504 542231856 76777432 471706830 807837600 108929301 377306339 762372005 261354091 100280676 87009409 849946401 449435626 207388533 259946614 19102860 128521645 535023167 216452215 397131391 68964982 109114139 385340450 11014066 749453732 341131620 479491516 593267926 318846760 758263529 470289829 12568624 300495378 547067261 484275454 960849344 655996562 861581793 723221343 917350653 961862469 662747118 619813414 263814454 722652018 879760028 282917314 703690029 267299555 499369529 100821413 336264537 461000035 486161863 199794969 210453760 679809849 531802851 803721686 998656610 290066374 126527874 863741600 443078118 526111501 200533413 403927456 34624422 62115200 979665165 951975075 876494035 494928642 424304848 992824856 217580653 156581236 128258529 921270682 423880791 627628059 874608461 612661694 88628087 213286683 812456663 151598213 893096533 196775873 807836265 744269502 486842247 934364139 608011095 929920366 312991999 808544508 186364181 347616421 723176074 18545705 152107855 452186469 513474347 576412704 297527684 731055001 585510306 425786213 504842042 9391090 53414265 231966863 474569150 994558725 445253546 139542172 998673304 338350072 336318045 806509562 82619567 823160293 593390060 543147028 605597018 906382059 204207896 644477565 106514839 779900336 663023270 258622695 84603164 176497610 835035399 382130848 760068977 273062064 807917062 117427379 134969520 713847693 349394242 609538670 560922778 794647788 749080842 559596075 132997854 85398880 218621997 68133787 761075539 664528423 463797182 219188916 423426842 520521444 863666481 529941681 300421773 526689744 788564376 385024938 555703721 476116134 767155786 315772691 749178198 427589207 433200070 884147718 141436894 782594312 493686381 702359672 429758460 95283582 114472106 415272680 180682463 185610469 335922833 941758002 850138893 799720015 13463278 273565728 172757818 877129759 803507409 473179592 256335863 444588145 710720896 812039584 920704279 330393041 127812268 669882471 757982249 413528705 406546548 899419143 48639376 900232930 454295174 478397836 995516512 421283646 893670516 28715334 606894116 82109709 822989703 457033002 881829724 836452981 583115096 54587536 713582733 239138864 380283494 969918596 683727009 91004383 634474539 604431282 273913790 614803174 126830112 31896032 28331872 533376660 783831541 929487621 286125949 90643074 260401817 134158821 511926721 6588692 15390521 118820830 88698401 838380224 428370198 970528126 674833198 11485287 877632028 240932291 250624151 110431881 63367246 934351161 53952630 697841786 391298802 327866420 165161319 370645280 212278819 46009557 904021940 996110360 975497178 42664249 86753428 235898988 29339436 598680149 242487681 44729957 570017345 331186082 883110182 998387543 154230567 410459739 9872823 884378961 651392030 113013340 994810842 567275643 899880867 901279838 117633788 143696028 81662618 282795107 514341308 293941437 328804664 270879608 290051790 304301835 313543857 229321584 392717190 342883293 828001733 635204871 387613250 250535437 818907319 123239791 248922973 973137887 533699531 111312162 710033207 37607920 76841869 557360409 604883563 976722736 458640240 722517351 120418758 540302858 5312451 634760066 834244295 334117115 905639674 976812452 490935317 71699890 206134029 883652507 267099549 886652129 371373737 654712800 137187559 190281049 777952591 238626899 15935295 164168481 349939061 725968503 201776402 426780930 135845271 806659965 256020026 594485511 529177310 376438784 987304736 387006127 863715216 674065390 721123243 621871250 650877835 64574919 693571140 709528231 948227426 960670690 596180353 319601156 467899849 585884278 362398571 98368799 824511177 378333867 262537281 26966598 956818736 464313683 453747528 92664000 123490007 709767554 539665877 652667317 938722704 526970606 39673438 802437914 53552356 613313047 276825523 704430191 677887966 970396663 266474781 478631751 783583712 862655134 798232907 103999920 301055772 13147837 54885086 125566942 391481704 317422367 152533540 200816799 634252416 458797435 293480799 757742423 21081348 833146677 262926100 959804053 212633642 155115904 614758326 266185998 768428951 891583849 823132556 298833276 714496871 89607330 777465027 350596943 804778831 428214293 454596863 105834596 441362130 509481949 83917904 685360201 679420682 236451445 886177000 313673091 695248880 32174159 71415508 716330228 865320836 186857974 528650640 930470844 341973878 143408959 49173202 110402822 34992801 872305758 261752464 602006039 961913088 891733857 952602982 619208278 172464509 259716204 725042874 613826639 769198154 808960779 151703199 301135195 897928590 37880193 614808287 445693829 70054352 538740161 14540416 787891554 725598135 543191057 718362391 67572006 686600016 767535593 30491194 574109184 492357710 144760024 28631582 306787158 36493874 981234564 925995436 61474749 240950761 503554670 675301388 862665281 165031808 827004588 163800470 62960391 717401147 631125123 508654220 787455499 22381643 523194636 427863412 747979778 66385686 146225796 668068150 605502069 766277756 551075710 32127612 111151825 548352100 60759194 417938983 437362340 41993751 343934413 498837089 135460878 847489083 26654836 998126160 12520884 853659424 14442989 927997648 423576930 645568112 289168227 63548788 667949755 812362863 491412200 268445892 731264916 490154363 789030408 189283344 108948478 192622477 73927322 220100303 740974577 134686516 638039287 178336910 29196633 981973700 677173999 17173877 681979142 703828835 15300030 547016392 410004619 882259392 327530399 833581549 380343863 616698626 897130338 48293611 281577848 241058897 169255869 12842757 731213260 958286277 54642467 840161738 3425113 128569789 60262035 744399690 115772671 698301322 922736600 144969304 532791381 452426958 162143182 67286882 8772153 29959578 466819640 271293138 912218971 794350039 104874680 145079193 411048658 854521384 45889171 692626506 95580275 215145040 557985630 679309901 25947677 465144463 519471633 29372790 593714253 432250034 773772481 709486924 130551349 549025440 706972595 515859096 853968765 869115777 435662344 862740918 751591721 902481984 134034049 516327051 696832016 91425095 661406245 960397040 798462846 707295416 505539905 746559487 922440456 63525528 278385747 800904499 381186358 797857380 830277290 974900611 82623773 456566130 536903894 65691488 858107936 96392848 581550584 712076694 965508625 17212921 427333971 569616706 772211271 413884386 85943750 321559646 357825848 747349995 281956679 8805053 307161770 787496585 607880906 82118586 703538479 886266653 883023085 84724830 536640393 565816734 912141807 619264166 22382857 301562061 684955655 733007160 397954909 119022598 297600213 215979894 136235520 724934185 785596600 760963157 991334937 724056716 82522797 201677144 323923071 216995842 210482197 631084841 4492420 818363103 713203427 560547266 557146116 596226506 497788462 93786502 14559599 262446629 713050668 36942457 416525056 250522682 622465983 814479965 369545281 920066196 882976225 358297167 497516740 521089184 119260317 488851671 245145894 54299480 690528815 569068965 271295323 753527379 52670165 128304109 424406841 765873593 688851375 981552957 214616458 39156197 75339452 229176057 154119192 640906487 118634880 570644248 891429169 741100863 237640572 113490809 661167053 120616791 471787976 11200152 641705975 591048294 500051823 739368235 645347774 43096998 160953559 916643097 796624377 213623725 44947200 73547577 979497318 586314941 55100528 194113769 477987504 982956353 423289826 632106696 476379199 541924707 202750937 220324728 135541929 440391510 333815537 796708982 413524667 805603514 807909135 55230635 249168167 160477317 647115237 894515941 56090681 808068796 663675398 852715058 21692514 561138964 926262636 1189825 999970271 833879530 47819960 477957769 816835876 323626153 110064458 145731435 865550860 165331762 366056163 1092782 458239638 699871700 650318131 871764305 505475207 310743625 779511306 754643374 323737308 426626536 501675675 379827990 87211692 17867432 85059407 108904206 431522762 11322036 962610405 431493026 697717932 10430358 761967161 367070168 186572877 724547986 512801603 52123730 889879748 878857766 905732886 200635745 578729459 408567376 72400043 936721033 571827367 851911349 543880766 895564675 131054245 45556434 275392658 218265937 915940239 360452066 179686509 347462994 224290468 142296907 631472387 922008401 5243632 393439541 141594928 191816509 117987520 654396531 96456606 860383634 533254290 854705858 61019372 964500115 115789593 985935788 901221141 687616960 690363497 297618267 583181628 821417742 195691067 711090653 892200045 111631300 71542712 71886547 311610660 148349546 66699821 943083047 922874313 71943453 189038948 64469234 116276328 159542834 718865765 212732934 19926462 104636414 67438785 933462207 69136523 35744744 771914355 822874030 723361704 462277845 120492290 159059692 136211946 168699724 870150345 28411984 280331024 794209423 952814904 591941684 942558969 19514718 387541091 717949642 91458171 576580039 782418876 60250866 736122873 353801001 272983800 608565701 310953781 192938952 394544268 232606670 228683696 166458616 55480694 952045401 481252827 28489350 111105086 617464773 49705440 833771797 498393123 330036464 627981213 303724386 774494515 423056541 323239105 162035599 141006176 267213642 738615638 775941419 327464508 327254870 982258786 452964675 935820572 293212560 645903627 330364833 525819231 727103689 349339815 433816291 531665449 830592642 314822007 495286901 300573774 364527448 329058691 798966897 547080278 809556270 102691276 321574786 85129171 278446747 336126751 78651713 398176756 74742382 854593132 725641264 254513619 689368277 31122298 190334184 982580838 677025925 373215383 360916428 256645974 722555198 647249085 788311423 553147833 962071092 283598318 853721607 179114899 465173375 505204863 726195178 274729639 460412505 900286330 359858810 591375619 236413075 438510523 989552375 163671823 145620015 567709998 418185442 834988292 598832297 461035992 670085489 128374581 834251375 883518283 385020555 556806566 530767361 173331972 962470765 345354813 309446656 668708731 376986078 774620031 26429953 103181249 49349663 486842459 855983946 261724839 78218071 92397014 552751729 920286812 108585203 698371744 487996803 379287012 385876395 86829093 840323004 908478251 67720041 674574373 791996527 452740596 83897298 175280248 626072568 46368057 373151427 935519224 567593154 750137505 562655615 594023108 705835121 464521644 80865560 561819060 726246484 11599997 506732440 131514572 784403175 467834009 829886316 124916337 847121021 68279070 64261797 687444019 976757321 131981838 214534751 621270208 584722434 150948415 649066822 63311362 49832838 22218242 998830586 617425993 772355747 414002560 211449094 330707227 878524205 144831020 892526287 457287048 8947383 251775086 588801620 793350558 719609096 271204295 918266895 419246476 339483365 982528692 106690488 168757046 114510523 173741605 642543620 551749324 324690021 291610435 615060686 374522859 166345043 466407631 991948852 938700790 880410192 55914305 121924377 758934390 53261691 14450657 68737797 62209074 118742110 657539417 708075998 690867572 928743712 478859253 110114041 120743436 313904304 69320896 289500482 280931194 95578867 932044102 832680518 420268888 76170896 447741197 647308114 242515939 914148828 491773325 33733089 647075379 547687631 155657466 258526128 600949322 22624489 327263925 515674763 141366599 984803342 223750754 684750537 913547047 702610007 794864579 34290477 16514305 716701841 176307325 149961865 812280708 960867794 982642383 85065956 37038683 282899939 732374070 132070989 49565126 224147388 18320444 696640506 624351385 173977910 955166634 77817067 49118765 282430553 593491830 43001731 119750254 817242584 727752268 33297295 372368951 375133206 920104145 241399622 91835040 948927836 391361487 904115749 909795623 226520229 989181705 799350673 509420168 574072134 783938028 558985294 798219522 802258472 255625793 275087267 976236382 63308787 352904334 25355140 345739340 946396164 68356871 465489594 616155107 648625506 351303255 988524058 23758705 123923759 82440039 115593746 72851589 326317892 872225861 835163578 552838121 713923925 487030610 62258282 140512418 123484997 621243577 938731940 925743469 729385736 66335566 754496210 792694523 419239900 632367717 138433856 365636057 553240954 456439817 981791165 201866453 660259438 822831582 78141525 784183198 757787988 46251637 709551153 84105873 918477498 397231090 636943995 484917782 736778067 551718643 625430200 860263064 25478579 416678499 786006527 754864316 483014066 393019096 547558832 902253966 25386806 538509055 120406383 578627761 847465238 954713914 633010580 507724669 630061855 711152105 144424226 387849836 757403742 706491745 324472076 528397599 103722829 961416071 13315374 693017262 365651073 491261940 553280319 391129653 760456806 191803205 145993962 95987231 584822302 546069160 998241197 462725474 84578208 971163946 41353228 784559812 925877853 526880175 144800841 408456068 238032273 289225067 796305904 995436016 995716813 120777973 376349974 951956008 934710410 242181715 497489629 152877843 733443655 50769941 544007496 346416820 95089513 690001458 442404051 532428181 88586977 293161608 995153655 25681552 264325547 889023250 810241364 42719760 415903418 955042205 451175828 506452057 96783632 99998091 354404432 92500438 73292431 730754407 896972812 860519207 972936122 246978800 13397043 558896136 150265107 557404539 905312957 245354620 99922356 347717001 777782801 188509334 640878609 625452816 214190886 757720523 514476059 24432243 800440283 782895843 831990815 104132470 289347893 928774447 56646927 643752326 873791251 129939358 227023092 623280422 990458566 199959207 870259222 856371975 758855343 20524322 266292874 516684659 118395309 366215230 864401661 896178110 407240930 357796629 374147285 621431816 115517145 888623344 498380426 768473794 524035546 182887600 725122630 813383440 111662040 781769558 309652125 985453291 911708916 536675217 461250072 754683841 589150790 331509287 463572176 200522492 204549975 729865050 717207152 322945284 96080273 434125172 71639754 355837570 791921801 445787039 977269386 759955313 186926743 328166171 380945466 710962289 511053771 106068090 376862088 475232177 740354014 686514213 313201827 504579289 75705789 774451899 111779490 664856579 105961179 575351666 865379072 163027521 305216709 435102583 485972805 253813348 869227755 557612559 609650918 513665915 3399592 439436664 126137587 190326335 620119201 507083054 901288624 131172966 465667510 130667072 458921509 58537883 817181285 772123337 563117172 745403441 546575229 674896662 262776379 505052775 250248321 128155444 668080296 407981396 415774393 6569460 661794745 285002141 564182020 123962022 798668057 567581612 415915052 924805644 610424313 36034247 284405057 364229296 19723579 602588933 494896368 478645088 661126816 164594013 103284784 224243982 909997454 649860014 899140644 172773826 7429148 1905325 153445637 528025810 409886721 569220030 534595270 924197832 706738538 98777283 48159848 357922954 518875261 316591266 135244957 129299567 352625513 419650015 493528864 224865458 22238941 988425232 703510547 535882124 5535604 806795331 760126106 915533058 309171704 511783109 88306878 169117218 366204800 94268881 697143028 776091522 516005277 231738292 552805713 222743808 183031941 453481927 580666762 701907203 770073194 715911720 831206770 122698700 988078101 177251993 200080525 862833408 18193585 903591072 398715525 23729189 562902762 11357990 939262248 724590833 375657466 880085492 893708051 741862266 826870739 590851073 370470147 342876009 675105731 923275861 418136184 858137672 376757781 998802946 560044868 146830968 567231025 243767998 122046035 407825485 273536357 174642926 270658887 291729942 78233991 521890778 167975498 493653119 533248769 107237739 70760311 908906235 839839597 964468363 503284860 519226695 407835795 873755008 862102704 82941519 797030862 132755247 941079191 26305002 131558187 353640419 25652337 551305578 449924783 214738 959131064 723461140 174857664 82306310 15191076 105608021 604197088 35682940 451777506 989962223 142920679 522537818 751384817 835276642 487006174 254669671 207019696 894841969 128424672 69122393 830299854 777971900 54394007 623895404 656793268 38468560 977535823 682445605 589774138 279976965 535176709 401421561 3438099 710034373 336244237 871145548 668158760 940441326 906828488 119936260 782919908 902265533 642474078 534304719 590058534 981996618 641490756 797078230 729354946 622431794 718716989 559654793 252920053 773110996 36066556 909713321 811579556 13602373 444675286 253870054 146095704 979851995 655291615 149533803 542402728 991535853 20679344 210561481 784493538 780024198 183014107 419929805 682289724 825488185 954234524 124864617 660001162 448241639 921942847 389356101 70673426 640659830 801527260 323593479 266287185 837593817 85823160 77866735 703712556 530498446 331736789 849808260 510350434 839544770 999342064 52753155 683596982 872537774 115831003 320606879 505078332 298845110 740536685 39884415 976849662 547287568 164749033 636850817 995529208 86691873 878723285 66202627 579868069 680250538 242312473 846155255 370360714 328135633 924021990 74073263 858634079 108275138 923881524 221500872 947819908 775739947 126770394 483933250 500794080 95117763 804540129 5872405 393962873 545076807 45756821 223328894 92364369 63022220 860179712 940409943 149714093 591419356 859128936 729582163 124186253 101441402 428253777 494546968 282093401 204792126 568620231 993243846 313067264 345018114 67261078 113403531 973274427 194031472 597336781 326584867 289149235 254393270 184973638 535628474 799470077 83246825 758957369 744350812 146269045 471653440 537277114 295983139 63072789 396406044 878081668 187259042 350363812 306335438 681806010 484973580 511127564 102942601 478217419 676711194 300477081 545478497 790114725 273751502 592026335 239967866 600336369 881175570 494361136 785310007 269320404 146347572 868556833 28277766 743214751 14825871 499931206 280491858 163325376 415520361 529414268 41407037 602779403 879778081 200258841 137101773 217268020 563902771 92560740 695485439 240613958 393037821 93480296 883245050 666789323 685506631 123212909 119642051 419198561 470090411 757468425 688518965 468954349 478541617 569313097 212169093 345883854 69244296 345177318 509209231 337281023 874591586 403132634 940060426 606886026 455907842 929678565 824154046 19810606 22239298 372155845 112940931 415277120 465636141 996185981 934582809 3659131 971915256 54224854 275374058 294522026 664209645 963893023 763476375 142751255 385722479 975645469 488635109 307483141 173339146 850360706 644764164 47930725 106009700 437340950 654816752 561917542 367019508 331487157 581728148 241775173 703643002 694669079 657052293 21795502 543371419 444151461 25454634 515286668 350892681 300828692 809808694 15102319 117238075 425801429 10369940 502960554 253963257 499005050 810443696 427302403 201882115 307724219 475233128 307891815 745065169 982566246 869809357 112084671 314053397 304053865 206376210 17696392 998722944 863428503 39491895 394610723 160096323 917462902 909897391 510989005 70807953 572222445 526091324 188046028 998023874 536461265 543522949 104503490 887982681 206483004 531805893 89864789 514207223 7039014 397756605 259272386 842121627 120082321 223873423 8691383 424136186 430249633 26387775 275375490 146194495 918396043 669986213 306290818 688375304 432399963 817279823 759183258 4622401 195887507 947229286 855162641 584865138 343268594 959666131 472847812 549751598 343988383 415228967 63958815 203543764 812985572 175747567 45665384 933067894 399620990 54356767 209720439 682386989 933260915 485095929 828581484 704173318 155082135 987388668 392548615 587482099 657184851 4248232 444620866 853072358 951477519 152299867 290453855 147262472 964482364 763301667 697014071 308470741 31046993 760972886 512014505 844032566 936720453 410196255 629616819 188857802 464553022 839337258 871244791 250330296 176949547 552342634 954503614 332031682 392247661 199568589 772030147 49432505 203816821 69167373 755021229 7810699 221467240 45475077 155073172 38465963 661293110 852087243 346936704 692340104 465576488 711467575 388889029 254813300 121663823 18505841 443671102 438733211 710359465 167432252 689063508 887309012 572291252 643567115 71857054 964538913 843135704 843887201 13971412 46952519 913054574 621509007 54763218 987038180 666984085 62352756 25504137 180793554 914439999 224957207 873133658 380016480 936424783 262022680 634829780 58088599 133044887 931017248 349338177 695920719 98449493 38401678 435746090 523257111 534485159 507603144 487796018 230137223 204006705 354283796 129606108 969577645 975792803 36885692 956615819 495293247 99238449 834636322 676086802 13678441 59593522 401736819 246211288 996018305 663759500 881041068 906623271 649320753 664574676 108477807 345241465 615540535 146879485 780987556 138797640 681364644 141107059 479110024 911501867 197630130 833393820 41107968 167207769 661702982 77993661 976339954 9512589 29748476 810976269 538115757 43426917 723086157 939852576 289638205 571620822 456128435 23195633 330760452 105449182 687770309 439238259 303207013 155827203 586117744 84194562 294624843 119998747 77817988 773734867 884016981 275448118 459645046 777641315 295172253 973864395 708151342 271512200 983376984 737899818 935004835 374009100 781326736 658090986 313861669 923481307 82228167 769990105 946676940 412988619 727955653 486963608 852226878 31162659 642790812 290860981 967873595 789932021 410859728 45691576 416183248 147393068 173656060 875828294 925034384 468828314 702209048 633185719 592856880 538102391 223601897 527861709 912111491 4928626 38469054 78489520 780926299 120697221 848479625 580119599 533685840 428951637 67083200 238429077 460114296 562390378 529290058 280504250 204838759 940149786 178712192 621022007 87542848 352368253 349366660 865093598 673712933 51575702 350795676 266569806 589678093 574397573 646947881 354305944 431842565 685416935 432795464 212768858 658630522 133791448 792888457 44832721 562743085 712488023 283261798 22857374 127394761 812551856 155877991 332233520 605218002 334590183 953255527 545277216 686958436 155138546 410370807 213187728 206714248 761166483 479757535 648908708 188080416 126705409 3214645 619922981 664638711 436010109 832691839 175785592 569801557 478096655 220618314 132544635 43101038 503880112 7918375 23012165 316431962 16312732 355245685 921649964 350902916 161017571 319443539 37861345 316156117 729814346 103565440 375386732 343497188 583322975 24295433 531577604 562544750 27510078 4016945 79699820 316036553 836708784 255485413 738354476 167321799 476103727 723415477 62939203 979983839 583850218 85951368 148932160 600162951 441197053 923098490 951065867 454730990 242542022 841443578 770887107 824872734 945009018 146273832 20886282 380848352 23085631 552463886 943393103 903112082 556480831 875609289 71664994 245705975 131094695 810019470 265544140 459714788 533434940 328483343 292214987 117285152 414434711 293663513 569964469 855631764 216761997 521030329 162879113 311820385 214990266 933766220 136693113 159999278 932556419 157579395 540847630 808158416 562559647 336757092 711270492 119040472 64882741 782935486 217262813 48493802 445471316 482806953 508208591 978906256 811290296 652939944 948707774 78241366 946603457 371188602 933873130 15881813 892218931 96752236 327702199 107209191 883034822 464395312 119724835 668107600 474491073 513088831 328782376 37050713 849845924 40052861 8607551 914728665 675504713 78386730 963222467 120976022 561193683 323947417 952398645 225000338 976887361 753622778 303241704 776007178 124811374 89631193 791888991 869546671 38899795 119591183 829272228 774450984 436502861 801513429 295074943 910993934 314602254 623857319 948044648 16964537 516426546 809168565 784209568 44447619 887555296 599948394 17940007 301265338 923895812 970338652 526265677 753299532 576477790 682023747 381823069 553805530 771654941 173712054 275868560 663071102 145819603 957657155 437522079 582322465 759170577 732597023 493316392 926289197 208970701 293877399 943253734 725397248 103045958 579979661 769844867 843117620 179928049 787784874 144382951 956340227 610639886 523164994 562156118 39634035 205188735 943979188 593439565 829360042 117691235 721824491 492431137 116027204 679481639 782469583 698349669 291168576 367582965 44182421 69974132 576553666 338059820 13227860 301950907 293622144 445723887 71795767 136739757 625651936 712097008 133639075 434508522 322736887 656804069 996664641 362370922 714509170 940643822 808326853 543869205 910851423 530151337 888816709 26878620 62149336 671286285 577744656 205834278 38869243 621927077 275808410 467939275 959986897 141552636 769890183 106125401 587276524 694202316 95381524 65444819 258815683 81536965 499953342 581552570 738341035 496617976 796439858 305366564 289778157 604766704 849235770 53145939 987434408 590568838 932540932 49583737 114371482 510285581 107934381 5757091 132212651 383742791 473696366 944715915 525295428 96102908 903357682 112571945 790305225 998739206 178016764 49120901 80276165 677970106 483189838 671133566 27104441 132146055 976500130 169398964 736912760 678252259 222544903 576863527 121337456 7602195 478963630 235708938 517887776 586898011 241466029 502616794 970640802 715162396 299849068 495936223 811265304 55723109 461024534 454086888 54462308 639041299 355724156 987254846 169527764 838913994 510904771 49148572 971060049 339921261 218547536 560489168 870689886 441092440 137352688 992027343 448694635 468832684 227736274 819098777 55730688 469202304 174231930 26371484 36881059 474080998 374824073 848146363 529804107 835848608 302233245 436782782 327406266 657957401 276553987 349450396 349387754 639975125 398598968 172964162 979896386 617146505 585969697 703102631 58238938 575838751 695129967 359449939 44671429 775382608 31065075 100402117 97101271 205297006 979289974 133982330 679378004 206630407 982128693 61698471 894995381 136878297 350997619 74918006 794835698 627551606 424368402 996739818 120043090 822967371 22220340 99939469 440113869 608190037 655558467 350869173 184028781 203204793 562835478 81216576 978587401 593900553 34135060 75688665 799197559 13425027 209670995 331091923 72571800 44316048 392790394 967567181 181194345 743788013 42485180 976030044 223855978 319369949 825286221 343899069 142337313 847506561 296354904 434967548 455696591 951913371 785836721 492241739 7634524 201188558 573458315 986221925 795089111 607593375 61910584 594286664 473534769 124097945 925378587 546106569 168413993 170685340 366190110 349608339 766989719 261191656 178154742 990845697 580561605 3440956 187261125 575415284 703463884 336132396 10382825 11676834 140562126 648735912 503918573 148196650 849924470 77376882 134418569 645013575 684970257 48845519 91816598 11021385 25459830 869711551 557127955 193873824 40396884 775834431 395998529 659902969 37026080 574153271 503265025 470104052 430110593 690526151 45519329 133574470 26658540 908418528 145251305 19737032 557154433 501686244 167933683 259595263 579063126 302352252 904608838 116549743 203714137 848941802 127571128 229173967 718653346 537215449 423047791 611566596 313049873 819046320 123985924 202592320 245715950 627250949 525212738 528342910 170293459 423248433 514433746 49468365 331666954 512201417 69205398 741337754 13887655 237139081 933010 445467147 539491333 758058214 562016890 743205470 607000009 542104385 972379437 178169714 79319827 247943588 642252676 244886067 919506274 766238600 447478387 17738584 393489542 972691125 546081494 563783002 248455917 60515233 613251367 580122872 572716651 682456765 173976985 439120672 919595846 174909995 884587819 311603538 932968209 299121069 907325374 392484577 841225454 732221171 423170657 920545281 980164759 65423326 17947707 752187392 831661926 465426094 769925976 77667827 290633578 316007463 493967195 539089496 229039063 107218556 971728734 801755714 642191687 145705712 93392745 414303893 173132073 977980564 578423797 106100275 277101626 485749165 351101218 118327073 70486695 774271875 891388721 50651447 692211567 909336428 655355205 376389852 227278882 425281175 454057679 370428826 593805004 948024875 909518322 822844067 907759797 733763415 477116140 402467843 879469127 570508885 669288102 52601193 548489443 247711893 11217834 678107435 585977424 214835418 648950875 656464119 841623659 392855955 559631932 533835219 154708742 214987130 910225071 381987624 492784671 216799110 752416451 86589669 17340344 514451132 909433736 777616507 100730907 239066236 32600709 980200034 809575121 701888812 885317594 210580923 949600705 749051794 888688359 388094488 816403579 537639227 44558600 658027231 930495182 604190532 44378810 85203917 671694028 807120247 319707908 164478693 23919350 924640725 103584728 893776067 291608216 13018457 671392567 392339123 104601059 703993277 225055517 914176181 258398448 110373104 124757097 60515512 711941264 13445449 448610000 380861202 403601042 493168600 38888427 186612583 949875498 935783610 124332867 621569519 742903850 296557141 638564578 619339567 221197859 742149306 365631993 512806075 607684130 37024554 905145199 712285189 593534197 130200709 626461363 851932645 93090179 603734827 912448157 657547809 469696642 213574516 38409005 873297685 706743116 929813805 912426634 509134973 718113774 36759494 130704485 313533983 185833001 621785430 932873550 407030860 363934729 151021903 772353302 971618859 40562823 530014860 536420408 634097020 512731935 15398130 338546024 458338480 619132957 103510540 115886282 88829593 317085056 6811653 814643644 876344538 789141824 727070271 385479504 359771957 616346132 368700355 673305941 802179133 990485785 458695850 61726353 206936874 609717753 834079655 31072092 650280576 216610874 567492500 136893955 729342809 582890631 475439979 187681282 54539947 431466885 156083930 143369540 748551941 15411950 958013184 477412838 657070140 537599815 862892342 16842091 6462306 84109057 690148032 661157805 927111208 1360241 722884158 134048075 611077995 409480172 17636534 261358564 626091046 437645400 398252520 207950214 20536024 726208865 395631496 75075972 157675744 404231793 70961878 758744051 419643743 881491429 236156883 76713876 271607603 951565591 946072340 278069909 35674641 488736731 939227714 815302216 490096973 514628232 801866657 101174961 776624770 819503191 215049891 255232176 109664951 613302411 463182390 130200975 192027636 858813887 57793313 349703380 115562039 981271565 108447424 535205782 862762987 197120673 464436024 134370583 1202624 263024724 264956858 36877265 751761455 56700931 704695847 241858421 423845529 506562498 195549748 200470293 178582048 410599640 455702469 288246999 23902044 918884859 270964341 68446046 630215105 181274020 418149426 745777144 15061944 379113217 133499285 877824931 428750256 450451676 864711880 429952880 713476400 982185104 319346512 465237848 38886029 24042352 559612636 315247924 383121216 755162384 515718217 561703265 165762017 823937052 702466630 42180428 595338271 973430971 110626474 78069735 7221351 381292267 823846880 22283295 760405484 809862531 752624593 41672099 260314200 469852832 471624980 973790600 452037930 790971492 291544808 343440325 815013844 851157444 658688249 50651420 458836187 26922826 612354685 624598205 850859878 167337674 519294999 298714508 140768639 629921473 376784244 506356 11213733 53147483 22789651 624135583 863010014 627930610 665807683 123324208 97783436 137432656 949631174 402337732 780920514 93692341 745778057 448450717 797366151 256982665 499102137 256202332 136421857 111456815 733316903 987281736 131310856 252611895 138512603 124595861 735049734 515296847 125102217 598779834 568444330 408234 75431776 431454338 628338845 741239459 407294912 578638647 731188481 209442445 980976379 364625354 155651153 579270795 813076072 953017304 836253460 312178202 61735995 972675318 276151384 795052898 812473413 407462240 47664786 950986016 532058101 635230887 318799223 509676684 234010714 887243553 510084918 309442490 171214250 990940129 903198316 578509162 569578769 486903156 640467974 403071507 851528511 796119127 982342302 664604576 749136424 671112122 829299144 810872420 496303799 105450521 458441677 161293571 365429127 358622830 112279580 750003594 993853717 283595169 259680271 80380790 170838716 622281556 389823280 342052966 613221678 145537955 773078495 35316807 632441112 413546462 438388314 483969616 62181948 273246976 1090551 811318372 944359098 830389695 474707151 440662890 788356583 933148829 601956461 6302069 144288018 566752407 756305664 138141728 850347577 868502301 218522518 873702659 490783850 460862164 68271984 956521895 606400120 841350479 991838702 238841225 107413300 282743375 575327207 169595248 555990351 576417758 980913621 352865808 259323812 308137131 793528698 900196761 93802319 248001518 906498831 238090337 667270292 515320854 228748431 370134228 236339514 447270949 243836880 727123365 908133114 312108864 536161619 367049593 5975703 380516680 605890818 113389003 663260055 33734384 282984252 71766766 610152142 116414232 424632574 721992320 424551363 70677632 622189075 370870049 171195516 381204265 608960386 838465808 749041485 837708818 208600029 985380999 137496126 304953275 565020723 898145606 617062140 101182335 265195192 623037843 481699015 723602376 736426846 997475437 757336760 19411091 69242196 220005261 135825323 346391136 941997582 412893053 269585134 416703016 783763102 440780651 797907281 245239847 279246452 399465125 935465031 340362848 384846117 72961151 645316123 949866841 823623123 114894622 903565542 88818309 737932465 237780917 664937051 326875671 235256347 422273805 198803128 157014909 642279066 187144818 355922411 436793007 452554237 625507546 853496023 88833698 66288190 503919663 334073545 198051008 903384788 122054936 538413856 140747265 47532453 183729973 90614099 871155576 298624595 846696007 812490251 889073427 84476917 477427296 68465457 172249630 752217467 267268585 329264539 247012892 306929769 685186951 683805900 759484006 163210856 537301916 848317704 229499046 41221573 34907609 427550054 797122727 156962545 965963911 937869992 204494998 2210243 881000457 75650567 153351204 727696458 888140819 42424624 664689741 218084474 110890081 836939372 970301941 230675033 18720270 69831192 537604802 703907221 753637092 297088802 867118077 143455368 145406499 949133489 37193307 32830474 229199903 834316034 189793019 47680173 772186020 394288017 49890416 505702836 469938585 203241620 85915653 210595763 98182611 750605395 281196603 209072692 587544760 104014903 439747725 606265030 173846095 977352528 162688611 927483188 126957689 882323054 70938549 124880554 831456537 108131856 157711029 60656433 942447890 347504048 108336606 567150269 741792066 10743388 72853099 64247010 66501374 11285118 127359139 164683985 761890513 408555742 373756678 201951632 512570645 666020769 808216663 686416740 495889656 823421640 613899921 622847345 705744687 537354836 600244266 389717583 645486692 757955295 302890382 440450942 957975709 263743354 860117577 552284134 127003108 785487042 616531144 193504483 796772161 743890283 358188468 558662667 4962384 731945146 760614300 517533029 250482275 421347322 203949763 746371931 97285321 670366050 221735636 803030008 207720880 821979902 45263951 705723938 432451556 200670699 146174873 390427258 464414054 858808817 942711393 591417162 644295852 411758896 784921645 293584372 8165539 143110107 852247040 13127923 727571619 465377699 530660953 978053894 739241387 587127082 576942185 836526708 257493125 798677821 492073075 317730371 620657716 537337026 23454303 53109265 738007726 22145542 296052889 54938139 880954359 91280641 498871667 377766571 355555904 136309672 671350943 363721443 131936145 376114342 229365732 859507764 694008407 760026685 690078018 433249787 199670126 119536562 122292854 457163252 918214383 614365930 774893623 391388458 4219315 650864292 297014089 742227041 673009835 593066978 649681546 406480553 536863986 148553207 636763490 892419890 284862879 160630793 108657692 416799024 536745135 338023424 128823147 83269902 98050103 671417531 516519689 150236595 790954093 638812544 607399847 709168469 105694833 234809830 100556920 109914148 885674122 250087375 852141190 411200316 843154354 354339095 670197236 232534699 502892302 306960719 124954582 640271547 467591512 233612274 57070564 856853014 571635698 38410078 940122916 522202167 709827609 309158964 672438763 353298062 947971508 132354969 62466524 53666334 219681165 15539811 16096849 105355281 118143552 868238039 369071963 961297906 75093493 39269192 46348964 577985796 198746278 171303546 70773702 518854156 257432186 127844267 375707163 829067885 18770711 168346438 203786411 581114686 477505403 728741540 934412748 277993270 861096510 849395639 184175971 80777668 717451816 200272820 38649315 835595368 68510852 260237645 649409634 143604345 152023203 695758598 574106507 203285847 867062145 644880210 722140004 124494324 625240843 97847160 806078575 496527920 118709965 862381353 77642599 596215368 591122886 12055341 874208638 304735755 713967346 58384602 238029790 431419155 258657422 129195471 119530882 179684640 241949482 768940516 175805352 393972686 464699108 602428225 597258533 184277612 99824794 171914896 161288302 725065637 122278423 819883244 74109916 240988388 682264590 151752516 837203756 125903835 16324223 711412387 283155957 730291569 622313356 521185747 14227083 880970778 502897584 133757965 913171785 744847067 902698482 88977130 138819746 219913949 543921721 588594645 256707927 643746516 760509542 417996229 221328512 882787965 90395832 295438429 123776346 772660422 447190945 813496468 751080624 316031534 377425214 34236574 46323096 999738570 407938687 913066552 733225708 910836271 46824510 646397486 655683331 802039358 587890982 647019443 874469673 131812696 88130448 131177593 628075578 701156356 401690189 849404091 436460680 492086021 144842513 412753392 117262803 444549824 226249853 868343427 760581358 603675067 902580001 659420820 455929997 163035047 572487365 189155698 73871311 471828241 688069550 582071009 126383959 128476891 81606811 853625 112805953 169737259 984547592 740881532 870893615 386237774 590285616 159870654 878323795 587644495 572624046 995586598 32194312 798873899 716446384 792775670 255065326 471542744 304712849 710995323 634577791 877200214 752667387 708449103 201544814 440736930 143036471 180445139 569213821 224643282 33815131 682019774 394380542 18362716 275417665 117790516 257116856 865703281 277661171 135440644 305864135 850285217 983543609 338058447 501675476 552506352 983350483 609257168 24049090 288063325 172768850 658626881 17779898 925436237 219592343 71841079 218689526 362628814 252286218 787903347 587272097 286101349 322439480 834169005 304464065 597857146 951959521 561580921 316076786 82137051 549537932 621940922 784938635 385597900 812515735 139130470 938104252 795866212 748387638 814669708 936445903 921156488 325812949 954225802 846592718 545405292 26066874 65282237 760550473 130869458 705701950 200338929 416970808 880657796 34507927 721434873 331031301 838983814 135532154 647108088 921120866 537586452 121565369 558575860 923184352 934081104 697706330 713804963 582463675 446093961 380991031 371425938 219766808 706803980 178168099 66359519 104725631 56751339 984158129 865276104 187620797 542376438 65615026 604591605 275550593 100122953 178542838 606581895 791623134 314074992 106206342 565260359 851661444 227771711 123836212 627362155 14369174 821542542 193683477 449349216 120152862 574674508 820775154 339919670 133994847 998943253 258795555 238720479 55694585 95470043 103996576 243315382 490362847 22127969 847906988 765913440 122250922 26449819 372495328 766390422 193041177 478701670 331650774 897218987 558989747 308003352 377097501 573358922 129545887 570780978 22708131 102215115 997971853 695999651 294651151 131966693 694942897 553446706 370687172 603153848 501433115 327200115 846469230 991795962 349328084 546892577 757709396 324095372 425858762 982721090 90485788 471416305 313939120 274652928 368635285 872928867 582656281 745732786 298804148 564718534 169030124 174028645 666933650 19518336 870028296 961584801 151485029 417487552 367547867 374688568 20641393 868980982 701888683 719626990 713293304 51216760 119035926 323519059 375312132 544894689 306240142 318314286 16310987 620179262 592967215 237462639 345624489 175623489 835711791 644428637 740342023 4741908 818457283 259792032 24260244 688485572 73893193 28261640 105973118 293957426 402950208 979130884 15454767 104838884 698757867 728748071 8572010 817793794 52267123 236400508 215204842 211023632 554714795 84032195 831202894 147682003 174011200 29343742 175821858 9722985 673772380 916163881 866981266 492229656 28472273 743757877 33231587 102365466 772019517 991721078 248839258 27486084 970851956 264294025 984841341 522126182 993042097 993413351 192436335 45309213 82330218 260157543 108849211 637045013 344189739 940052106 784727016 518200939 969395848 960548874 380440290 495684587 729229115 247421550 987914243 610217754 991179427 873662197 565099586 615715303 865383268 813938844 495717753 688751583 78232862 480559087 63394125 71274952 326488797 108346826 969100539 408819015 368504370 77949743 45864022 712694109 870518215 683107404 83411407 692430423 496172638 463851698 40631369 77918112 563789614 28545606 688135866 407485400 754724169 105751811 23200696 472623796 919690655 371434815 13891739 997923517 851993902 77285864 921714836 30999058 185632690 743331734 292334439 554137060 673797843 190714827 119347528 396832418 873822232 55275302 941779207 222511229 519127000 982410576 152945707 82916607 863472548 841081573 342918373 618196710 946833384 218635435 90820500 719040398 590070250 104712239 569480274 294580511 34514469 343711469 325579569 72663525 87043196 617914008 626800586 613357406 808628836 598664480 862706190 534967427 653939782 804485390 609995022 25583141 639412325 762940729 108499748 502884867 456538661 303934487 973597943 255888404 522569922 916934809 974928802 112640165 874163414 544409069 407220676 908677883 888120539 585316611 981341409 827680101 55746979 460658354 293553866 864375815 59322827 8776415 251859601 565778976 813261805 861854623 591362117 305190490 477311711 552378232 808075357 933850372 856312719 634189659 189738769 378882635 551124462 17183930 344039166 277804235 561592999 751259843 38998478 302229897 189092813 20339880 982426365 244839792 333514600 128496590 109215600 245353793 137273006 213591567 811132769 950534811 927962556 255011246 108241660 405274260 807389478 916317017 191640991 663702190 403023036 381379760 895101191 954147498 398563690 239140351 84468092 812673056 842916560 123466570 114902946 32009366 143806450 949845677 276849159 329837416 78342261 238581125 427707576 215615267 304689059 91356704 18666437 232651608 346367950 126908098 490442235 153757421 895741481 682083226 669975978 298764510 63462980 565077162 105428367 314543036 656733879 189896460 127216085 499650432 313363030 94635398 384176165 309685847 896997441 661025324 492039629 975339702 752122815 919747205 43471328 56811867 11103903 62137766 141979842 357471853 41562230 632422077 363745641 937303711 314505296 33721612 88584581 230484642 451315140 46529314 397544045 108049013 236425774 377276496 460215811 402305171 324428260 844391976 711991018 221425695 357933659 56547006 49281756 110056468 976294212 92753085 19384701 987398115 7407217 161364543 197386327 901485820 793786620 561131968 691305890 108291910 447369946 779890471 191292918 898685087 826419786 588836963 6734093 915361926 966113460 319466270 317667090 143058079 163858240 882174474 364483774 521791899 938721481 266281897 484364733 915015686 211551348 503749435 754930160 71474931 665113978 804832853 972960751 458900592 218481181 664266634 419708868 665851127 296673465 463518152 564536207 975609617 52355109 423786666 890971536 870984935 743252937 61154986 14043007 759627543 943329460 231043148 133935801 734567300 497325045 618300535 502099345 708876393 122049963 109545864 780351324 787163941 914378718 605828434 98580892 132859892 122611427 370806126 798711019 419284892 834324279 215763586 247410868 739195754 492066618 138382398 462697048 87835914 52053750 329256421 847463457 847899576 560299569 981399259 582466870 910140980 599699787 84566208 471533732 574266116 46628439 104401415 213946416 961007157 710229849 312527309 93867042 832841277 683333435 745094427 104642528 370174073 813374379 352053397 109369820 305440991 342952161 572066868 393276905 395005911 901323290 93256722 95421846 314139218 74655974 677888716 76796558 526872127 614971291 548330290 101138236 661599730 652731706 315084652 475123246 362961548 480128327 421506654 48319184 15978122 19117440 152961713 386152195 832491820 505015110 495522016 137932804 847967271 920105250 383726075 95489541 673944899 476982797 190911387 988084118 404155137 868800104 64880669 931027264 336287754 465727325 32165493 850403850 118459024 199766512 325527089 333936939 679894839 747033743 382256123 695872961 766151183 535217836 82025150 451159362 40232939 430063532 441608532 888200210 202685141 825334608 983689751 876630041 154833764 27117498 717230518 558988902 895917602 634627553 342532525 84721715 100354871 227214385 935125565 71330262 426980897 113169013 405267201 959392102 712719122 787523324 507781423 331386664 322741154 442322939 782546027 215490459 872386471 224154552 103690663 75071605 902005526 939896780 804218012 56839284 967014278 521448523 468344552 715448239 8592435 810877077 652686320 108947307 38091455 440328244 180277569 317588718 553497257 585544770 129497180 118732738 225584453 637278603 450119403 548325607 79601535 232665423 763816067 804504372 309336341 720023096 732092343 211341861 512436235 536310349 120697511 331966873 910275238 441558429 899931478 918867674 104951865 552617792 27814974 143043321 992946036 60608909 313148405 398959653 498670045 442645585 517692391 724254498 79924181 967811794 125096465 12042082 52993576 888912532 816546454 362329918 461451987 401155157 426188145 826404588 937465506 546885656 10887820 700257103 988444085 910819299 619124770 93395943 315953450 499456110 88955630 161415845 412581385 254620402 560375498 911251430 549782353 930584256 635505922 482222901 750912409 760602387 494264983 803905986 502031278 163327797 18752263 815999631 564482954 444940408 642404212 354464819 844342430 653292033 54721915 685302874 416627691 526363052 631215183 732581141 878335528 572687180 893996986 290916907 827307582 306888844 54684696 229606294 237473093 690190618 711829195 988385502 303309364 58610538 644807847 657857008 221938335 516076476 473856632 638937655 961016884 968777211 993402474 657875673 474585603 900640755 343178540 891213294 279520166 974393724 623794428 10372054 399597263 370307773 301288961 79421204 677196617 355973657 309027498 914669710 898680642 20856687 755571572 54506365 79467225 252895778 712363374 153921926 768972255 38736365 792859581 582505498 7513569 638778414 92897531 482099172 391935528 436076071 225828825 671455695 262986154 849623253 681827749 662583417 72447386 835633076 742004621 749644003 44123092 51032113 516830073 942803734 924405173 124918004 997310100 3872391 377813782 709673467 10310683 999302403 748409832 803170264 434324261 608439768 441948671 527221792 90538933 833884199 963297863 168884125 357856253 78800377 18507371 892200368 593900160 90954757 727833437 188421141 693115127 771956530 91969620 209945193 567276623 16374786 334863197 564586716 872763550 565193345 126776542 883074233 564495742 727702741 686244490 998820003 336142502 980709527 378558154 279197801 667110085 194372376 448081926 24966332 273172753 319105664 769683066 867072914 262576787 350032863 55494048 955691914 121989386 147463668 18153466 541782375 16354820 205533029 106369085 889118370 770726375 85661993 624708962 187738476 813364734 163469811 39074838 2023595 144179331 417632992 133737763 811289416 612005368 581819689 688772114 885178122 753441719 310971540 604767395 16018500 661004403 512777809 824226780 635510155 512757843 694896613 177292523 381629029 900429642 136177974 123263758 671156010 74356334 747972720 858894486 887721068 911442531 897969324 742261030 55621855 168118675 875998793 719427637 780124044 310334841 260716111 517818525 63776554 571687651 122585913 932311427 85208413 487880088 609054566 720718568 853154297 303951172 898011091 234783319 56897174 886705432 358047077 728053184 961061766 106019790 439464030 701299193 869978687 189949713 443560216 778116908 358068389 172075368 350060904 138192426 482410210 610777015 508527317 546186764 34981025 483629596 331014550 120189438 971509684 940069116 840908006 677180340 96536648 591435457 911963659 153433822 330657248 122527095 881487006 291719007 81063251 173467395 993018200 951041938 215933475 289094776 581675205 574001864 461170144 931736109 564710656 943580354 395029484 73237966 342283477 430010509 409383928 673298027 402716314 233409971 465883503 96140679 910590311 562420151 687576136 675070329 715853973 18233377 797597424 449857338 162468750 731177041 623324734 8003310 534735338 839258209 149614452 116410536 265776432 610784596 48146638 683003454 406881310 295692488 608757786 601681153 725702998 18141707 127495540 128419305 251551678 593379043 77076350 14658348 155799187 764652487 689728677 871653160 635402230 339842460 174026857 650387347 71019494 797351591 658390657 605754832 489126159 808005109 574681734 607418957 271306064 475344738 290422404 530703740 771037227 899180190 132384887 349256584 769838263 259880427 330192255 21389934 853259470 407268605 36048282 861575023 24437451 578293325 585744542 659839682 918135785 759771399 162743388 989155279 409639350 821134045 447426470 898765509 481655513 22108197 358700826 605477943 349969302 649123230 136181677 121006522 400819780 121082930 470263106 23174402 380963357 800455361 44564337 86739186 60240325 933128992 948314209 84677777 363938677 386575110 744517459 282074455 146346502 907260847 123746094 555985852 580911251 423688930 307267721 915083130 298313494 665968547 520561066 648282796 167608136 509259109 769289318 420944282 630342039 92068783 444118685 11305389 745040510 341199388 950560948 805280835 126844739 751391516 889958612 490783416 137966619 486992430 772857872 136829488 246769636 749120332 692815340 827680887 172809255 852599427 595280376 471122749 371084333 115841436 119405538 538692470 477616911 741211222 959636752 107958944 685796371 256271796 971780706 430836874 597471184 922341648 88634069 724315924 526249523 978592681 215099333 664216143 465585105 840473571 801045631 712354741 589593896 346377330 392551988 614919518 51493117 987832364 86042260 422577450 956190166 57964165 961269920 286323437 651691753 773423032 394282381 190004484 29694821 218579446 620841358 479682372 140921087 709475427 203998289 519686977 540584468 271613988 36419479 6169566 112087553 837465110 571040673 554197815 36358799 816109027 169117326 87851916 656457751 107675953 510429367 465164276 18156484 324215646 751487713 522364603 950155044 145770087 712369087 832366232 216865900 185726805 312048597 210303353 895202232 368563252 729990330 288303059 640177240 766409809 146988991 752264793 456391278 718029665 158978968 492750078 386655051 328096294 433118360 43112795 288288613 943547727 508277072 306445097 120279733 112281144 828809701 70434770 110567598 393695147 755317368 327433498 579421952 67365958 537736851 327140544 288445576 267727175 615443603 928622817 34136977 762432595 533403969 343044622 332978619 692382937 835794700 719633670 20479225 121429419 762746466 161284204 64977140 123539897 467729302 37773239 235821041 149055362 960724382 346388639 542750509 716041744 673822137 122172455 635924068 64075348 301829365 924369645 331802523 917272968 705508821 218455866 679705556 238912783 561500488 12684168 931295721 249811547 584834205 804291312 371240967 200097030 965575516 288734473 323636927 285821177 179024078 411974334 287392905 139748453 758362974 830143415 708306563 284701470 804832236 196746991 348776818 106661594 121116629 533095707 876450928 679141816 751551574 408672844 918054599 165568421 273873378 701866679 267896335 858707583 358674350 639137302 58804606 176766226 780388141 234957899 315103769 959412219 646932234 602496675 99160665 257811567 285156449 659983595 542513037 89988678 856730586 743806222 49166638 830363581 276901922 778133932 509505390 880969862 186806769 280076348 46538277 460680148 834459394 166950978 171904090 45650103 806088280 230708697 222416329 438992780 465666596 537520099 398404992 112598823 140016767 350082023 222926756 277689582 10065611 765439794 220194626 719312563 361762375 121877630 549676137 638664297 900011562 911697893 372150519 86818325 44290601 271205162 400014839 878749995 438156140 571918929 924400098 96760779 655143992 146816421 535753559 120810582 536852886 934158551 85925771 529386019 136756933 161368894 807075601 999338918 926808688 27270220 718651474 141087422 1664216 120843971 779751719 901675778 32541857 4418597 841010469 76832458 275623759 93541667 808098819 713779899 665460597 732498911 810540678 173120948 731831698 346294230 146447896 121200943 132969140 84890034 503103328 122242440 246258928 162695288 121581351 25583975 42481874 692749191 166671397 44146090 813593162 946423116 945821868 698651386 950841714 786832331 628000210 78981832 880373998 288615389 792761732 398350954 21114293 603302403 571471903 605462357 802113000 717919799 579179666 935082140 802809833 82282987 57324573 49068754 244978275 31422290 74652729 287460149 724171482 93840492 331606239 390281003 40263602 129944466 941448755 843621682 916776797 421965325 922603514 649667155 710580714 567881605 900534475 584211373 23700368 324522737 42190089 825813368 42442530 621369755 613411867 697768729 703652742 523252807 599353850 801147383 554675097 526522945 88607525 131362938 620363438 272730130 374160308 513143406 402674596 315609056 209281447 171967753 737574381 984401327 674151274 300671454 552282926 574685742 884882827 575983294 899208480 927072916 254313021 794167376 548442664 867724888 344452464 104611765 390977688 796322680 905759148 798169152 175361985 846883039 929532090 795725423 972129535 156208757 161385188 227320491 471817814 223183001 399288244 61908554 207584321 73439511 362580009 612383613 500641619 99979195 40883266 252366458 27052105 295196287 899050200 428011135 162921169 96019024 532622901 406415223 892341704 290898408 204584368 67703682 990297814 986632825 715945471 962427342 142841575 877330659 42264192 467175755 100513653 441552436 529084310 160614341 367508313 744180685 772997954 720666299 844159880 813881221 973032757 871211985 109077501 724599317 151739480 124515036 820618341 684362381 530930260 712960038 827777155 588030994 633180087 818074962 574663812 349125551 633018664 570021754 78972570 675282856 37197502 32002589 969351659 418798178 45133296 189376331 162978856 818131251 910042630 7138730 484528831 735591747 730867081 446122698 460191057 882606561 423154101 133325757 419485301 954084361 846285795 99778816 394631714 331982241 917853778 969295527 681107793 403388801 391833640 612596729 931188024 429031142 644599318 900539676 847829321 689732615 89916000 863324543 360380225 852474997 722979639 697425422 588066737 306363080 143548113 900774160 41486000 419218580 34099910 460971302 225819300 732902071 560750118 620451015 64884306 331120255 442262901 598508465 587025423 834096541 211105187 518213440 115644042 708220871 271269475 963473363 250469845 213701841 679314266 610850070 66176831 402293898 160791851 506759934 708656978 156856331 260050453 750142979 576074911 294150363 63630640 801894212 27052428 476897124 422345220 944453107 808017379 864608121 542961565 247559161 551221021 606583118 765772601 666865063 314803982 889558442 482854786 565273828 103260277 162169045 28640257 21953474 416979309 189432109 381229775 125636281 346288440 641280228 728295626 922363351 787946958 644442632 576773922 667515752 121339749 999119142 611968852 781873494 716243622 7446776 29432649 119981002 614029894 647721616 786846066 781350242 537280052 269700845 199140429 493056695 284386256 227780687 367526535 701365565 269729162 601272676 679518212 616017602 95069264 260330197 390897312 883016222 904772829 967671235 550531967 26112571 819306736 15017178 660502432 388066718 22463954 689935081 508047720 489010214 190173056 147410145 122876815 727453108 417110990 322017245 73026162 701497246 549797932 293069064 255379171 819527094 894341740 934897383 288061055 989411004 195227574 531474733 872427219 100000396 351662327 275475545 978629341 23485423 143009089 491648132 411552141 17989409 34099572 772116227 506999623 224272628 919526373 629876439 951725737 189153722 951893684 877268265 890650969 354207975 170337322 146030133 26251428 64679056 933443882 166828849 906606426 128671449 698303582 631550005 81188212 49965903 907025550 912333919 73451326 50034633 256498410 337519833 68024042 290597982 109636053 427540032 514870610 29162419 909932837 319112706 70832508 714342880 196380965 961483477 68550848 219234653 960029976 947318649 136430075 745990217 114147491 43036495 727178033 812451073 674586500 660882611 714933342 434128409 425732889 788384668 336679408 682231299 125904494 257219817 972829281 88056914 537276215 487699884 969735706 447209045 806812591 40568207 14068284 855709922 854568050 82619132 74944568 667114385 882454147 211374644 413104596 996601638 106927505 140282622 661569070 781514005 653681599 229018772 68158773 79414481 17403433 257354548 761645780 995824301 514574365 586991420 936397581 51850573 74691297 906133280 351575984 734020254 799217854 365644268 442246535 653785897 300779766 517191104 173416642 35750272 581082114 586521238 32351903 688009619 579320226 546437339 322039983 85518184 775456111 390198756 164932665 645375911 647553304 779094811 493716571 14644028 366086224 282630511 919010974 293293887 41280150 123103317 879830508 840498004 488747585 322077036 346800261 642043717 691784506 520216903 677793989 272866613 106738134 562662258 960876232 538574726 109099591 135432574 624092910 737072068 525631331 641541941 234964338 25700994 420636745 581197275 40345023 639239335 863827786 811872363 932533222 905107937 934975681 664880089 745605934 276239625 986957126 92406188 918283343 531257991 465139457 596077325 804124605 424393957 11255943 617517196 962968683 120355534 752949771 439577952 709943968 131097461 81119886 797424673 9314821 354272997 378621941 49659844 993512332 94966087 714048574 778561914 74017 649024248 295958362 598196317 925263873 135431847 543118872 696063575 666689839 8258322 144657260 323330803 432652280 155913203 940847999 248137322 128785103 546314129 540231641 838729071 529927956 473867893 488670103 539242778 828140891 867292045 441418988 674169582 962258132 155467555 305247855 814848515 657008169 601206218 413044825 434788402 736638065 956163697 130851970 255844263 816938386 275509230 579175066 102107025 431422433 372539425 350244347 560207536 918853554 890475988 251452967 301297870 216860241 740123070 840540648 45001125 459931474 281959629 571687073 274705965 289943551 729451295 89554473 946951720 183173872 355115665 381740115 919811937 163795721 365108452 28172560 980734107 640617682 607347626 82841125 924556482 979887051 285601839 337280377 751256965 28594186 588733344 52554828 245454427 181372774 893095476 142971918 493820614 27571464 567175358 768526580 317515015 296626646 710597419 116983095 479800518 918229450 498723210 252128814 82025165 863831662 280301374 915275638 356965704 887649001 850633130 134038545 720052411 988751335 471318922 471309369 17345514 60052260 376380563 115316308 93941400 121992398 110804592 587762014 149563863 677979950 208804953 319595244 974606596 771918739 436578339 306923473 690148182 935301550 411568654 624689713 651649571 691870028 392481711 861131641 432035388 95631200 995170186 4604159 84382528 466489102 475913528 954244415 379057728 852294092 922077089 325515494 974286490 32881675 913277508 976366719 710861625 974598828 295961957 537984581 746517560 732540296 697424420 289182101 520358205 108993067 766388181 24524136 653379462 11386251 885655777 85414843 107017451 733342323 90019002 43916345 52347784 418448897 850677126 431405512 123259348 772754209 756921006 950062204 658152250 522714873 926428917 221530234 349830060 74907233 759514815 96347613 659963895 309455595 238046081 32838460 418448662 4434255 57362596 71828117 15820506 795534739 9759327 975354330 528877055 952294702 19270668 581224839 223259958 722464160 865146717 199035672 347734728 474584082 149097870 5886971 997298956 928043153 227417206 199645375 2950379 839448387 148509355 515430640 148903975 386555436 548269100 419869004 243506057 605631696 344213487 111842929 253682795 206489180 87197252 782559850 11300242 958984293 216301049 234560200 533964812 81447759 433595873 881699541 408548208 435210109 887586512 258363523 363253255 967520084 458008898 218720000 806968465 606518253 734150640 808388806 993073689 134936100 228257803 89096105 740567796 572471291 53455400 994250591 778960471 140652652 629326801 790260713 952153311 698144216 877337280 338634483 632108341 163449512 220334017 40656542 598659621 960436895 299020065 961912876 927956973 757028964 33149235 587441797 216063576 619816241 248346962 61653625 754752341 476604766 150749730 347836497 901592423 204205131 194603447 533069253 197374149 823930248 175846326 2043820 374590823 53183599 340678303 6699158 216633111 413528686 47355700 815292732 373965574 198892132 629721967 154438906 808437462 515387568 594397069 24501031 135203802 842744032 86154656 889956144 171865157 89420753 90309000 73457573 293625884 284912447 606526826 343516399 108842689 782373152 345560219 335949878 688073117 538754888 342649036 904706228 952283574 242521103 572515319 178765508 293929601 54753645 333204414 102367056 570141213 927601484 126868087 557861382 622861875 65539110 300333885 794727032 154959863 390642885 868184605 301102113 675555332 327227790 644618512 636914387 962117309 990178732 972864266 650190419 381449979 168029661 407413007 333733547 410550764 832444692 512499055 704480365 887198338 698219835 659363787 309855910 478337678 638748241 867717292 101199546 704287351 20567536 895926578 711763580 411210421 616627542 12865686 86765747 796371699 657484198 723680134 758489001 500179289 549060759 261195779 881629269 717090421 521125152 67879175 127641178 353569838 432894596 684637910 93284535 131114424 196518056 255656811 609452103 835266297 123374097 563168015 392070007 143941633 311610953 103833580 407668421 928238495 116699266 494434168 577126553 626699831 70630661 188131913 979395486 619691421 449327693 713541114 189298201 970452845 781420289 169455745 176539042 66831244 854093655 122339943 197945669 50611705 377996755 659914138 738394368 353887218 223082146 130464369 350345217 534693099 86814315 758013638 315447954 56029948 104964165 892574507 682729779 175594827 80706414 514641624 647802614 382550473 228182732 837100815 205519677 862119387 6556553 234575086 928950632 713166575 356915029 126896294 616294646 734911784 639326798 354689007 88798995 862408944 337669742 439144213 249618403 424484058 49674210 417582723 480514006 154638376 162673589 15760144 330233203 95896369 530401768 978035817 478446842 758584500 667652991 536482886 473220247 674209544 771057972 402170872 239892478 127972994 381583532 856187124 862884779 20910323 63392491 804200140 735835633 401062233 95860712 837970402 825546291 145534923 255553118 306060290 300173299 418226708 321820434 630406502 514123077 852222203 460958678 845086286 463323062 128611662 381569165 936543309 655337572 5143496 191230540 895230051 133116490 425330438 603933534 848517635 298757127 667326025 652717769 34592754 68388252 748578481 725079522 893934543 894113404 980632641 52511193 46803062 251375708 226847993 677209564 618015151 79070189 990684608 463101430 394909618 971812636 697186961 183969286 479666568 702330457 227716193 227412978 835446948 653046631 831346512 536480942 951803759 498672531 41715070 838912879 419577149 790293552 563992394 166028051 536923315 397141394 218539244 583726378 501033468 445387238 113452301 119048613 376973793 104136903 434666409 624399777 928465905 131853364 808369064 408132466 834183821 36085250 635545444 522147128 541648247 319408316 58628064 493451999 818080847 100343134 184881237 90174355 743153052 748873632 256202406 132592727 998531392 474741651 568835471 499564854 772645255 682287772 471129833 2135407 638941041 905796242 626535185 419923306 37649599 287420608 828055772 724349787 176022224 316117576 99013274 717670471 635525892 10157704 63638830 306123098 963017212 248520067 396297453 558686623 997393699 652499859 691279350 848441451 979757876 112631180 200522664 752403124 794918953 671652497 754538532 286376353 577448732 233590076 706299659 467614698 521010684 386871791 44480844 697032908 555505733 143494118 414703372 43547984 6168189 478342202 349671082 969185401 726862270 598484901 380388383 576772328 103501119 71667727 277730138 83258989 36815273 478252802 688178479 831734226 149905292 295233370 970626946 579870391 528823446 529442964 47485082 49834123 916314755 944482299 746867031 324336847 940492783 14086763 367884831 946660972 344945331 717555913 768362732 71807594 168557173 1267475 501096289 272058293 72935202 778826427 355317282 109750475 109595589 43495754 794001068 259500881 191245491 617144373 839371272 720068937 146587330 739372720 769903061 915418452 536371378 369286451 239755292 476864155 235889580 607640124 276041486 580834912 177712396 896920585 505158872 346269570 898188060 6255154 618327863 823639628 637597948 826161511 785906469 747193537 722173631 432423896 859210784 913419122 49568262 551098416 633488053 48671959 142987495 255907473 964090411 679358874 477710290 56362062 8739388 713599871 664002186 284780874 294434776 694230949 34217818 799593648 40500512 932405878 658365169 511344741 756045499 148479476 190022611 394468328 748189379 912196242 826892224 607400156 825615358 876460487 11014931 311619770 925132446 154002427 420043609 741739216 833361301 897753899 798101278 842100689 611353763 314619824 126881556 758304905 8850766 13615741 410414913 901867651 946021619 68780075 265728751 554583478 69775917 455751362 949051806 817965296 367947597 775944023 277881811 46079314 504920869 288896743 210215450 282569674 442899170 630259059 24308883 128776830 528012952 674926528 970877519 991883081 989546352 950275441 750187980 998397118 963891182 13119252 752781128 909912795 81899327 18509872 317012632 4191610 474261234 266064431 674673272 694725197 894524820 952555083 740804512 251962049 93968185 951019962 534531723 389383721 433795381 411356973 518160551 961808333 86283494 489038063 806207773 928346212 291829864 408912112 779259689 255721039 422031364 532040810 18150193 356447057 403067048 335162825 360638667 877328282 453743622 35311932 424569838 348268436 840383382 17890709 600230485 786867933 968910672 987278574 176251648 255222412 251151906 694412199 69547104 189951766 35966622 875754877 118297971 327796486 284666983 897557660 436033891 706698347 282114829 454184085 63145398 685181877 641863276 276300431 415026518 95606892 164128730 839596357 296391694 857028478 857487066 896622179 643896404 678914097 736417112 672664418 934136509 987569019 219592977 3683606 177520778 255559599 731954850 148335116 435872451 16621826 45892769 871906342 575836539 180523965 178606786 491498303 718222208 820470063 620315101 133248720 916076955 784443831 825361443 64985008 493988668 535364868 961607187 137885065 66795325 550540658 663065850 853448200 538109670 882658827 709648173 568146815 138218419 441603016 716481931 426607236 310741208 614891066 298513571 739094113 795415031 477120358 83108776 366153599 150106780 703423877 351918685 66183728 340384067 29796487 131168736 834372735 565161355 945292289 824774166 484473046 348349306 487840009 337921240 886458977 223015195 47569406 307122151 213749980 341688788 23604075 640357216 504946362 638495141 938870788 244040468 286426532 268507505 327149244 652580131 418614285 30573114 4498809 337314379 223473547 34295296 320999481 57846275 451973017 118808129 882620442 936446064 467157435 222976810 126883663 206132771 445992006 26969435 513254922 659741986 221174589 389375363 152615562 726120951 27870498 91486343 970161419 166813396 212510214 149827023 671909893 483640865 32916503 528925068 820955244 256390051 415736730 994471091 166752692 867709747 113279213 49373127 656672170 432953014 124866304 636072199 491602152 423374676 663041634 4857067 83116655 884216223 246748797 88248583 462853533 127135661 32251292 285531312 293949057 244761506 435358335 965858950 728402371 320791204 347300377 401873974 577181255 763037107 248861424 743933948 483263213 214657003 645823441 139935377 647610018 623206111 628523942 139212163 46580780 144081936 996585603 982213809 28298152 95850759 70462385 343668052 222986420 102713678 629199364 516935477 199991550 64557692 335310786 928393922 237865262 682611163 182784255 815046518 298164629 431645680 411496825 781427843 646302683 909836632 773879586 146429060 533042737 402403521 138157589 432139883 546485457 987259559 414353685 427299976 83110311 337332437 770968028 306096732 440046115 252683751 675548575 640037665 169757809 10859355 420947946 407623071 545986884 456248568 75185948 844151514 887894248 486682773 478095716 386713290 249035765 251975295 385658717 782078502 506895182 523816306 66734744 53380633 363592224 481088430 333196975 446702536 818420867 956681369 605315634 110983341 209365113 280864202 603537372 379122922 144239923 24485312 786745993 542743174 333250246 861931942 239411047 73660853 201131074 717506763 460374143 450166839 969482058 846032860 84761700 328893599 222365526 151496445 234790598 585957750 485101241 567987573 885176652 156038467 377185301 490492279 267021808 586550414 623872848 870559180 818189702 768112771 747560858 457452055 163372304 80811097 171900356 402783351 6988316 373031430 120290107 467362460 675714636 942288531 165911679 760476336 271182124 240793571 764489147 505972722 826751322 249590381 926476662 564444333 405628848 303661956 54936606 525167022 742728737 531325820 248242562 560918432 151954950 995803420 18370480 315327255 929130884 42787202 718110606 936119200 415818633 838400714 255998019 91533262 633205604 274426065 704525964 904387728 515219636 321531471 262876810 194487317 571121852 41869831 758931651 829267067 345531787 666384623 354434082 88260517 197710436 602676644 501695316 349665386 450996424 372582162 664992641 232643667 415369365 235619607 21279226 683704364 74020314 129793612 627753992 559742284 404219677 184796315 316646372 919439313 506327786 579523182 113926624 77449632 621393013 872858275 759233065 819441166 391759257 113667140 760218050 589469693 568860151 114429725 791651445 872372941 487011887 309160446 105016601 754897618 544780053 978812200 438601975 471316733 108605805 66355960 31059010 512825482 103668642 347705382 284781155 609996428 779744930 398707779 539962426 253654302 124082413 299195484 73095462 515841670 265378991 833313512 957827729 686755508 947743237 749479167 559128442 287271483 58639606 516661409 42169095 455936025 347989968 333287436 927252758 456595774 252159763 958311769 821937622 355828405 158533510 106718770 965824833 938278441 357942915 358303619 44449102 482025328 657499103 117544564 850383364 775394460 803374442 808211086 462149961 603634038 410206613 873794769 890905522 321362585 242972537 785590983 777298611 590962506 971394785 557067728 47558273 76070907 367895856 722012261 431899312 526429367 828731032 250240505 317224167 39190306 608544124 361673269 521215635 118559586 331734200 224115358 893954047 135108635 32326438 208620367 738742674 295049417 82415130 482164555 468928368 177904033 120271897 98743338 768866539 91666675 655811067 668941178 20253949 23706916 390953433 452153261 402652649 72200824 554910132 719876816 111391130 15970615 934066452 485123131 134530202 265800645 709238490 881000615 253425646 594081294 89620975 992168320 889130711 24552471 326849234 210575438 54972871 299637497 309318777 823839410 243820539 965129844 492780582 264074488 988836760 736250381 716227749 244005769 808451205 123654241 963882585 772358701 139624856 750465396 257481826 274155058 16266034 966720316 7672032 122208047 413317969 97293008 114376360 154965039 974361852 293741961 365540477 29334716 593379458 674859254 705690493 837199997 639989091 50987434 101274478 481342211 787237815 670018594 725347980 448205379 793672835 541746924 220564073 933297691 144728680 330562265 59969109 13511080 149798940 67641141 135719127 563116909 17450515 102611854 718081948 844328734 396353815 83622419 726179816 842249639 758481673 431870302 531965996 250987124 482857736 485756840 584845701 122611910 8291793 162710040 570817289 801964628 704456964 791381363 587778679 849185644 121943621 500264154 862696725 124258928 567905295 998415852 687375837 437872177 101027699 405457779 282200904 349897880 341596564 8380713 44663879 100078230 292767382 576629875 203581720 628141484 62386708 788427421 750753395 70678502 951137461 321570677 725159496 508110785 965468406 165454534 209812788 939928394 665718688 925025879 64187315 86140343 775958091 751563152 524012520 729502156 9537290 806213424 79400030 351133854 667110503 124063909 303728451 812394251 553210150 359826537 440535729 615596858 770318 43805483 538791726 951907779 365376160 263951216 312534923 183360926 429405750 374864078 123289313 95124432 299889950 39992994 33781141 75848034 791556146 557793661 657866557 653609803 216523444 589782953 4743650 883633947 566363228 160988467 548544558 119573371 520815005 989080287 587686595 521585323 32885763 126478315 326009461 250778289 242945897 491060751 434139215 672351647 865924829 409944894 619992445 18331138 449937888 653773586 94179173 94010394 64083606 604562096 747620197 280607050 194345042 604880213 16757357 760708270 765868681 565301915 732798007 139200045 406898561 320484595 513301734 292300690 299479276 839311195 543078979 542425173 182888305 829734561 67293180 48813127 239679448 687285625 67144266 689617337 193575571 13839805 783627731 257659177 618401901 383764287 538266228 665263309 988644500 555023585 278487938 607029540 120325493 11285938 746229585 379740420 184286899 112047678 672041110 483766176 951358874 67636448 26191342 134247172 897371009 93484522 35576666 137050451 633286514 102720932 679184154 826862085 969077110 315328244 937037628 439995370 699092531 327820215 105258672 540253390 882843800 383746610 147282924 855685659 247548914 746028875 87942438 431835813 858076554 759983548 915601989 661951787 827619997 941793332 648715325 724990999 887794220 684291991 714557816 521080727 639529289 246258329 200459171 461122758 414102939 137496793 901118128 113195463 317833374 6376793 505965220 53193534 242639769 653248144 908879193 490188683 251793378 996821632 922024497 109869925 609321539 690142845 771821712 436941529 484452536 273053397 14448888 372246750 957345388 581523070 745843843 449391037 827781400 946303015 910513795 94400698 936316174 664148283 60112528 106665907 523041442 566077748 159859441 765681212 71842251 68738628 108386254 323635629 918076626 882927117 433505555 379914524 573069956 57843626 816856054 57522485 330897023 683821308 282285601 140758771 265344371 28129438 442666174 945642137 826948819 205696328 40042829 615781352 869844611 100155357 722447259 392886047 666233105 882306701 11083618 738075356 803561695 119469872 61710978 574154680 854913356 347732899 954069204 280499671 258092892 623441617 190538522 588989915 159779284 472824124 582265052 425123656 353469928 24931219 223282152 32935106 230627548 263324981 501232824 100472152 215996704 76196442 345874565 882229809 958503143 209474549 472821524 614581197 181460788 387048869 41252236 36374137 587298134 847837807 316873808 845391026 323795783 507412330 286897301 483575068 832752820 869162353 908698724 38739107 894093573 131980869 71674213 977237487 247822217 572907037 930226005 463818921 649103480 128616930 198565090 460122982 338091479 523902980 927220546 519552267 910951849 968472782 555926404 350766343 668826948 725316578 196157362 992622732 85245268 483054663 476197793 917998088 204733376 237412876 956737196 98826942 221910111 28411402 928580795 322248694 453834806 858806793 786067616 955454652 987423723 837149072 268093993 178031562 361052045 195314532 697583829 124520254 16303674 106026593 475286597 685130622 831343171 523960325 530269713 916588439 7014982 6467499 834586521 64264724 96396741 643840076 15608032 170823219 524767844 944188827 493071913 978602650 655511979 131655888 786573661 495452062 968804960 54667648 673483624 182373365 102498546 371067446 306893619 118802220 477094039 634696582 656449209 160953570 158656900 186718915 77542002 18188248 45702781 764644889 82452972 142099522 408484958 98061004 165439107 933252803 42249824 658511021 764371812 550278170 790166909 403461833 45730225 758971863 458129481 719213849 941345228 560628027 942797661 100755206 531946614 272408060 735451788 188395816 433361630 746625054 227631097 510903632 764813303 273333878 128064881 699782641 267949767 536549839 797843646 433388874 322319001 692609836 91899888 939207180 95404365 734583164 342669006 141134590 346071386 653314853 712864805 139932973 66459239 655662460 240688179 598405853 928070520 828656333 786801669 213948509 575281380 14432760 724852141 192611042 140283004 852917022 892393684 260749137 241983221 542753689 694138012 416818588 87879884 638554266 356025761 183284250 225653789 551211133 176935206 571725175 204525979 889800012 711658148 270985219 397978831 952346327 869391072 178565710 633519019 508709101 392514219 61316759 375658227 117366353 253927801 368457597 822799742 998837851 629206735 917299329 394107899 175861106 334117910 481987784 814415372 542660038 517788400 40069155 93871164 694723606 464310696 150913510 584523611 175968838 421898729 982502442 980831531 143806160 13584511 614350544 505031627 406098730 675667303 880689854 375981450 782111470 101663811 51297551 780949315 730870546 968596880 27573573 906731652 155231149 509561357 573663383 697891187 27349750 466248904 791762352 574589723 930559601 942675862 11629693 106528432 217090950 994132136 939876329 213413476 7716640 406743232 718445104 266331737 82410528 451651317 642313187 717038365 553315128 693610738 350504039 284185667 662207611 378077612 43433678 817438760 887638970 617097062 367846307 767505086 83345959 12125018 194611168 13905553 954800880 206240862 972950358 24408189 52889357 765343047 237821665 60605997 172086272 956266769 179454100 107013167 260434446 821767287 824051532 813749574 515378018 27071930 97935235 30101988 405149542 141368913 700057115 145304871 610982341 67903415 912809958 694328301 80028433 107421119 560750220 887345679 166178347 386216938 911753868 219067704 4076344 2091892 132190068 176162616 810875028 311644168 135692149 71309467 133411449 959743681 885059041 501305833 986815611 835510642 531407822 244481513 829395922 83981296 389786384 292894622 151884711 155112701 987222923 84429510 115050187 400489503 971775189 281228534 639222807 736045416 500296239 643299151 738137308 632486307 819461767 401528695 944130475 955153917 472838162 77541917 767413957 210413563 431364117 606745928 898440571 962771939 851227441 580352852 46753228 93530184 873247475 51154305 248642886 712986757 135583815 363693073 113476253 107358997 644921607 605215426 695920779 145217839 248514570 286574446 777704146 920492704 688103142 574350981 728162980 13457663 504409264 348093296 223871226 935773381 954839224 122311791 751061679 658583024 555181009 650331273 752113209 428428477 701485578 756088 141415228 689585759 216965527 107407847 649461122 861887134 565139640 345381894 7104967 813654210 631956341 637325479 586663273 172575842 64192819 314826246 186033505 568602084 662919543 409904732 504375458 470275126 384732889 107953497 981374517 939913898 758284770 586004085 220858735 312286708 439276539 214790329 1872460 656242066 174714542 651333583 518129193 739854182 849231843 377750526 406024752 333704543 867592372 992688025 506280385 931785191 160030631 692313891 500387268 675466540 102218616 857279093 145741659 339467871 965232590 979632542 131898128 723517353 565636620 205273229 35804054 4913152 420063558 890192888 513671584 447294467 394042830 31800771 39665008 243274666 262067663 445689760 576979210 129660028 290894145 83259588 913961586 303441142 628089845 266865213 978907682 582824827 124144299 977165707 922292698 89376882 956798243 906707193 665410602 374951222 111980415 553731022 232380741 384560340 296440269 746052325 831854807 690483099 630369462 871519815 933757766 744953492 169725935 363253335 727129886 460620080 299029289 641091465 764061222 927119135 907956679 595485263 362460321 884617344 572650963 137269379 826510593 381965565 43976565 
344437554 609433154 8473346 898168576 841813895 393033686 47125205 440382579 224888486 737608304 923268408 96408295 523882429 668221893 118650596 887135764 247868138 579270676 38681413 888959604 195848257 818316914 649432642 791333520 180777228 386566345 216500842 318046607 213076931 450982774 214539538 557514485 60415921 223012885 308199421 754746182 616046571 355324626 47645120 840935058 92932923 970913528 789859719 469331719 491651780 908510315 208983842 739519919 340297350 247665255 480995882 388661973 65982162 130428517 32511852 99275757 369511228 249012694 269838730 582588160 699995468 484378269 992619011 612927755 707391154 153334791 367673930 323437718 508659417 415319051 16889135 454108707 238748938 659265220 923440426 730400719 420291894 132424261 469920631 760589244 232605883 950916513 1767576 151104411 933861396 34279428 102896534 155888983 283292123 372735265 738477143 835803957 857113534 583612514 448731706 564504681 736947305 668922002 740458765 98123082 84241046 757347901 552231789 175506351 269129480 328188574 905907070 689421375 313129201 228344060 302526978 398251450 31776932 304294555 549355862 965638328 338573983 652252396 121527304 621866106 24987654 712520814 310186423 734617554 148649687 758918129 151638594 885596992 280356490 892097360 983720074 217113903 501961620 388468222 392620254 771091100 716656796 298527317 460512468 882302364 526871377 763039447 280553807 558648309 67333995 682426035 376802996 258424344 187194791 350846666 880290451 64698811 915883846 42993233 799316366 64533526 801911362 950954960 950130519 82267845 843052313 786366952 151898114 197530292 174835168 544518368 968621393 744008330 843045685 281650220 626310687 222433421 44689660 759380861 633598096 964540028 441806889 10401085 75480732 629001680 213764118 955771183 693700492 129647957 998764416 345533217 46697850 653192137 296488170 849344735 587976348 992056850 635711680 739874463 189587135 663063214 136909190 10724887 407071538 979954876 292375108 885898591 54904656 189581134 645279445 688502753 6637522 939602701 551420204 82118254 421120740 617700688 37889430 114821225 599865012 889170212 312870808 646562862 394878708 609358979 348423956 835371422 453932188 984135636 427762244 643519323 499715210 564671435 654244211 906786748 397142670 946619319 645201698 452047326 136200446 142997503 993066445 142837968 82600197 397003009 77472588 503720937 14703690 115362018 471058529 614568702 857048596 783929337 113647923 104443663 245804675 462071879 939815086 699736863 298723875 220093689 195772546 798439085 784765124 702533123 557742192 181907787 501668801 55460249 486471480 490385613 198457752 479537918 485739948 281057949 876540927 563212536 637295253 743760984 531090921 108353775 210846045 240655876 744799478 324493969 345099540 843120520 639082214 137430985 395373742 937806089 357524674 591146288 588761533 142289792 146195770 999020091 176713945 647864571 54480334 663185425 138250178 252938086 995239710 623990126 386512402 724296996 39719021 23807648 468057973 570809942 984677796 678904019 811465819 581993633 855914354 9081718 425114146 494996561 146512703 820487889 285319010 356553743 264150536 726596909 351359901 410346307 725616994 528073847 58210871 632613694 43775631 48977415 885551780 39015334 525483907 124580541 615828697 565202929 148388189 83886663 136012864 133065978 615307048 947478683 567575978 323737761 956560401 992690124 818734323 955589470 665694372 956569699 312143207 782361275 683166601 663503108 45223941 261299954 44093314 103434812 893913648 87868946 4928594 631981788 979400653 530412501 756562329 447745709 95615423 757466885 384148739 84144654 743049229 999455787 884139703 310625200 175709908 693216464 155831684 994444231 648805927 674042422 803530289 813465500 456403690 339213249 329484968 501627631 600513204 373578282 457578810 346943211 313963594 315023770 831441365 145880607 845436271 440520054 593626316 793568061 197986932 977775055 730229081 941036161 829747202 614368777 104177721 5457103 160101600 112525771 852417700 808907528 786568193 508464348 474889387 95488243 847677597 804374355 597115874 300707160 30468997 907211050 647650372 344432591 222234813 331608096 342829564 920187451 772128150 936455881 566271871 970115082 766747295 296500945 763667603 449010856 763386088 720361690 306984325 923487689 832887461 11918384 584911576 619455647 520382732 59800956 714943890 220576689 864175312 164576124 521283849 894644309 71787167 21450580 91593259 146538347 353058677 434422824 66725791 125186820 223395064 485514028 947818269 842658725 782014973 564002231 144185941 397917420 284363914 451170266 321405102 117251368 315605017 906316678 589223381 835987749 818634001 156683631 56564431 535325672 173776121 430364647 282486340 98079654 451815227 374079599 244618001 804873904 661018789 163860158 930060725 884413853 649374186 730395353 579588938 283905518 294397577 723774879 681822939 431277857 27461504 855744407 401045591 343066521 614577445 990268972 31570630 433211439 999468969 88135061 968537111 173245083 371016074 103539810 271324738 822831302 477619409 368459105 627705199 138638192 532319264 410282283 875568411 34209809 140677629 307673708 170631694 287591572 31448580 852454633 718869429 58910085 560715399 119915013 401976606 175292837 962700352 433547236 461020642 814685680 374198664 282074112 987930764 745214738 385613922 111771861 420562399 863233332 480230966 48267592 854387890 865066596 311066241 582472660 899276406 304260237 890146369 69908093 444368175 774111315 774879092 15753964 833021400 188110850 135668977 87514366 363403688 950885695 373577968 824424330 618087735 747776632 106498436 458534858 345507730 344628724 570306719 766070129 60378415 903054051 666854087 914766305 768120641 830436695 349755325 519913406 134696925 92418053 442337865 431581466 866529368 69733316 447335430 552067128 257844166 435520774 492097860 473764220 238922828 865675828 150704910 857010563 465968820 109719712 315545414 811476550 454348436 738368499 430063038 514726852 641422544 949433492 282009516 262059544 779870180 631764841 634489316 767083471 576699260 76827174 51181296 295744988 999076863 498516727 847812116 109437388 934037501 192426335 583201609 172960322 58102156 733906519 29970879 524070976 843626231 198032659 188063885 297974660 936401159 470643290 812701512 430340062 420076775 94711022 544915972 52463314 578992229 179405281 672063151 8207849 108748821 723244447 303952837 107825677 221761167 4281312 69779431 8315027 196707647 652981040 181275350 254809803 386887552 63762595 631397146 83030142 114311620 819461031 381004803 50712772 142620680 46222674 333569200 562697455 993450069 878485172 467677135 424958658 910406819 139740279 433166507 19155633 862984727 737119344 979497683 937262260 741400656 49277108 945577288 938108303 554774514 126852631 45434465 941662067 43131592 676831611 24692202 157443212 348809002 258213371 60672351 491429682 156952412 246757917 54127131 150402474 125243083 374320632 575361132 888166268 514060912 8527632 759838268 229561998 598163342 591852310 19340617 339563991 493645784 964917905 130188653 48420292 944286902 175623119 842598725 987418494 852454730 719807293 997378073 201263725 978020665 58050417 692693408 134973070 157324700 599336905 137891910 135084149 973657537 565769409 23250411 340234808 426813407 783088679 422313172 24976743 227457348 441653790 217057100 721103133 406571688 347245754 769523425 203374950 522868873 464638509 43309803 375323596 184445795 40687869 429103688 14982819 951254659 121797089 2472255 108579353 573650360 140364166 243663502 399824256 558649941 119430279 592575431 985463348 902518958 14888596 10440084 129976300 456542386 80013551 703595799 715630441 427259305 325635583 919005391 950128178 790274092 962315194 177968133 974719887 3003057 607071821 842219073 806774082 581385276 844691328 915353435 7551995 837571860 11533297 407376252 248738160 130963576 999951683 234201502 885998901 867356645 97157952 868491567 176415391 177171503 572087359 892045832 604430808 897722942 811051216 407075345 540513393 625882769 585043479 367749639 481402192 192115293 209968705 288176268 773500570 907176400 56046062 781052565 597264619 67579359 40945176 846002780 51059302 893413225 80204275 937058203 760769864 29878593 658066129 937185255 59566463 82669847 681747446 663997271 980392789 345315021 71072610 373422541 971197790 508632455 741172180 452599976 700747748 951140886 593292610 326764677 710833645 649338672 960333609 308098257 569434398 1278778 6617396 473010066 747208370 86821671 262584628 360494593 969216638 920650757 150196207 28783094 3320597 831943653 545296731 836229752 177258667 468885707 209652286 972816 977518162 950824466 453572792 530782270 754481711 46865395 857546947 317831715 548720434 670396915 625929973 970671198 524192060 632547369 443681257 271400423 571885407 706265885 631895016 393618404 479433001 782091223 422401498 482753598 466551235 967698229 171499709 643809902 289100296 381151995 644782718 266618451 184492820 950871877 797400721 791490898 850253638 507464028 109322606 251490431 30377302 587768945 222161622 554569362 72832674 518359245 825969785 644718081 77141489 310381160 38336478 556574490 944988749 313254342 39328081 411539977 133468930 63344156 907866245 422569226 444496151 405165323 541704044 481505338 356037193 191621124 272996229 58807190 699085152 234835201 310297622 729462455 822604147 532459244 136548176 895436821 50818483 962517962 392671261 127959972 125415481 283524105 537050829 70404224 596778447 428895276 334460567 582763743 492239433 94843172 5332963 936735584 500008495 399553373 270757281 856045688 591174497 543753510 914852878 142776009 778588712 77666859 872238464 453709218 610126104 8786633 349146032 513460953 823820961 741817293 493937291 801752809 25341391 30988113 724673399 474636204 312399756 59133959 57399940 804639189 6493497 915249276 593891132 506501992 167319008 864648414 215064039 758493506 260918283 129916911 901269515 39506988 60100136 626024338 345732572 670226240 487327337 694878604 36203552 163664658 289212256 382657210 965417467 167070013 266161689 690090859 494222583 578561445 601741184 404138890 383200627 608234682 171904525 977091760 114736667 339223534 694256533 182317073 97717033 955174816 164750350 998986548 847198171 224850486 477527245 192930736 895076727 964854582 740325707 783796645 128519233 29537956 166453848 93936693 49124336 432615538 636543918 543346919 11176976 90801462 947485809 246893970 551552510 119390328 76502089 518805543 311130228 770758622 701122616 408847261 578449797 865872966 260350168 425647961 90723446 737877413 471095064 838316539 555248354 211420764 622113177 683767588 93475086 641083392 630220647 142599422 73698923 119280925 538462708 937392272 62598753 338464876 36802601 614151263 310371570 113304690 132956799 621501798 736579678 834079416 882865425 167545835 552468741 143215586 593193796 643192187 733609365 64288853 334025085 141374079 128225983 956138263 825141667 74217436 449738014 307878673 69333224 375953303 279675964 607795932 165861934 342274717 798777175 202664536 956425980 109148738 168485592 89382773 583166903 757581637 775978555 318548687 925127472 180963655 314280640 370837627 824155843 47889998 287642847 10697287 41780443 415868830 966835550 866922110 490086266 269089923 27317143 559419491 645043226 306993107 19731782 810905161 649267825 818508957 13569690 458210164 780174062 34571648 400109303 215857324 792153285 28604217 534406011 569797116 209567873 848686651 940634744 33723709 749093016 228277584 44420996 790873459 496662780 863772913 510311929 986749047 132862829 390145438 398684897 630422422 697138545 270933045 441327576 198922729 89441996 307413632 657132894 722132424 194501646 57242190 790506114 986654932 85846408 177428484 408968407 147930647 26115129 349603144 34170722 627724511 430397094 78591718 271114329 927059875 794880997 633942624 766325281 780260193 24088055 17526537 263198974 573742967 288459582 704526550 772665696 230417944 864456548 282314949 952550368 58958187 192073506 595572841 898129485 130436280 773001326 307097886 278366927 651632821 509217396 312537649 131873691 939614491 243645733 402988020 866674359 891043097 36930638 485515999 523819649 913535066 503042536 787018623 487278026 791502118 344061532 112460082 21920056 208518073 247291397 826986790 119992626 439364903 422559625 18122105 422317549 48077310 177736357 700684476 699710131 686953753 865738491 831583822 626568237 109384218 87088201 345758955 852943681 124018839 831274954 376763323 890070272 186833849 16298305 229864657 978335968 360359837 342324739 256017 568877910 589616137 679759173 688870536 881497406 102318791 559509007 303814949 2912467 737245364 857015791 702622598 424199111 722754276 534206413 903283714 684654860 621294615 101559029 390114900 597829820 932833983 766878223 340416451 119667826 783176528 570281109 950520160 143536358 912605848 803292543 564930634 354738344 483051709 106317529 88752110 437886867 665826537 392567059 440799334 255588260 102099209 143421926 679787371 824853485 530144705 435587445 362024704 3955679 537146474 752139604 454301866 322496816 371534186 794718317 294681008 7227073 364999419 245201161 3279797 130121627 48493697 420726797 337376337 384061773 527044327 426128447 674465006 45387223 818695506 115264333 300975483 920794716 111202625 833279221 598164560 493863697 268866659 812705631 350335742 806013133 417361594 804637608 128509942 788895781 599355919 275707317 648639220 816871704 520908478 651919018 946993331 421918542 72645808 136886028 658496681 452206501 563014475 332961680 350110090 234226341 300742379 651085574 7537416 264461371 336881154 605701976 610841434 605747813 270923966 961177176 264277305 688285561 765814778 245303613 329697701 217687056 521010930 978336921 34558753 894435775 482772298 834068451 168870676 407934473 970954479 827367357 860140974 386485313 12845396 62767424 620711654 313587775 713852998 628249070 430565512 50734145 86467406 41406939 508998324 357391372 2584109 625791995 45676926 620915253 871095608 375374627 691118675 244622898 206227908 578193794 139058666 689000206 264778604 160445708 96934672 88249442 987813065 809592013 474734756 658454 872359437 95446403 166762595 438728794 723695474 597328108 341979305 810162880 638735047 850977629 20070611 493835522 329285983 65747538 967267141 52897950 293638531 658385809 297520848 499866439 89095963 289095880 188866639 353874567 449541588 138317677 442124010 289871012 947909690 916858766 290529466 820269120 12305162 457292062 111514273 588517002 54620163 453493578 251196241 545871576 156987566 271266853 892223465 486273549 189530757 859490599 539171500 483169288 370392768 836692348 983035728 459488731 978304595 24418726 813363298 280362542 162736403 108003667 570233555 110646087 24862426 860763021 783431573 889683962 170571442 894945847 330717323 77707971 348439418 581913565 476095914 505426985 705696784 368319372 991700534 895227541 80326330 383388393 378396822 303235464 72597101 213948909 762724195 50901689 238367635 428603853 331264231 401104039 536607520 901497786 511750126 413986313 614777167 147698058 303670268 637864975 42643898 634387591 715572947 243599683 68817515 44185220 749026668 774514299 412504592 593243561 522258199 345347288 976631955 900655022 648582753 49229049 114603924 263823307 952647111 205487926 692427160 136427701 606591965 81551040 37925481 118342084 495537353 505219014 118556508 651723987 143083982 161200407 138627937 711173295 404800090 207445453 755358515 6343117 834476118 20379466 452103044 356734311 365726755 281251358 109905692 14309501 182996773 77025982 130649174 135643877 282513908 823076335 272071579 889105873 757143741 162513426 859964323 105197453 520248806 978520832 756921440 515849154 992237605 895549377 79538809 249554054 102994823 834897324 255897171 789987308 707793157 708000215 146721612 73519905 989251574 109143670 940345779 24764706 38686018 70994946 160408584 321199927 746587647 284996529 62822159 356247747 447509955 775302849 461445200 967758761 606340040 218366633 336124274 598577638 113916004 415663083 848131692 69427193 103076767 956545229 711930867 810869924 517061803 711168845 736906195 358829736 820312515 529768333 383594443 858998534 453279645 544003027 32714820 52383652 828999556 95536979 408631399 129025870 723356194 870076600 949300997 329696227 88443226 285425264 780790231 54875596 701088348 481438282 976819163 804165115 437983504 541266389 467551398 955045308 252435228 204457586 166391403 925264109 734225919 549985846 636779002 40021923 93988866 669493822 92405575 775504788 617547168 501036975 757047024 193419721 371113568 706348014 523115949 312073160 844289645 156422539 219465123 397894352 637860822 48800645 54575826 75844319 590067034 522127224 883405993 695018628 726584810 49797390 620282731 313327088 452299602 109578092 353349011 398804835 779071915 445754587 26825982 249135442 946791562 783873007 442555163 170421489 342737380 818187478 335011015 187027018 974610018 554476138 584921370 612470833 455793149 639497196 540831518 45860177 14140779 276753871 593395171 740725589 179067627 66194261 906569043 631367229 175772354 112434414 30172057 954844269 558189001 56998040 56496070 357496922 693387413 351567599 380434777 36124786 169755071 715445792 75668171 144365082 122438290 660589541 609352281 578231439 152603097 2700158 476607982 166743876 131970395 70003147 759985832 311038022 136197408 666554868 794921618 311969762 778989282 677610041 119330390 189694642 587124447 28342826 399707930 280511853 379910426 780142707 169153006 549665497 495588493 244821177 546546945 618026783 905410718 8415585 48774581 910530181 11115743 525382564 77274051 143086139 595385711 689776249 306640527 584099485 208847476 101562138 896069248 987836759 631688546 867916004 30047760 218812986 896258831 429755691 351841206 276169250 62414757 520994212 678351113 558003250 765815389 77414417 28546392 523742466 85830002 77320974 434272641 949462118 602703538 364063058 945064623 50605608 53839300 104221510 634705093 115203142 58300014 383290700 103039894 689988560 103723064 985604028 908801547 999981895 267876078 113159112 128667504 330290835 634153324 807018617 888294086 399968706 884433034 769356844 923711172 970263036 846677818 210500172 772241513 301897715 427079596 717306130 205019689 333435262 821527640 839724783 448638405 879827654 75531842 404194665 422332574 179254906 389798686 183650480 31753160 657674764 296809592 160420664 987965600 930962916 967439281 728776045 183447981 851872308 350649248 107159146 674651703 49843426 170175685 299409576 351741141 597255281 16715699 556760831 930690544 690759705 249001973 231845308 423103718 177050181 636039973 845436292 356305088 25838653 29086765 388058248 536029783 178412723 548478913 376511742 109375632 368434553 957804153 292823613 72823221 308453395 252499126 747474924 358296821 275191177 46884493 562554328 872446458 916116565 119315152 655653361 459392629 220833491 887498669 735012714 397883673 376055002 432965365 606705127 254410021 314568497 994763375 790439804 492981220 395758647 19467906 602356853 764193201 977272059 747696832 837016422 138241813 195951 437007705 349055000 127903494 336408565 911609329 349946 105041489 883440847 508519673 416950485 104274332 248534702 151963192 354674371 624589704 584928557 961379498 878999725 899497054 808659232 521955888 244994634 56934239 393940160 847351487 673643806 223728579 447564678 363176587 361970392 300276996 800184292 711025393 428180490 989109223 475151081 281046802 94150706 358591921 789566476 363617557 315382619 890617544 515580749 522573356 367723607 953025672 336469213 99239691 705039086 145128439 621195579 950033720 54579044 15135733 649901566 728222850 91380678 97466237 91399430 453351070 397743233 744100088 16892822 825923724 585725671 492043903 106970519 532392743 703152191 749053361 896010300 18534803 492187264 264107408 393624526 859910871 217133073 730093739 959150562 922172159 727738544 432862501 724722238 782317588 300514600 374623797 363056797 391895278 324606401 306972593 845246348 722349634 903589048 714655537 400789717 489314712 59215799 360276603 21707448 762367990 961846330 770234114 633419160 454033588 34341515 27043679 166460818 103990954 757137418 125611374 26163107 337392322 558473875 603401711 119709903 858988475 978025509 335283067 103400112 155148269 494772026 948646460 877497903 398361067 515818356 130803980 740192145 575034156 343596949 614415959 337402139 305443272 384650066 970821299 611993226 271507947 850381344 778454045 375498902 460035122 904065419 254178375 797427444 315055653 857580086 769653713 26560487 688121954 104936773 129960599 843270223 452225166 931123425 573284486 850586233 446941775 704088466 443294738 21975924 47685408 57710690 211894429 205645046 294877123 35232088 817638273 566385070 885613432 448608677 941883972 198164913 205190455 196062340 995592357 520246108 53642420 765246064 399322961 594280740 722699203 529283560 437550957 27440728 312923344 10835436 878026962 759865119 567440268 173838059 634357409 467642042 231548749 698768205 525803454 526425872 734000293 195958086 92810936 472130084 644566763 887211274 670294998 849757218 83273608 518403714 222519685 989432401 136166137 621842646 436229500 858865341 3642565 873780457 886306069 316565910 737132259 616849390 76431022 157088886 790687449 563304798 477247294 874752565 114589362 3050742 253694796 848589655 199008828 199022098 173236098 843575592 86233366 696047462 545849169 22023340 214451170 768368855 863972107 350617307 390211494 300201600 61999007 393854060 26498417 800821443 710419970 616147042 270187192 639367358 773235929 60874635 55188515 102999582 788143566 169777877 106050324 41838355 870883898 157575519 240860454 44119990 1151104 179610186 592683818 399516639 201633526 807134988 167885487 65605626 10268655 410613348 218323592 72267662 804467408 97338375 725605471 367403737 713485418 995792664 859287461 339237706 909183665 914475977 442237288 697327224 936770220 548287613 591681945 807654112 705863132 832542399 704290468 559530602 12152578 149490645 959047241 66302470 956625634 979449095 984424469 819410655 390062436 55264421 744194683 47046203 152602796 469800148 266966306 866088214 318109171 126253760 205325913 227292829 893246103 647563202 777136419 830016317 48367174 368818357 490186788 606746672 53877116 46993615 18793633 918546067 196484260 977840874 984848538 5626253 809806328 821789366 825036908 52385123 877053787 421747951 99431326 29656577 891548099 366397632 895744791 62173629 345167759 953587071 289466458 238413855 453666632 66602870 920946538 502033806 287937593 263649685 108780471 194331075 310643300 127574104 112877136 359643927 957931344 950242040 365270180 620254032 772031399 42823448 672639155 501601546 464571399 772070482 531258123 208635857 990984480 279519273 270809486 336152232 85622703 412792310 427082454 539289335 331911546 348028985 41323134 619849139 611678671 2619971 814180215 774838337 982710448 779573717 134482257 793158152 729815750 352268804 265928543 354363508 395092252 938567698 855965054 712180017 563154539 239739536 920815874 554139013 371775176 44141719 742807611 457397879 456934029 169890058 996687215 788845575 370435410 890526715 261211073 982114081 745663053 927907654 609468777 580889860 707481364 743951035 226564371 289813473 96219832 492492914 496693348 343828450 431060606 205174761 56008460 994215145 444914298 829340700 400870517 816689474 725998785 143678122 126603712 35449173 166084546 123290920 824294748 536519956 13817629 938022187 371150396 611997048 865929835 980619174 192886901 425927558 577086568 419451273 568257398 525822766 911944187 64950739 722167582 195521152 270125500 630692408 42252657 567556164 312549467 295639540 236761997 38548245 291834028 363365710 73997418 457918575 486656630 750808532 846954897 352990625 688830712 70621653 964987673 407276906 51240820 10390934 685720831 480843754 282358573 253978222 859182886 46819119 171445327 581350461 242340272 441570827 64559228 137109295 9126985 377108695 432748835 98405348 415656940 724582864 461771058 342170724 35017798 948427689 92979249 881972695 153934673 634326327 952594348 971438713 41603227 856351534 981829647 579840424 189711647 116704579 833818646 48894526 163523698 5263966 482761353 405863970 299351159 547320581 542973265 160994510 924429276 975722101 259399859 192602575 552821324 721170917 534773299 587839122 522114965 627752548 469811810 528566005 114595235 274922518 500004711 8714828 131274045 334350717 588555252 320985693 451055296 274890257 222396585 614578994 132670589 705157939 872959331 432021748 252478513 268448955 445532625 29424149 96687415 704932484 222026724 649508739 278619760 756800024 237347854 653251092 237068931 559676031 181817090 351664166 834598549 534338167 360378994 965872594 868688884 948934246 139374646 172260539 223824496 361771232 639355899 356495085 66929164 512315223 641033200 171924043 780764179 86565818 201348192 877451594 644014668 423374917 379476693 922634428 32691300 616824547 428401879 269760231 29016937 610218969 621424398 863615486 144557129 981803392 682004440 865762379 930737632 821379086 890539284 7078487 35666677 529895177 216089939 955112214 894726766 857123139 127036251 528007304 943688957 180900809 257975258 440219984 456792092 637451951 215370771 489483392 106792857 643772651 759243624 135809795 106507979 380668015 999425281 103581475 214987766 681429714 969343854 145725391 355325160 712399498 5320245 243508203 94811034 221410184 198620411 989537800 78533316 178173028 517545098 874738639 211590203 775520356 167474982 668382296 265488666 382845753 157865681 372281523 26618397 917109305 508091318 133126377 150293679 507516593 236707852 365281446 41462666 58568065 363523203 249304192 770967563 221359814 492812396 865778597 442769998 691432807 707832757 373819680 722122201 77894214 101074678 933712404 853414570 268549660 602094693 118903229 651395414 612476741 343701118 530530177 382102405 851792437 663656554 532396085 211825389 752880772 750193897 253288055 811448838 113717093 502592248 434932760 187593274 995404644 153227717 630363272 539353810 861060474 856699319 113992370 938954688 957773997 47704767 644885617 78840017 502315827 616305212 582751797 114792561 960006330 113281967 496894966 664315126 629454888 881807417 876140515 382335653 632001307 129428564 46300850 598234767 484537178 333749977 785828041 332458181 486977694 268707672 724328357 200554527 125406984 838320727 992025581 935697348 886025494 489427557 867053731 240857680 105732762 449805521 355650241 918255458 415603854 705061574 435086944 45058735 586868984 311227452 279910755 71386651 293172382 326211605 522137784 630225926 659961582 160482184 962684107 999455642 429189856 539528823 52526528 407113207 377849543 44552102 195326914 116391397 533979659 62380638 357249077 492228787 364702525 565415685 263000605 780306379 270477252 698087549 677881481 709862602 861831367 957792236 781249253 7520109 136520200 155903396 637746035 796481783 316385580 452946502 648453784 745575437 992475325 700980313 5205003 222841228 745532415 53048283 339232625 132028434 115428921 548998068 476773587 332647812 114413746 739774192 965470557 237407364 290378100 643352031 947269967 4725827 453660626 581035579 12245936 590180827 736938976 649991971 239178969 53324549 102938466 887632753 651416352 95413785 588613059 656621355 170771379 186661834 709669638 510004004 171206634 677614925 59002065 647980221 862779103 25932178 240270773 828249654 263339542 530648873 324118044 63125868 535374700 777778671 644161448 547620636 220475857 381100417 50128967 459654826 286941332 153067433 347287572 938357685 100997584 788416998 447495399 271768963 975078832 9681397 634289333 146285459 687296322 545807765 646782046 402591785 571739943 887052819 83357798 687595851 270218052 407475842 750721720 805592752 37770872 394883161 205729748 258246729 628499944 255858715 717901555 915441276 261442514 917705494 853798954 362440099 706122485 153810713 486725428 533717676 163492110 121014755 532519501 850788432 666822520 31817906 105896576 91078822 918870726 189254374 778674673 189088771 596730217 381912752 847197889 487017455 776795913 52927630 745264185 257812216 161302711 315682099 173253486 422745226 85903952 879568806 637701691 792026437 33379512 124427112 178260472 196871622 97958233 563296339 900176421 764780753 595114246 6072990 708375941 513984965 195327365 339566974 555590102 644573948 721479726 402787984 131591396 350791999 308231981 729371947 608604215 322051058 45054040 781857701 744796284 130957992 513942867 235014334 775500796 547322379 359441447 806277634 596710368 457399680 369573967 496886782 74696793 964688213 355476138 783072734 331189537 550803503 122639701 886779639 47893810 696635794 142083982 179485207 47427786 302832329 908857154 656032001 624883388 806427560 290406062 222196031 789901919 804348929 457210366 417919074 204187667 816651813 76713067 800898035 126567852 446287034 150301176 53781011 263491606 505777315 836853746 447197509 909097184 812009813 186493507 956990995 361161966 328577490 136476195 408589752 631409819 897849715 917138120 108809566 556793635 60060541 331005598 199211913 864409470 788215964 469647353 921113503 457384136 546360420 574527898 583951988 992647455 724829074 637733000 108655420 83122748 327103105 555852930 992219933 991629284 742346437 801727287 352791244 923440293 790719848 613897362 407366472 541085922 531035475 516176038 97879550 591096016 847181636 149607829 308021845 635397593 619255182 81651708 92781722 18131962 656179606 529250077 10779410 233525039 19499436 971951203 316647788 199118907 380320492 161384080 190748184 122666923 963111367 396055794 898623582 606347574 9953150 305990047 147433489 393504991 822166086 97829406 984601008 521864081 99953601 145139212 9778034 719208784 226790920 102559756 737340746 882970526 484326199 600636522 116495559 356342001 425104084 285659713 555460908 805424577 299560159 746209093 780607866 115187885 142264880 679231441 721535459 4734396 837737855 868968948 398239388 512420300 819314720 235356755 34284374 919268322 233012333 44062408 490993465 459803254 999138538 80850570 195290139 335981096 681487092 164302064 692323098 106591169 302478143 247783999 764532112 602038302 846509458 545139971 717226187 841290705 76887772 438761639 846025101 914625627 160246947 96780848 279562286 979561667 184653969 313846660 751346348 417666303 210425435 242339806 877469557 209563966 323190376 925276062 545545062 857193834 89578120 90384519 816301370 244572629 338168519 580833475 846610932 37194336 978489813 563837112 878485041 55377578 855115118 577026502 822519571 15362058 673807350 102081850 847440091 858461320 268444876 451302799 128643982 478870311 693642605 6113532 540950643 869349348 783905960 86495699 726543175 726000446 29396584 395360904 970573076 367565103 976194380 817184001 404759440 807200552 233537472 135760840 715094496 88652583 712787342 390130426 956531014 239111052 344728642 656487465 97572365 613173518 107790257 78732713 944560196 653949228 84846245 485510832 375814935 721268571 424522897 102358104 447269011 453919482 350235374 270358446 674000951 178946113 87542440 78760384 986146665 173596278 67037591 701241154 114765228 779824933 91371573 923812608 18935978 288616581 432816432 969024716 901790100 393123055 47757422 698866655 47072277 985120040 36893846 275403578 706388605 461416744 230278048 6173975 767852592 580513423 276532421 441853536 759459536 216591227 373130287 745606195 242703871 440167878 299363708 357469099 72509170 243251648 133798067 91445149 531868229 566614499 60469858 286174688 959737555 960743654 985041343 859326198 945863687 21935183 134729769 504768651 335868293 365007818 363458992 103720878 945521241 639991413 398090780 557497136 709099006 623737433 155619690 951802878 63905304 454983399 161788336 136414475 550751413 295586403 80375990 82619635 862200903 993362221 221310690 821938451 954105868 58868392 533781008 752485915 933319948 668510777 109770925 121704600 886034961 473229918 77941844 684072561 965737697 476032625 241569691 674836697 99770051 397189381 479155934 16191722 704689146 640944270 5122563 255440552 936530674 938014926 190576554 798731570 931377140 264403610 473186380 737999368 323272002 6967381 343001642 109108310 527994524 305288933 230812910 266545845 778518851 308754755 950618406 596772908 784787380 44704456 124125964 737073797 441893838 603281898 605781885 146582977 244226161 463420814 254539896 33273194 253952099 297632816 832004764 37845599 562036426 157707503 775844967 885308428 17191250 971362975 994416738 397702141 276651901 77746008 664247986 907687119 386500763 614866385 504460020 23804502 659570842 628585984 760878299 953981046 84384241 219176544 953080389 328610402 535113724 60136644 361883597 789065824 357769460 46404720 826911423 919805886 56628590 455272749 657630674 73819840 426635717 504563771 471521981 555803984 582309779 135769960 463491096 968810542 603152712 820467482 992615044 115239913 301569825 606009703 69220952 385954066 825186247 874817707 714564469 212816330 934954352 928964432 1882147 292723805 975369152 828793570 65046051 31997735 136582678 722676725 958333949 563218395 227240489 282372289 119022373 809550269 270658616 435029835 630877170 873811328 108013677 623492208 841567607 409583502 82018270 763304925 795537569 907204517 638122625 362618397 120020840 425593336 291582822 974419361 718317142 119468333 655729290 783363193 3982435 792311969 358556277 962316384 208046723 585796766 97205032 179585462 247863394 367863648 614615298 878740565 94191335 722628975 354749132 935758942 132212470 436767402 699063860 780266405 196488278 189702845 142884795 169025484 615296181 286983983 143444838 186129682 406452317 651690495 822009241 262951118 444002457 180565511 77783861 652049180 618878644 174988893 831634643 866742038 542852542 298766300 597998962 637043877 873911641 805264460 572802813 858640477 94548221 124383032 638906876 291036499 166602243 634308037 312578350 781898425 921292021 308539554 820544473 180260697 960230049 642553708 443211815 256748865 675635585 520995676 908798046 294514222 695984569 592949048 13772620 238837104 744231714 464287948 875880982 618143348 269552402 301200154 329300184 364100623 278099552 968207060 507653489 444701796 455031457 820231839 79116580 376323471 128771386 899661053 556584168 89001429 394731120 999795983 198266660 70366699 373308018 107064699 217397287 69292580 552530113 231169907 160646051 149278186 695457856 36527026 767421534 817526624 190243546 96721712 34143606 468343098 917445138 541797095 913044894 224992954 362028927 992161474 601316425 343316680 744338887 10416952 284834475 139070000 862729301 483101135 61953065 236037312 442682201 279350353 157846259 995212314 510520260 318492310 144490494 58494475 207535702 764428394 876021099 397779248 713666472 910164706 718638712 483627970 304478160 484199966 708620924 666507088 328877799 162453709 9823761 73216679 25387027 147174602 64803046 888116329 630275737 126756111 124153634 72957931 406106464 134516259 920686612 916626725 453008569 917693472 827637566 660544271 534638225 556175025 58323512 100821057 318856090 629478591 584449027 623334250 113678550 145586310 142357697 442556349 160556385 4697824 368289395 185943413 151872426 433092441 74059735 782148164 559848552 50729735 855106095 965955017 185245995 628309066 735098101 638254564 546002531 562735660 151315195 80640750 118910678 62155073 33978173 290283134 691633664 618427200 913617385 805312214 616529876 55975075 100384923 777086262 60672900 468674318 963029675 212545326 901766759 37089403 994693490 314131670 940335511 702315945 280086680 125581499 183141370 15184774 616352430 729143902 430436801 767667625 662301018 401863845 829822698 696279191 692146980 373972722 167222750 458280724 31801295 783752626 514255799 132186218 413355247 427445065 453376902 376384915 639990392 207660020 265990684 487200241 521791691 58842555 42032545 801878371 36940420 225173916 669579512 653292850 806834184 952532679 273476834 321651561 206912883 955815899 17930745 899059863 329788614 37669861 209856946 361589909 673938853 724112746 346292494 87294094 4074170 799669396 316195375 644064562 7329410 582186060 983781170 529121101 641028615 25813708 183515831 677969035 103503990 705611709 183778245 910338174 658144381 309771445 84506094 865057265 265587337 102436839 616633487 447892317 992623073 826490434 809482227 666561920 403119539 8291080 606372380 407193709 807960476 922567755 903774638 815289886 357270174 887555801 196927346 998298789 765885875 232959544 528784184 721906232 938571253 565078795 484760765 449231994 874850240 569266860 166805618 140437571 524220065 783439105 440846254 516843132 462445898 102844840 35921411 718081803 111135920 642293791 125275506 919096397 417377905 881566510 586902642 774648080 621638670 783829989 625463228 240040904 16789526 6763771 961947136 807877145 571842566 446707895 257109132 446692800 15974748 423914750 439646737 392711179 59870215 880492991 909554311 374832479 983337832 797992088 92914276 94473745 292802238 70706148 866086508 710180144 952272658 452989144 484828217 426427687 89335492 110291438 666468591 958641391 117055210 628415721 766518529 541414142 927639982 876144028 988106942 796131096 152575137 280270038 188842268 212445352 13279389 950912946 587277832 849133587 748905027 532708474 796123698 41707259 603414622 662210200 604403769 408203639 967715710 89231979 834631326 57051195 52039783 353616276 868208952 21611359 982031997 487243840 415541868 762188338 363387861 256165169 558319427 515962999 536435208 599678062 580924717 402230963 550591001 20718908 251364543 152012387 553427382 47488234 46236012 9358363 562214800 650639781 417562002 382446869 592388126 104709687 292014430 496944276 458325964 160223375 371072001 292874320 647467216 786613869 55062652 863371443 42779032 465898445 231850801 431730606 65576500 812775519 833961569 468683867 833494427 937842478 473212621 386921803 837847078 519448633 396280166 252578238 22604774 666358535 635025107 467509266 771068222 927039538 964453542 81910545 87262906 188041903 227301232 587246488 827172138 134880250 303134291 722467536 600778695 534985092 6714501 518871562 347760604 840676070 840071795 33771391 631034907 313284409 420693194 468881979 685249409 669489726 721460217 707854183 335848254 209001683 27879808 959432843 136041214 992333351 41343381 75820487 32891613 121160979 515583341 860063751 256041229 818717632 435047647 856819925 353702718 441762148 228207846 553979688 134954578 68279634 587751079 765989485 234080410 8444266 87387823 919329819 530450359 808848040 479700361 866298613 17849717 507580169 678247815 6407297 352429879 572107563 82227784 237837858 693268542 450327492 97901603 949309772 269045117 385465616 658646056 475264201 827227764 886853902 29243883 962182342 807649902 616994962 728171821 894246678 477955595 815559644 666092856 8405947 476924044 145793210 727220926 347290127 505889746 257985101 206213790 710835991 830092664 140957941 948673850 523361199 591285433 899091819 325187330 860330550 284557428 983833386 188111111 111785185 723203647 217354994 926483894 383369909 686866322 507172074 277616580 17338276 175248077 943709437 25744223 652172121 942019013 605481516 851978614 300425118 863466617 58192398 11261103 546075640 199150339 812451319 69436832 790435772 711543131 247140529 503282681 848616925 230973908 691393792 812918476 954177556 761265152 739402363 190063824 448131468 99090796 467680404 465469744 274338874 263906200 343730334 926510995 58441573 801728216 631005969 211383057 517711192 689198367 75160526 63786825 740865072 887611845 985740030 383817203 451671335 232880552 887099884 300288253 316370827 431010036 113206723 123064742 44791547 705125452 313128566 492923015 804216249 780808970 810909126 78555116 897231537 7155819 857582477 955673110 808884035 341104805 19572526 326595220 30303165 94733053 242898411 623684603 982344898 228638434 7501799 434016227 314035353 747118050 586820846 630406180 30644445 552543935 753470922 75435992 110185747 66599481 568359008 914401996 699924817 231784493 845473478 597156347 238940312 555572314 405345816 47824340 896677120 424918343 226935926 779496651 519651396 469834337 255697614 354512653 698472771 263199413 788528880 12508117 10317456 227866086 495430663 40961901 780410021 248901578 116397894 890595768 168017425 537273268 657514123 867942243 769057761 355503960 317614949 7998066 911076275 722960766 908338779 660269754 395468 135274698 292282764 372563230 605109035 547980378 727075883 156098165 663696158 368121123 21122649 526529980 595987209 516553312 420008248 376397223 617971257 388922508 119509351 785988682 926195776 777023474 653930918 547769896 132527428 971545868 408284328 896120069 547022993 169139466 408906182 399934827 304414164 701188946 772498057 762039565 101685684 499573933 918137730 765381842 867695056 791776745 144428181 316198624 160846417 564436429 692595848 778817674 953358937 812105199 564806349 732071072 441645032 71253627 132357327 574172460 895315861 540641655 322808888 294855213 709781121 731715070 694790040 866711651 285420376 467288090 628751209 387106060 819378389 399405299 5004261 539589805 43698403 149432442 855788429 204544820 713868872 400900636 983362494 519744168 65522194 400685203 251815234 507167227 471938830 384172561 81339680 219771050 777330583 256664935 514626263 339628063 988380005 209416296 206339708 273800374 529220752 687607283 513422800 348599134 87012575 518427061 888188939 130710979 520375870 596493728 187772165 86761101 997394364 171134653 606505269 62916552 571819856 858320503 570083779 896275052 95009424 503939825 116046095 872340007 760604760 630672358 64484429 601501125 692605020 270824137 875301499 221825765 958431421 241240659 422941265 897960362 759667720 163646564 881187707 132559949 760140292 68959866 219321050 757534649 92610885 825826320 672967567 516947107 536663182 95567705 413222152 631672606 599507531 381784613 356528972 212628650 12456964 421013402 814129775 557578350 544353905 541947634 779404115 355301685 783188293 54861739 105778407 395372372 218508303 986966114 527932322 978648595 908442346 747253372 588699604 853569597 425596051 261667164 370516697 962259234 357234870 636255215 446448199 809258767 18039821 802977172 21887410 883013158 76506933 688533552 440591501 620860838 82997545 72511975 976162524 718702204 127373715 81940924 114074569 345882018 921423404 494523257 177046973 682382110 94292989 765746577 388468066 519889040 27413734 758984764 334664633 237164970 247756338 781112833 46423730 265796160 436606364 920827514 1325677 513113297 461877425 441917179 986490501 397391336 366945520 815169384 116093533 494319235 749626674 82684468 692717620 523566438 429724092 869764593 58464907 524017081 635511163 446932973 896422487 515441263 58434096 231087114 605122600 306190435 12199940 504062696 571986595 301322670 277406569 573312272 814435967 739283994 867745817 653442827 136675323 234691331 468612205 105285222 581526932 70755238 40486057 274244545 594321676 470210149 144009131 652786583 994227230 632036660 99719550 743166076 999994290 158153646 974253190 605116883 464344081 838969496 109179572 888847042 140292159 239102508 314675674 807244492 978386502 182421484 313203679 967578192 269629181 781815884 925379780 851156114 852571122 965865837 125400652 299409158 436075979 121926150 952195741 282819568 606479176 51915284 25985638 458989825 62585297 852755194 64106701 379445744 544241050 25802640 268292780 537049575 117421514 582968454 196810427 95808009 617906304 510014106 915902567 887535486 144346349 693798707 738691593 849433837 659664537 716608611 148842988 948256883 691051127 101038723 83592810 150046663 5470373 109578448 609036488 920572043 814850009 525659556 300017781 211607418 403978562 420826927 601173359 521400076 3795374 797983786 469724451 474218044 160514251 238143378 361753523 157376966 931942085 952961482 6810797 444122981 522086453 8170151 244896223 65653939 109208874 328489034 215700602 967195621 290583848 677253457 740284023 105433850 55429372 40301797 169557634 459407934 313645090 770730994 833324376 169956830 421231139 155565186 644174875 434261757 393708564 5928391 591638723 178167008 811406240 598449520 474806356 333492686 606619672 719702579 399146625 568344912 48191606 467363594 388056892 338775455 144617044 128340909 296725671 200046416 21159072 318799672 511970716 187320529 89530659 345295085 357277359 363278164 500860271 1452227 797539921 747085202 859896992 241695004 925252210 671303225 840144524 252574925 857312277 299280555 972277505 108975261 720141834 20469104 576338855 108198719 211760925 720955899 89055994 361002963 773518681 962731440 679802635 285489390 2568328 621849660 483300841 359845687 985127824 984161113 361297915 635184105 583762674 73711266 876879109 361531243 745014491 569539992 614106169 454843127 721336914 586383667 563818388 441478741 459369137 140157237 402193826 523646429 713629502 343766187 884649392 487148177 159013986 564452020 625153933 161582314 38818039 108454768 521428001 23945856 945132247 735242282 511646327 528894914 808953548 241041795 890426157 406484398 663098154 357048685 861327525 384435061 943432352 425145907 678430168 255317849 417819510 80623987 778964278 131449005 276906540 516130029 471113548 288436892 80582042 96267475 450019206 119400081 57238609 823963574 995862310 2370849 559205849 360024997 383782129 220675757 453583158 126724645 627160155 116681305 483773331 488487674 353632732 279722042 766149947 32062893 535039891 183969450 965203254 166520528 167934821 94626153 682650557 639048370 383063046 615748965 735315845 833082252 587665412 792554454 509562185 436044082 647441669 68768028 648585445 31223791 141960151 102168596 157948436 769120306 71366268 641721767 110124339 424999000 921443810 876274286 457061894 309000060 60243729 274781507 328036955 80694917 369407660 10687505 719743287 752470706 478952837 307575491 438069318 919134615 100129938 947631503 207695056 600087973 868915897 856280501 631311764 10876041 958449098 641776566 779996348 29815359 136014693 890120687 307330725 57458496 618911333 764392619 218974922 531671428 39174119 547011877 612366345 261098146 410215749 332109625 13568845 741684952 639685116 451638163 660819560 592331420 251786026 868514617 44935752 120701916 577311477 676247516 131577958 388276934 170540442 764090672 270608659 306555135 506727718 577939385 216529997 125639044 194848363 435504919 509826839 86538849 835033163 122193177 347636995 97765271 306819169 361205840 839450223 946504285 665360370 352786142 391352065 917146396 73817118 436287817 37848305 651128596 965051700 21942629 39405523 135592135 638549667 310014183 442147270 997793752 887953568 658677267 975949162 82801924 946698552 485775994 21857139 781731708 460485538 369494134 879496979 767304707 730699975 571463561 566325351 248576704 924249704 957677416 165723093 998066822 246481593 56087764 649195411 64049652 930546767 541117301 199641787 421612793 851131484 494305423 419406538 591601411 5499049 247872060 526919701 952197601 733648054 548776841 586445669 46649951 918270975 318459007 813954658 501487309 889922569 380280003 750064013 814172266 190473778 768303472 664755447 289471737 824391237 166467218 353521389 607454363 707584519 553163176 29067149 411232362 47468592 300990054 2833766 52967641 548862114 382269833 857681609 135026527 783563040 444127271 181676479 554350375 762586278 995631137 55837677 505025206 228427499 658418057 171713831 418901278 279237888 836469279 708373015 103629118 2936490 61894398 563599847 710521009 467573940 592666997 121753364 367558899 893657051 977103503 273042906 295035524 211889695 130724508 430062051 995452736 427368145 611738530 402319470 42470783 607369661 310673513 547495989 835797160 969091570 719209821 107214797 100845818 408195459 668104179 56991302 411131949 582514943 620591150 974169324 50088876 65774506 948439054 270164141 959431557 778058916 395723414 106983440 989948611 378964288 537045491 837917706 806332434 148784015 92753535 701319583 608670042 403427049 101331931 296983561 225034978 820541752 404198359 325880796 81253570 72302531 382872099 492385519 507333840 3463242 319071202 409939082 69237748 267510249 680103224 881185671 45569158 75826631 988169111 888034136 307307285 525214595 578468201 113639712 526514976 671221737 667475661 135185011 74648779 768807593 432168573 152200123 441865704 688883298 478080920 523119275 613702195 860953019 15504787 121036028 864416261 187092356 530975110 786170375 454602605 63594693 667356039 352688130 991937697 508041509 93238625 299244976 33256097 524223192 265401054 412287440 47961288 932876716 547472451 122610067 554200668 832157390 127326557 996066372 521040681 605407477 519185640 134742869 466360489 387206794 108295263 183293109 574299150 491786740 969463484 881418121 555381433 489335882 86622610 399835490 997377391 179861235 699080466 883149854 704084428 816997886 147953653 752045716 602390961 695426105 727172150 156591622 380099854 854498707 5174354 901140536 312422543 524359994 888399771 778783032 764083154 849211401 814592507 190898663 340998134 636572350 72316778 748895933 125908225 158939388 148731416 975801982 191316990 700328248 711468195 895401418 517326128 859421849 499963493 119717082 407364313 79652002 128825071 787464167 786667075 133999425 541121062 99089611 510875785 282037193 730389009 274958933 131248587 544981509 465857596 324763087 34070218 390690740 73659013 12494809 549630129 74906796 988296791 740947119 775235044 552281346 488864896 145077531 264219554 841344755 117310980 524100233 920996758 98652417 164080759 560180192 232651842 705201822 659269804 743527627 839755381 242175172 871002926 823520334 787156682 189376882 799780 821226900 580067622 74458793 833721710 129697744 1881955 674534860 723161229 629633366 79332565 64542484 774710897 196068485 905887240 744538243 720168718 679400357 843190660 884249478 92096908 75842495 441967659 751366712 671886489 281723033 993541885 395405774 105243360 633214926 584782656 106043140 306958185 164850272 33018299 993196261 147064382 887416628 520247481 722741978 517049987 599580046 787284462 144277243 795648532 545688061 888815487 368333609 77604777 584522506 252583080 169701686 512881368 694550739 773584764 37284216 828790138 619643008 432689990 786549864 105374293 17472640 745109370 412332479 34839278 630644036 258045099 181903660 518060657 778292580 904645638 887627010 230388986 544446460 31904246 26037511 942650887 773236099 246887486 20255658 210274965 499470567 42473710 723156333 46537665 816058474 760440549 875327804 288217842 193130532 514394027 393592135 63119538 259503391 805924614 97958816 890147427 63969707 279862477 260724443 694778653 37024474 867812 925167639 433987300 32772058 803721516 376638181 658524524 50608996 249410205 868799489 402595929 144400281 444472181 449133594 960458755 204912723 176977757 101192956 250559621 691371785 494785092 313679160 803391542 153226065 411637976 546055328 69712138 691500453 806779771 764490792 581041294 807647583 689658424 15028587 692936007 345896300 244183134 203976890 396505296 493593339 925292745 799101225 637993620 369764919 100751178 450968735 427194008 130245302 552161691 677753630 821617087 46946776 991432790 477524988 52689208 403070759 23580309 122401346 947087579 682876446 886892138 528128866 343040388 429066922 395673819 35976388 774963222 639856954 92469645 23984877 133450286 17762383 823086102 623960273 240043669 776353646 927445374 667237677 906598948 332123424 197507666 580732394 231586567 188940449 58257375 284275775 444527575 81837684 406677121 391615147 617230496 293569253 772260379 960270884 722636175 167934191 848763639 350115756 807791145 941233284 374100633 793757798 811512033 49703094 270234430 904072068 826056740 50196163 423826105 732655682 382319587 621333771 165904435 613906154 810274221 224161811 898181929 107318155 158515861 304859044 498933302 775746358 450944663 123710040 588533601 26097197 291644231 437297233 376212953 951951743 231046876 750313586 598225900 895075276 800016680 868460330 799147337 626073413 918656493 75489801 211245454 153492439 696823573 377149890 767398594 359614153 453828067 665580516 466932308 612343928 822955926 965865610 240606645 273900582 89575643 829140247 299997779 233736240 118953839 676210732 38204342 202517082 279040677 636430242 97592351 79057350 357406931 749256054 557647130 128579783 824745856 768892584 282072223 521569422 998558840 49470810 881183575 452386900 567567692 200632242 917247195 390523612 19014211 10370199 516940560 108589854 839510446 816938340 194842460 810980652 345665431 233046803 13497727 624706109 869477045 111090078 556279825 79400336 712862498 113926948 207980119 537608347 735335899 490052342 911694135 733894732 539523152 645394069 38797992 107090838 846026311 956045187 350130816 865040522 966415386 867071376 826146742 658442192 536526075 20989196 321939203 734707873 106552365 335436930 211930341 828545776 299043374 768210166 907946112 11905865 882137115 115926225 402030579 469989373 605978567 166241073 56400464 998018086 811635143 95198456 957625290 657661447 903760009 160272465 375218329 722691755 27343834 201365064 233650306 416386276 74870626 555589509 3610508 33939357 891026439 215540849 862485134 42586172 983751015 770431239 907008410 718404489 738873830 161555348 188393855 197368757 327796422 244794320 195386836 139431558 192509142 5528485 649609371 96269145 165800950 24827693 818960900 45661150 78709124 52611199 462047426 153579750 460717074 465657934 187519108 204259872 681198783 50004235 246846044 517466158 672951840 6370813 235870640 264342030 167926162 276780862 461710787 495722584 521575182 657097623 635154142 714084324 662626108 137279872 662869835 828427058 162107566 334347094 874088208 240816690 239474659 188651994 246912806 700191733 506826294 434431914 904451605 40541437 336952515 3814008 558007595 862420722 10184822 793878235 126762745 178110984 70659090 588473532 673833568 444750638 98087514 161504069 11351322 613229988 298783941 674221157 294173405 460891507 8568245 20777972 554224563 100559270 209429966 801137370 800751004 716256261 88085643 705202602 756797698 425038159 709016611 167321652 139975240 719201433 961199887 266737985 897312417 884375344 707727883 423662344 181642341 805815397 585166413 45510029 271561744 883950354 719731187 565735149 197358221 580815798 586513121 751582784 681375068 795943088 552720147 334642431 364715708 640805791 39845027 974029772 918360316 601378004 141351417 58335549 173095796 955067670 177589900 922924579 691959373 885317783 346586916 873601715 543649539 931753329 919111744 815211283 668220042 491359290 380946425 865578263 924691454 967459546 617161041 458582882 615918993 22397547 793225313 833151067 515719704 685586706 807180832 434080013 139481069 801048615 344931928 312576865 756116279 522521828 88017803 300592011 407839604 434604719 26710085 951489143 218874407 945821830 619216785 887094450 289697479 163203 605189072 66905293 820139116 74866472 525488175 288574468 97264020 318713481 121725529 612983724 4300181 781422727 899580104 143781250 434987702 244512025 308874482 43620340 767033854 396892285 344212351 27389817 684013371 370922437 831395327 902887778 169260626 450612105 642498587 458958105 303291675 100204019 525863398 975947157 175070491 51351566 117037984 272334511 222581414 91279879 737834602 79397961 872702607 637414699 75695577 160206668 734443090 237086425 203827008 353993303 633978711 548039359 381383121 170508441 918961796 65294807 73396212 88222415 515906912 568411166 399696887 671714953 668615185 925560285 647662103 843685676 829428218 764700088 968536554 904525998 855979967 706371149 983923959 581198933 196302207 912135902 741405601 930745297 149222321 945232609 137254960 635717398 345788328 518638081 806225839 264750117 583932888 732138417 205488899 952356166 153065942 605185786 624071113 821681127 383262430 124249575 517883163 65207007 741466029 338936076 969733005 449962356 45307218 806173323 31161282 94125791 718309219 625083250 877387454 720047906 422832218 14642407 355765297 768620546 385796854 14507495 885887030 969729742 746645912 91375922 774602268 899711855 696561708 251189740 573909341 79824131 375439315 91792497 145031139 116905338 283244939 967280510 419384060 181068523 773453827 303061708 275194314 344279405 928144958 5098128 64327304 203493536 19740535 272608967 824630448 405537390 287116462 710517471 227783491 33762367 654409759 2385752 785990588 203487826 106091858 359899923 135828324 481531174 304208786 133375829 450952878 587453726 100656332 870336938 768522249 726626525 25915005 896232930 70905923 954059964 901331058 987749600 10069859 921071593 112874926 834700307 179125342 252507754 397734138 259425200 138786488 52143890 114327318 924777076 108148083 220419177 137193358 243976407 701950351 441402145 377352236 5419588 881372237 478008568 728272892 502410845 57151453 754187897 398643768 128057376 560764220 152491185 968323343 570834079 73562772 933714635 258050746 105204480 186222383 508301250 364629680 325008871 412961506 478956999 102302306 521109589 699376176 239495665 765085996 253842886 680897810 142438225 111778840 414786406 472963160 840051732 917197251 530114613 594239622 168357379 510688355 7520202 320848564 331528057 578354281 246927702 265242686 688921393 352132183 303981435 197222636 569278229 628990306 610184143 48235221 731292612 131293725 600127763 970788277 748896088 706487015 504202446 891334313 818265855 918988852 216813832 658317580 688702463 746928445 105073562 857059842 257616794 112593764 177908399 589144851 543464411 424836102 706903903 232385798 629484651 10885331 282124800 198762873 492392003 892308943 99514461 76200975 876119035 552158590 46989245 477531482 258645599 403708058 221382154 76911447 175213269 438195987 587745394 863915732 185124425 545335322 573491933 295257585 657929086 751400333 884402437 53909856 28752794 443822699 286295654 658237445 454708031 568420455 709516684 947100034 313245757 809031145 23301002 41881151 213706095 922806621 519412633 472351694 179031038 740794788 401779507 206760673 31507134 842041267 70676399 216631559 387376582 496684698 511889145 897822034 100601390 248807941 951731891 129354184 692630640 90543904 640107995 999855037 658964359 349624673 799471431 824726483 11172177 675288799 866607634 224878272 450611779 238536627 549746332 629642817 831847781 951525840 836403491 863354915 646083466 759596256 79986467 33460042 108797313 444391978 783798442 209398704 545716285 735530326 338752888 90863285 826074231 978860884 90718315 337554949 181001916 890189746 14797791 44690459 417994905 881405426 269568732 868606684 972458419 819315064 350765861 804306193 623357263 39685711 520177467 121957089 799281967 452680300 7933497 908079280 897072279 791731939 117477977 295304923 379778625 308747232 386168208 58369215 140124475 476886524 395924164 173642757 219592629 410721956 218333216 637587534 144643741 487901948 358710578 117102153 159733372 709476439 773924712 635607001 749162150 146618538 757564090 400960476 599298838 765497587 161556115 348887476 557229520 131550459 644192400 937008145 440297691 30360601 995377360 432938532 359763491 243817883 606581289 579356121 507056205 824914505 69460014 651699946 165332813 428170592 621318465 325066185 137647024 247759536 960673186 739325540 394378074 570753636 140286009 993676913 336251216 301842125 195080748 745997102 433392584 839273148 535521606 726206641 869633750 383415325 159145166 81913600 627233209 765726455 661269721 134289407 443157319 583246102 638505720 608490132 11416687 112340544 933556317 1580078 212616447 746745863 593421984 606994521 170015858 733707994 453187793 506267074 888066485 648268542 104780536 173975428 340058049 640302142 900182069 62208158 23717461 59327228 144121759 503467036 677570049 805391480 490272809 120727361 241153941 128778522 581733860 105086995 93635433 367806536 106667073 306251880 114552392 552605423 765762767 137084616 138829776 71466920 643351691 26896254 719735462 748132227 200871682 59793504 240950728 101053744 122001663 264668189 12897338 118639788 768135225 542983753 924031268 110924394 516227481 17701569 92219282 97961334 122788564 185854715 318284236 81972003 344622961 285352995 634577426 110385722 422437611 773407203 181852642 65789295 800303457 754104470 666437888 853691506 666414340 907388617 807261616 640932369 24573165 672675321 759572157 645224757 68175433 536119785 756149151 584402914 553821354 848368433 534880614 676609918 34223142 853164851 758581921 231362469 138517839 393159340 341748191 413471816 19082902 376117199 331777478 819386360 130221662 998215366 525594225 796636003 758120342 332855834 290084731 635209874 5531148 49656882 280434624 73706582 585776667 36583768 510625862 139598014 737468567 898022843 668724298 624208075 603704053 427306212 855570545 594738258 672981918 49835095 8210067 692064821 425952295 339987545 363967540 556173957 190719271 889561765 205326319 801355979 74933958 495411051 436565846 80465107 397584299 569516836 6688055 983360966 458616970 369830283 975475346 196085531 120369485 496716003 820293606 724073538 924022215 528380510 318811789 449520492 578215606 179538223 141585306 4167894 519525768 505552846 412858217 562761405 247630970 618184537 364117378 322564929 966111954 653199590 255546402 363696246 222716420 114750823 199573571 681333390 484581106 27565276 729935287 604950592 524281279 402745253 181540489 300819853 931125763 500352279 750340345 509341362 679890502 744442018 366025622 51932629 102511223 778883840 614694035 350142194 249584736 831327779 672707123 215696683 484527362 928253525 431909295 559760148 43004341 631482866 93609898 380101813 511564508 823545185 985052405 35845780 226290431 19109254 189181999 9932554 519461533 792038710 519273916 51868394 536480721 885299539 103801023 638991945 516699738 571011424 989134139 766284474 254855562 514357621 981981157 739382925 442611139 266406811 151659432 338131846 897889677 245269330 718233659 261970544 68814509 555802424 150332690 147621306 574911678 339514689 157553860 94373204 131553392 676827777 998757971 520550480 414643675 955075360 12058784 931343413 378603144 853709289 550144246 633458706 368066903 384641762 225357990 663194408 651048573 377017423 1326247 401454609 622286753 719559906 663425153 691101262 127878689 813757843 838722569 702790367 5788891 996276429 649679937 137342283 525620565 648437901 510409129 792780606 456029621 374984279 576640378 834632765 228693561 126784617 468091464 449276830 511426379 693449455 112471231 14991311 70466871 113797478 416445920 545269990 685873751 79871066 88887612 813752440 893628909 927610181 369059167 899417800 776402969 18739097 889276450 154539894 519693365 252201938 947320500 975722986 627186218 376477238 810355744 708396145 503261855 130963567 157672969 867204601 676929388 122660566 882195912 599912625 88974411 298641826 145182609 774848162 231029258 234070221 441116961 124658161 14196761 810176128 876592327 643116096 681431592 618385136 797655990 201124950 723103441 597492850 29364295 202806018 973970088 839720039 911202163 329748302 823199972 68875125 49469262 500129354 44052058 931665175 100041972 133026469 82823360 97740947 907874631 313852618 184327534 201507951 291027145 198524295 864200446 20135832 841640392 545632031 638520968 491812741 599273347 214140768 941821957 628637642 416946786 768308404 320874040 328148943 98056700 144074005 249540434 42328 496719725 293592492 931707503 449278064 426618961 14530856 547019011 187009951 328383475 731346546 241034269 619410620 782387207 105234708 639546452 476543958 503383105 130583780 968356700 102656445 344724548 762695016 731294087 761671335 531003414 52168120 942336644 481576480 48758491 44393437 481618808 545478217 337985930 265842671 994756281 617121257 280373527 394291651 804131209 461273368 978154563 45165471 80683982 760541764 2916545 572746800 89602081 506299650 555846946 57958774 461472461 900571495 673170157 45282907 514759189 56689930 97451027 309612192 538266410 998725891 354005629 872401584 396720467 691991559 138244248 243993107 161629176 271134142 638284759 965760385 732407510 468955681 863442222 665607858 82013804 718875133 90871018 171615886 77691142 646717964 82091026 539163603 399805818 755261183 584446510 914565007 811951113 534413903 76693558 202733882 533139787 430699188 75135460 929860255 122690740 65896074 26369721 136836282 337030216 664654480 102596660 69437720 133610155 818555248 735045578 68140325 389946740 825916596 239756211 467637882 325150920 321847238 6801478 724956738 77108414 591247988 492038105 889059528 125661884 568731663 91793403 511318038 999430851 19445229 293694652 974637958 85341304 320064373 111474233 422371520 837235220 66587260 344325606 823361741 737658874 79371178 891502066 127605608 757804140 131258271 595243490 82955053 453105509 454561335 660428158 382730289 45809316 152466256 124306176 23987567 721197919 68615946 387821971 573145130 88061175 534032989 547783081 25918845 854097362 511773680 448290366 543848941 578360940 792615972 367210675 168536174 724503516 111229101 296141782 334824016 242487372 743901638 270295435 548109247 198462966 930723593 930839536 96788649 935706215 55145706 973292589 509420494 123761652 213630919 82565617 64339193 747663908 482865064 90258039 454277629 994638744 538548405 998126571 425516044 183680736 217853605 594052218 760700619 329082706 890194000 95524628 571570078 486611997 218336429 119679318 685074964 1576382 903035221 634379979 937282597 958180927 607672561 299219450 934458945 821303480 381785067 998798138 421483747 864650131 89056170 875761376 711805235 480120941 873887940 137321272 663801678 91741539 731373490 277018656 273340611 474083849 225059650 844910690 960695846 443396079 817106374 498287169 297488827 572657954 132667141 87287784 383355240 592856068 386507234 317814178 266675907 768292302 169128676 688159654 485458792 258184846 416437390 49780386 738305788 142841689 187101658 254623825 87099594 770991514 531642481 360440206 97591722 756702131 57867255 58287562 52614569 874973629 409091097 350103397 300147943 394274605 437391181 683503183 839647039 823898415 1317355 106322940 444707076 22962397 646998960 782682235 281147243 63436343 832462621 871969397 58794399 19564273 126593215 145893993 643072153 510752062 506334199 740663876 119970552 564201454 651467804 25101488 291691443 60558894 375204885 591839386 307349865 665112432 275342562 146996898 341527206 129176283 105836204 786234283 152138680 605351530 421432877 285802290 521304240 253895491 157771680 580098639 125976130 136881262 725992632 769048284 500149690 84843191 362228519 620120243 649044645 13696316 645221731 940736088 926771583 872942982 532575467 86637808 538055407 660434396 86151072 879582613 789610679 44503642 518333255 794265726 649855172 939766132 80068009 23675771 46177983 90356055 456290776 24670479 227237317 34799768 793718763 727387008 119642959 8463641 200023610 768687604 22159957 697761707 709423686 948931541 570704682 94515512 35569342 961276455 754949908 121720414 693375427 397076947 18740422 64225042 43859032 668595594 3991167 123927041 544787732 902685523 214283096 1078501 927356003 294036780 35878269 573591125 21423781 155521228 582054767 73963757 924208833 604214724 771725464 486148878 405662624 194946505 433180756 293748332 8739319 40647024 267985112 702114746 437723971 286725534 766339788 481583003 807837495 622847322 458026410 352625220 525532838 672309506 206220087 305405200 966346286 242098357 878996326 840286433 250135951 461051086 766766556 26861143 917782176 391008379 513010021 175961160 585954884 946190778 469709492 594694203 986837802 590210971 149325309 277078132 876936505 915665097 611177501 537290359 538512412 69203904 889915579 916561617 594029776 96135660 221966810 412892422 190750383 100963129 105695214 440886334 414530581 872461771 467747478 184829117 263470143 833273865 360790277 701941394 631981002 830499769 149151956 471335163 273227099 298477265 748413295 2679964 214142356 212107155 539970323 605171134 281311059 282402262 521732744 875340836 231054288 596215921 140749617 421804671 549695416 246444831 715207371 964225998 118906595 35471208 1571474 234893105 868745074 362361751 936834499 500726069 45377879 85986448 972061233 318604979 384463714 572990887 321284943 451122436 785098043 861255266 56293563 918925468 143657521 430542674 646782663 374711809 26758588 787532280 649032846 576454004 33977105 364240211 393196361 5400066 399711419 394767835 240293171 120972852 757129586 177127663 621698922 802507466 115630478 446276514 121112438 500094192 871783767 294913747 951216628 509398169 156169006 860026557 428323631 152342894 290569224 75106287 527054703 169844178 715154934 28603909 746298183 749132039 392844120 992010910 754532105 645071905 239295105 994825277 766044758 996424691 24469299 240260039 651448516 140099777 686536553 625077320 492710335 410836679 919991067 296443322 920234849 928676440 156469873 201074839 81019327 299555463 128697492 460590396 469399642 843852426 489194305 68214184 445500824 882038425 60225087 52549289 379626690 299520192 47374559 145671441 148461243 924360231 385931480 652426125 64460002 924984399 130019805 409686703 335821071 50010865 706130026 108572279 831203671 862599899 309647118 912222998 14671721 438344611 225329754 484071363 282197030 714524059 552285547 727697855 449078844 612510635 780247144 828705534 764547193 680138069 974376975 913008436 457014659 212824814 417950921 373991027 137809206 547970726 783677731 326146643 450497957 489807750 434718923 281701622 204924008 744366041 46440979 219595729 35227011 271770733 703667093 317424042 986294793 108468999 897638263 287889996 720979634 530401766 116595523 338043187 63056194 943488864 103567982 520070853 8830037 521518903 894061881 146639243 69489622 677739605 325302252 519987580 20063714 612537541 654205568 77504088 209419942 700646547 297099817 244646953 824933647 853283276 562070995 663744799 961752276 312225617 951634795 535248269 842627383 68230311 873291456 905683577 864235541 976859439 425754424 873065578 498378335 172332664 872221187 420384324 850072269 50039798 940371904 722652349 662577340 447093831 800156437 871997282 256737 97256247 116644228 825190384 803055890 531231590 488935176 764808159 843457207 293086330 152572787 686084584 213833007 25864237 444284520 78068541 2723669 870038944 951134119 353618370 42371601 675871665 774002694 744960236 725911464 566890957 320128944 388488797 13984781 120285374 113002438 14241519 70057988 229646666 691948269 873113878 760878256 33399805 490438396 456851823 326486135 643011183 142936400 540319143 521391786 439737286 618387684 376631821 162292590 422038163 730250192 57180557 97909821 356769245 802140794 676337651 776176569 122269731 64826441 642677716 95071472 30345245 509435601 17645826 259991912 201383864 890759704 873386534 234783669 233714459 330238350 561269804 729242008 325691116 101588940 250633788 765428403 572492991 627265609 927720993 847047520 210032160 984901550 797473707 419317772 639558703 473811352 195494334 614344801 391154159 838172050 561932639 421499405 200124011 579578465 534007683 401507875 322854528 407394210 488807910 556568987 590148927 50077707 138327354 915840043 4183014 388961142 533784805 429192371 868743118 314022157 128756250 78775271 151440067 926229957 350609409 643515136 252557668 546103743 110376296 643711828 236792153 672308935 917727599 436916164 251887393 451735275 690940405 574741921 711645851 179748308 983827274 301794771 82342381 122154622 70151174 939041768 363632130 456452345 220750498 232375241 770474503 349506748 163666879 774430936 275736699 514276288 417946065 528294367 912896398 528322362 24522554 2204910 53147656 942250153 439121074 305035050 246501787 130061472 732293337 958147639 162326146 716120605 112458769 97184893 690791593 35126309 36226655 54423716 491578655 256977153 139315324 114569517 606483902 302982203 889000453 734736967 669774857 159462877 115547693 582671248 687785239 140070248 584876158 740932896 934836767 876513598 898484312 33854914 859091436 630777642 992002553 21417575 199414606 956977688 118602469 890206199 992103998 7345490 797146282 483682646 116839009 936461606 598252163 723322911 91960168 339768975 310576237 761735025 499231852 426123931 196922633 39533451 566194179 781798791 780466347 353547305 510828749 531467018 387402219 369920178 14761019 231921131 243854120 214175626 188898813 214972955 956898191 33519170 74834811 754044466 517201816 191673820 543022431 967970345 914996732 634982599 307739313 78089328 396717618 806971165 504213259 593640251 846504616 70407431 227955401 479487322 276471103 738784150 10954333 663873322 961220695 25715353 895794454 57591174 92407345 84693260 272564129 49305529 118212430 347398940 655866362 487930612 539072760 51405152 308417316 306585851 686387752 616156629 384675180 83105363 275644153 888888439 529261980 974665136 811812237 609733747 306668817 88283333 201034257 170139517 604673021 162254945 48371236 500467468 219846119 140778581 437677094 344926614 42600476 408405890 692325554 550983204 748852868 83914673 602388357 57270177 243016891 288776102 525943172 627692071 224397831 801587326 369096869 606176177 628768821 33425465 215909917 935437638 974225171 416944174 105577148 578898186 431715485 153948384 931882020 651561604 147243331 222075474 996488218 189843808 630481364 541330131 740827012 231850592 477761171 195731728 289120769 720778062 484507830 815063942 200986492 561422027 469167627 570083361 167598197 97936441 456025193 236024481 885890445 430250357 652968655 991467594 861664909 84684134 997932344 793546923 588762104 145175669 15622390 437766682 187535843 498620120 831613179 928362855 730470712 309374343 124094577 872107848 30152398 461118773 539688149 83655256 22540794 8855769 653738618 42655357 959308583 109763804 278679838 697715387 392530527 784164860 541699340 106711796 721365360 539631678 900258719 162643823 537323713 768397475 600410505 724859556 119533954 284540044 505738770 702521033 593914387 482349713 574628874 476583152 943468487 114317016 560238408 818525647 975689158 66493385 713697370 787514100 28773555 992377209 337745846 273820449 629058428 879445187 380532245 350423781 271593224 133307323 513067604 808916937 901704798 965994476 533776486 873755118 250534513 39515249 576276144 696965266 374381329 3421377 26064777 170366175 970254766 586303186 988891822 798460283 505312937 555105551 438490742 534086493 399999119 776236589 807906942 29057540 655681769 40955546 231997687 927274993 174262869 745065292 588708289 75967660 563576127 122484768 802239144 814110640 14516383 231031648 363592265 241414078 234453025 389657043 411780253 57224151 975960229 253188434 855684434 333789525 808293986 294175170 867876018 208293098 70411752 528299319 89867005 578609887 569254865 321864692 358401239 743517734 66929977 947109528 672001760 483022470 922110662 326757264 149649469 789143411 557788912 513241735 30557483 792241937 902898778 294854102 849466088 731375366 548042537 557666882 65164884 356336516 851842052 785557269 417145980 774770170 166372947 507012985 205896416 735627813 828877678 416814021 331661906 748324021 216439908 856180033 231346485 138550563 182937290 380995954 780210340 740726202 894237689 663284189 385484498 649652826 958138292 87466946 381028185 358697188 645133828 298709436 715033704 349492239 84266698 132179677 976778775 250639645 491709029 35191550 838783824 320586700 452005571 22962090 68910714 668445479 879142123 152773565 659512408 62079406 386285886 292239107 655321974 133039934 955523297 893322838 782692761 766177948 980789784 16237305 124875129 478439971 314946741 692425199 680448576 399213439 677121242 657227344 502369451 21346630 692418894 341153268 341933330 144424458 364115358 263360411 665386303 95773840 268650342 324898704 10369612 654936228 617137812 665691586 787976163 425177468 411530784 570668917 43871775 244836927 586906222 21263270 723276899 901852964 566204835 256241834 153582762 95842436 913469179 655952213 117189067 458404432 849621848 459122397 455345257 66253565 574999174 120731553 162027406 843649517 298146624 172397018 498585738 767800802 838088605 139078260 45494629 102135748 709747177 89366404 346972675 149169759 110629674 70249567 903539089 529350875 179007768 57121844 625193311 92476940 565590424 742382378 403397738 267728631 54021135 711259361 333982196 629020309 684507281 496009602 472669819 982653905 668406621 823771924 602971066 359011585 962850184 648465695 461147333 525113721 737832099 808120008 674283480 700978139 730885942 430338928 82845373 909893710 339977138 708038684 854887016 905567562 450421056 110801113 25812552 504442191 822060475 359794749 133462493 506567749 855804351 458648679 341738013 524210965 134936962 944709079 883222550 97787139 445691133 196886242 622900860 36039591 5006244 149700699 737017730 735892186 580039627 819863103 498302255 920016766 380418146 353189264 678100687 830839202 463990377 703913240 187797752 138567211 63707982 173776612 645134960 772028699 484941657 839389339 148756024 619878619 636614777 31978567 717665758 82305903 81381176 193082978 118345494 86387420 195300043 707879590 674795972 775339671 380259052 173098220 547872796 760677199 378803850 78489842 444032760 842794227 634919448 631830513 981361439 551143796 658123491 479012758 323172489 143065141 170918457 471928513 762943760 807533234 356423446 333125877 889839138 437804622 378725221 860700998 376708408 574025265 568580582 51504373 201881295 948839634 77118959 749754091 562033192 455922809 680760299 6065946 151233396 315679741 490412825 132594828 866823537 148536309 464123952 42512385 144117816 635042409 366957264 907061576 295092003 723380711 92703812 37447500 13701692 471429034 898148498 390410101 45454292 319245439 294430840 99851953 120601433 371549800 849606044 682634625 827472609 382882702 688700571 978706005 698562443 31629755 963817199 417902340 180166064 280457511 312931091 324283880 915499920 679888356 83861815 63108282 255785426 29081994 100555782 269487118 500511028 998704281 512413585 398481686 317949713 806844426 498333639 438551146 178394219 200456042 121185765 5866821 583338744 662402702 837089193 134417547 694032458 800906385 404836253 726714888 81363889 717767344 50998762 849380176 397655693 987376950 912488458 653441119 16458937 13044234 775444604 369486331 864264881 287858182 767968017 34730953 94702601 118818015 473282100 125613186 171790423 446984231 983996381 755129168 961903299 821085567 742063081 508452116 474508311 146899327 235166998 408388567 864666671 138682126 110285102 114838724 126059069 875289926 620796209 995034380 740850526 396240806 364520704 605115400 536615355 985005088 639846354 483834322 103823096 965644820 609447509 128129886 265145410 445960249 883259054 227048702 119562175 477838494 735500819 594070486 624737821 823184183 854975419 341920851 961866309 965260521 309275941 940441744 693066807 930072151 787992483 433917326 178829316 5029547 891549093 715444671 990034635 383911806 199278987 946374097 349556619 661242862 74503976 614702029 107203104 810279396 694267097 226765279 288117883 282284275 673352131 765372070 105468451 528327544 107292915 919851126 346104424 269085222 712809230 39171224 199157366 500801706 325604917 377986683 505831253 69670369 93431347 348382247 453582175 145226700 294756338 803138794 806469562 221776680 270357182 766189032 32056070 964624279 992954311 172690319 99424914 518822802 938062390 204893365 47150339 897871671 124744485 245771129 166956886 690070081 137458720 218630619 43388146 315580003 596617302 549219400 385250372 542565015 897601647 838832547 540308082 44874344 494487700 199294003 266651025 764844882 965483036 151223461 581985520 810953706 323913780 681410434 329776501 261976163 738820166 229443206 12364193 716081017 327730702 179321080 406151091 465189422 397951699 449539237 780769425 847085367 851275003 18536156 242166741 601393010 857368703 782474823 646267354 351856396 981768827 765434745 969217644 947251856 916658206 403719523 610721921 240571980 85129951 940498423 355064509 676466483 22457988 367428703 392547493 350188690 546749783 651214950 667894478 797217848 100754180 301180262 644303208 804545550 319716418 886469949 405938553 177085114 521461132 904722273 381457876 503229952 670157012 350675513 302998167 439331577 754395037 913720088 679903557 692041354 706734870 34968060 221024196 581709225 254913129 613571689 931897915 801662912 117302998 452308753 451397119 70573544 753489015 95700320 875119094 73205427 834686635 133574006 102806907 208664126 38296273 484264784 711894078 560969651 834940297 867408611 301221 441851693 633645059 532721145 986409413 192896288 420205571 207433602 774605513 675118700 673521657 559019788 329297971 790824655 11328534 780695090 861398200 764817549 728911776 736517287 690539342 416114770 870091294 793346250 624778897 760903933 277611027 189189334 321873577 965067690 56597939 174691164 259435743