1000 400565298
516791234 426512967 232726012 251805071 392442206 94212279 140077328 396493908 250556428 211533630 897500617 311556822 767242562 739074984 39545824 79496646 205515364 185189911 161737597 371552445 602402488 875547500 528174778 224574325 752669104 166190311 550395934 892422338 274607161 859742439 97703833 575675763 172034669 331028186 782755181 182566480 478103593 698972851 761978982 454429357 230721188 493168415 150144739 641130827 904436388 597267217 330350658 5811221 819831962 99419855 13619116 1978378 25075638 974724157 40756189 472595019 630522239 268428272 719725535 4452337 946285102 847867852 92357030 388701044 692142778 233275512 73971721 853964288 326479582 788903562 339478007 112928964 182531614 856391537 52931927 571090433 144417591 278844811 248694350 532866970 196893182 828959046 148432174 794549761 524327746 370853454 969555267 11108471 893156325 701117031 534563074 732263493 41560221 439541054 306883178 911358412 295416911 545952192 944339195 887523566 881074728 282940713 62424935 267163788 804821364 429054581 731133711 515850608 848403683 392380490 65350223 263114365 301540331 131375744 632706239 223534664 103520924 981545057 82965981 146583697 813117672 78530746 966450233 816217655 597944049 485121145 699911652 711343173 908827798 672551668 85818727 442199657 738400252 290736901 301953288 179337904 57991024 511013433 22634787 569601750 691440292 400000552 344551597 752194549 569992741 220039471 273895202 544931798 810961333 311517602 293485685 852577904 172127480 845330710 689580431 660551145 395411902 856950278 61921631 669983164 239350586 792790009 137770603 948350119 74694713 771282538 54900906 63720187 323458763 591632768 695962233 135325425 221704969 697804114 865069454 323432541 810025317 173708211 632061315 30608638 46832167 939921933 503369994 859675921 55037141 81600738 943747452 178553712 882202953 805297270 506496088 174788465 311621169 508297225 921557725 239082823 552891660 853255808 473771503 32487441 275683734 338915539 705903433 183474752 925479023 689822718 350540496 808079733 221900603 808573256 772913924 995758560 65025819 914021013 762550376 891601069 830006045 61805728 134818612 41257260 867679077 598342733 890333271 726103695 491811909 470146906 785234280 815009482 261623471 292719545 877791130 917223840 291677255 392299291 425972307 232004437 869071758 241781783 751870301 437866988 886073805 801722755 943705202 674157099 745875773 99505695 530442490 267451655 58219050 879999688 172419885 525597876 970898107 881447492 184300302 120350266 485919159 612584709 10248135 666691719 844999919 506917826 452381625 713803709 806213421 885497883 945807126 869662917 59008034 893527644 738198355 406345397 942889426 933960010 848491989 570829625 307697383 700010292 616279424 138321170 153971747 495777677 356009328 834605091 157038477 240178513 452931609 961833161 262632730 508881089 811894101 486069775 876807326 263153087 934937126 108151362 9969892 69008556 741629763 887598435 410493136 364092164 537175244 625809058 372765514 855094190 882271233 686083751 333450224 466462979 445177976 586152434 244214611 236449831 214263607 470729115 932287052 204595540 823848416 267143190 16155348 750951634 289444826 989461109 646854012 267871910 598756420 29015324 571935407 59853872 906760043 381237458 520884865 938607869 518486682 870008913 402395804 825634915 910150754 783065958 135690143 223369064 260305156 784589921 308861051 516317655 713763000 976242372 682991957 227512643 436792412 344718888 489083569 944204425 18609608 204913288 114763997 76913505 854158286 634049044 182006471 448444100 831597827 455618454 167817402 618855346 201996572 845686527 250612140 39768117 150872598 17623167 895698264 23436087 505044990 512420617 761905287 668377813 42460797 948066632 173259938 405745727 89842444 984143612 812219869 295791113 94510231 423280570 306784064 110359267 232289194 156478075 849241526 194048856 53580940 322204175 229533656 441843188 374204602 432557796 825250755 67758173 33284520 551329550 932044957 994966377 464164291 686754426 264423794 829448215 184119809 296174507 868406583 756961504 662732078 621152845 24917991 70090223 403506058 709736015 794345927 868675667 871956503 389703324 857917016 376043855 309241393 500593649 694539345 105486946 188607019 786558533 151756314 915415879 90828718 606437968 622377950 417616912 146783457 948823447 585114854 960029088 811762937 623703628 490683940 21071177 295090360 501637939 4196807 547968962 584881498 290142641 54630786 429133241 783396098 15492990 293488938 714219988 614885726 728718983 724504689 498355648 122063575 167735745 741429721 318712030 304389675 198075359 319587939 591148373 993718647 775213713 942301509 57482933 300011998 68653046 613695199 189371371 421671395 564596598 776860423 244182724 60916703 58127947 117687801 614089346 672886244 393836866 645389412 418181296 527821968 588373893 176818555 680968606 560755459 996164361 376495349 904528156 511321898 735881600 505026458 921689516 425093166 205107364 462599965 616828414 782528223 661937161 140914140 691778021 338310611 27734264 175999499 361608123 572701956 107568483 368970016 346059999 237775795 58739974 597695549 206608849 60842724 951507790 574513195 174289101 522102125 809721849 581943063 586358080 537389799 133843371 431483725 188922324 31632299 987626168 752121590 325725493 859102994 565286026 700705405 239157314 244476718 820255194 477302884 66716941 411210021 29077760 82079561 302155447 289898528 369052034 725572617 219987398 11302102 297626481 289567505 320569899 54508031 243759315 90091523 542320548 220625000 214211273 939291681 919463249 252161735 116734115 544422552 542315401 423166830 407200805 74384635 124362348 741717146 174236416 45554610 841347963 904042536 692406503 7863325 829209147 760180722 374936166 870596867 318065423 295013093 877725356 602360725 52329605 357564884 171402792 608107235 884507463 16255496 774597854 338370055 596753983 471804793 534888953 247141720 702566322 26161436 328147566 910425033 370160083 969808366 589473922 948196734 879665384 28737967 97956810 573785401 718637371 100642646 161002693 24057929 193240247 558909196 164734676 982219322 901721613 763304402 141514408 329539833 410526155 810834771 946268207 283119337 70711724 31573351 22509529 317674785 55494164 66734140 706603873 851908268 576312277 570819910 520822614 642443867 777381411 748260053 288320057 866151604 335976909 127406772 842004681 80397502 373439803 258413514 222899122 171420059 897263412 242772734 66596972 606767571 285239224 837896118 169294614 881620058 54165888 481511176 869481738 261307001 257510720 727583624 369725234 115329620 90609085 990337717 387853878 488090082 137891926 34900293 341838894 276156976 48259295 940168859 868978356 667288698 261704572 1632099 298453383 51672291 173471797 29814255 130054312 629275435 255765288 566182946 284714884 32923941 613447313 683307935 215311863 10287372 394376761 299784127 478198070 835203603 836389776 80651173 31809370 598579671 288149326 976400130 702612222 726739680 489160634 218598280 844397276 27749639 185763235 308198446 1298352 781313882 526482897 234418457 159037719 136783675 160369691 93257546 663296597 575386697 392306272 355102413 333129973 450595378 258098843 269582148 540762748 858176028 294348607 690118889 473254535 49929382 118398339 376017398 679916125 658187241 42210706 95676285 13922459 416802390 960708223 921812656 370116523 904806171 549703445 832443970 266600498 416970870 312010317 19814836 146168915 734160251 113255319 677627905 186986537 460907840 197464039 858799226 432678425 459679166 377959129 457569811 148212077 343381259 846379823 44980155 938725460 773229289 866157385 56780333 10799235 808696473 757411822 45199764 652486541 587812424 379788286 146117210 435531585 742323455 594822776 490179142 852852159 254764488 612527309 392839915 917497299 47094353 116118731 709451954 638073073 412908082 681968920 423041703 927676350 37804615 882320180 800346292 363807147 135458353 969824702 536694297 275828152 118798239 939033687 3850010 975509922 325383438 244543837 704083243 632828869 17307886 921219805 854435348 335170683 39208215 410038973 107360169 940170570 43207224 677516346 4306292 699300221 896968483 780812012 951972644 346782366 875861320 610602562 581971474 247233948 268985404 206640013 749120958 561648451 372304819 753723694 874124415 561566897 412026021 972431643 571625059 433638166 573912120 415555802 113046628 876034917 215932849 106851002 797362200 100840857 327944756 343371510 675404827 902232922 304922833 179095214 474551745 853944098 375126739 878622463 223278468 776289898 344469232 238343691 924562634 257784152 983971933 447443498 273190651 484600103 205748275 207098967 771394996 932536538 290591406 311426921 295280999 767940954 500658631 78213958 184802619 40724667 582686709 467181131 602281305 194262773 877096527 384408419 489797107 741075219 212455457 705402867 706511799 286368914 925139734 923773597 273856803 802371720 250365710 353991489 613767270 16006051 672929932 27408403 650548164 949629327 596888081 912647727 937586108 380991839 977975042 765152577 973911975 239932145 556051054 590976830 554947555 569350130 136133150 915232329 624786035 891606147 987018070 727090411 650785112 877205280 718300580 288109430 999797243 456587405 687309422 869794794 17550713 754440998 229530864 964982935 54784692 590312019 608529165 552373872 54673509 342319431 101711379 271624267 174890258 387264554 831269646 56543636 212786462 829081931 994977430 943875112 86022125 510126917 693132004 769265717 420238684 926122054 674579267 802902459 249658286 294152906 488375229 175565370 204033280 192417050 635629165 294903390 75968924 56181372 289408682 557700514 966157782 687978744 137225937 904691335 66374729 864516441 431111004 813505961 728623859 460939002 543902308 544787152 816226701 60315580 331046168 382876279 483912238 914739510 514168664 44210986 113237988 33864936