1000 358
668233976 621665440 456884646 288569959 85066803 874399920 233173756 112427322 81371723 212434361 322017340 183033294 611327422 403026003 367626175 745232960 726227187 526907446 678059413 487676330 144691146 545971 168042519 425401731 64435452 63553780 264332761 208253257 348356750 932393943 88248240 215398207 602229176 858337637 714375736 802893374 157222100 159146240 342137511 605711955 727249913 115661869 663317919 727888157 854460027 637462280 554603386 811938563 25756460 479384556 57320619 914863092 80061094 49348947 517137277 292888566 755106179 715052599 32273289 418109210 456687595 172951350 824797709 107210745 668605843 817339115 545917598 473142978 588811704 882283669 896479995 733289134 575077816 409726205 421819222 373511010 702951711 515638348 357207421 889059948 972911745 737278578 872302511 5152964 156653488 694157848 684125729 919507411 34070765 710455755 885207276 177005776 844853584 483518131 510128004 140316024 127688645 358995278 621473030 937117047 239337004 923305304 630871066 282836852 693745715 339631049 106254912 600212866 476945891 963197296 585593382 147801335 253625709 256916649 201010284 873556830 637855753 491892233 760743564 898961094 359110658 185517893 708897555 532668584 587375312 326269630 809593380 316542565 204072059 446876959 796396767 433077452 266407906 357346881 298264422 914970765 978172174 731744189 46013576 727546996 189753619 289913449 520874795 577709422 375994266 779179433 242099705 795590366 684552737 344530463 669236965 770872756 963740991 735893897 878600375 141506482 997436126 865945470 362887998 441321471 45234489 486410452 325296806 448369178 496914748 567846005 172195710 621169252 85076078 498179565 452728857 866788537 932665534 627734755 763165006 401427953 311486070 416691755 888615495 810838613 697274291 348191943 463344021 211454795 264619534 59383185 575533886 876026850 194900999 918546448 741231668 120120177 936927880 334473739 659267869 175372071 724994095 115898473 164488411 899866739 748223969 56877263 497356834 980485669 87382695 96450862 386447404 863470647 729448115 566506106 578210349 367917492 306382650 342342371 988749002 757364141 574031844 314573294 944949188 657318916 559774230 517326084 564666534 484965652 51170435 901162175 104078764 554645057 614438061 826861603 731633714 725573535 244032432 38557243 963975721 773110054 741238078 216870254 238011275 903149645 644420286 42924194 339756383 333072030 727480746 99732946 584592574 475589116 756653717 820022441 251463789 298187357 932295313 150934897 993001314 330267041 164532716 813880139 512905326 140383952 863476224 227362452 347697989 68851964 242637327 705710041 731065213 395233241 977517822 310839979 503747815 718626392 392430567 335977546 391932862 727771268 794506454 815199392 706061006 217662842 318917321 973818696 974588656 162357945 891580488 290840906 700928069 179795288 440777193 345505660 207295978 480060886 664964700 522175868 753890064 853606041 604077547 889447908 495616780 220103862 118041565 622894030 784730569 111496059 491591429 458969854 854114884 322333540 134818645 316500744 965089387 482584239 491201043 729827642 72350370 69182660 280113745 879173336 902580209 734813778 334017955 176499382 970078100 939160910 444121410 506312225 367046242 999808576 789769616 197259472 467119404 534908201 75566561 290248043 828840906 304173557 790462290 591065381 514992910 921719070 9683318 805263856 136357003 723941397 711990577 559173782 590857549 922298506 700044504 492361411 360934468 873832179 629376709 833981648 434826638 213835349 413801019 771225463 415032618 12171164 32055622 322829538 60995007 229567441 849319162 506862957 695525542 736853163 230411707 97676371 118126705 514922206 40710257 938412025 479707158 228646550 587967124 677141145 897955937 592880268 920271762 10063695 366244323 475826192 930839451 708770388 545779341 43975433 574091895 879521486 178635639 520081421 115861459 30661049 244376074 224413618 124288894 953675702 223291669 582319734 539813381 107472567 868254989 287544502 794987784 456703628 32356235 20950066 698557411 411615519 46791787 489458633 998025485 243677875 784114350 588639000 231381781 753240121 490110270 235834224 744101228 620499895 839806526 639622248 228857388 948540302 133948891 778276166 931076591 848345266 670761658 490419902 876284894 185348590 232383149 995815295 128696614 129355766 350325190 471457320 252699937 68093103 72754079 943850853 644479100 964924946 251211962 719389059 450224473 349992849 288300555 254382395 921192211 265303325 450209166 127294021 879856685 525808959 44016362 141817276 535801921 316730664 452730497 626706478 326117692 727543615 300189459 24272709 266788160 430115988 199529531 652124597 492632431 853245980 345137774 475324781 330600526 969205878 66207177 265632554 13865051 13508704 911656757 483752865 413758432 256113796 677044534 823717675 452398965 232772673 200637674 310629219 929475184 791227431 122661983 715143252 481375230 558051240 91728099 704948061 229276096 418636862 685414937 5310050 526412541 11355125 550054508 511221789 832238864 83290983 60778157 51075480 904826705 965516638 651227564 859002642 640907327 152027232 30208206 664216 910072613 941667797 27981993 278325302 185447972 185897599 895911191 691508111 126727673 108903743 397988159 264649594 760049198 975094677 562947443 639462773 730478056 520677794 192846100 397918618 412052441 774500959 498388103 140957480 243623521 967337798 997917523 861123009 671115577 617656977 883779443 42906195 392966776 700855643 924839817 913284345 251626756 524577068 157883872 354224822 786860034 120277345 973016631 754901110 62035820 885021854 100002680 100251749 317897865 758984556 525950946 17060487 704271294 967054918 955550550 615058025 117819736 552439059 356314986 295949838 266283985 929291673 807418532 265905631 163558791 828146610 876839568 985108678 773710400 783396641 883818636 518989914 969167755 66074264 573443940 472413789 458412438 438255948 485030538 202796037 895512939 423587642 208683328 357757887 375350432 163684257 641132933 441374140 716032648 262799957 56372164 522062415 978153741 35160062 331451922 906231423 206063533 816364310 307172950 552581329 984772471 851808585 668577155 962395073 245277944 110522297 201096018 630831811 74895159 997994004 363213972 987889170 823753163 603322996 275425264 128020873 368490964 583192830 761436697 2064632 695946862 198911339 412433550 956123160 164319317 330440570 893772755 638390108 575061710 280859493 256767815 947821887 236790034 728558734 448385678 329651157 403147179 791761423 68880461 108165525 943142440 392318937 786954143 221218131 496548128 683726447 326902727 102446282 181476323 397025838 166289570 276649731 240490398 506342921 220528299 349897676 709700539 706410576 769633766 24577026 363481761 633986926 159393711 230571286 644734340 268709030 332830983 800255598 932249198 955568392 788660962 316550205 987758389 826805269 887363068 103990844 5315041 633981660 60335345 751032295 898192260 155977934 118932271 426002390 595583642 892707169 354821135 103578466 33771575 18096358 82876169 590585378 765832481 435531538 842401816 798689249 363223958 923455542 246772409 299153649 493590604 388404123 152283106 486272085 616940512 588151457 739507770 983853827 703965569 697330248 932079637 389548505 601713556 263767687 595197423 944625716 736985242 135548432 725783711 720265858 279171740 925395027 797253928 664665587 904439756 423054439 779408733 198990938 849382962 367475324 848721529 706871811 247617795 649534223 827051029 927976165 718981095 866860912 323365479 816150753 674682812 911450872 673190533 276337153 802355755 369523543 60570 379893902 647209859 560450589 672889159 668218228 577413203 286716682 777377866 19462470 143528568 399222385 301308924 308527955 755867530 942184722 342920795 888265041 603649420 860310677 621392589 652999761 298613667 344289165 460909393 548849264 684799157 815225040 773659046 98610367 647217971 801074878 385739069 41179796 31574596 816421031 901007912 807563806 9375183 51007314 102389949 627160710 783274182 502453080 60892227 169819500 885796341 148378933 898110965 773259133 55981439 567692745 950955857 982999139 514462459 982247782 691551 992666993 523364685 118615516 380595374 938256133 985359845 244569609 260588255 458212259 446546734 757406561 94697234 203620929 876648407 566311610 37534354 185816745 771241187 104736111 278328807 116558616 139133290 357639030 701440755 4654834 624497475 424853922 35581802 664197107 388169084 401688188 555679040 85794604 356439892 62688863 631718531 278116516 462582738 169312688 646329182 965094975 609536717 151230229 200950556 805462441 337840870 586107945 303252818 569286920 980409798 512080717 243903795 971763077 230305588 363844782 57470630 787915751 948443108 555294110 476003158 395633665 989032132 955465932 749701446 598315974 34245915 118916943 795545386 417539201 908733439 781581726 735740087 693747026 265930488 916340332 145435608 259377389 194058088 758193712 992886691 459875204 500021406 573609743 996540861 955046677 658604070 979286314 930428384 861590963 643419116 359097089 246577052 887700836 315022103 638609175 902978854 429996776 922093889 35742680 637840296 770128127 97896002 502105584 260911048 786188503 177929684 748022798 620053581 793567370 154389603 300651163 440847498 800798601 552440353 548846332 227870711 473326200 227156590 675125913 266945808 21358684 897057483 102316817 564627211 292177369 125811156 982990112 205011414 139745774 936844688 330596301 373105891 51053066 350387021 331268879 469993701 320326285 394160869 946807172 338281392 845154086 366479940 382764218 866458670 24769056 694728106 831031117 17768677 660536171 958145717 152364480 823571941 996071272 921059598 100233437 240695980 867114537 688462932 294266162 976761957 435353470 127087101 795456524 746688117 677508361 242531249 937864376 510020203 621140328 252473200 97810159 649031591 884360360 687589295 769155532 42615931 711870452