1000 1186382987
1099189205 1067748699 691858253 978414641 589045168 1011477322 1031037117 366735101 258308443 945980905 873511802 794506281 553631491 231483449 570619911 520491333 595398950 976443076 588412846 197570806 946615723 186494950 627759221 104559696 795520457 114682608 440763819 1177593625 494532807 79302470 780417058 374409195 239545843 972622369 1180543958 765068577 647724961 94746999 637447546 1127992486 164961606 772837529 670417839 117728022 501252641 808361625 232308780 639012277 880748153 266627183 1156941464 1046057048 254413528 418324140 467980798 98125105 866807987 757778810 44156714 241671449 1156443529 925001307 491872477 1156122959 437277726 349486447 438590881 140140423 841720675 1184042584 291576034 141521427 165948222 464981940 208675677 401163958 25062636 247676127 836519312 1157835310 338168670 1111580193 1184120106 629835813 1168918903 668513408 603472515 331220417 135272686 921565746 1069544582 203535262 543651583 142847438 833690877 708152468 1027047646 554254264 602224577 816196456 358268486 919509340 334624149 274265671 1033837986 953052824 230769104 629623540 819586758 432210095 231772781 303579456 389379474 335789807 990694233 41354883 399793629 108828851 197871527 50931417 932960494 1173834761 1054175231 992329791 727968262 881350972 753033323 882306305 865562043 1181108723 787226308 264473038 326580584 676708950 1113188971 856246041 340719715 383651323 538654883 298958416 611477385 633802519 647256349 882457123 1068510846 687169864 484404669 282356749 779148202 109240662 846218505 299274512 89612120 134720207 1126350071 209075027 455292769 207896964 608477013 858849813 464923721 627520145 12824893 559402314 578063381 700913614 381925492 588336844 1139383864 1100412482 935130191 1100899102 403859032 883939822 710464921 235207913 360385509 866373735 473298359 524125168 1180836963 164790232 1117914131 1034570721 575167636 225972154 937648588 834545909 244675928 529705064 1146316781 436573200 481645910 8411244 957077959 977082358 189180520 169796350 1108975100 959689199 72024703 573464241 813992643 887454955 836501822 315056081 292680520 283895964 471532689 74234437 854001275 1171669424 273247668 27198589 1074915579 55743239 347711434 660349703 83185831 9598229 709127900 500243957 715361822 655522603 120405098 1053690973 505296997 954752845 945382710 790049984 572889474 247557664 421466923 332651168 931708175 1046690142 654948011 816204041 335145742 919811567 446767095 38609669 999554623 283741119 528609724 1064405559 478895816 1055090643 1097727230 712531120 1003690460 426044232 956223975 284200476 354637194 178224715 23060743 273700429 877797990 131641640 556996967 708335174 1117860890 878555977 1073446098 809212546 398118547 35042085 313946798 96634172 713381582 1026121118 810385109 340015646 189453201 508753243 547251487 827984178 700164139 340687198 801812124 536887176 925020179 771292391 254507884 923107620 276373528 661873885 685516413 509858716 1082735111 763644004 441160926 117011809 652844265 159642506 893775527 315935307 1115053950 985651985 17958803 927793268 651177002 399575267 143775035 108843972 717801887 54608451 992709771 549866336 307831327 629426066 1093997127 964039997 573473101 191274418 515626538 229596568 901010472 241930130 447597183 804086892 139509795 1016994560 674330073 669628745 910835609 518961017 458329148 453490982 224479293 855287283 865557644 119208347 32352865 966355207 1059444581 553965799 1072122808 409715156 236941018 32203459 1086244320 40504718 456397214 703016069 655323313 346582446 1118625259 343325122 1066507231 985318042 996158751 256197367 1134517468 227817964 168838202 873680923 319489352 523135389 639151441 472062604 1038065215 609751783 470037763 1101603600 1066745995 872719837 1182002678 1094838355 596043327 72083811 557561461 591165318 1001074336 101219387 330926336 312437266 158724921 708506663 80927710 393373187 249071498 451581681 1092933789 120133463 525882012 362997378 547970522 492929774 372783141 646360332 1173073802 1012591801 98450471 1059834604 284232763 342951111 525236647 140874995 1003982742 1022506260 637805194 186817587 319884374 300536018 703730615 410456843 266600029 160000382 418367606 920530907 87295919 1175153991 345498606 785445005 1176064825 487296666 1034541619 986096866 681894981 751945846 488315525 377258045 51490594 517113794 548348513 10401393 888806428 490755821 212367390 651888651 840248923 1144526533 911502138 255891171 164807396 452422845 447324435 429252168 154909062 153923659 236096252 1010581170 496978969 517717306 742135165 17803686 160228057 366479532 12420356 905343817 125636591 547141592 921474887 1042218890 816686325 141872428 510293971 293065740 566724330 1023498281 282699950 332642747 158504130 64130911 440081386 731128247 712687417 681528689 720331222 441316433 419160718 282122960 369649263 261593974 351288970 1017816169 859461855 471888008 1178436448 429755865 423642689 866760788 1017762089 97011813 985899280 677580016 497306536 196760768 673776877 206785248 611375090 850681445 494988446 81976488 628319246 612084099 644847898 780581976 1045225796 915568536 83983893 364088848 785618818 1152653197 817696439 416244665 1116154254 212092052 114104981 511650581 687583454 817261386 556885016 980848897 18632609 626845126 799724196 828696594 1030095623 455132404 1069232176 490973959 171440774 974215601 248358399 488946874 1053579036 118992702 493352105 673319480 901875042 281531201 995390150 1163058317 985834852 940445702 521974998 722578753 239119877 901342396 48668314 631653474 542698504 956092740 442236883 261548762 203188613 463643746 980462605 78520777 104789532 673493679 779974840 121576260 590500975 1103844631 811828494 792571956 1183041904 907066445 1116335264 938115673 55742069 951360897 587131660 1054114185 571595676 1098299440 1064623975 1144112564 844225075 267174976 561301365 432971431 534627177 9409197 1133552001 144059385 578099914 543862228 728258248 858516287 1184899887 383671695 550970531 865274781 544842457 569403596 1004431063 1075331597 504909777 838634143 1056704197 666156301 256481973 891247670 404780710 961016203 623139899 119481040 832259859 172608435 95526391 1097195985 565791096 1122372372 833837699 1113475894 925486565 922719373 141746697 494599505 244292368 1062864203 636468840 443742994 884236802 286525037 926427484 768919343 584200370 656679896 75868364 365785212 337160880 467347311 378623001 241680676 346470403 428771171 742488194 975434748 100063360 617290328 432668442 901788020 771499630 561407654 700841052 1122380298 378297331 1180778308 1185887835 814714577 545590685 614012918 221230991 1058663505 145945784 370885606 758004449 605133948 195753427 961102006 618666055 382034659 984236678 520645574 656613408 449903557 757105431 132741615 196775909 1082187221 651466552 671373267 654489943 490528297 629522816 1129986870 567600795 899882759 57564292 56878605 723832206 182746785 742872582 878613679 1111782937 754016021 759633865 751437647 452030122 180449993 925254701 657348519 665246231 486945116 656506678 914849856 1038138835 351103612 343391497 884695806 323234438 337359280 1082371893 140576081 527529249 876993893 977074273 138191150 426018519 1044504209 1171136011 915110718 591793929 1104857955 442266396 1172397988 811359168 269923587 1137390958 401032274 608142155 59324158 438731605 610416150 233737175 684984205 988827688 74529439 719861026 59799468 60990372 355605795 671923233 104934216 298668833 532011575 630490145 590529306 12394167 627152945 107188994 311353882 74009754 591820933 1113177079 166882415 680517483 1031654902 983360817 913631672 795495421 1135454714 1103873568 851343130 638194860 480663792 1118001310 893516712 265786666 312464330 740773000 641155842 1121326391 858127411 109870530 1025426733 5049226 725713111 600381998 139700135 987005311 980541818 1183760963 269018611 1113234691 818663923 548543692 8521691 1144426046 115931225 380433464 123589768 787627839 403959112 353857426 502059239 81700665 936993596 1175006075 1077341853 837124208 642630482 1138250066 964076713 362383839 358201585 1041536352 290459247 123618812 847301652 909608433 152867011 1017314974 66385026 377765026 746093366 150304387 902335470 442109211 728050247 515943852 843780703 848867131 247247623 388542552 326238009 324970962 1180854111 1004164786 433425189 919771268 212552590 580562450 87380452 1044422691 412225937 1048072035 46873198 934321555 310071542 156052279 1111859217 71643468 472074237 800560112 1089717577 113396501 951496315 87951465 256079046 396425697 1086938251 190031335 703587099 910915710 50869634 886867954 221609140 95787819 194396984 164109816 833058461 1094860849 373623003 806440183 1186232710 409088453 928135094 1060809915 959975683 350641959 620930684 335883357 466402650 196286941 839021886 114395208 10011990 237940870 469832299 361287928 504176790 1010871741 571158044 250892510 844998336 41266178 618724009 737230236 605877371 804030659 1086297824 634983728 742146384 962493586 1167266659 881739860 419537064 574513232 307440902 1107033960 766758633 952153609 765114218 87772383 441663184 1088786016 1041318496 637706766 610577985 1052484849 1075201483 583699287 1109337594 367043893 884261683 137219701 198587670 457735212 928798887 890446686 1033672892 1016170041 259729293 675863330 639050426 284696460 645145797 760468329 7621157 386285267 865547806 131617511 1085029236 1096617601 403485322 1089369247 1160851943 993744378 317859320 852188422 331993933 836815076 60234505 197951241 563283883 334976745 272545067 138307154 226075009 739776200 1002261663 210383369 435437236 1149971895 1017702297 733023935 1092014334 824883838 270544234 754418454 22584190 946997277 245590712 72168535 1047432688 519743946 756405125 288943789 428796520 897330630 656269227 388894024 677664143 410506767 549935677 712637979 981230797 18626038 903358684 168334158 747856630 900923202 30776815 1102875504 950090931 94579873 155910052 694409402 520579469 359326628 408271148 571193757 23614314 125810500 1080448798 1090322270 272564500 637762844 1070448154 1011543577 589189899 282576233 905164826 189600250 522098372 21625244 83772370 1001171871 956399887 221082686 431865162 632498171 599785963