999 999 187533445704648864
15490429 767501910 430010629 681509128 754797125 702630353 700900545 123061770 676159810 867340708 681845083 427894969 637322647 958112462 991962177 557108648 323182800 607022535 652901868 961486467 904236577 670302146 582447903 367971668 961583019 408871403 574963750 227029946 563915704 556641960 689594393 506891313 912717308 879052506 147018776 710331215 823121620 401539354 552067726 928120578 289211016 299646206 800434287 440149972 12176521 46813267 334963323 185785897 534968501 593904738 337560187 135083902 991317136 309287213 675240065 527642025 124278411 446859952 216196138 930964509 884697919 288902690 390927324 789329188 702396080 957797171 39248906 716204837 85395339 621582158 459787373 889091037 688633962 3240150 796094794 940820391 751999756 112415850 473277104 769733814 659054495 564399650 864754616 559494743 131316216 104636625 761802693 165117490 81872087 836553027 329747908 232541064 958572838 777024382 949321066 310883955 799681336 372733954 335858810 741403434 463904268 682341643 629273598 973148476 41412232 844551627 198791563 906803410 690190016 909653938 201249407 957587951 20165422 169748392 681612612 602604465 206990841 672350031 499425420 289084303 261274160 950626883 333993620 562125978 147775758 299236187 382274659 311789246 514834229 642523111 834274058 804761599 308180981 628129009 17085667 618910142 501803651 311417470 416565971 52213748 261180228 945081548 994072457 655097459 371947265 564114323 964754623 506392618 58268722 465721670 351238774 651641439 200101430 656477265 398789691 713309684 52750998 421048922 397190246 114486436 474550343 75163009 562026839 969300036 365347046 167239073 56533690 38182405 302556155 879065487 923410625 158776750 6607929 810763864 631015278 121582307 520863418 491467396 426708424 849179747 315755588 491282263 484196130 713142595 84214408 257178636 280627801 866520630 656562015 800874266 809365780 421896902 858623501 128992113 386970372 628607641 17145984 362523579 20810531 253962926 738765968 563707293 969638135 27378335 691344190 392534773 891165645 851600351 867102198 385615131 918830592 361043195 525168079 86089250 318957617 247023834 40338119 681945621 615645326 913974783 935443209 446722620 970121741 157904323 504532008 567804502 332250031 225339293 41863779 355446238 420358591 848471644 142421985 387117385 907515666 473640808 112094708 852301124 426505799 213823494 224844376 983823863 414644486 538752659 92993650 169443398 864230722 939702214 554668178 806345484 680283769 509582832 983695155 433017440 482706672 624101436 196002872 438079697 996924665 142528497 562486831 126632107 862612526 497763757 697005967 175552306 681161397 476597417 770291706 664782820 92711035 426028537 486781 893334457 44601467 423595466 602776013 215044196 145597942 945762468 732419978 827833744 892721082 100505768 526393726 921004581 104440158 128837841 856402908 473943426 583434881 259605556 657305987 426085058 194248719 282514753 463937337 769212409 441054078 552768257 612978418 780372342 710072842 319682648 684870920 415664897 988354559 871703874 826985346 450806043 983747565 277174295 781891919 665733698 49052659 296063176 400190858 643797036 196337910 544308257 303787701 831330568 31608808 897870087 396879359 19050690 84103427 212909497 140754048 507431998 761623821 116269329 130009210 944858778 552392340 442768834 324900503 754961006 900070193 950367640 527864111 189178636 454113478 534515389 620882304 983125954 229584066 84362992 979478262 361770772 679414617 404344525 841621602 310131204 91252430 842993930 248473925 458273100 172886698 611662773 293719812 747351200 998384900 332929913 675144754 99948015 964118456 108861655 24121803 80847008 601317810 548450671 475389556 48737495 834498082 269895478 870920126 239960239 782154183 348007359 773859682 908104062 731760679 709089653 356175493 685752598 76902098 118976220 913644274 204148480 864522403 131000277 289781860 283648960 297104640 133533912 771674043 121403926 75738903 584238649 447412803 827840569 434146081 898412901 816145651 251432731 957831585 772339236 654028201 448530346 38834851 100237270 468282992 767623178 382295295 768425656 516696251 336125661 775675797 919581982 816960169 32038525 908589199 484806328 390046273 424077886 163877028 290669006 731422389 214363567 479597137 829118086 921975200 602367959 106661152 81352731 580364874 679440505 598413026 58235429 272471776 78416210 69743862 66095573 150297022 321725783 79874434 78883127 5292199 51048954 958958774 30910575 930714632 443692644 463966222 683064574 436409402 421180601 109348238 230324477 213231295 331589977 781297413 107706462 397345154 462664218 602965836 732596784 45595161 18835857 401867654 762094041 600661252 868378184 165715552 892278363 160590573 750746630 315596623 112909201 888620007 830712588 333117398 851639152 578267824 642587476 498459327 551064905 392689137 323586514 899789151 263688451 649360762 830683061 914344148 970243683 833000840 380391844 822575432 264645701 857710081 725379842 311991085 717616097 865756084 616887084 591427712 307621385 381187484 139749047 905295367 596118631 494124059 17190069 609554069 106725569 428013120 4027886 802805827 872779831 615985923 572601385 651236278 683989121 120710790 799008610 680935773 585338674 484152659 786068243 232980146 753319161 566093218 644602221 709128566 269127389 994445457 967725213 329080566 460920190 439631724 780344841 663745354 707313241 163236068 515010962 207835282 18968322 493845594 61097682 995231289 473712744 573850387 817285725 598263348 324071446 19512194 251202817 794298434 405272942 330088067 817743623 323986730 735506158 879395483 268723057 204221953 24165740 684686651 542865212 982840164 573508443 357606908 607671453 750352568 744024070 38809570 228097094 110546286 194226898 233749147 150796959 780780610 362700925 595685823 173967631 719378041 128760931 427937295 805487922 25916704 121342389 778244791 462455329 761410642 695855809 543068301 504905135 409986160 511782447 274703698 680689576 991261543 17441856 427082477 39358739 514877936 740947983 876998325 765782895 371553993 589078737 473510566 120021494 307261438 756085014 695290023 887879390 951190052 550713863 97532364 896172692 355500954 284791976 876602256 369919233 466683336 213654805 176703768 839739079 413695585 206063046 500243572 565036675 592670370 82488524 705357279 979160074 144187026 3002131 47631612 613337005 289862722 344139168 690380824 724248439 741316876 635669715 645777773 345084523 492547286 173928355 534434394 994780616 697541453 569108198 802554541 509423686 407860524 3234440 339788763 965217113 141240692 772789968 246903364 400666218 419098803 696147872 782199922 852290595 239299647 494250420 43660888 124598177 744100218 768973791 912755348 210065857 47304973 907506259 489899951 500085333 540921902 710006231 168396633 206322542 153637340 65174288 194232751 191942801 652936223 73718715 777537143 418740739 59424587 476735470 825085536 748467712 778408763 824944476 1699397 780575741 956490903 911251599 364863592 585750507 572535824 561450030 322836408 737892213 170561441 90081334 371899149 91652926 9557453 597630275 595966056 360196645 590880997 948423110 145026614 792487554 193922625 959777613 540803724 224977768 898184579 335000512 82749545 860392931 228712921 682019999 271514872 783415865 124634426 845488199 498293453 75471659 256693669 773134636 90856229 265565490 734252647 529518878 373608232 74267588 712398163 239633542 640503080 554560654 680358921 901073831 229328353 453217976 52064561 649605599 385492409 100883494 324336063 493495525 10665471 998162100 476725807 915486218 712934445 499119479 117629383 816111482 515368743 308235776 332183001 165517690 220806266 587290521 901377792 404510633 781292448 691670151 278360672 439862848 570437945 188553032 99429608 453505364 777025617 846397396 375112336 772812304 799146398 195400414 392860573 682711038 813056193 948751634 596279258 922897468 357972353 668851798 378863583 721245385 629386517 751838474 516335691 702146999 827797337 801070410 234101515 332068471 636504596 271739432 484433043 369448723 4342330 298243316 329416993 518645612 414684966 387672182 861537278 156679298 548526045 957402672 426812094 118675882 163723855 443202462 976314492 644534231 747527319 298845559 914387233 973846227 208768568 794219755 292813468 970309252 971805535 356005604 543019561 779574825 386699301 526541127 468746636 456596892 339867084 804053554 10576980 734030992 935184383 921518397 504158490 780021714 710031892 758724283 184249025 370366602 21574731 270259959 90988469 84038008 83667213 272318329 177800494 509116473 927455791 809088577 629866092 59196033 686693423 691242760 65492474 525996895 979394419 14647427 239711468 142176894 949948302 859445153 31812643 711839584 808084605 860026570 925553541 869738659 418926051 447621407 580045639 235744574 551928403 682445759 343044901 374887874 955756164 118873341 339189158 20332442 300372123 215865260 145149274 770903629 919330150 803232341 217068573 275580601 56710557 797091453 947766867 883172439 348477218 813984226 914193452 543430267 812973119 221994428 683067103 643993491 47924972 25960446 976273904 449698405 176071687 711341203 892599403 730615635 111226523 864964771 511607848 288405911 74626332 96896973 866092295 637730953 414074535 226273133 817333299 268121814 343813700 600886741 647374689 61711816 415058981 337037205 699026959 416578690 205227238 871813812 604907719 257447747 981341901 554066934 870943323 42381984 825125640 567566870 891061032 51576011 938639091 859717899 602485845 867627216 53850961 723884868 301392146 851082708 805471120 504186605 761431003 490059350 335546632 801648426 440048053 107449200 886462010 271696217 263661421 372874261 389961234 751169106 354792670 698017362 102889766 478786471 428302889 285704846 785696502 987765478 774142715 104671947 398809388 513241812 948602316 471646181 760337627 950861489 721339677 480410831 842822594 165656440 519107255