1000 1323365249
443522140 910117249 1079411431 1151826792 558106874 732360330 892989424 781081090 599446377 751841340 926126941 375665624 671482052 682828082 1317813552 1226578911 54251116 971855492 1034542774 825272444 600802470 241430083 964683726 473949060 912324805 709214707 349633211 495039359 619429299 1014855275 1155244431 859433348 1285705055 958528251 635252592 610780104 1066535154 929376592 1155230579 1112492475 917280423 201510287 436914244 860768420 1210160687 1046462456 11001965 425441477 153962364 1015441181 534643264 1239961246 200458152 206157859 855791452 914705386 30492197 404221576 1133124948 1109183149 443185501 490821223 454634254 710096096 291266286 904357577 975632553 1133044968 213650170 1104862025 444984815 1095224298 1062359276 1136577152 72163399 603913615 539297116 1235233437 956921113 507539356 151112911 300048739 629996596 871176214 999499022 310708814 475552975 1198586187 869604715 740523247 1104015407 223998854 1077511704 128621930 637906456 824692861 1171500185 43473300 740963802 334236960 825325845 1020715120 125423074 888452189 659634860 21572294 1305610960 630843596 1101569037 739412080 579235712 620917174 1129794918 329373435 1193181022 1033183790 345376367 341623057 1267942465 30629014 602380748 1153711462 828626372 685173098 734470065 266636361 146440266 320566748 154568663 1299408630 958518326 1152709460 254902482 723469957 266504789 241378022 1293002865 605686968 84940872 179042862 595223043 114437987 554110956 1276913372 591084444 1065682838 1270249209 822078763 772746182 1217958810 713472777 21842573 826888903 874148788 992266900 379420780 921351798 158845858 1295687632 499803868 941521964 1001813324 1090811567 810433956 429131989 1006000227 439428 800662173 341359992 500114665 796775166 409819551 1256558878 761801559 638680422 484887343 1157374392 469391636 1062737427 154187634 730002534 331202051 502540879 761252217 298769412 71701178 590456149 1265989918 91728583 570149237 740127332 206445878 1010413136 942022941 717625879 640514555 274949292 134406814 518400631 954427550 285677403 257563774 205449504 835009358 769204498 1015010576 1043477958 705534039 784826352 1321142992 1284081098 557008030 706684973 356371887 683525083 832483080 264533488 481394754 503390994 66867916 1170332171 931446424 244545956 823775959 714221498 842072797 1280643746 403633681 271801303 1277613389 254945958 926366934 1034968480 947516752 593793792 885037783 840594355 855817508 1214890957 715449166 397242431 1205528927 876214422 179912215 324884243 749983672 1219865202 906188309 1314784368 1013706879 505984032 347015137 1300364273 1229862278 706085714 173358175 669492426 1001280921 145204608 947052048 1218606199 1186844554 1207449027 916599606 768090890 388996194 488128028 852080301 1306710108 81777251 497816123 835842745 1053252861 228121034 265972124 17785918 373667118 1156454986 82836149 544171904 740780606 9350870 556191633 404038554 727426428 1285624856 1300668072 431248738 86945598 307313718 1053601300 1038718265 1117070056 1027336333 666004744 280971677 933833505 1297901260 846093694 432332057 748964776 846366334 1021605248 1142929157 101379332 1163915099 654676245 2276410 596207532 522643637 162671579 762414806 682704741 93987004 340851296 89920968 843190839 257442884 263343074 1201296450 962215723 28793991 275608628 1066632406 1309456227 173306767 1012388510 611029179 1300854532 42062469 42140009 677691367 798667327 217472704 1210651074 1036840242 1096147795 933540513 1140784884 575870603 72349854 1296097433 977708969 1272084591 628610787 938092664 936765846 224867619 1126702105 45097292 1044888335 868210223 1286068174 906348965 391243771 963171422 920634452 294097296 1215189502 573454578 782271869 93136817 1198736138 565622708 1307563278 1152713813 806466475 579509465 501603910 423023822 966930782 492715278 675879363 386878818 512219017 596467524 136247284 817379684 1320310308 505843201 270945373 214294967 555661053 584766812 1185435169 609520104 261669692 1134866346 448755820 306775161 897397507 1173367401 710111392 408287066 978573801 800240725 103653149 610234275 1318992178 156998750 996750847 1115996392 22707835 76819204 434870715 290548127 338275083 992243522 886716180 823355917 1051767821 1162513409 648646685 8414547 628574323 59056372 317049451 315299048 635008025 987911437 894691719 507668592 607896791 551665977 745633619 756859360 31034926 987006478 769965053 1217669471 700748758 859824574 668239143 643861291 670015941 899239164 558168636 1127459944 997934608 622455623 43557393 635667572 184196833 935037489 1171948844 1199797109 843234730 529325317 154403730 226513696 599719973 568170023 447384186 273337599 539834538 161063522 492076016 1233941901 1121112804 808514729 676525776 718486807 321267876 886879795 576331540 81631925 582012923 920256798 967339464 357271480 854989827 403985209 377876439 933259231 330292853 438709747 556491435 161996375 200522872 283574916 764786796 1220399701 1671638 606985176 1081213331 880722542 184692568 1232166344 265463096 626308718 932246380 1140039832 975913231 282715506 1305862927 1020292573 1015287368 305445354 350980496 1132461488 242855843 734558752 1180375786 187068941 924776953 1225978578 540237237 943317916 596096830 660378397 359690623 603393671 950381363 1245401476 311884700 36445756 783223867 923074946 1073345127 891843198 1299589588 212091323 1110704321 212315987 704609160 482808020 947755137 694305886 224031663 1315083998 707359989 1274853252 1043862885 24742473 650175724 930777167 620267203 194618533 1218692621 1204712185 811193369 748282733 234850850 52890197 1075673888 788543720 689057135 336109002 1297799288 1253434373 732072956 832462083 133656111 1257704155 942597115 959251164 277206958 1023147746 487073223 568957494 452863456 326958165 153227585 1293792626 632522549 1195340598 521695239 171628640 1256322741 1037075528 322100117 90243419 711626560 863522685 295860663 906983363 587349295 200447923 672823302 251307297 682862519 1184103677 168925102 481193311 371826356 228907303 678331076 1206476785 331548916 1230574744 1065331338 379727156 450303988 293379832 789482989 1185127260 867471930 1279069983 247140183 780215052 116594303 1315270693 580512397 973848000 637799086 233744796 905964513 510138517 505176791 514093070 1240677338 502120903 1253772745 522052791 982164524 723843791 1319419318 925484321 344833340 689412170 82608824 521399331 1167597894 1235926237 1191978566 284130613 494713667 799087293 734485857 1174091946 711545192 832967730 1308707373 1017062698 1024807732 317011732 679461979 653032869 315355642 159353774 530205888 422752465 674971565 876351501 172844618 680415151 723253681 927390992 848503229 496258328 489766887 1246380337 813332775 189839457 1188595081 79069884 865693716 17946355 92151672 612858217 1001010706 1127111969 289676978 682020743 97116592 666102777 450611623 575872711 1294042749 240500196 1163381547 1035061683 194741373 515997918 773528041 493081644 1130898955 479332748 666125105 1080525487 128986560 365215130 157474699 1129239577 630852085 1028374233 565371729 884575400 1235730821 263829392 872113974 646827097 794357161 830627536 128664138 1050063298 205698908 1042330204 14384974 969729411 809908280 1155795213 1285321536 492150018 1246373555 1251119914 1113158356 887129835 978551186 187650875 217097559 1147295452 494207550 193327322 529031032 887442109 195033831 349960793 545100216 221195930 508921612 411835346 950904133 728688377 904455673 1198443381 873249482 929780024 529702054 606911109 271630955 186795706 669284530 1259604978 623477133 299371685 526578387 776849294 344946249 727518710 189121426 631569968 910104753 834233972 159673344 3318050 42098429 207949079 427953693 861619277 46433395 507758078 1148537232 1305298604 1027263424 478938088 307531200 303042763 41091129 871722360 682824483 732203964 506741449 1037448074 923623154 66968179 1197780615 1290558717 817995338 1171815670 242655071 421635027 932994593 420576563 542010628 854387600 134331052 278991469 1297460098 922269511 668808594 240817494 1184846616 37247090 1204933505 409640426 471281761 1086738264 1203244216 535918950 21461046 1035595022 1059053632 323147924 779950794 1093507006 986039408 197881262 1312713887 601415525 87585678 593360897 1079777148 199397401 757644480 1099153402 299217039 1027294374 699452231 863861829 91074820 462413309 58897964 303060968 81105622 602957420 133091321 1207501074 1009480250 928313605 699286052 314601011 111161712 869887115 1104367660 728131403 562512743 231069655 227620282 666126068 58772911 817911065 292427356 430353514 557635504 1277285046 578057630 914241785 951595983 598428567 1134534661 89690642 1311810310 79241584 864943908 942132368 1235153116 1145319225 257857301 1107262987 938610755 932884716 1138973301 223339767 815135898 579450566 673367723 1288414620 871897426 690272316 672514844 30802721 527846766 926196034 227003552 1023075947 219674184 1067628299 827084720 1096215873 250648698 600270821 337718345 257963439 1190256847 976679956 1160294304 207431676 988189353 133182662 750511366 779220267 585924097 1089278246 1146548734 1085613427 425797293 866904531 153685949 1006819719 1064586767 189656545 1095997669 1257471 496676828 1290915729 854466892 322411701 1269045796 966972214 480533424 719764781 803363422 959571326 286723108 486617335 46740345 1201591362 46979426 787175311 1282418092 63566075 754644189 18820867 1182075055 517654191 701983998 1092861957 1072266384 643540250 65884274 860955381 47279062 481330731 72715491 426118880 913045222 419644202 841249182 947641465 809203607 552564869 1315702001 221508327 1246460541 645959986 181255068 762081017 192507171 532795552 946044774 727224381 338481251 111494546 73135163 851051536 84141077 670997449 1190309048 798435461 1297572417 927868451 1166363197 246918996 557019813 1081261728 850091962 1112826704 1285666923 272111117 620254556 1124177278 491897240 1282021860 889885252 126024825 205426539 772242495 186631169 816298577 126285181 14680552 1052011235 272228180 291000452 468443809 893354131 577237495 693644224 1212485278 173266693 157379789 425085664 120828679 566501679 419800854 1094199126 1071960481 246875659 724481460 318628698 935951061 966536595 105588445 180485153 382637940 431747363 574030086 1046523802 441229182