524 798 1000000000000000000
210876788 183207201 140923647 590935407 757963241 743318922 671861605 414860744 270743243 454868124 159039252 15736924 759784801 7816989 173128885 225132218 175733444 931368180 989862371 775977395 613897758 587640171 85302632 119436186 462762733 619988333 922934148 680932482 222361408 100310985 544965158 362504323 508417528 579767660 855835440 574258166 814714632 937352106 853654198 336881587 431922614 904444022 690314047 675702105 738331863 14780069 586003458 345750406 365746454 278777391 626668330 450107418 631981869 546826349 281737746 305649273 327900201 340078171 687994761 645089221 433724330 690421463 178190863 958184743 269247520 542419680 555233813 674897414 759460111 264293335 232136769 59481677 39914315 149539265 453732775 287365289 543528764 142144898 508348944 240421577 778758427 873351970 65379382 221341084 740937010 671797772 651050502 74540437 714829856 432694602 11674844 416767722 858408722 88610250 875207114 933998544 525595146 41315995 109535696 436539072 701582364 954414896 120217637 16783541 681868203 330747803 836187244 460035435 954364080 776111314 498882303 33875873 133530355 331793134 337291560 214691671 49863759 587088743 687902050 165282320 317304562 790757208 745858460 202421009 839029146 463903168 433660277 677196192 837102040 212521919 878914688 607784261 763506256 448676052 412152450 435477003 332340471 105838373 699473326 278283967 428236115 208423351 392845039 125103920 331654846 563303089 184964126 501018221 11157155 272750493 924927047 4563210 425472703 930878375 422878697 832832858 398677857 391803355 552773938 71034293 32522665 34590570 115353158 66237620 481343436 508290021 851591032 98884975 534759758 659349888 776027022 156519366 953548614 19457360 356132353 100054677 372518045 271868813 584813370 665446909 197630542 22840272 209855702 337650593 708128679 372659542 804180963 244568806 818306694 990785338 861908256 716922161 559024029 517975230 479516480 484122668 741721774 684991362 210342183 559095298 523252431 742036939 427754538 614204830 676219047 381953213 732648531 351349487 514617006 538588833 440261787 489727271 369677680 340235551 333060398 796667126 947857866 93645700 993037738 116300499 623145259 971900669 834498399 585186611 812246484 507313882 464579471 219298511 174965528 426770124 654263215 809962210 723997084 515726118 312701860 917492072 864426904 529894686 878716935 711142752 120545555 326902541 234560097 519080203 96561194 545995947 315288943 113237034 64094537 366068563 619774814 983053891 765013360 794786885 629280271 946084059 155305071 911444702 123781972 709941692 81313577 512808161 402819376 316423473 174962644 15563441 755593755 30475333 906843703 718385556 138404155 209967880 72675819 654165489 655332524 8709321 804059802 610979730 835692985 485118556 499139651 572225506 266708767 439806548 545541491 557052976 138088784 438095177 749980044 545540586 905894061 500310036 774458625 217892066 310173643 584387086 233425304 496000396 620665775 113174356 764954278 313276733 353522705 238594309 366039382 999036013 811040156 141521793 390551778 650793717 145714220 840750763 705444055 549130834 387845902 430400040 649560405 199929311 287677251 83222942 613308749 67730718 812351932 537581813 333988544 994935280 357747615 590389912 960375558 315977431 920751232 499081653 405385988 966242619 453810856 538643064 29657460 955351457 562132306 553963091 249741089 897428981 66645224 619784249 908620071 741724609 153609033 184722654 210466103 313367155 673617414 31767288 853636560 702304155 894893216 956812160 532767879 428709673 363145931 679523313 8590399 601651635 776658606 523443848 859554161 367331500 292714784 111585922 812745829 99221166 853294060 829190240 825802615 524509105 96121357 777991717 109411154 83298641 478170098 861267862 37721399 566679819 927575995 488818297 493179703 850551935 824331641 798448854 554048116 493172143 162753905 461576505 831004004 17168190 315133529 223984365 378279437 199569586 378959770 879062593 860718666 805516466 426110348 664741575 455553027 942445897 554738620 184026511 781246328 62159904 634666792 720605552 833537399 173552839 318143105 367966527 175079841 404591340 550671975 669838870 140827817 50008737 999401392 565311374 454367892 450049690 168529826 886200836 109920505 526568044 425716788 231455447 351752513 10342607 565211728 272386215 281761000 154943453 285425683 649254296 898503098 780352336 226115851 651269004 315754006 86396615 561245815 317898348 397605678 915070977 206701963 382977120 63117636 489733407 160147881 862644753 205320686 374847718 72599207 678630637 549272659 365614330 318462223 612958563 671660396 472925220 399299674 730868002 184122947 866820237 888866612 299590494 17834038 574923776 587688891 632988427 600766772 363513899 977839551 744062239 104536062 260900573 912645379 576163028 353845863 127870537 406055802 684889059 291442580 276636482 477427594 28890313 515872829 767575420 390951500 564503813 100096745 103983057 846676425 235325783 391513653 555269753 594390334 279552515 98007821 983323984 352765272 293390091 49582833 254446611 363000441 133176952 738806321 105831074 968628977 362642 295328817 764027200 53999940 606056994 431741861 746877646 538034794 571163830