512 999999982
942226884 145217484 997820637 842645383 805861393 737224886 250405249 301617480 41640405 772324194 789398409 867988849 32659291 177857586 427838800 234790665 526264518 253057772 210194949 22304252 919130810 677855364 944023965 614709302 455347713 706116676 809626760 146902681 275657513 644483018 99392801 239205746 424924537 599388261 554136519 548263738 435021938 642022272 735401339 232349748 1583582 556868656 912728447 88681082 71146723 366141488 222537394 417269537 864639040 206140158 472709476 494492255 726399319 99919162 885686244 623990476 645077302 36636302 175118331 161248683 648099399 614821235 825823824 58731570 18182464 747695429 462792232 57786762 159864269 770977349 897703030 524582230 37525379 648937882 932329241 888543116 563664273 11298347 903406988 11550800 762237026 872914984 492502798 546059734 342231483 847026934 979913350 49018877 934862848 239163907 33638005 438129561 397474307 177719199 121103204 573251862 841746138 824066636 420788070 955511041 129970475 184927687 734649291 372649 405854821 168760326 506053121 975705724 221312470 388310550 529114557 790841545 622033474 151586005 471710537 858370332 480943797 690394405 998077828 344411221 103650307 822948687 825743207 259385262 570350433 74128639 63084196 768649320 901378880 385956353 298312926 418198003 561003939 411960385 749943564 851953795 545374280 694289785 1609078 749586158 211739108 381069285 200790649 161469440 36744491 716223947 681660639 997926744 99718730 961951119 496346201 336624733 642222302 345790282 227007784 335765785 503402870 900079045 151757240 13905452 780471953 555977991 464445517 974524685 585964645 658794301 965301591 193195819 725207265 973256204 807434073 105237361 600831979 328815079 607537472 586164405 307649733 842027198 589638447 326288665 233072448 170839806 17432332 842571741 156806866 556792529 793870456 335210438 629389638 851096622 90410839 386426518 136556976 828165437 793747797 590119496 704460738 325373706 115055108 82750118 591550202 738380989 954902406 612797903 966233590 678727430 201740045 414696287 407207191 216406987 657826463 247222287 118975224 457326834 325659734 776073660 151983618 895691513 490962979 239757754 745430607 793809275 339900108 874144748 466943676 908492907 507119009 3635705 511956184 65418470 547848832 29750395 17359772 599660506 98189918 395413320 532229873 34335132 746919295 33550779 238057168 488187053 233802458 971891943 536703286 127250207 442949741 983057246 643103467 366554414 252545403 320730601 900874281 697800089 449119105 80951876 826704148 597155244 378329825 69180399 948813436 513740332 205640747 212900877 242468471 164054298 882268830 979632523 543036387 355106666 763316196 496878453 487343927 971916012 109781304 146939542 753418401 145771785 425925801 46843991 525677956 274618357 596622917 278188338 416484458 675975505 634646407 196174483 24176706 324976070 350118483 660372120 62727706 435948062 162373264 127647917 523589334 611488582 316713521 662400878 992970308 622120171 648234903 772064787 860885838 694424475 304573267 958725468 297299638 468096064 573319752 335030122 708916288 260752494 768061263 186700370 636549917 721539810 299100400 381092342 237874226 802214091 569024765 944645992 388986836 79528943 386256281 439329830 486170109 789457823 208686685 81890376 610872000 263849712 774404836 181645709 888709182 538186177 446507783 545166139 703964939 796930103 766351996 567062526 863900649 799015207 418113889 90076557 727313435 109005593 864251980 602413409 764035459 680956175 468928048 851384482 213259458 641961429 832402077 393498744 22837108 300709865 946650139 729353625 376377471 76843526 4730647 361145618 951230108 950475423 639200530 990431735 449681749 964001572 239748708 195447663 741996083 218213190 370423991 117929792 225791349 909960424 637863041 800103464 264776320 770213007 79703710 984167962 843324307 662462873 505309970 453809201 193856432 477422965 223551657 545292519 380465132 737574394 480558652 246229786 760483985 181827599 627865096 11378142 681978170 959066715 231494452 765994399 394917718 798838821 484414611 550885001 562651621 326281689 368891776 552594667 141364221 415497936 30727982 67479315 401879645 48886575 989324678 784697778 716323853 697446264 521897325 634521814 933724075 138134541 315718189 432709332 63397632 974236778 983005882 14694820 297175623 510528264 649277218 734405685 476104415 729584896 318658474 708709959 667628416 10402311 706055618 29491579 809082217 438126314 514634823 643045364 751814251 73587241 784393062 491286533 759453915 479653212 39089430 800847520 517776074 748205097 843854912 13049796 215648653 248239056 444614551 625683535 723876173 699379277 527840945 913759363 111055828 684263183 668998137 703639351 631244034 857672003 801935679 480165583 412064935 933437105 351071539 687166957 354709853 326140627 603234324 211600182 938253337 910411452 994782299 502603172 548818757 61861037 788387002 582308231 983994763 52080532 553694438 274533239 27062191 151841051 606175357 643113098 79219245 553384528 923373117 376023205 301617798 213758451 140019707 176692811