999 999 283292284917592455
88966829 72465068 531022163 300226479 559800060 918535514 555086409 455186058 43114421 902827359 692588631 135624221 138281812 369928610 40442341 703028612 135863297 143778758 535208871 945385527 890505930 847914856 591719384 923373896 921480937 767150430 42924417 658519201 796637442 24735479 182644145 60945993 442984034 119139135 938819267 172522397 814025795 808727609 56431517 42870424 709697285 119164965 141078765 419884301 125470068 206439609 131399276 619937769 782115334 942915690 966570012 557604980 848606235 943012770 752145804 321929614 909377341 764418056 188036368 978690803 728301151 872803261 754444555 671402105 629082400 962241179 658247974 450815823 617816839 254335350 297598360 605650750 146786501 851492188 140716126 565939177 6340472 226116823 483420289 458301454 888272868 353554727 328100181 459685059 299294649 700573577 255434165 196506300 832585938 467352693 396027210 41581953 637400690 916297945 23410115 694284474 891127430 115063137 256267804 172749669 65396455 223898544 843904985 384825627 35015831 495353766 64656969 517444433 861168385 800967833 213631941 987525266 839361851 162803869 131954416 192827847 948485956 772240318 483252726 899267953 334613832 220195139 712512974 328514283 455934681 770278635 448659322 364010922 854027829 2417200 621690692 796650110 698262916 496561544 504332288 85566160 882581529 935215008 817673295 219359204 991999918 732075169 615804375 368193558 52327338 280214894 763895437 15571998 618129500 439173857 401471469 576365646 898953278 119023890 671643198 795581904 352915764 731985042 857119184 599481322 476412364 447306153 234989119 904711483 986545790 97622430 841136559 205459709 557294827 111771629 9676815 615397443 963801888 83212687 684258904 75118906 94374097 876251191 79805901 797495401 795808 278036881 893775675 61047282 663536469 582935172 366815799 138441936 213691173 928488558 936792164 21375513 313680108 133082732 647689388 583071292 797014389 454520977 382444164 270893121 435406511 968035627 344234282 2547981 885322998 314425347 816481512 699611293 353308242 975600027 133592144 369402695 945929136 298391663 629204863 998812926 18893868 79209015 243337052 538309773 726863433 446610721 34371287 291121880 879169333 803504408 854541356 291993632 681828360 34031361 158157343 580866877 298602754 314557947 293221184 348414179 597041362 183362204 575578406 275128543 917329867 363870776 620254645 590804825 858528558 351307291 53417562 153535506 933529701 844918475 418981707 755232165 311266883 555069257 955457737 481841351 123161158 304216142 363532383 11915144 760444375 319954320 379920930 827150481 938017159 219538684 73698288 146863717 978318929 976698875 739757235 414362786 316103900 166664367 764011933 901750079 150139576 646010676 980777835 955552205 778577821 698641121 493908388 872509112 287174321 347576710 763749337 464697477 373505984 880647854 235499236 653922067 887176323 624086748 253852715 943470812 33971164 188531919 347486427 823285810 636478742 72134335 540305199 949373060 191377703 480065951 168490920 242133912 327571950 65170011 681203283 438322896 143009655 991578393 851704841 380243047 518917428 919864441 335931816 112841907 405247811 29904087 807274332 688850274 884488620 894655877 145823706 332104383 666662306 741889555 498215329 654325995 897217727 999668105 422195257 770758950 223879241 732254633 631862133 908221189 938242674 781647919 436920498 416306107 419742097 9887762 256362519 137220434 282774379 43593410 170591189 308511216 154753134 363674986 490490215 484773653 204907762 295519277 964608208 500124889 107099768 711137642 799642593 899950384 632815852 712462585 299319665 544547623 222351845 20602221 843454117 991914534 277381089 65876817 102576168 215455021 896297867 226861677 856781169 741076505 551425271 821913345 553441793 53648605 861570786 205895942 883016868 15871179 331448308 615010673 911006381 66276299 8791551 863801713 275172668 901476256 256381759 350207406 935842937 709328168 905914265 358870922 366774487 706020762 829982686 664064097 582225492 315318727 655395591 701426890 679256501 201301851 314901880 684768213 963637708 441669658 196459070 316392524 919152820 523435301 949557843 715045876 825663248 506360373 662905303 150142155 23383377 954887388 16546646 339836489 357270767 733432264 254991110 930026145 820684716 513555969 541655559 141342206 755139798 226335784 548938659 152027592 501756548 368085944 98184845 439390687 405999317 102901319 431798307 715037660 567164214 493413059 763700654 964002388 420492186 179624630 138055071 388917782 422153153 964840323 614716113 84397417 368675444 606419881 532220875 558425425 444004036 231033341 528360957 23685321 462962512 872299249 277788415 257282056 999541629 804707794 159590871 471770046 788772029 262893059 589132849 42712661 421240779 933642308 762626470 267408178 676134891 925980143 320261880 245447155 458020396 432391735 616435537 376125360 356315303 712487784 770258825 641370683 123995582 457940524 482760031 84640098 348971360 500721858 103857340 986489386 380892737 724287558 629116661 102725139 646403364 649821678 797804551 645100632 722554899 527429193 202952667 541558573 196834722 95335039 385298305 944552705 50613809 137557397 975318134 521671099 860020009 597407656 42530272 633280511 30946363 245928239 449411534 799465064 894875302 378411066 71273594 507476173 942110832 916337079 882862472 101595005 539076009 411411113 406276422 800406660 834546093 348030321 9180140 86553830 219605600 936390407 248028379 839242721 519771505 545456704 804834784 390231597 194254745 269255431 208410223 815515964 818170843 870636453 236323561 497248380 540048067 381945850 188105689 596870289 745354665 67283651 235979568 225126558 688939501 730315476 194855822 318590843 445422650 19694685 622528378 306614525 884819396 924773927 913561766 449434930 507370380 812391638 71500078 320565156 55836568 91058726 765559511 258334867 902944829 123889199 947971666 956438589 613704023 107149986 949958776 62634008 509210509 40666635 914492812 841058323 648317327 855450895 255248510 604349402 265290585 253850029 611632677 248745489 924114288 675425919 137275009 320400790 411373601 801440759 812945920 981788352 652906694 992721316 697466039 59461796 954011906 467033452 484768166 383185484 341979138 843341009 864048119 466560512 826823611 251821102 417949757 389500543 252680241 368251385 819509687 545222724 651591340 329145856 112887180 711342275 392947969 127082158 770760717 66694058 396464849 825270340 831793656 221712419 411242691 834674210 965356465 717681166 13669322 56719357 812812424 505741129 908075619 683489576 658313207 700382953 382247381 453723085 699665123 765711488 674884976 88291379 106526424 684469591 10577360 449343991 411702095 338830770 603832346 423847764 277310698 904815633 93623099 788809821 438205108 670263403 698370350 174403647 704864610 287121266 231353908 49555586 261716630 429350867 204978714 46293574 419459608 971538805 130984312 762546056 468431645 748405943 849151215 52926044 179521410 741219251 686017640 707921970 59326736 111786367 357757017 192116499 613639863 926652265 340710656 571638498 85075924 259779640 76947879 368206493 928624493 212813167 790862816 654182810 320205681 888749195 145446601 676444365 33842682 226590274 985079367 666237950 395057804 447988675 909072460 451466517 920504149 307823098 9286674 961403216 679097965 834383562 42163038 2355336 675393301 492122195 919638464 22491250 850950393 737367595 767735247 166200793 961486704 463200423 407650928 52156902 666156216 654507537 210824206 589636954 65873212 769032688 360863712 382635472 837014736 58382917 105944359 244395774 202256880 391781066 586152046 562190834 567823622 79702579 582529227 594123350 64458147 946638190 266141978 404842926 486853571 718714596 176171334 974301334 635203339 981925815 483302274 866180102 613069324 374778628 893386633 818472080 907766655 460736288 501364195 217168286 654423432 970446557 989398817 909457078 921464564 58933443 727622942 702901431 353861245 364956249 269412413 923958043 102630914 475719003 198594735 385321781 805882322 81513730 104744876 560629618 314265056 141601602 204745398 692693145 756337421 157680645 108280539 542540557 705330274 695660146 661363186 484614663 550929492 40746538 610975706 832112862 586858497 101096582 452247488 738447424 822605424 851470300 646836055 209838968 644051410 853264569 20594207 49713576 496008389 548272934 322434208 125636878 393905036 669746662 567124398 780787776 337690458 710954419 696805796 70613873 250335622 85854341 981398955 10456492 156104918 899840205 304415474 271352341 228896438 258578099 443698164 917774637 728142463 175301981 586916279 899307020 536526003 157035562 389794569 676174759 895701052 23320560 333941187 4681225 195707826 626146883 747579399 213412251 259418772 656560815 740514180 790173277 469947019 125963770 687821486 282145068 549137580 277469029 263965192 103796476 790781620 386682858 270528859 871570973 746706507 917710204 197765374 798214008 730502212 976634955 803377422 920494545 446305753 347131903 841497268 432706308 701901808 422116090 797819236 672829257 110989402 991598489 869625882 219576433 76027152 469850993 172955292 350044456 980808566 118234259 493929148 253730867 415136666 209483978 718494613 114493873 535785844 944435417 307497163 917651548 914168869 196704191 62911437 136380103 214808889 461817332 490063636 52706462 343334375 767044267 991608675 936303595 797237325 613582608 364187398 380388429 408211638 276098953 613572373 134398528 926178006 424489719 528500400 443303002 269121801 991977459 958408258 93373577 953993625 100407827 849912511 454530903 531366391 291450148 634113767 315392296 488495103 779417199 459231363 837612921 431332662 451369974 819772837 739402784 197778957 720424373 816134122 975257744 144152861 686277347 480635320 306759443 869760105 548053808 853068162 494586384 701014689 790464007 697017601 709842756 897442395 47897547 381576314