1000 151197835
530814538 122812139 317928176 768053770 839370058 167046287 751766503 949787097 297649971 172317591 178809053 412508367 455121260 229276326 192523231 543585302 190856247 251125814 85277914 313216043 243223338 414935948 879776906 875623370 374895761 677433890 508692300 102373268 775116718 831474226 702280945 847501715 46781306 29934198 176459186 982446301 98719598 617124959 260244356 629248712 589044382 96396858 477678916 676163206 132513732 200353086 77274321 493779942 844757 180912534 546613237 475910426 145772477 953559616 574804957 317320115 892867695 376360675 342583064 871224507 682921567 244163166 507305842 259485328 473835218 635297943 820452889 101805266 599799184 59456349 366809550 490318261 318899316 839989773 574381419 751372704 897465173 267446429 18015316 37878745 663106607 976141693 961585729 605128432 919545575 958323297 64456734 387726253 349883987 991288991 253275565 206594575 841367205 393004965 110837755 623576712 424774575 839523965 259169114 697828573 330379531 808043531 171248941 731082346 588363036 95796792 216569441 668426945 881042270 976320489 207098640 209884310 3066879 208238681 708909240 369805925 738515288 399673887 553440926 507372642 51816556 389509668 689738844 786510232 725624365 280881055 312693712 81006491 522979856 472345467 164934118 80128562 609347574 760566956 857795332 177951832 693335366 103549186 12056083 646838874 103118142 713370992 570423157 979913101 24483397 338447136 721932539 281732246 788998068 642530453 759426724 516067809 445574585 316157920 578337264 869831540 745901755 349531134 873008406 670199909 733617504 389170219 90201365 521989536 798683574 891034643 490795521 299317803 128408885 805823400 61354226 530122094 328767016 931719888 128286015 681539586 115528087 898869524 144904633 896098419 166421246 567433204 777661112 474388470 522076820 118752610 155775219 741860975 430480983 610351352 614391201 610332381 994542847 706343747 881828709 946557732 619608884 351129224 130507994 640167473 710282070 150604587 557507651 162913922 337279108 90120849 628048211 239512140 907709775 254928398 822670061 767410260 195152521 536319943 378429793 564767603 415068088 34966962 500461278 907598625 657399690 983726138 304880007 554120769 429858908 324666973 949920811 694816026 575354974 38290657 457722820 827890973 94766077 750509313 691850882 611400557 338012552 510639395 533675551 929530213 808836493 384607684 706120844 549270565 326721014 1402969 210990474 274074611 567702494 702733511 137295879 502798754 478865675 840822368 744449323 216539522 982863936 44698598 353405012 500803385 261802017 344026679 270475238 724021495 438632258 608868428 111158235 388698575 530901577 652635489 469694440 421665932 852638366 637164965 111387432 316455674 54672172 191595029 324875726 726187060 590188719 805085358 449473356 640986615 591409800 888596371 618688479 476104804 388892582 820205816 347644010 390223214 242323537 775474189 368958645 556807149 783800981 11171405 10710286 885135453 471949991 765935101 687784986 69530416 371964912 658465643 362499161 733256242 945947294 863235703 322047528 289353052 213156295 942558458 793540408 603608958 96270802 461013468 754691881 689786825 9594448 426628134 624720631 187917223 548001879 645986346 79836957 69064024 179472229 380141024 358178152 754576872 626973725 606252678 723941896 225906090 193452128 747331606 71949175 9467000 8522023 96504234 647185616 606048443 767172226 946104260 431120056 133549851 894141430 229634180 648130820 644150785 443212367 579087359 162609813 506309000 196432459 988572511 834858235 152227010 508356287 981163947 129125182 215579936 657293186 273780774 238873922 484524139 717146578 947437046 960758011 290815981 27058268 447986399 337621102 303012714 166361061 614532412 463508994 903739478 826286541 246935075 889560435 920650103 600998927 104061269 214354539 174205429 479194116 473166042 118315981 645844523 908180008 779081860 147039028 854910006 702192723 704121085 39791220 790043003 512944593 948969397 780476307 879412834 467333336 661868130 907733974 883087415 339469433 537946199 657625064 15394530 462197088 236852798 819276505 672014354 628012002 113601329 815608082 189985613 154485715 259667256 64827061 619441578 666700894 375498632 720450362 122160200 30656798 520332768 596646208 773322058 302143771 786192960 599406227 756958609 238743369 203490986 93086189 832634710 848123532 288761305 116599221 574131732 911046732 786176141 354232160 279502613 107192562 477481319 709819195 146379738 729102947 7113551 599766190 206457349 666367737 320622876 852908035 488338218 552000826 834802294 782461120 162663746 53879759 915546825 264760310 281443344 360946779 478291395 395959821 966694272 784377700 14155289 216376513 700013394 35410857 990895785 665300456 519402905 793370083 692895062 608073246 495083290 270181187 406195253 470137739 136744277 935691542 339575771 257513383 157155082 426413055 633427139 295361261 497609468 490550324 495663884 988489720 195909880 754573230 884727641 739119336 912689645 337685750 101209053 46145124 483902111 667424361 891380593 258420686 272806031 112734235 224644095 343822984 870080468 802280168 146480423 41994320 112632263 953349624 961985054 726323878 480532227 168568378 220845470 377603559 245311419 667589250 718339945 410049168 889723725 558466686 790094920 193263222 982457047 664402198 990074900 357156647 702193905 562528440 877943096 626346768 758255611 247656717 635126242 711950780 74633423 311562626 441699742 969531963 671708711 120281358 139121741 571053088 642805928 499787557 870007006 647317314 253035108 496449309 644912043 467192530 47780635 681425984 448166736 41754881 695839853 818180099 142056695 358201277 429906895 42359285 177675199 336681764 356059901 332745412 176319970 570556018 577028005 21047062 627903233 380216579 174981680 890153472 868768881 956859236 227556135 367089727 213941660 547431470 552519673 929569702 580346802 737752983 444051707 798242827 734630852 8023341 547162143 172091853 607694317 432295652 110164331 671311708 25186017 674151757 615005656 505695314 224990347 346669517 202369731 36321051 106924638 793016406 785334770 435887627 513718704 411051866 376567590 420499719 360905622 957800394 979530259 524276108 509906430 594636584 3782908 109763500 929927105 27609534 500317338 975353988 234428197 507913086 157931353 897219645 248495409 92857546 703066988 982530914 877638742 27334433 411656428 429859328 452419698 747175662 769790817 208332975 261218246 236925285 450963301 73500065 331009955 86158362 33439102 937324704 732228137 945703691 435385655 1866375 74954450 205215007 161891739 94596287 348463855 546872368 411834844 629064897 964047561 486363544 360622115 738176572 714188238 353427725 444175241 106124252 66680627 483413158 263412655 404478839 415606458 334303964 110476397 819905848 94681912 600999987 349868150 168198142 732433602 27809814 122470527 909254328 878668520 133112092 410478211 299854586 615642343 441993964 537359003 883914437 260320301 886209328 176844113 190978425 652316384 400651565 270243064 360760652 277977326 985845434 712705827 160164449 368403806 325705564 934207781 724658810 824162312 316849638 231341993 284307589 236406106 671342633 895064079 955072139 836832787 759630177 726752129 376743640 468537328 430363405 811339623 689257909 873636350 235925867 749550791 862362891 328541438 367850949 328074238 365846629 421575182 106943844 841182393 845998219 556515231 374352921 862691106 56412775 115545152 144049405 640778822 690569801 681571051 47057183 187323625 737642039 384774507 818322433 312103377 745590245 436136893 212957734 185872029 718082645 829875798 987637642 360697685 133871272 217240329 633815676 851796819 354497060 817915392 635599875 58450932 193963444 766656339 32592899 938868576 224323150 822445878 772027510 887734153 183902544 405342912 916800710 979933332 271337231 832124057 47527012 542914723 677213589 407789462 581490598 644388651 992191271 373963233 440015450 935467585 418073770 33167687 403633636 132819200 426273827 273219426 104274630 215655930 221258980 491301999 245959414 40551809 194209068 993339488 97881638 962707944 305412390 801655677 220393805 678437415 584461297 738891813 422551662 959408544 856949442 608551001 796585420 864002910 272717063 37804141 657194934 869748412 527784307 375251454 535004080 79529888 100021445 620659706 453719229 347502436 359387282 288836223 731243461 116535857 33573605 588322652 423921810 806901662 620646729 796578929 427440367 961603351 784213741 71013819 786767137 96852350 606840734 474161103 284484190 283534208 359966348 280788535 786385797 574112753 589291335 178585532 423541235 8026079 984546532 432092516 932720896 429030495 690696272 703923819 253328004 952755416 40465809 218772264 512530755 7780131 822037588 404793324 669263784 988220640 959940830 510017348 574873525 427514860 340789259 835489924 646588346 438128757 320394405 563432367 736563815 796633418 386889845 724816212 543175377 512689849 661116889 404754518 199221652 391075521 367770208 535611947 833844483 81440040 222990853 182630064 138469968 161340294 859976523 737158623 460433345 35829062 384950930 992885603 850942779 407635256 284120864 143147105 862119635 994113536 139792971 632448353 250353597 730937318 951650090 80098368 691260768 516730525 490840719 601542685 88582579 918016635 767018484 773222805 868944572 622981992 299408464 621588590 756521269 934818269 200300823 831475142 791723247 128784902 582651836 897551732 881803569 497098183 171135277 619740839 396783736 936257538 848628219 654474019 324142978 553234861 137317499 238128181 140470707 156848740 588248807 396549792 98889259 674105792 309233441 600576610 821746614 540439045 421913306 937021833 425894363 307491992 381350503 494211598 31256907 351449683 189356612 169846744 582075894 529687672 772754733 508491281 314011752 730671167 307806100 29547154 75297021 364018541 906951509 383014464 670861894 413499964 641515834 510744423 702945042 330217334