1000 663
208122754 173264952 424403831 219633797 580881124 867694282 628094588 336961325 703447880 447640344 748252737 391135708 620857630 52029813 155583920 704573719 542321754 540074086 74814322 676140081 590799842 278231384 979406660 406913910 267247117 192649765 391840718 419682632 272562067 653491408 558910294 944689050 43786937 663457198 993941820 525159726 796753758 416367223 617373710 105549680 812626142 477074297 221409113 155108093 858433950 582187183 983595534 730247077 635532257 946495614 562759441 296852868 451363492 396905537 642652031 182951936 656283500 877940508 555313223 824077220 762147585 774959897 354161035 57290039 811200182 556719444 635301815 235013560 345587730 119685198 179301097 781613098 481650906 211581374 454068837 500811701 294623795 526096348 591417024 213282011 5397602 492261169 326420274 52819895 649064246 72454 25872856 880321929 576563038 415588707 376472206 907419800 757736174 496307361 212405709 431108292 821578184 295912144 206814694 81688937 606471464 309694649 198040996 608470266 547190552 762786348 473688730 540825519 223922801 758255842 583656467 157751591 220853055 583239934 508853939 882603222 856859045 217960202 863956873 227668941 647279140 748432512 465324071 812056784 669390166 248046326 810280943 331569805 791488430 631769402 548403301 398431713 307400695 624010967 657824189 496430035 18989530 773651308 968772249 845888647 329700594 863827210 417519052 611525079 547922952 612584103 717488332 449646899 161786538 27614044 375864709 299180224 318900475 63697723 55953003 437785249 453870665 849485251 87960803 596802017 882156887 675532601 529676680 188007969 817807133 261953150 595552930 163132148 935770359 842688764 81727151 280313013 732015754 562326307 682723349 141128614 795202550 123988911 572892063 347583361 301452644 330353158 312440417 328853234 887619949 600932790 354499574 315990156 814113937 768735869 765899495 90670770 510078749 324785851 912075730 669193132 300758904 602932116 6539081 119515619 757741254 439473489 764781496 309221466 195856674 631870429 815666560 129870276 858986519 670565924 657096229 463832529 519520148 274889984 628470130 747443994 636838690 187909851 848952627 152237941 229336399 15355932 917005474 861300356 949881324 492365543 220049120 516715613 105273458 114762618 673592068 107776142 112931451 333783404 249071108 516230649 164154822 700872219 858316719 499270352 908915266 831558431 313304720 377392335 331703143 28087994 464242312 426152276 136036001 85002627 781003059 322054426 533095731 985154687 296712614 857354261 481914261 236455712 592812494 375962436 344147837 431165131 268167896 763868377 145964810 33457130 681481841 38622774 442211703 117117871 87909174 628324980 608208229 414546623 116635350 848925632 133451924 284057888 646853720 489252025 860410470 706785722 726562963 545201191 986367584 316799977 244989621 152542768 826113659 540603419 596801482 142156499 754052403 939304461 480053414 539890617 124692844 174915307 810324006 720642551 347320725 103547199 162374345 771644792 533350163 457289112 528168881 132661958 260929135 37211038 749892854 993377995 358257399 274368289 530806799 952248624 545595056 501836330 944689896 503015384 979525852 91069719 689507604 950705826 812612 732895863 800508404 518727833 888126667 120257136 982277018 175676574 19551804 432166606 859603337 362258822 866637455 558138012 192718681 76343974 838401922 40346020 46751687 511103091 69326133 28501383 593162621 59551948 965206337 376341462 470523329 61779072 377758694 385469624 497454842 241750510 988192422 187770298 663866728 404679832 549509065 119903906 792153746 349639365 474106443 434873633 500699535 830002948 774294224 932806180 477117284 308338440 129134628 292642055 33424362 566518276 643163770 137414427 105874696 349712186 888116179 53216381 503497752 379068148 15614507 114151348 271098419 561812915 583168554 641593739 329621174 987091537 380774795 195138662 893421392 207202145 648984640 947419524 247972048 864640838 873689196 616054050 840663199 841407240 639371165 209692144 243965385 874028823 811244836 867307513 425868275 248112247 279965464 508373317 215791064 929774265 252323052 679149995 456808568 660519108 616742509 559764601 902576730 268831563 827813066 978415373 204517101 447509641 893494543 311450101 344719454 728580710 518115738 607704817 330484228 342241303 814970880 303791594 110337127 214506684 923326415 78486443 218093355 625710912 257835301 505693639 175708974 234848418 115657783 55124526 580876817 18901072 439135269 738495930 816899858 188253192 337161161 266643619 780156342 14112192 586327383 150639051 687642485 874445720 470567897 242060839 276916161 953958205 7370990 164346837 254049818 253261461 571263389 867709972 531933558 426608337 965070738 267828939 711215933 692813767 159433627 51228399 991562382 890605179 345405706 841561547 589939810 85797038 124611726 798618744 710147348 961170437 930318577 492069624 300795086 568153346 809505319 679796735 974930200 266726943 314838008 649661258 151039244 474867499 964856669 405541802 624254394 902801560 162691527 797903112 581419718 934607626 428959551 836651826 63401245 41810598 893110298 606529392 835420501 697636887 206011712 664857473 834456969 271956433 788246072 425630350 741472655 39029142 239378523 94094129 37455146 560511901 818068662 582411766 787041309 201229293 194556509 448202724 264002010 472077260 243931210 11336777 523613336 142520782 727640950 624300063 278750998 992820107 181311262 650391749 718111370 120216664 937686721 821440296 364287093 431537722 483289691 83700206 913887367 599824580 772565430 228046099 174960392 416781751 205150396 318294255 53599725 642853946 270252951 431034675 473328203 103982094 304199688 215675565 471358066 500445275 616038932 789184224 930873470 9743260 923496790 612427286 622268054 115881756 366092206 604049429 257872920 836807631 606942783 228482967 647234384 495514757 267981247 774052926 58605986 175577479 353522317 152561142 954541064 905045868 224547971 694646650 310212472 736573364 292846165 843968628 701366124 539425777 735012055 488405500 444318339 556257349 912818494 717017966 725246531 390937302 887979236 95168243 852097041 135596887 772593008 973902958 320930736 51717663 136850988 711619334 673290119 943681526 700234494 129259542 752939741 722264376 810639465 302456599 399526691 236965019 373202818 852622606 315793137 909353694 433083463 347050509 871887927 632647540 1914480 175937631 550066176 789759442 223692083 881239891 573652060 318672354 86220637 652966991 84708782 876417703 189986524 15374902 985055318 855735259 645829290 572114349 430983213 414015386 301566572 522615844 580835368 824062008 453198260 722129554 462268407 501264855 384830772 487652330 241236257 899257714 84451169 232342202 686189655 95701697 177249864 678638116 425495199 702211711 587247573 568386030 146856143 262536544 597359688 295953064 362174498 617043233 255602358 272958346 548599102 499621208 989059707 332074349 768586349 510438176 285256461 229363897 501535811 198060477 406070580 733998338 525460666 385727539 691548894 232566190 787741652 858420397 955783372 401700477 295058104 115870164 324255256 708047967 22376187 279971990 299661981 565242244 941709077 623693036 833399538 962574373 118986458 191101199 964639942 284172058 887910703 932219830 858093720 718292902 923982049 449330995 533987860 734773397 970956725 413385124 26196989 410051524 562429879 156416757 373094972 522048248 564067066 262664409 898365415 633593437 449365386 398606186 227452101 853721033 358740069 771362594 445731838 147933231 454933699 591091964 337832906 713740621 462646511 514440910 346519611 113947284 300584396 503247391 861235177 432898988 845163779 325754439 284019183 582535572 892105280 324872331 423660626 235556688 345057227 735901277 214393962 213371017 711004257 805288257 29144754 979161003 600824846 441238717 27979259 812392388 292327401 168367723 973002578 797303502 591834875 962467157 293013544 517023399 288332820 255719809 125394472 160826272 330807289 916626833 450324164 324572537 713720213 497003729 566648544 433431553 41800891 435215525 345989808 765258266 50998659 935158317 938761518 636774678 425484504 957138222 598823553 190444665 730283229 563937282 3570917 685506987 105616876 714976327 536201858 755847452 601193488 333150099 724306670 882194581 114752863 131705561 357256256 278535713 746781422 468714006 239185331 591998090 967475138 295284180 974451571 907825643 485506089 451846833 130289811 100337337 18584112 819051765 118221380 965453900 376419608 346327655 338101112 554643586 772803739 583070600 569762522 801620917 438793871 151838278 141142447 841254070 144879171 721609497 761165221 34920094 938772307 566915172 256890034 28033764 528646019 496439942 819882919 599413118 806900429 634879703 642857421 926878670 42929340 297057022 157947565 844565859 840467562 452221208 811980289 666939858 666600610 807943420 577218947 724041170 266751812 795500587 663335274 636069510 107430025 800780609 953676064 909013475 573938418 904418849 73445284 327888220 859815565 971972824 565358519 57666998 225589669 616402698 45546032 495224555 984556701 230476074 495178437 535148051 224026504 65954659 575959164 553714160 193200578 854465441 262823821 140972409 924871209 325352189 304191533 631123274 528500738 359301282 292881348 415003030 416884254 338450901 590597307 482669893 761960821 373195957 8072026 144248326 213870980 198812797 803113080 79246593 264669780 467657071 112399773 845403936 332023067 90551085 679898624 658725498 652155528 420223158 849048566 871381020 940764553 363313544 673022996 694443384 860223588 399112225 262687119 541948443 442526774 774945646 317889666 967857080 769293746 134887448 748055414 529097064 401320977 132268644 666478314 30503725 13057932 747950620 906576628 983271318 422822836 595403283 906292244 72432651 45536701 61727984 83554531 314547360 499883118 380884060 222109490 3866482 730177581 842682900 682888106 468579764 630667540 995707682