660 270
834871768 56143547 738645275 113684843 712051207 597138928 702770403 168925726 153636708 599683246 672741521 41060336 129423520 770554846 752854384 121375472 845015838 657685575 887104477 36966507 769615261 236555630 48631358 222345987 161307711 688399877 190975233 878810206 203662209 680604534 645403118 109246603 117833863 815330448 618082957 825286671 735963488 82528644 157940660 130738591 691587450 661442146 188029023 588690023 80405228 17562140 830910908 663589516 180406934 643395413 205863364 612775880 700041284 1057593 48992455 59274572 740177520 658674233 101070291 725241127 23879639 201606050 630202228 737499385 6503641 894084515 837026777 638240497 172746085 768642179 95899362 206620972 630266798 731442849 994076044 654273757 140626724 633833865 732135500 820511843 854926084 689440934 126126666 840621433 214338420 709427387 115902965 748574311 763445308 166361602 38463111 33844113 170304533 595439550 211444913 56970708 23349491 844629377 138240920 142116117 27779367 14346358 666169643 122610662 636611806 193017684 139185882 724039185 619480751 48788296 624199862 586894019 85658311 170047998 612624011 997127408 686775665 635366497 111819410 36486885 165752983 81046220 683075847 14078105 195087757 70050477 231971016 144384908 30307680 660058383 761024603 154088706 996312338 826589860 91837149 685239004 72803749 116844469 54744372 862658933 78027796 992791100 7374947 833458027 771712223 835189739 883751901 734781331 879572348 639578493 865872229 625523520 137069315 684259473 126821354 18649672 167203540 761373502 867947363 71481728 225930541 829530751 12878466 207490078 636946389 134141608 618275514 167873593 156275009 98719027 700916421 745226750 647716086 649250944 130647102 593765090 12267637 632258983 865095731 41217898 745924233 646909532 778341474 126773513 16369785 221694476 39715846 846167776 745272497 813489728 617423330 676436629 3432545 175935512 591823240 17897319 21464624 223797255 32431614 730268789 29330810 605788026 608471431 603411818 999565566 110391857 884857966 703869367 196464626 863406520 202513431 754385741 173669626 890815201 675673827 158538975 837536346 58307064 764361191 823697232 157781968 860777801 877742931 102102484 765812808 73903421 837319560 138325741 840553357 669981178 676827628 716013929 93150575 592345628 156613421 652714710 892696001 98300334 224763680 861226480 215643861 177283029 119506307 11768165 152489122 772647825 759750710 667677544 627995039 685494953 885903721 688400964 614454404 774614325 86729329 11088792 82227142 588845049 877228017 9984915 114599464 677972739 890082687 871477173 102951652 729167499 158362371 64778239 26025287 666293251 760233103 740050563 717356532 223743099 611228466 103971181 142895606 887942834 51047634 167968577 709267731 632177568 201826407 43415876 601519056 24954943 133884305 68749015 847917726 669021789 869364273 853847880 704431923 88088651 106292922 686208903 823058708 62220936 679166231 615943388 714396736 762216128 44776773 173898763 842719390 836905133 133030751 595941473 100494694 120337897 747247444 812362718 816407337 603449347 761279364 604501965 27228637 232204940 155416961 144383860 87104508 625671718 999999999 51707531 20180928 42186530 45838763 589700545 838574933 615497530 757764859 671941953 599170698 715190667 825060951 651396758 753567486 873950035 880965945 150352876 123782873 48839466 232660472 673856759 857220079 644569273 629036841 664681090 597736142 57718573 156331880 3681514 847304965 744103927 642194324 740198184 866570790 72598372 743430849 721235079 233328423 592133864 620612097 21212670 112338987 745167322 649387463 189527557 621638625 756421406 161951429 702651848 118286308 727425160 662395327 230768584 679038688 872540776 600963783 594908660 192111144 135708541 634698143 609719267 212928680 829071021 840003877 773121327 228426150 677931711 668686440 843172042 145888949 83815588 99934718 28739953 649365869 701826927 634951834 131843972 108779136 185867006 217162826 826286542 755443308 107470767 659677776 58537796 689911653 182597802 220326326 849429882 719785275 666899991 130661307 892628625 182248854 842128306 758739781 54194032 237272791 882341549 875257814 858050377 822840254 673496875 859781890 22248171 821893890 836704669 199814731 833549055 631345390 830506847 107717724 999103159 693067073 165164848 713566044 608240575 606788839 658772902 187429578 857821004 130893728 650878418 815635398 148859907 8190048 128058356 885790203 7801005 193069572 197648841 747900858 183149082 194455122 734836925 895272184 726425204 875457341 28981459 205166583 689463330 4182182 1983874 733565852 742041225 202219403 605761103 840824727 623427104 994873899 596653585 61100470 880197814 718477199 159291661 692527847 648647556 613140594 694212131 706962873 774850838 622006097 93640523 653962394 853038822 169347115 79034865 710589827 153780189 687772937 587298483 638007796 594831306 45193305 1358974 63711624 227234955 118807959 74994733 210447028 20336150 167333532 30714815 741708102 602099002 856356694 894860743 625140984 208999988 27191399 869737610 49887282 23015357 200217656 757242349 135483724 882677581 123932283 5536383 174203234 659610244 108322607 107500256 736186822 722831165 186708361 828050334 832657542 147438307 219358736 160361503 89341759 9626142 695439862 193249750 817610831 675262757 705741395 126711119 823096876 661933135 590143238 179631054 56517445 97280348 175423632 728288351 19685621 831095887 35291944 677125165 45013104 228695741 708195030 176823555 234541754 226839635 20611115 198763599 42277948 655586082 671145109 669629183 752093182 704579893 3128 67247042 705919413 819111400 814043575 682292330 31219105 701940984 60209331 864100210 150723436 84372369 41225952 889208964 858212018 763927170 178145585 15775362 587330845 171283820 151118267 777182277 48866885 180776486 48093750 840399031 640729816 840078877 236210371 237616968 991870577 740980190 822660936 216618739 876626481 184429971 874691982 633233527 842607914 104983633 76819835 217536428 859162535 90747784 158749783 146861647 183236159 712486287 767178945 75417721 146681926 133792044 160354450 218881429 812837856 826100565 758586587 100494602 998949562 67837328 743846449 879140703 52983897 229829109 105858502 94877115 164158373 815669234 891293491 590333861 776195206 151812536 226078869 594265994 681240682 626655099 65834800 691127916 124912916 14182470 69148663 21883791 871078163 46741163 722409968 649194687 880040256 997528860 832264208 664434952 656229798 235378785