697 18
796357262 629095294 797332844 327197638 189092746 821556760 285777306 612187560 344631020 140459472 239246349 633723077 21194610 878087615 401493653 801484952 772426712 588739204 475119445 741187782 855397615 75613570 85333417 544236145 950360518 957408217 739868725 695187256 766490541 981570371 692779734 600260112 752892919 17189693 397079968 7604314 791672666 741085318 741673105 816706962 772146357 960158476 966496325 834410727 387689245 576711024 788954305 663963088 420079265 507777475 65983563 670966178 418514371 573960951 960505612 920048674 971448501 787167084 46210668 930960 860008153 498681428 782428485 266034293 897435614 380762246 49967112 856333554 852401802 288447372 101346594 615804207 155097764 793444896 536561442 421681151 964487509 844121614 307069504 74090623 380111749 98489098 766113987 498489221 813266909 560604236 993906862 951285186 287714286 957674367 330067826 259993102 622350289 830938773 408078566 7275773 901367742 297035979 976475785 457415092 334292446 995296466 337162384 777419965 822057845 979829812 986778914 329139245 251652232 110801265 159569807 748867002 296207542 506647447 417061321 945026220 701936884 382930006 645507826 365231044 376189312 677141382 994094278 274159508 409015552 318751313 626947149 732116555 81015089 184014522 658023487 591629627 311133166 779167588 453828191 209727361 124924961 770743092 878485314 999452960 948157448 541692338 555150913 910943628 375366569 267849624 377510807 111499574 93239773 954675959 827828860 516125204 405488595 431309450 757189360 432218476 256810596 93774130 860599981 644784986 927745458 991350459 297671311 689506441 661161821 635195921 137234573 515835809 660797287 983585558 311815516 494752762 120755752 155145584 218954624 355712027 405742984 162905766 386696310 450544557 92480167 510874112 541692524 720861484 605123305 818678615 399106149 416983930 36110018 80980616 632378473 958856817 111703148 471766099 600025163 781383168 362856492 943551443 973453900 120575787 659050269 131568918 936685268 585876173 205410643 883291938 446568784 774982364 616816847 786100693 194252937 919999602 122032466 84349670 102026828 697554840 283136898 974115411 120684972 474508414 306354760 48821260 247674340 751558697 699419876 713097618 408155096 641880675 208088405 692626665 628830120 854542121 121662878 912150691 809646106 589329099 839464275 930077155 455515783 56602786 564777991 247207328 416439221 477738761 884343837 848531774 225329844 490402966 518815900 844795762 759906057 364356267 381345119 354709055 957309382 244473486 420426403 53230688 959209998 406432581 681438019 322076916 941845759 219793636 526883362 183587372 225060943 841968734 47777018 450642107 711056261 272864992 855926967 603548801 982672443 110289242 820235903 368689337 971843932 448869283 989253595 107368607 384998981 743581251 103050900 846714648 726612471 392731783 93649241 125901263 108062989 923849564 19073658 906365930 172833620 434508548 488643539 60982599 998440210 593395099 486961154 501353769 660875667 351300824 773004977 32525911 604173213 685434344 332456131 246356003 836304213 804272809 991446780 567221378 689122412 908906466 714009435 499318944 403285151 77281902 597975063 731534144 644649031 335331374 887529500 962113553 348182365 107492991 159754007 71139882 318538388 887205234 950043067 683730379 432354562 776687804 31538264 36580046 3983597 817130435 43165056 495342321 248349440 787019135 744694937 573791162 600896140 891434527 696585371 117286277 768725359 119944514 773674921 414239621 933405273 883927916 573045303 964961772 523190200 213723193 998430030 405963280 287192124 634557823 108971044 377374591 648632853 503573635 552268900 442180718 780081161 540267160 619329323 88594741 144785898 384847777 691558601 569610722 506325133 528952839 926452821 786045413 466435513 312759468 777104802 661820829 360601154 388044915 645360573 819923496 626846338 1242228 2495283 963249673 821808239 353323571 895767242 901394891 998989391 303498830 379603878 767322260 994947479 365669069 774029501 879034218 845988819 414498831 134043173 965700494 549310919 84160924 165514187 268876624 269211762 767631179 525182293 25448301 849616381 421296626 92633575 157638047 642046689 793412680 17979872 424087119 390621445 10765835 671883511 430315292 311418049 50999550 464357127 43255911 205553916 297133668 504246518 762783410 911780508 604784102 377454438 989283579 639212690 919190772 191780123 709054146 592228921 535746674 374493468 750412682 550287693 745761227 928376822 511123935 980982720 317012794 267197107 477842587 677479852 357435982 232302438 418273391 76968573 703695976 743355135 619748645 393228581 711831053 871268661 975306654 886699143 97111369 176217366 40306698 855039990 852106261 475133190 439920436 296620477 522250660 123248062 237302769 718097482 928944710 592287918 949522142 345313335 502083286 609838760 26341939 649470034 884518504 822818161 863656141 477327875 827747113 388270109 223789960 490936510 378413374 785160248 891768553 579073173 179582351 406955125 600563648 562689416 646822021 276328188 800468454 475737090 733574521 777262786 181273792 684485509 128598657 722837461 313345722 214120034 611711416 683020872 804137961 787904694 575235187 196497814 182685338 185629188 135138596 859392841 7434004 670673754 7736997 701237693 880355315 228843937 612772718 171641510 161643141 819721959 915174322 459472076 935538078 57077259 662649282 25464943 385345166 125452025 344006228 426037131 192877988 124266380 94820846 624878549 595407075 285978625 675838854 635048420 84427779 815968434 24974978 718076674 583604964 821413050 16245802 912404859 882107670 920221223 713553091 635204424 388895937 926004118 781408503 485363406 822461576 186527400 267961009 222743691 853582627 930888568 936789606 36383908 755984106 234439475 331566549 737318906 97726259 686479536 521298388 271180778 393391063 533079557 458188079 600325479 362926691 651512078 989480449 827102881 503452279 731114361 465716549 225957909 721878687 892058722 243639169 206762128 599969957 342951855 863059801 627144240 205341631 520197897 544354237 234890170 707932633 550914002 305129873 226922020 538527507 748010054 116422801 458983176 393362754 113515192 962361792 412633388 531514134 145319158 505256198 463525631 992431748 174592954 97036333 822401639 167719947 979630660 920682217 763619986 834790376 782751032 874334379 856950666 381987802 989350715 175941910 76355995 843496775 883593289 914338483 360020533 667372771 534820120 866640835 235565623 601788369 547641966 409152539 6790540 658492846 607031338 269517992 441055571 44886718 702143492 76746035 758915187 252388838 957190876 107884998 763329374 763333822 748585923 525321225 421300305 168550243 917622308 134053752 916418514 574062708 600005799 983085293 368738202 986492368 799140193 959453896 730157642 700781167 226677283 1591949 54996973 993920798 820350455 541239114 191600540 874951798 288253867 966935947 262754681