1000 550
53733545 643198776 396222743 570423416 167435819 273677546 821903907 220824281 700528629 153582511 883077597 759873241 966575108 792718365 774747615 550337725 994233087 532325621 614769886 361106483 37129606 75850093 14251510 984030305 342103875 869848072 823471720 205499125 866134709 424852639 960812526 652514349 65121468 552645877 44571113 251200114 913283595 324052320 305046700 788164610 557987402 162450731 982444883 81581106 400448533 513184719 665871398 221329756 400879569 232316498 768194662 525916643 527714729 498533549 237523134 927958363 271306101 503449281 258059217 196374148 532320331 27078227 703189021 84178082 949279905 419857649 694087378 517121378 781192843 646490593 168926114 471206770 374062625 658199245 413780223 716961 686380232 14780930 295891976 802733659 303291923 613702127 355889150 755737976 810302084 378403371 577590092 600933687 75277280 469169850 78246096 725316233 371286949 97659652 766591055 117491595 688683423 813223542 707982355 105372509 767210065 964510818 287152710 712639466 548256285 523994479 543352641 886118012 739632501 863330118 956870566 775426855 277989941 797292865 793281670 781490518 659970550 569706043 580237872 726851027 774879782 457149620 944032462 802215782 36691417 743531224 147400101 866291581 756287226 927489796 83791360 13637747 516123703 480421426 219860777 917151967 274295708 169934987 701840484 39222304 30192774 430145616 873319427 431253322 444478952 531195120 502393293 470647356 540047960 697993821 645544292 541822397 344856587 542340458 101107493 667213252 318378940 522390125 168142124 62130807 556133180 811258900 318028636 286453542 958067177 901650436 965734279 642233701 620125880 763868725 617497267 312510987 985378569 156098275 887283153 651467062 765069953 337081060 313590612 430235477 365539027 849336335 201266768 22331564 487148125 794305670 990368518 924292083 912150950 506250216 118349435 144179051 25190293 396234482 898637671 148974867 537170131 122744818 200189884 963912990 673653271 303421266 644223177 266680182 122085602 771091901 259600233 528319995 60077961 872990579 209860471 999853834 132305682 80284834 193236296 143078424 685467146 943103054 49499747 211301563 101854616 44929787 134173637 860362068 316541128 73573946 298750305 961841260 255063782 760279108 750536651 404422317 998022790 65118482 533977922 711614494 944202717 569834215 396610117 151385654 106682447 627341073 408773826 657301012 296127769 945418951 493406961 457835181 657043678 512488377 461050214 908538315 935160515 246402323 884764822 263346521 701977592 930110770 489684912 373448896 131687279 771632129 397013669 339843036 704401539 218128018 284885525 308819109 103988075 506965722 907898463 221781052 709050809 730002507 615276429 74921441 792498904 553315243 835646034 576656726 483458999 315670921 881188256 44467841 916419013 512310059 271551101 63825363 607545360 848062972 526584029 949369898 537945784 264958126 937663094 101374044 305188704 286725847 983433981 196646284 902131221 8903999 458722883 891301397 817453264 789015325 769047000 302878185 677894966 644826963 319833883 970410296 196450989 785555035 671527698 748973023 842973299 607624113 16252793 369940693 642803378 584639795 442873031 157281416 898087758 37764096 321472932 392752538 474184814 154129851 514767109 152742347 140439518 479830188 712892304 176935481 830476351 199879086 57909279 575138944 291388818 457062831 38044678 718119040 956544103 463050050 667168824 307306565 964200422 635867789 531494282 482627776 802068522 977583016 374413989 247767336 353819030 675057870 378267817 987370454 657862131 925993370 359453155 252567050 900367447 719469118 983274869 386538457 30426514 759490101 193623292 125707296 112249987 973095804 42364048 149498537 227740990 699535915 446793319 345514201 836990370 186937205 221824031 390854368 493945253 971359792 929618745 114767358 667214708 33093706 798079018 796117112 550993965 819995704 980466463 485794875 588662153 960932040 45510713 627716927 197982801 590997802 404773630 832943411 601277176 1116184 771930870 196699847 413086129 287141569 710058308 446736752 789869509 123795690 317260193 859724550 979270235 715622205 649656495 770996689 880998062 91120432 555937692 501462230 741603110 119725445 770544067 274040567 908248380 920547589 150349754 772627716 558283419 772056819 428378513 753086258 923159025 404643324 105094697 86955344 982573886 930877033 875451321 694393889 73826278 778241728 490966381 791614539 717559502 823340751 738151546 382341798 906494121 934781197 799865436 469588142 310930385 215959563 498434786 514624884 701785766 643996945 138436846 319419671 193990799 106806344 481042449 456864999 298245798 487799268 862559252 771405726 586277328 72422861 348665195 670430108 848833031 147989752 804878446 681114835 998354880 341983198 847307689 845086008 414456534 456371257 127498887 233708483 840640908 762524716 59757917 978654488 350271210 633643253 919737987 134428060 960766478 204373750 640564591 379661465 688648318 496577846 42454493 20141253 514480339 481704175 546868183 474884877 340100749 435883015 68596835 308657797 228907599 956941594 357983938 666005239 435141988 787628399 590926728 515595245 722391520 366146811 317631878 371212979 328953764 273383389 19691644 546963257 40874857 854137013 257821695 39202302 740244994 751297981 628313829 783763889 769789019 394724006 768919437 743794295 856567467 389287073 720319268 315387202 979010919 235482474 898825216 803791684 586717167 29080852 588157673 239097721 34267041 301360572 998526576 607630764 131575998 425817545 740347199 663061536 821015202 143061429 373054528 343453809 196852058 529310219 98759888 622565522 748606010 269600694 452653531 261170120 713717765 46383980 915407644 822710499 146583740 27946300 919171005 360634746 411626459 179906370 305267012 501767651 943062260 980648933 990651695 420985341 198892215 585628133 656838348 591170934 106495319 56998849 650914001 721137669 827313224 776421051 684498542 733762661 417333142 146742842 383066360 453880224 393122415 397159653 589711817 385759674 881567273 68292760 929066153 790304715 53529624 4929127 181622396 163263662 112224318 696827335 193334645 227431381 346607810 847017347 506531685 601625660 629461224 753260657 732142218 225808846 890111538 751381001 989088434 836053137 662856482 542017352 845364520 27400733 778038847 329972890 307532038 591142417 875692271 938093409 42763144 217504147 367351 43715679 273732628 595985707 462097529 541009014 638362895 406493473 101770263 953563226 673010136 84288154 801815866 951102257 185312924 34989336 415125255 538944402 519984988 945636065 451807019 461753916 799829931 110247564 960522393 968688071 798953164 451589297 77992813 815610970 804935571 681578104 66596333 405788842 235970380 982408261 153096896 657141106 197519103 757470843 528315132 21668933 671689857 609172292 470321278 945189964 959695643 242013209 240292324 250297862 763140227 850195177 870182176 945319907 562066113 371294774 456222502 675755208 596184442 915647010 428809777 95123433 555193882 484942017 416933950 780788524 400469713 648496895 695346469 126512095 92851210 860026572 166542072 618073106 851198467 950660096 771077346 601802578 281453728 814585127 377268929 987383335 926026506 787451603 818077228 491380070 614346297 588472514 221490175 573246754 44251975 49456662 431257847 385291562 672627143 422276154 828480496 129631588 852689009 41306352 32775904 4747509 244157033 356805085 339094591 242532021 188732210 555385483 802975373 923934680 767465770 39047259 516833040 435266154 982926480 667645727 144058548 84207498 899651706 611969763 116463253 369098943 163181707 765270354 696219203 247615086 109569697 123495222 565845099 107042596 420233534 494764715 728473967 562065315 900675238 218783310 769871512 550799287 849689876 717852672 32945449 249802955 310195503 10164943 515433088 831066586 415953315 843678170 231254953 377680617 307874096 938243767 945430970 826796606 294180882 317373747 353904113 598192524 3709774 404121551 845077632 116867151 154840707 412481489 204144276 843658350 255264515 523108848 884622054 608401636 206451412 359874019 797526361 175803020 808049341 570039035 927020568 551777775 115561310 956129648 217278976 9358575 742898292 898154821 196000755 925847073 286329546 240623844 166741584 45677085 172696683 848859786 481553360 168976056 109683060 396884179 321697623 453198231 426593912 324998934 24548120 426527531 388333166 311246803 94122434 525223312 493578536 40017074 825738187 590969080 818422164 152887012 80448514 976402603 601227757 645608674 834586384 7919524 237972546 39069210 761926512 269731194 890764348 763936387 806124155 92264351 107301028 662067420 9059998 551575597 191724111 436532391 270477345 177337151 616182998 32719411 384273175 512369833 703407031 514609311 353074965 14900010 154425423 642575645 312689842 361371247 884324226 481307355 958532349 459086482 207512730 697590398 788468389 506245210 273348736 370052036 887131545 196496848 165545620 29881138 665959919 226181049 84211263 621809941 973893329 258140701 700633341 678694643 841815736 937590617 566669341 256567473 476801363 773832774 621882393 656158435 528741513 399585350 469384350 706327553 759450257 279673506 178200957 299378959 171172048 400491980 431842652 423701289 320747916 552287406 74124520 383381402 844470491 855483762 771602809 632938824 543921496 913909065 979324541 366274945 72600061 984668399 766669298 711309457 266370393 768243251 368598918 578080593 219279381 879192559 789037896 97922157 144240101 779822809 840016697 652091757 661577649 840991529 59023244 879207333 810981735 464878398 627755715 962407990 904982317 813974920 748722302 869087274 561120932 12877260 836547176 947514366 278050237 254648614 546950063 630236821 293616820 456599128 968204392 611791533 226196300 581018583 15738238 771288955 325854840 551548510 502509397 559937279 28362932 591774107 559248301 218413382 874282775 683489441 704732188 983059756