67 100 835471243 969641465 392309975 48105252 69523103 574461188 141521678 520468817 936552040 25131221 75044629 194732414 525635085 36652461 889936866 692890987 925624360 242392279 677249572 619874479 163363893 875691337 629348263 404973418 611483034 976504276 468108044 635305363 738707794 952225760 976149532 402161620 894856687 823708413 570207827 951432458 805945660 674375942 351429419 576072558 835649962 941978011 116267225 13743444 663659373 294405564 382916680 623138621 39311344 131879319 47000543 929022548 96062765 134773154 637824827 809887330 65686411 873050977 922945165 940328354 906092103 931176125 277980737 714297064 875773921 470239302 853340211 638965321 445205993 745549160 859690043 716566085 79251614 538344383 808683385 856711049 38864566 928855192 101381448 662804953 279474177 269487672 68595568 853361827 883667644 502515439 813425848 618341190 19575848 515610204 936534888 993594789 486343724 860165105 523265300 219723882 969225012 980706861 789387818 950961489 100 679183705 584161773 208711206 739401805 271864943 920860403 482271199 87431221 209165288 509620431 827217898 597860536 207449326 636779063 896003565 741370377 771264397 278892624 892637423 487774763 113441846 625022133 157088307 465813693 230258703 29594119 31257413 160223951 392139059 553572921 93631962 409596357 93351358 483030855 735096289 600670335 114167677 201251027 2050727 16261951 240650525 746859901 707330882 937798103 120037194 820696409 747282598 397065597 982464332 681223009 217111020 895721495 843924536 57877620 16942662 633226860 680062148 803165636 658707183 457430109 103040004 673772576 994618380 396327384 522651556 656149923 645107703 382732354 26126694 3123821 378468632 108906269 612781999 949484497 756562099 414905228 322440641 696954552 819225791 39320622 484083479 622566792 843339180 845308165 768695845 463001883 906426267 367673704 181851390 84152859 10358305 401639831 542964717 344968205 741475001 805726755 262327304 588172797 825316019 631780220 100 972351565 179329689 777233895 15315918 88863543 146901999 288984952 327985385 96747369 659246079 204981618 335515371 599612211 946290690 137394688 478184846 415126553 850265488 79578469 168073488 205021659 835115802 445549867 119095207 749195434 852122735 916449725 516823444 566689377 966386138 544159833 133538294 919253620 915710891 832688651 811905963 508951351 429413196 330593422 889580384 318504868 757275234 471288969 759675579 632000337 835932091 321225220 476364815 16793718 960023329 958407079 27396785 201633701 2455854 876001564 479391039 901706682 933479602 716001491 514888406 104870160 678373534 360231301 58314622 370517573 724252001 597523396 811344939 330640981 464435748 647084497 251922053 999820258 504283557 967120063 880365895 106087515 11794044 126941767 823765479 715022650 926633934 39859657 657447277 325844825 246878755 272380479 306217584 131191805 668630191 746198286 609470154 355967561 847050470 330367384 66169577 529149213 102302111 788902672 719657867 100 578586164 966593536 87008052 149816459 163730480 387619320 512482961 103123121 518370327 902389807 456590682 167554673 93220449 216599971 12277028 465127403 971083783 912457303 898320504 203723341 803268687 986751128 530137988 377532099 929841958 319297314 319758245 648730451 205647439 238471537 84544020 849063682 556453207 498439744 959523690 458410460 771818410 374906559 346857372 79484954 203795747 847192099 318620657 928848374 718606169 195028364 802799961 287004773 815276381 710731752 996293834 568904708 9232995 595612929 42981278 189048286 754364445 670399384 683579512 725432083 864867630 892264778 864424191 96509435 114338136 563281398 197842915 287737435 251322346 547145634 897008958 488129253 578154095 129858100 42763896 856985308 670200402 271019434 111169552 940769777 484633176 444739356 313006506 80040977 284719788 904000502 49303520 816145059 928984216 952545502 322307406 277445908 215258846 568220464 416830706 587272100 343596385 653836412 600470602 862949555 100 392175116 279405993 148391600 960054449 46850865 68709059 386426948 820783802 318588248 191094093 294598088 526865 377588683 897242159 835475708 283381739 60629142 561745254 188012225 185452189 615430849 742263472 98225180 242850485 663861393 97409596 835735489 429667918 771385075 829496242 899640263 508554397 696360449 847151348 155561858 993316319 556804237 794370892 343037258 245263494 176011657 835617547 217807833 4000757 962122404 374987825 316781324 682028331 335168529 889859759 550842380 261482548 618266730 796484025 576109734 718990561 708627927 710720659 914015374 705797734 784339618 862840535 288781505 599262604 527678291 719307443 968887188 911498458 716670139 307589376 328876969 888084478 414374792 500738640 499489370 845353994 814567597 1400074 806992097 619709415 761872234 360554564 770325017 735875879 466463921 702643088 60817275 655117934 784796530 390027466 134073639 158534693 666762518 831200115 1875527 144659383 730243974 849587681 962170422 755488295 100 970293553 301066191 293649924 568120545 261340992 5238002 189321464 898008926 308952804 605296729 922447054 925303310 618609897 223819754 622802203 951935668 80155946 496215381 908121934 669788169 201087825 148835798 649294320 318236812 788818177 676598613 693064337 926824913 339304931 608773086 401057269 571425939 78956665 130294776 750384859 594642346 199122250 695241588 40008267 525827862 14160217 990149072 217244734 559074208 73820980 295320177 5176104 645955576 155039400 928047599 588916273 758383819 860697764 948819723 934406001 244044780 28880848 130168509 380439245 621213394 746815445 197695984 135566655 854085049 642978252 188157095 776213924 120527967 376722390 917205903 897390898 672938073 151222206 230743898 603488669 69798773 335511235 652026419 801991065 207381400 495246378 585186390 104523223 440708763 944081121 458146122 62667116 303451200 566334174 354761740 338077084 707247993 766976470 414671537 490358394 389776943 842676455 666435807 786672980 453139074 100 328619464 327886955 382444326 833227106 262804387 896741368 954714407 400141315 496885519 544402184 84101179 330987499 45772941 74158914 387596405 470750764 456649768 876762671 988696775 901019206 250860669 647162122 809813095 460049316 635861462 817178689 496001933 428718076 43942956 65316613 831422322 273952606 481615875 782559451 75992013 278851554 629402611 57142767 979715774 387754771 375446233 92050670 430912184 803804376 277940901 418920725 383679879 796827637 271132618 198037433 814124662 954783457 713214261 415514913 473136569 78484398 851925168 567415004 196154291 438278995 738137367 756187604 749999132 565023991 642961336 529733491 136070680 156040942 550600143 329864660 177857244 330362963 459368980 870275509 25464029 827895575 311383259 603624199 485722543 109157013 104881189 548837288 824273556 190337101 450508218 310795894 388541173 176562823 956328160 899491532 323341508 310783199 725336757 219704513 539729317 749369536 44011596 542630117 198601320 2653213 100 645559818 435905271 567346153 125632548 888694431 808112859 90456089 891788715 609044733 932223967 203622176 154861665 84077981 129091327 799630250 564712784 291131467 734028407 552518219 656601867 672607724 219328032 908610671 910137831 610683180 760887332 953047692 452765774 609764241 397356175 592124455 403291534 502067804 79679771 852022075 625381354 490634837 319638999 307011498 780101468 985130791 114912865 300089635 308128052 701531038 102375729 959712175 770115267 505391064 333298921 483464391 410029522 568696250 135869016 643355749 806918268 206603520 739296376 572311967 266994550 778793227 799638527 302414107 440354637 619639768 456641665 229414610 699186380 175076531 582367317 530105941 291016648 583157780 149250032 31199241 781744230 623950966 526846986 775524413 139636437 536085435 346467856 862369762 313964269 747428519 221610032 910417390 873605979 99015176 310884485 728359907 183013679 614071978 76274253 933253579 195637743 956251346 115484201 254092810 955480617 100 881429924 821372289 266889087 981512376 826462654 907637471 473105118 578125904 629010008 644497309 175433636 135134204 237633167 42392025 192276477 382637528 396577048 480181124 252799614 615065676 867414514 9675105 721657795 822826344 583254624 737008445 134434464 319386358 29357426 247647658 614103488 645010874 702485287 652257621 792012160 576100111 751010511 375260408 777614052 326115337 325119675 389081100 476390601 296822174 713560163 155879140 840132117 404031402 416780653 232819510 663976606 428898878 303149952 837714578 604929813 43530170 113184961 16454828 327206745 340344166 960182871 270511102 953740543 623365706 909652648 719940139 150091260 323407743 126110833 232314254 89030049 939138018 906678896 23468359 987282379 280301796 119232767 997250963 758798526 47652232 174119928 520419296 673977237 370797952 899594205 51924342 517897965 133260461 329160735 253142872 907573394 301669008 719131813 205316861 913698924 768144358 272985483 100983221 298109308 133817150 100 154414901 963275660 116961731 49645258 803478759 830908441 911120613 402858006 987741733 836034278 620384506 834209874 547954681 743786530 809939754 321359263 414390121 442146417 986688424 231479410 956582728 501503557 587216789 687346711 650467784 284770871 521386239 960716709 585053227 470532463 307707815 508526707 374620470 604510759 257099010 823209490 176237404 578257832 802734701 950676497 305833037 772493683 322107913 312635138 828373821 72260232 561987886 957985966 554116379 345662691 792487639 235867827 891260904 406556229 505636422 70234255 118802450 907904991 170914040 689732763 812755772 322361982 221330868 542014819 425552434 47797240 730237484 205221883 180397926 84854974 251718611 998883963 859007856 770053327 992207605 423278057 155205143 205743386 394388617 190844918 746549499 703997520 616114381 514049342 713150496 213439472 618950235 394068878 744845736 322905881 857592520 905483137 369346878 51807994 65962286 828544462 463110563 574555765 596738929 906498650 100 125295831 285143131 933196423 92334446 915022183 597272664 568374858 988735338 783458969 455732625 36592341 617680894 476258495 299344900 769768073 788914104 424412509 767884464 325048140 746050081 795225105 711153590 641981186 24960406 757416258 190485264 683705777 995717349 838978307 873151029 189113569 491044427 365298625 813038507 665159337 981129474 904464127 240955723 787595177 501832115 82268513 856450141 830100723 629275059 198373482 922407336 739917883 945164770 746798786 7257691 203547177 2096466 250949849 205524438 898528301 240145301 593012149 765645571 859566897 631014749 741839575 511094868 12576098 930388667 687449703 501556701 244515429 139855019 548951441 444617696 645435787 563481806 671011023 679582428 206719300 400469546 685666426 183621484 796078889 602199406 183565751 110253522 800772304 156075816 673432396 882609832 120991863 788192913 566067085 924156903 656499023 449617543 428740099 836636308 496253786 135743388 732404323 811934305 464199847 788685782 100 693807875 840838756 112537771 625597444 645308181 159275898 240157168 622552579 483367151 362948610 474814068 624753770 25713120 759388652 160528103 499597000 406644130 903771056 28819238 61064193 704669657 251814664 469147976 562703814 636439025 465418683 678582147 243415744 237426030 275501758 993146595 816363790 789985951 416207403 376290321 289327983 233827820 857337977 860983654 255502115 589627294 24056874 947893241 169926763 479943790 876523013 660959858 665026139 340937030 137665290 931380580 78134452 663805876 149439162 646560576 705057548 837542984 690480155 691437340 143090862 199052232 110727622 26365115 570174664 178899561 709270939 569384074 379520590 667394683 370512213 969350691 245277279 618919184 694429540 844270656 746562815 551189544 588535516 919137303 127541294 279547343 951895001 304381682 256385073 741134589 795373261 435489774 915670329 399494157 146516016 315782874 30174655 440751563 282145588 29437612 936758370 16015185 169552691 406864764 831193116 100 982915814 322275584 372316195 954380048 305848579 615288109 380424254 679325065 55330933 133331003 561040858 594916710 77995519 11624726 719480351 727884219 11831284 476037280 945966467 844085216 296074720 257809026 640085817 284256813 893928876 523341784 372889211 974621937 769920710 855813131 426965148 7056716 162627631 36587413 984216569 434207689 664501587 930622686 692680428 596001894 911298625 412483888 392115304 281510026 242142294 473284611 261504286 567705036 68120278 568530649 13977307 242412157 909456755 273960076 279677044 774836099 928806869 339311542 166589111 579576532 540460357 324170416 776977729 895408781 622686359 722022436 160139294 207980929 980634970 635710225 623362374 927252035 850773798 963103057 5178918 1345144 773636394 466514273 967357230 646160243 208398145 472417028 813579245 558072963 302582961 986970018 686961710 860310319 13063394 240218176 648755968 283341138 117995183 575179414 90199101 489277711 979964996 519445477 6929660 565985911 100 173548768 88562743 380347521 283505375 849581618 420003173 247484331 718265643 230366941 521389114 842565677 509385795 120757539 586549212 823070059 35398165 316919804 892791675 225996011 460659356 409924026 499587137 628867740 42911924 1540206 180378656 69990003 635070299 87166270 34328790 565597326 431346073 988035144 356114086 884044182 874019777 20131889 729447404 451967073 903402382 319084930 234280014 168991301 214465569 493421585 629432649 326832374 491210848 667088464 459212536 235525712 100284194 233712266 726708847 697670560 2158716 609391022 209705308 871000229 717798465 517086890 993494775 157842188 14614584 330214695 961214702 267565157 596362074 99560257 428508427 276269724 805431748 120241500 703951295 967374048 788747784 526722745 142421397 257103079 943044529 23069159 82348653 55851739 633615302 670700931 370906327 782466115 682344611 944608302 180482198 580963348 650653594 466326214 559250828 660970465 752648382 363021147 323907097 493461248 685808568 100 813041202 944335106 335758637 716143992 78288467 966145281 918621624 790696049 134778101 331707458 567453906 455050861 564664702 580203474 760604019 649644743 500817491 876611442 549685280 633790363 464536859 525721246 227431305 879790868 752983357 897280743 488949824 476296627 454132994 818134603 582052040 466939574 555069640 230365670 596490711 550854355 638601421 243060262 874341570 24661389 36725376 413100177 790888948 512780865 681962596 620047327 281316085 25728959 920442752 741694374 585290621 525893217 211802126 648223822 641954320 635484686 835401511 99826424 877408069 663116912 461237498 270490024 121853982 711263718 319839131 80893595 352760188 666290168 573807975 412914876 668967741 726445896 103156830 229730586 463366002 47063623 691718035 445480102 31926407 32394406 449047410 377307085 68938033 684481501 999984155 189803057 878584070 370857547 278739192 107385242 945904927 478360572 515993286 973603346 506090409 410886614 699146720 569231599 324307993 172962126 100 976055459 28305427 350377175 269625801 231297441 185644439 3596156 818665572 301641839 6104666 29846564 750279413 242036623 814560655 827442617 94859070 677196776 674307861 397547400 159253093 293476515 780725669 711811120 854640927 442832733 687335278 850941523 360636689 520854324 707735121 906187765 94426972 138091245 572297796 895972604 47020577 933074996 353982043 679672994 136681333 267852196 172075563 637354095 88478200 271214520 446160524 528617595 557989287 706747123 409007283 65151838 283980883 82786950 748362648 483049445 153328573 551044241 792562454 758550333 642062366 744292178 143429468 119307820 192122834 562637974 162748887 309048844 829275127 374677417 246466730 401496146 434850131 575697673 387475675 121383064 445832224 141778701 992071765 474328909 579143412 695721778 26972505 56574213 79418691 386777331 831673006 540302251 507186939 216075646 139059239 386115576 761657083 414593946 497107216 496486227 8266461 691176378 3437131 508392364 357613354 100 349233213 287130384 49511527 164091347 372375212 12854210 237866362 131507426 105830360 115242247 160882774 855594819 488214575 537955324 991577164 325449954 660824691 426177267 157037311 113740589 437702840 728075444 246871048 704778274 795658848 83166924 244453607 83208904 884616878 693660093 984236818 123934831 958297942 432002233 878372627 16727334 831275299 602850328 574966921 257704469 639550153 720839538 864323403 786474301 985925264 974372590 507701915 947104370 15049330 507951629 631645593 204788338 707867264 413324781 791771492 897038294 162984209 881613532 337768862 117726242 680028216 30373621 304468140 105698575 44057768 913252125 279737814 339757579 796515568 233108333 372505528 110235020 257868151 185705159 470650570 742836058 380378504 56442435 404197498 693785200 961766716 939377309 459556133 210043499 237976440 7495162 514046304 702250547 813049784 594118620 356579029 634948140 822654146 572647373 839867109 501986944 689954410 665060931 265772465 517877188 100 121309441 722901203 388407580 4771148 804715140 58120674 427040143 394947377 60066756 449621130 516217650 28785933 884980696 30441612 788724939 183789781 469851110 776100452 14813927 516674296 304097076 198485574 988742517 22408667 946171653 889305834 574644168 63722061 797367922 689674604 740849772 860433998 360276311 63683272 949336053 969325368 547991324 155305225 215819848 34224247 510612410 913919121 532954028 949862074 573227211 919126048 419257083 402515965 638794013 296724590 385553264 456488610 435003601 346684448 587755078 459907152 931373405 347566609 981806893 70685586 948769482 823546028 431112800 254636695 530314895 211612424 681764802 7222765 169561227 718554864 287622289 633064635 54563620 125623049 485449487 472571930 777668237 997365340 685361911 156010580 976916623 839252510 117287755 614330326 787914107 463252240 333122042 790996367 340886780 910955808 422582511 929983736 550653035 595324868 685660968 513770272 519149212 615804148 30043267 154602449 100 642402843 134238039 440250083 855519984 467827683 990636014 513514509 488165758 825665412 244830824 535617406 83771993 20338935 410508343 918731493 14302355 743515634 418321478 386736746 752423725 290318237 906103360 966977072 928734791 129661440 2505332 895371288 23976057 765878824 512558020 738189105 790179001 484820905 182750451 499293469 568856195 428291709 22229821 523402293 815227973 866563748 565985518 257805029 203618522 718233062 94009263 686026270 757446912 535504720 514429318 374742493 981022327 214377567 662949281 338990977 986654614 653431291 210403758 365531221 16532939 570339189 883035553 25864387 965072764 927155486 668945734 746771829 302652005 677842066 570551556 698289142 705028131 659593803 616681582 665551893 856307468 475916607 84864624 746467073 353296786 169925073 893006860 663070458 747448648 927147355 446905767 542544587 197768230 878643822 962194848 273317398 23052699 702168243 178972866 424093836 656721451 381384649 872387081 517464439 504819931 100 417566863 597946215 565931350 845518357 925772926 652422592 917252874 539742827 185148608 950970840 136910193 706789889 574797127 123147759 177286353 394818125 674748841 607264482 281878110 152434121 769160023 948132872 801739802 110283577 363678939 840838263 460688768 182602175 664928834 602973527 96393561 627253037 80792280 181227286 393017378 991103458 313327866 128215918 751178026 380373423 567184731 346316987 439088372 257979006 363119896 364128965 524659287 565720305 668423241 95350316 688430305 31102412 642279168 868329396 626535661 941092012 26018876 863662460 186307759 869660523 842635813 750421626 266344660 95597418 456995519 543546767 256870082 642863315 630223005 132628172 414699446 40356279 503995744 429798137 807649283 854130911 289634998 756450406 661848199 365082121 870621597 484893255 27815655 513033957 725777382 627854285 60780767 482128786 721045436 269632692 367344227 614495462 511203789 628793444 425282032 344995367 557507351 789038649 210668861 82533435 100 406836019 980572755 199572489 204812232 716764317 388370083 289344841 251003674 946055760 680688096 347501945 701628236 465543339 254497800 393279729 447083999 380193640 495963151 463280007 660662804 102013977 159705057 466133980 677369652 149746274 166600961 291064377 50531861 303746842 534005667 639180162 670374649 679307161 251574777 66169416 474776268 622808172 284199977 913338832 466135596 13098253 656807567 182642698 42643107 331439004 676123055 260740899 993367026 249640794 179164863 939333964 745710650 234879657 417103342 733874764 122673854 935428412 534440549 492811446 923481209 197216655 816256043 981033581 268021282 794286145 736815901 335288440 571565457 990678479 714483110 189262414 228870366 140984962 208239292 771518444 841396600 781000606 472191435 772379195 133718457 833511278 694176420 196393551 464951729 56118093 326960867 853097438 448119738 919429718 569326692 457400812 266774164 454174116 400499774 867809612 121182560 649816393 700555986 334292227 573654826 100 439997659 640190273 444208749 806301126 672313063 740556786 391978992 636649446 173322951 318771115 124674418 922033853 890592088 272108380 387802286 744308052 521022362 601132495 596159957 601094125 232848878 851127152 603400731 509685997 849212795 69414288 141325172 890347906 138537144 519070050 831559153 205278521 730373359 792169092 160874342 126470882 735825808 617527275 321510022 7805506 410043301 266185143 120013619 189976167 755579141 259187635 466883765 550355743 944852592 525578256 8966620 840309217 646962563 934882116 401944599 320622198 234265645 963002329 964746206 785820397 168144459 367713913 399036401 162201495 569583577 970334371 697242173 129954753 237416832 991599782 266934019 155821917 633522377 377070363 277922130 865264864 846283086 586617808 734839384 673743488 777289697 509559214 189906963 259892691 105460161 980760108 61758727 38086588 619329684 510530175 346589025 221762462 368756191 504224032 318697020 823406664 214190385 36213132 175681068 501556947 100 478097272 563427067 328555448 866334352 958761289 218341064 549504708 390910590 729638965 227486074 750021847 622455278 728586453 32307035 156929025 798209520 7180894 934647918 676719637 546923001 744130979 866756304 899488952 55987138 388499279 903160534 637030580 331622968 840458344 307107199 837595258 980506337 321776477 674730700 500970665 27358371 192117235 407782159 887037450 838078938 753113356 473713003 741528174 57626889 814516210 806862616 738426706 936662144 215743765 192235114 394162309 535323529 642582710 684202345 263290451 30896348 462815500 215143893 805611757 294487793 6101766 764131455 848406546 419045482 904823633 3040287 778912007 10888784 88291422 80383640 578670380 534637055 170038303 391563522 564880675 551883822 256246429 384586679 329608844 262685786 61587244 932482140 494554425 342764523 181325755 651038812 236045954 783033111 18711989 124369520 895385176 7530117 102373165 881597397 942277338 410171627 791812382 966093266 286376773 550792946 100 587193357 141676284 896079923 900216592 953344779 307879415 201400968 108087920 566318907 999205477 645551635 986497738 107884847 644253906 589179410 536573578 76147421 505704826 887689726 525979360 488187719 186000363 34731363 304403293 96039338 915277453 255002002 19038803 678191204 730993541 898398828 551405965 732214162 576879909 108135964 227080749 211906028 893730626 52718785 842417860 219248440 657557039 21613666 720706893 451546215 901810736 364731429 902752714 531781792 550864380 228258748 516139722 838840985 127057546 884923406 279825452 178976803 694544580 514684583 580045295 230550889 215002460 364637794 574043404 825146541 645920087 516979803 842195014 198202620 98725117 511814559 963374751 391102418 685107195 392586855 840055973 674945315 9950769 756597666 526263747 399720160 477334448 980059469 428542865 512120719 164528613 845158151 497700136 15977308 746418912 986244391 425318746 343372305 333772076 859625209 825848134 242088535 370561718 748827878 461031531 100 634593514 255218224 662751041 833149286 208445680 365543801 642064314 681138879 973283470 68214969 664184607 390405084 508227808 753458018 291600347 684750346 682964839 947606494 84088801 862612892 511261470 854630611 965820842 392088376 325225770 776590705 821797744 914365746 429303774 89074192 425276290 93429790 537162303 783931099 763205428 310899866 699798772 259181601 296019602 580551862 545161718 967504575 483198852 565129443 749218540 698638698 308455508 430740610 483647001 332100709 371804835 974656142 946313031 119037993 737542546 230065942 601904784 480489685 869473846 277572213 648473922 816540475 529679592 872453026 74308131 706839468 27155614 442055976 441898462 654318273 903021022 197015882 54041545 494643436 997554340 718428569 127102 784088746 683405776 984324560 887897268 73522622 876792158 719021126 678689530 881290805 32305588 814200170 790079711 487981116 589670971 10295580 201361513 956720553 645787403 873597273 469190280 595052825 471457911 810203266 100 539050005 711353174 477798510 179936096 136628863 328841220 442191789 112177826 890169417 224207809 934851277 12974297 487717368 865728350 708079888 625562216 863979733 126006803 713861239 765156186 812276320 557331712 627676028 542248911 746188200 927474334 32810586 504957878 941397887 141439013 479777942 355726493 794832845 41284457 903900809 994977668 492064810 83014065 980425477 853382726 972588569 177927910 826457711 602702312 915840391 945874831 957800619 307087386 675469774 239621030 707990341 778444605 446528100 450526817 944341430 679227317 323525994 29263436 276569325 354719309 372128476 444387048 956923842 822374665 526636628 792078272 808469176 290525349 488360073 372975374 367913671 864007904 57840193 893344839 522291382 463575492 508462850 703769756 257533818 821229741 50760648 749029280 457477674 715017366 457932932 838879115 850909609 434006900 38330521 744798410 350050368 483820956 429318613 855929117 414149051 475263628 443731131 664744712 23437807 915588969 100 243684284 300529084 231362740 713923469 245887939 572769215 193360590 828170443 303063380 177203942 761767800 392534737 366434105 868587214 717627988 803765747 228537994 229697455 842496146 812276379 977031217 748817494 435868314 530478022 432942630 351676063 93752582 339410480 151090455 489133753 808195332 908070199 149110649 95008881 641249994 609818747 808570965 174503192 463600259 608244596 668622711 600992431 296097895 225333525 714955475 549795378 679751810 938837290 450464800 478824492 764399240 974637062 884420514 639915176 149099952 419556354 939813770 372226826 597339366 803442673 59006714 546059695 655770148 581101510 281377902 116356312 152198583 500003366 456016608 528042652 479596884 249316833 613430631 173977799 821154578 637832518 15364191 341890544 808402104 950775020 755757525 553992300 633736767 175221928 600687675 931916544 97303190 884407146 384640128 644978084 652407019 966717932 84025172 405742268 790275678 862131209 879157978 160737561 17800980 773861381 100 4183552 961411239 524479380 940119040 11950107 771921813 788939758 434544458 434950506 102095676 176776270 932067611 822573296 190306252 472018360 71817360 225920841 897601238 47608307 233519638 980324019 323662036 229027012 442251280 959232675 858339298 772498801 448766729 223030142 644353664 897236853 558144394 187828530 132585965 596688121 500943070 167308401 674927078 523894879 272883041 666627011 677815996 972547411 743960904 368698212 461625878 901069592 173854170 452380290 812560099 489392626 21741153 17873954 53207446 436759430 960111702 312334538 724428065 600458188 894937989 602249381 687191619 597263444 242278416 882919244 315216757 510693476 193115452 897136973 625761106 336930172 798932062 979795294 445932231 354155634 474667908 891693793 649302016 436607815 984344265 757309650 971408016 748875671 31882239 984839316 247988233 8374645 769748996 525911377 131679132 967863519 875277568 873417314 406207874 87557677 161990980 145269274 327426301 800647400 929498508 100 471138699 79632538 833915948 836294638 696179081 838164883 989527619 525612254 286860851 356823856 787894523 814408329 561785015 8983317 725747161 395697817 127712438 686918715 677309994 151156331 555376482 269693187 90175744 326283660 18452926 216225961 181448287 345608979 326313237 451905282 598131909 968644288 714891426 23244322 678015603 406110049 186403826 273250878 196425394 640361115 696875508 579585717 386191915 995267083 918228122 586257205 13800497 972444772 189475077 685993935 427143650 710173454 567443914 449250471 806310164 683477994 201173776 581445552 481347905 195135902 496875021 174103293 516858834 465475029 965700513 751735038 559324402 590856689 899260549 146715911 166373434 125233882 259385096 392047493 767959232 221113969 923552795 498884796 114041271 873488361 756324226 377605659 276048309 661410742 760730619 867285149 802645530 539106725 39114147 940195867 690007467 211985977 25196836 703992824 405326397 94856689 489290060 734621188 488389761 458138657 100 932948867 7675110 850391751 889420922 146468225 521184475 990867899 174268802 744464608 487516854 545544278 229264969 881509111 294511909 578221918 909439046 940705566 662904245 561140852 26147934 201636648 933770615 746640556 701609255 289041533 373878407 55983261 53022623 540410201 270736418 313055641 926227777 875995820 210162080 543030579 295496489 559139271 12102831 15190483 739392715 470009132 568699899 371997788 437280063 317151054 592637371 27285733 645829574 800669769 729665891 320911381 496940654 900940731 511998146 429542725 20372694 162746806 928448978 617010659 124984867 925202912 35271080 305676277 103517346 993422112 950049824 59514486 393198038 397447696 98387318 60831288 774687475 802398285 812573497 611637204 677813672 88188454 89461250 308305545 670109517 16387522 483236046 546536160 759124670 15469188 459495976 590989200 542271185 484458061 210291821 958692649 945375555 288218026 58681802 695272241 939964563 868198699 9913178 374294313 637445504 100 986994346 865457902 340127110 82587875 525577372 525416522 143160025 906321034 767228334 754365044 241100221 521188061 915446792 667214343 352219353 834363411 347259500 919941997 764290932 9198352 10307041 135077341 912264414 344689579 533116438 969456343 294759064 299279465 477504074 423778345 826099476 794390196 774610880 755555647 750845242 903787981 214574119 796488351 461923407 929656316 189284795 847928728 249146097 553122935 98637201 487137926 918633407 637605861 374464367 218197231 238127397 480351418 492565740 175417095 806148197 53780587 763899966 809006655 65292892 953410019 948883536 446685419 255411488 132116491 109111325 340927296 580896107 825566416 871412888 427029682 726764309 902049279 881039271 41761585 541383214 648908509 29357812 711952522 330563635 900467711 473768125 832316732 661232652 849871170 667104629 545496287 131353990 262870434 128398840 186239316 434776816 23392427 17420192 732979021 194814926 643660854 822700820 66658956 46996907 629995250 100 624195604 462688852 870403073 936234438 602674052 988357685 146618862 889187944 731193831 167982015 521365175 240051015 318356475 573416238 932066072 931242477 459243090 267262922 598219940 494540997 135284334 712513720 654087615 324188180 141130895 954797443 245240539 810323694 441871527 915738433 566944557 684482675 713001921 981976498 898396488 643986004 81685904 618252458 665452676 497393597 172206648 375594233 423305136 365818928 252922635 883474578 181209239 954947478 627515785 529471728 70133428 735783954 629704148 633512199 593871734 887474236 101824028 969293481 880625813 368524742 248012952 61756700 912163784 755207302 185124906 895341246 74587529 316411980 436274527 305832038 113714331 849157755 290935694 899226436 720779377 15536420 195554350 403834894 471612042 311999689 439152863 321687101 538689696 359302528 976543613 874995603 31460265 446269085 215469998 771116619 397869577 667198429 431061380 997441941 946609092 316963232 941494221 963113732 150744399 622378225 100 45260053 132508279 407146785 874929315 286194299 297801450 315057914 209851656 583911984 745753206 950205417 991005065 521770722 964156559 230681836 161701391 532179610 612338272 346829552 330887526 927644018 802399653 539401678 648251219 266564476 844339788 986086389 207199754 764005446 688037454 968715254 50878028 372816940 948581587 657676721 151918773 771946875 729115909 675849003 230073497 820500023 359608228 961347801 70083713 31416980 967508524 729438805 358510147 795520075 410763665 215096064 162474674 263664693 403786705 738188745 591338621 950082317 446862955 863579628 914795557 846872704 21820440 958529596 276996278 598800337 831937746 904847632 766412230 762526827 114643043 420524775 633115035 901418228 207510328 669130297 319150130 859939344 756032989 325701908 462335233 70231210 739174555 981261942 67561588 938737537 921267253 772113173 882246084 46879289 105189600 253868870 716624461 326394841 452646557 799532982 776151441 357450439 421188791 751823942 868865252 100 142000647 554973284 642716069 95000639 612853901 651490054 224588165 376441367 293764809 166886330 868300394 630017176 483342866 849160678 293378019 802278719 700830832 47244032 76008592 809884103 92902990 917390057 954126600 388923252 817296323 718389985 543966723 191156782 937702360 73344586 650202466 587308985 283103941 407618387 857767666 195764375 253529482 316851664 301473678 191759285 405484841 190966938 453202486 962588494 901736561 528999587 621396469 769021263 813972969 189496400 878360150 21532275 832892276 247008694 767658505 6142991 39233307 503457728 228637222 399062642 762313106 309199093 429231543 397765936 562294414 731367840 694551194 80093959 336086210 189708218 601346041 848906173 885479406 878012304 250459736 4001228 911356863 449725644 41837209 213711394 986731832 561466953 876735331 748066663 107822937 757510523 587640579 785751500 623758690 500184407 698563693 546384988 128846884 37362256 297567865 771175010 879536242 695005835 228534170 227417088 100 283518806 994859520 998722398 675093696 383438896 238152268 713455238 464048660 108344875 380397961 820220312 8988685 5896091 347096087 71503796 357598390 672855065 172604892 110866362 798510472 970936800 161188528 436676179 361854481 196200504 507680091 86679084 149580975 874560850 777118350 255901987 448855658 228062847 154848103 740224930 139749479 789796591 453180294 311819283 166947220 334108259 865318934 295623542 979458692 555874157 212448886 531440910 46546972 832128762 211392722 914159119 721307044 462427345 826702869 598650291 361634979 707659464 635135280 202995789 327785175 477796172 578957621 343509561 451969907 907624204 357927875 640032064 505218912 235359322 512305674 472537024 821732689 218252444 759008825 19573475 3349166 563579224 247527080 545634578 709943582 256073660 163390549 966214007 139532467 224412749 401959844 643604465 68228573 118812409 739912991 16950263 601883123 501282838 457922854 834362119 263752217 499677256 585396661 92639776 331616418 100 459496848 693870416 69347367 349780062 985361810 843617777 403933130 528149850 462737549 618787423 494380520 543285825 721109127 472780803 35235417 866557854 649753190 530092472 726418181 349759805 505490047 901377704 846249757 314645854 726495471 301665289 778898773 92270345 991453850 871511926 109387331 108114844 982240701 128605477 169902373 942688068 701286097 336309016 673585026 930054213 576885298 379179753 346237300 762820732 909307432 807597600 739827705 319310153 609220651 956666503 861885548 915760090 500579120 899856538 559469990 742188634 38194707 271722549 706563190 419113809 383000775 11032703 562698937 669740025 429695081 526190338 106178979 973427840 556915222 464384067 265002804 300723764 623936425 166855056 85362817 424621238 635375676 996533154 861947095 39013687 430632549 298754397 2318039 472596540 970480781 790641621 46741168 306787276 6450173 787680204 597189022 391028914 566287912 486839891 774240025 134293224 526586939 863356835 967375221 383100946 100 332012595 991932617 51903482 851744391 765976007 327818749 472646400 456407038 237702380 156406192 94912203 417027637 136510240 952556099 738234401 734579630 63869192 363883055 831580661 504685261 870461943 887841843 692865382 469569460 86964853 560380390 433165360 710992054 300135603 432216143 136407853 977187610 12350536 96701644 196807510 770665921 315064074 845843144 651515658 217480031 426207442 585730015 26257793 773321994 457935680 154751967 888756872 90048999 336970472 918726762 758112892 538625274 355551965 154365872 411849891 822113126 439288480 496648127 646118774 186450436 899932325 734473458 432536428 384655025 781166102 325950342 757714036 758449784 510906435 615369435 157341173 712331654 983732488 653562387 768163205 534494212 56129573 257936061 421691306 393869918 128725827 405127160 658003856 343176734 422949970 600023292 221061955 417373363 818727283 852124810 641209514 113170394 48197670 195365244 46847130 739229283 457892935 98555811 4299717 38944879 100 166184204 944009478 118240665 403945548 92916973 289946443 47170430 727561441 842241464 790733153 849083043 300226310 477975733 412444727 806590337 850051381 28709594 548646311 68860001 756413024 602394687 160897560 672781615 920668463 839084814 915443027 770773471 619006189 126670717 689753035 797409785 29367122 481947405 982785927 361539770 656031107 946896540 564043631 669236983 746807501 640990542 148774479 113103301 432295529 704311407 671125357 994599854 263482041 80556861 802424510 889490138 630474944 48518617 495886593 500119777 906597617 248225395 577135117 531047379 970273104 199344209 867242989 187763846 421080140 98510231 622615709 498923798 487605100 993416804 201432245 173546199 313450272 391838864 832720890 98446824 373939478 669330683 523666433 619004086 52656273 198423330 528710717 585433603 283931868 370497104 551269406 778323440 589771732 607721266 154579845 437714347 684331747 230645354 911134482 90103144 502261080 332208290 542288391 925877925 23047948 100 985839545 562793439 652219528 352349709 582545629 519624599 678713762 382790107 390743661 641842109 510861339 172587245 187359987 798974699 141428344 646989579 823368655 456930968 606446257 467031135 452936428 633788571 818225959 881132089 266422828 426583506 481718028 679998702 487379422 501373427 349756309 136342626 284098083 819069111 444546955 316490319 764160822 271343886 885784015 870136310 871408896 604099214 69192652 789953262 488519408 989825566 553118549 689049693 447110919 830182887 104903491 253516395 980472936 303230582 504312070 669587216 920539957 674879290 565420260 172264527 979210125 809253078 780122916 769414967 884476044 71999761 572369740 15834320 685372184 260538288 721856003 438315552 80502153 708253054 85342923 279100869 896285532 89068347 376608489 84231959 397692577 127677542 573455613 50939109 878733815 246067273 410641433 484458503 327518341 501337656 210714236 69646019 266397394 166709094 247748074 514720082 93717112 695282230 207172863 750641335 100 522918296 188488357 763702183 120328584 861787486 406699420 607189195 927900273 458153986 267938634 392544053 828421332 772281966 734421397 671441432 211931906 583738202 797084178 957549045 427072066 910067438 713672706 68905090 138998369 89520838 551572615 266003864 430951550 923728473 856616948 191496186 46435096 200236755 219614905 58441832 578967167 501180555 745709810 20762667 644132369 784940168 917348397 83717209 953089485 932020881 317663986 244054022 340569120 260125320 894979681 110500954 760068204 218472060 543013986 874321813 243838451 621037251 629778233 331242119 190584229 369269919 616119840 723140018 341159517 778331175 627061242 92478317 88851796 668721078 537281867 347852743 941779460 145650596 685593614 633230478 970152499 490443200 59762604 521020923 106088105 663536462 640640566 463343632 616281009 394093691 414061492 223985510 776301332 776545643 780711958 611124002 395950562 459671148 741977425 608933173 831771702 561198402 281386932 489343462 32409489 100 94288493 479129013 349005620 763376913 668334412 935114141 128034933 951104251 798846829 936518529 954750260 139023021 516090677 591435785 840165101 507892426 151948976 992765829 500755235 178287529 31634476 837184276 891389949 860402038 832668154 198343773 836632293 378364134 50689299 509747283 407260143 439511718 937380115 69395619 272490499 724470314 822433742 108563289 932702522 547753298 178654869 571797523 856623758 824419445 875322003 273148093 302257671 96219682 648173974 906065565 927833095 445792633 354118505 950375003 271170696 462256316 231740324 762919696 202267899 696113039 340113188 1219990 790396507 414738838 949987601 469124257 638455228 110913188 25024368 350143257 715693094 339685108 80832398 457495474 491715033 736804290 784937114 257737959 287305134 825053569 300098828 235949687 820106139 736864497 249324575 77519938 694298636 257507749 339283541 628722528 619977708 251926090 513809043 305134267 268843787 848374147 100703103 506907074 995951895 425009796 100 193571678 232795541 99788178 317381930 257393748 298684790 628534760 970735769 238165256 531797819 496408670 818886259 479133940 971557196 219511547 925636907 552092668 283001287 572378780 892226866 748161388 680353327 657025226 559420979 928649759 604841025 338221608 618624428 912555995 715410318 481538178 381793979 768258617 317095132 724706840 985579542 475151134 571571316 376824588 816497813 526745132 122905902 22465899 916875521 290723680 417914240 22936382 631667890 924525804 451361067 98483607 728829050 985366975 554700802 806769760 914292309 693804494 749872683 822629241 635624512 287361521 816166677 84507122 929844142 241434696 139046206 148922375 428267547 186161826 873104080 195486633 150089258 534689019 51270170 73304921 779873731 385781973 996472911 630008750 354499144 239748957 326727785 896606865 258696526 955171027 222966068 953008551 936216087 270610725 622639779 904451520 97523255 804323240 789713373 792641017 285639846 902864916 757115511 348751884 702858837 100 152145115 816524115 29180214 232534450 27486887 327318745 734035319 911057552 246277242 223846879 408982830 239225278 858045096 337349721 269546308 420873845 619774660 131372821 891326145 991114522 880656708 812184205 862352249 555961473 573818319 751547842 85702795 706680422 277930641 890411985 636322511 719380086 433132169 303727419 221912958 762590962 713422098 222953323 857710384 202762895 470834097 558948354 684199535 137191136 706723653 912559479 5030878 772075887 381906572 39151696 31220407 873069775 987189577 972687447 720330209 191754791 439447764 938450023 106637913 578775636 47147169 503591602 313547738 562646604 478803610 543729885 986944997 109766590 320086634 418330576 19240861 799659987 195721072 414898651 273558125 937231321 627964946 542528794 557785247 785274845 975549525 226883691 250044265 314176613 931627385 460517405 59188237 62514825 320447901 784278117 107145841 187263923 819192713 331926907 111285902 470192578 201340669 228335353 402502053 149325645 100 32523902 626525241 493719802 414661763 875596205 240074387 786617009 639789388 939355386 964928664 507670209 579446232 936667182 833073264 115755240 179109515 411677912 360124296 751555463 462638558 60084410 351304200 347545152 134460951 937878960 190527304 457524038 435439598 765464708 52253387 151471833 902161456 363036730 225563998 44193185 658348390 975034648 790105474 393909104 783675773 223865436 113391150 245133584 831902551 690616330 537391689 926003765 958076725 880571600 363702780 168305717 165940801 803279662 85929433 689936409 482950001 756677701 524654608 321569785 650632038 408784631 89927322 503883570 699691982 175856028 177727086 293803997 723194095 655970770 338718929 318492158 555187427 816254934 344448614 892581380 420013567 956369692 975477297 845755168 304381130 481371168 555267510 670231604 891099733 383414605 643615060 704245470 978123641 33646888 133378753 77996467 88319666 412300779 838507240 976645973 665377302 769036117 17902702 858826391 806411035 100 924384960 637009736 659774659 87802130 519351158 264000673 671864181 642450439 97953821 178811628 65270850 62038350 200017762 548491594 4911708 752003127 958782077 948637555 12183396 432002982 175001003 354964512 356747068 720462601 261853435 741035146 593728193 340270984 767914070 661281962 74095687 439393186 503844106 144864707 8567114 934240125 760731789 357399221 168812280 399107726 647530958 430045299 853267867 224943505 314894554 651689649 638981701 544760958 757659359 407607802 337260382 637620763 218940308 857159313 694100940 805958959 277563346 203522618 204604222 577805343 584539925 302396520 933187072 319240295 444857110 472685152 920462832 24965922 351470433 181964846 950003806 58405556 335109346 331665089 578424134 24554056 930254805 942167565 824914605 941865199 407446682 606537373 118726447 60275976 900288389 859683916 783818819 639516490 297460901 556519069 476943074 314312231 843351556 112906414 996879487 64271571 62045112 688861012 895037310 838938936 100 304194100 552815686 839608390 782465506 2920940 582436530 535280920 750824114 574009546 630552761 421463503 137811859 283033608 18465990 336450049 85962556 523320763 508728890 486022959 367159024 450864165 874959451 784529556 874072573 338243062 373900464 126562796 395685829 575474869 502644691 239515459 939242108 976258506 301532381 259716200 85527791 713970615 485624995 542038868 222339103 881539553 114490543 34702904 626013012 305306145 714663768 808001004 243831231 777514310 3192624 50315196 644614812 700116007 430517692 136440927 833661411 174544199 832416961 452897016 200941204 871123301 784350232 558811985 442007391 65333090 238925922 282642310 772853896 641567603 782400687 382188186 734420367 146277922 900401558 794484318 816175607 566763478 121258283 268714699 521248642 516128570 376085890 629751136 341674552 630925162 327722786 340043383 671470978 4560027 687994342 658992484 944504717 17108794 537945089 839526888 456347908 986632638 113608473 733965975 831298708 100 490526988 497247505 671235094 435615665 153225705 69469000 895199842 633562648 509280853 670337058 779719517 101684759 522965095 236533459 592968049 152219467 437981121 417255853 421441317 973254939 411595468 713903427 725681070 577563009 198525207 55356581 438614885 82998567 822996916 578564469 760402944 802978130 921393148 973973776 1477280 144202931 835932180 629135194 2800147 759208385 384643022 523744468 721109127 685874225 471751758 932927841 405286175 266858741 455460060 714817252 780054932 268147277 317069385 333525035 807624421 3751054 434542957 460487948 699175361 69565035 510976590 85811297 602132382 732524039 281465282 667906176 155700196 378642928 941242043 617905608 210593457 844894107 850606619 237219793 447639507 245604405 49095527 305536084 992430762 816243867 484800529 547399842 297671596 298588639 781697815 722860546 353197226 531352865 998874018 823834054 362770364 947338730 142851878 157913329 405813743 500769718 334508883 543468692 390483176 225240725 100 196879916 28320434 980298143 434489467 118148415 147641959 735864545 155576400 437135344 455302992 1319390 323056738 516767638 866619719 897639446 14036193 633313752 57761696 405561209 906102682 242426788 493630889 395391967 271133309 708170097 285956503 521538381 552427848 386280125 753444780 834411805 794781795 491100337 302444412 461487795 206977337 284821737 671022470 304052837 749206321 414762800 135716947 170372780 354270637 26641718 888162242 61516435 270558424 606902400 277892539 709523480 821378359 414495986 533952939 974567265 125940980 779553886 830577101 332871614 718570151 51502340 802463120 655773910 910112843 811678404 670832966 793482736 909428813 945506821 993771038 234028559 313426550 661974998 91545881 148317827 920417001 941501528 913299535 753525341 977393549 802038411 646945529 294324244 764850381 920098632 416947115 779581570 137228058 857436152 233110103 275857418 808068836 693129404 108455942 710343094 151984026 557703107 258805221 259509725 959431548 100 920733733 750892466 329325531 7048560 752832944 555881802 837841449 767359757 738879465 687489428 396074866 773473515 54791106 571652714 831029826 91497329 156968796 703850335 280054199 392308582 21782181 476274734 657599399 645222456 275272174 285922672 59466981 272141359 457306075 246424478 804953512 355714488 805950117 918737960 885775209 196152250 801015342 622766518 352472589 116669278 218314026 209762377 97674575 648547111 380674201 901016435 621591787 922306537 498349838 912656320 798983063 646683015 766790589 450673514 584633217 79458634 643963263 233247384 230484426 397202640 5306425 436343827 17034734 279916498 396489288 777388862 616225717 180912177 928801621 363313658 9672126 552468544 454947522 168155962 403406845 744484692 274649760 727487126 468056814 105036437 458427925 490439640 583880256 817221342 965499853 366590552 521774664 51319575 50755740 219528482 939936541 184248910 806583067 149359799 159359542 849268341 395986900 981269674 784502189 614022996 100 705427127 115485774 375049922 745403462 761480296 403062076 204751457 64648541 540230534 10782127 811822033 112152974 965283236 137392500 271738031 286711497 759060727 558431232 623816944 289848126 679213292 557586454 744501245 604828214 25933465 384503728 58507522 458829220 543596951 495377254 309958826 205436074 727257488 311539752 298500064 62398481 563488459 393126123 53693972 696273017 424497066 217395062 838159904 724739524 773152729 494857038 443220063 820834779 747211957 343254543 766993162 601944006 511251550 228143956 152548505 11731349 536499678 57726884 376192594 653409812 56185426 762859848 787968769 679002366 108248944 798149500 960499134 91434428 301476000 403244208 288994618 496091463 270268408 620490525 230008242 529777146 910499248 938378288 960362248 650823419 230131352 734829027 19350209 443315589 645652687 166509247 619241081 414093120 638772716 58714851 640519507 228206976 435245939 404970574 304515241 729248511 297424414 502021022 895745007 555228104 100 797454865 650239350 778162199 98005393 738868540 572344518 311758280 680264233 808062803 978785497 610863212 473177404 3021948 751524096 820653348 355083818 87060340 371594113 178133848 654413490 680688331 65589933 541022204 907481085 391955603 964529488 585104470 300182520 792039677 397445858 609852700 323284290 878276036 958581983 192160910 974564758 560603591 383689725 139726118 517597052 95304463 493464047 40838592 493178665 741595904 799188409 249072875 181020122 411745114 803545662 651509936 815146788 748562207 583487818 410633722 827397847 681512907 691195158 201966442 596218615 412858491 308829802 926551319 379147653 99290516 752181709 661816882 822241225 950940203 975483466 817292747 240769012 668419747 95909361 487573059 765103699 787942718 974004434 29517026 973376848 608183011 58389648 3007114 174433577 519917613 446159760 569541742 187996669 921433418 315330645 941064926 760639821 17053414 749240939 209021517 514198019 791643171 352474808 156515663 750693593 100 901352994 756890265 690211558 644215826 625270275 801971833 144520464 269199963 61196124 253456950 691325382 584975277 471735653 782521807 958336649 156497036 285692702 382829092 961034174 487052272 379465526 625511543 789948155 587885928 84029638 851104867 95594479 460474967 555667957 506020044 169709948 648661413 997767926 718015711 540106653 984415209 991780305 310410286 556710963 788777234 381689835 638323189 553219232 377452954 173322876 426300992 426878943 383124661 933361948 634915664 645811762 715185039 810966273 738693755 248840179 277148764 802313116 926221126 149111529 193477857 812997299 395815853 715510454 11617038 329893084 975268558 194545328 136749715 122694867 712142130 911465250 73184681 380585979 97741182 743913992 539536146 723052399 848825018 535768927 650096279 637324353 590450210 422307179 283962371 195145003 514832516 380970527 512635745 136658890 823180806 746302058 378227137 982088853 730597249 626077013 330318673 107483139 954152446 481911446 575190353 100 3664229 164537025 858124473 805425638 258550118 396746963 990038863 479835766 890329539 638821763 14515382 407094353 149417123 647123890 411048876 942280793 625514794 331248490 531291142 864357985 262029498 628903341 167413928 170376388 860777334 520123597 148337594 634255050 279710038 97902881 889235391 436095765 126963612 487246237 504389048 413438600 946163283 516557044 367242968 737381969 349623004 512355694 365731236 601544608 457375823 346864792 910443855 387207918 576385826 132134169 848313805 312998045 899235085 2704389 673272616 137731763 271486776 610032837 769092802 73623886 577371564 387615749 826901703 225075542 396419079 290616362 463775987 480314336 390329349 111958494 725897220 94852327 249507540 196650431 518777304 466280397 144418192 813288260 952766303 57638476 267352577 554563506 648853520 83520144 270631820 272878050 930837365 357164293 486831487 474852059 551003515 131517381 777951772 725196094 977638998 897804834 578655966 612879831 714675954 867191499 100 656228422 179254588 48113747 895786481 485077717 105111772 753046026 467143907 475276470 681874060 420554771 7985352 301493096 327611752 298878323 293121151 555339287 675085968 380960309 528098871 286181724 398104463 366679435 197954422 285573520 357799122 418541877 138768147 904265371 334789366 886248617 83925574 635778750 237838368 534083271 833765504 493125630 102379087 177071031 838274605 255082587 559094685 49014193 753987556 512770146 482269177 735970713 16203740 831340658 798988313 293032031 631565747 60349309 881503125 564291175 204099415 18740932 177254562 339105382 813729527 807610423 111055820 789775360 744632390 908760095 611697157 230576217 906072699 503874322 255886058 266662006 122081715 189833419 301215229 23249452 438960701 600992629 23662568 97298751 37157126 833394624 592149440 515618051 425395825 568513626 933081943 191907760 891002614 94468066 685065612 711626262 999154487 14113432 470479453 218399018 968433138 868415377 474227365 861245372 530585047 100 192003788 822597249 970191967 784230608 563020051 484284587 946569221 523008571 135410071 281464747 282285490 27954614 484824313 964137701 547920152 704578279 549672198 857613737 678623083 333178221 159153063 226144905 648340832 699179649 936041754 390596910 589269064 320278588 561186049 961269940 271420449 246724747 854504069 701547595 926206113 10357835 2690287 692496979 933028546 934714459 437544677 562020482 944834056 627158489 116145925 605165921 119164227 519147612 865844830 26126788 480436351 297511935 711906467 235990366 150358827 325622393 978555422 959929991 38890953 159083511 131971822 492321727 322349678 905919234 712234942 699163236 840006345 494968661 581755477 605958074 188002420 685131354 18771589 386739269 318322616 791364310 70796330 633839607 785583349 451992021 66542903 965072244 144398466 257735480 85823847 3080411 360757311 285204197 270140598 174332539 213881771 276418844 862692146 121294479 857452364 913312556 748039554 40263777 458894807 49158337 100 952028956 638169860 613784219 337982602 574155329 132067362 258865298 653664747 982421695 479401119 918425072 616275615 345792580 612648724 598641886 540565312 149541624 364006236 564634808 742000458 580821121 34173780 132213741 315684376 29229167 805653581 67653596 680354506 192724148 199120513 2241045 697763640 756087688 385707192 553126782 79972288 722719760 53445490 284842793 514206157 886089057 191362509 164697306 256927669 267230604 486626053 741812654 564932229 509913413 34440796 360964396 161926695 301307187 932652427 263725847 321940930 650520955 871266486 647814194 986922495 516841327 626082404 888670211 816741465 577512176 301801126 77514754 982467440 581392098 414780393 808639108 280132004 55325914 129329404 160406947 666432229 299289486 1634981 898447075 244594752 412804918 929073718 51442491 600086801 904805928 505966714 794561485 977899647 97817445 53490180 781493398 164104080 79103339 110139280 460731339 338205613 101708710 277202841 486120523 748683139 100 194546969 73450752 826200353 727002087 170785922 363925192 240094653 562632169 196682109 840885504 628612939 170581242 197010625 423604252 296447643 283908639 416193563 670803022 344877039 900040330 326233824 922474995 686204239 388932156 422527436 639678261 161787189 850744567 332580336 292840141 825829752 483159673 452891792 206313659 604685363 926732004 239351437 528660262 36184396 209077006 64788812 898094819 899838361 283100258 368963002 145192501 379606114 902392331 741715094 702702575 359994676 37034046 101945336 177210764 92430884 157405010 821773228 398293439 138463197 648615985 345924251 952110917 56610853 700754349 539251601 607819073 516513070 152416504 782555336 603283678 157433523 59693128 500558825 629297437 629121310 654885233 189718139 499617743 348615722 795094799 463730377 732177222 706675530 423622240 709281853 885665465 374670555 847107237 721273378 41708647 560694433 812375530 188853943 276182489 289819783 791945208 239265345 866149992 853188277 504570180 100 273362666 535704391 489375317 419932382 322180592 687653232 892321048 202459381 261202766 413494246 963238757 130303676 713185957 165573900 641949487 966098890 451881337 102088482 730349099 517100666 429348923 488584356 286858935 238615639 384245667 125275947 325497773 763321879 803774446 749354834 492933459 948216483 869700262 151395345 774951349 242766127 891664447 428781593 129367722 948657818 303511015 536667748 199169202 258372618 304061574 918778854 663346012 80604501 14373877 432151291 423342669 772231152 668538357 829187892 994214431 992972453 16532921 382352755 6874261 162008919 860450900 843690618 719484960 99023054 473406885 744750424 170932611 475732724 408239043 211660720 230484493 466989739 711189638 121653341 221134840 128378520 650899908 466873573 997578726 314074622 372705369 875405680 456150887 638966287 554780740 591317696 166333847 488907213 166417807 914457947 532544378 113697828 247869662 916595883 864004465 901969445 178678860 807774790 350924848 149933842 100 515408937 279100305 586903267 728646806 572948601 117074719 948745180 160628021 894208740 30098659 161127449 263291186 409576675 560958719 971873754 728767176 939300780 325968418 763227063 820761915 235452484 360056431 60747241 754160471 211397150 88115535 826504249 704699819 824739350 738255328 611440858 890235248 365694232 660960494 516634510 941301140 630896307 905981200 258109062 808394996 387570399 68757623 23978810 64336458 565311190 475952880 160214515 173316800 549725286 771323760 333461432 858382250 269896280 790532483 290518938 679734218 3973887 525133011 475346054 676769122 180978568 242618882 445802405 776815159 9542295 609430279 261465539 854080286 789894753 265357703 44466452 32435300 57571865 915185583 60883224 577449877 512803753 84926412 697425096 29627854 178572783 608194152 542195339 977485034 190041525 37567498 778611668 149288335 127444121 594735843 524573399 481699544 720867995 720552621 127366543 898672105 83874927 95982648 310610449 576863887 100 213672686 21224820 827838241 211132247 44948340 146454422 983476287 983738358 805031930 422812217 593449180 916330719 912977220 870007201 838593087 320734348 65038496 7971002 695133218 108837977 141371172 897538963 792316247 862225600 654497581 60629790 423224847 363529603 14445529 339122453 582333919 720468770 411353462 254351432 396470290 116123166 90368052 555336474 994730679 370723821 312021159 99057437 823729212 379799702 228660652 721052405 71728672 811468276 581992734 826997751 821911616 845165021 859967471 246530261 190649736 516546127 27540544 38298423 376832487 205310726 454429090 430029878 268476078 880500165 856264159 935655366 981272027 27029017 976331515 651330823 489661647 216459003 312768178 185902062 966240878 982687178 28604710 632255459 836642956 918697683 504847450 580636473 812206719 79178335 857469582 404547071 150234856 790742576 193176305 531757648 25116039 476378209 725582193 114866002 365500902 143811129 282936582 856583418 44459641 46804585 100 630455945 878351687 131971036 515610057 552461235 436466124 188018525 372052539 660118015 216233632 174082828 894709178 107268846 573979326 325898562 677981953 973309227 452086773 566031708 876286634 33065878 285902569 766071106 196952965 930145528 854310971 483115659 493543658 750528201 355684132 286327303 541802476 410056262 319187605 378587355 476327978 712614936 951833213 314953439 638158338 851817764 339850146 931237911 471365108 640121488 854294710 39035725 230313366 395536460 757287643 924389695 546634795 191329589 404336486 357945731 848187671 313442901 907993489 744774162 180153069 9639862 835133725 195892429 131862699 691036713 851545851 304845183 834505747 79485653 370297215 47165871 419044578 558803970 149594254 391519709 499796898 789636250 494721873 214528964 708980411 304868242 683544237 896265744 603479603 220567153 872582069 826900718 921377536 510428541 475081860 351171246 338011314 399730266 306808752 362454572 786034755 982206915 771879923 256431836 647580243 100 905971038 279593654 837858166 878176744 515958011 726239791 873482121 194542766 131440610 482070673 335924824 522084802 207429016 429782528 881882984 398295514 27408216 197261944 872549112 517839710 884545238 685271626 646067443 677913512 191194836 913991037 232317725 513740164 430950821 405670202 265256344 829398891 80712557 153215679 859596274 615298565 853486013 724494188 512900812 323696397 730164241 886467385 115010702 200855502 171292106 451554764 255708569 266785725 109481764 587315064 684489576 879912646 228990924 167631769 402811080 995788256 689990734 260238893 578077298 421337721 310291061 958896230 106369702 544369170 554848656 578752826 921964358 723913874 647231540 37335712 361376192 695003889 403256471 931086677 508995599 931783649 894167998 760387279 991926301 71784205 321325608 349252145 464634306 77492152 354739304 444716739 333201922 727352945 246287914 752717876 213235526 423584516 340749298 358614321 503149553 277563023 94776728 390840536 713624146 826677664 100 932271191 171420697 313615134 510509587 85286214 662878007 352246109 666705989 986734052 499281587 358329725 878667927 491421299 614983505 979430876 612973720 245347708 870856823 214105289 130847084 992186610 539657502 777736278 107291354 536042564 588572289 618855993 815801072 288355106 981356958 574190411 378524828 602964923 281969924 416478583 688261079 682793200 707225403 89607062 544758390 412661105 812246748 533577032 392787102 75127649 112236186 653921733 706194875 896239475 984083627 138653384 60025815 533548328 53572423 800999548 735619223 387589311 299632786 546336163 813808646 292533844 25219510 280380546 33641689 612602252 344626125 626337763 929182176 273298892 491870093 637542230 394573027 989291898 926408368 689440952 920828764 633840296 187268916 347489182 192319914 202188249 610921947 702254304 206801461 19371993 843649781 284052768 427874536 925920004 422298480 183364292 808342498 555781234 460746718 584338183 466972875 398165956 471651616 235054549 788244235 100 15611012 820086601 677594477 240027238 379952333 656382473 518375270 78991721 100711486 34929375 51156512 163157431 680618434 293925125 869764231 949113389 786468588 468531290 71228849 929492412 571640793 481513109 735427826 798072801 324402989 139167153 940668741 539708537 259909506 620057855 128423756 679092230 311643834 267044753 899364917 701068452 875753920 692566172 318459807 469678768 347486975 699803585 164342620 379813926 519785381 356144513 106744408 123517454 221397367 383883560 166284542 838402242 588749116 882736574 153672256 637394040 792037519 428380770 217650455 496586328 148338086 101418736 272078326 657110896 877892895 62746770 436682128 99009415 927045371 459277930 454972147 645267885 244910556 602397097 209838262 459082242 596419040 14361787 869295835 498663465 239070194 633486150 733512608 798977903 111974275 776998557 951545259 419285352 663245936 680916687 614214397 820414707 961012674 643552953 349461399 147165521 54716742 529458661 960788510 774074900 100 676157875 506226711 947426005 628280539 115253778 774256611 613725232 476853411 873324287 431487529 384470227 933548809 215871250 430389612 513628882 526580902 207016887 925631000 575511977 611223514 588975585 157427723 528262910 842037283 983315156 954871458 151304766 557824014 167001759 176582844 305991471 302564952 214498302 340076606 783127043 129761349 248991835 512492858 914397549 659217688 525371571 123174487 864964279 989108849 685529045 507875701 447301816 472091908 566066221 37423977 393963231 935994544 160284426 204746330 763194793 884554675 820343253 728848955 932186532 717977737 246810084 319610906 428576760 937384038 800433184 51913749 760983022 402801936 216175839 277862005 998410954 291103269 972995475 215769693 433732003 178358820 218371347 297519034 11409652 775379451 197182911 121599630 372000726 69462725 754030777 337302868 975779098 655228196 183301798 501606600 461987082 942021847 102811930 609652515 153759818 361496119 599385690 423812056 787461251 105437569 100 830059911 438496880 460338269 188451524 586637978 48316622 803621472 729462857 805505427 63563583 246952951 456517496 32279443 822906161 254115092 769846811 559650903 503177797 534313352 29369166 305314781 606325970 430004920 729275587 148086807 795517273 437064366 33959606 829614219 541629432 197450234 23629117 926749501 782204835 515438581 785173710 825336137 495114822 165125730 513195332 197751685 944664512 99893088 960118938 2309921 24241438 474281417 835540494 995400272 31954615 638062015 117712974 850637492 686744609 812768343 719250418 796920459 629401262 886347628 497655756 922063061 414411219 510436448 325502081 666298571 416891359 876311793 284128628 362277757 91791131 281654130 328369214 926034359 16455616 652140227 728424886 369500692 511153869 895212988 168177601 870449975 167747132 709261222 931641683 784176751 795675731 553181410 643595487 828731491 3831739 178148384 995776771 332083772 219548798 567862198 671635047 621799732 399597543 663587393 592039204 100 161103723 90323435 80233341 111621896 275483078 498437080 397277395 762135207 6705412 112518194 664201418 888833861 94536476 37850254 383300178 475085092 605356075 203809568 106203561 738947692 700368617 296947844 778305141 59359184 744906051 293840453 558903128 199535420 884111952 29021115 453860738 951266236 539255956 108083090 989286871 140332871 582081330 254204 713401683 366811552 113873311 921018728 292269436 753584316 583266443 357379060 907805801 209835368 773624532 580159422 121186423 179341942 165815351 547947218 58665298 436798998 747194546 83604751 190105650 88140013 765630724 78100010 422706347 955597019 505096383 273257726 802906631 29607770 224355652 780338833 593639809 14926746 25948594 120658927 876680892 416159776 396348623 873183658 397237798 572946670 675536564 769776832 114663424 400576247 229722014 637600592 172860 65621172 155139947 28019966 282878026 104780075 856677178 734889882 82568914 953025809 989955336 129353811 311252322 106075146