1000 1000
0 415335212 437019262 878914770 692819383 929176066 657049555 799637676 179913266 266003265 731227835 705323037 201246867 183631677 270611175 680342740 326297106 21564799 746492922 599870983 729200873 612278331 480645345 574356910 493730340 591363277 253325503 325980362 738703013 254741788 329123773 683907575 669740493 450885554 614018844 374077434 163113062 320936537 601029514 951620049 216328970 770681525 378142883 85032251 155899669 629223524 235246972 542322453 338915460 75174853 573887052 64213608 920497409 576086096 749498946 767197067 363475924 818309531 279080911 339033753 321770125 765774517 173557204 514849000 829916620 850709523 182362381 782663364 842602014 214140041 530278300 240708812 653573066 302927689 252074632 223654983 610761831 555859320 355822327 958417890 199402856 867137962 905986212 91242177 347675278 449364585 416436444 86842727 943981064 858527700 176373492 209770066 315153329 597307279 925549009 888137901 434772005 971860728 540722011 508879689 276569269 899815865 644228756 492316089 766480007 143772726 74583140 402265862 924734031 510463898 737656734 199740970 876483237 302775122 746517968 79257081 851523674 952372240 774957950 645014315 395646527 838098132 694970240 882381640 299219187 194059538 143048311 519832444 189284340 227491612 971522619 536705246 518293388 781912266 451008092 916363327 379872962 510606382 698548075 589361599 278705257 383112952 984382801 323952534 905975648 438699941 277623576 149001525 413099362 252031418 988861638 756861154 821558232 43108663 478472091 897190804 142238842 310887685 622789930 884147582 11776394 72340310 302339054 829404650 648598586 715960580 608591101 184389331 822129349 88501953 212306188 738892229 457529955 190845897 656970683 477965779 831791147 901802628 849278450 763726707 722255436 212762190 134484678 185931654 503003818 336406888 506820842 843374043 242719767 829345542 399710249 18316929 132876288 652680078 991071283 934062668 716379281 334307859 894537255 650497421 261521120 629193703 164897301 607106868 785569377 515946533 90993685 291104268 318102593 811382590 568786887 107419341 135908712 755143582 712306072 754250122 489546191 640259471 655918460 265991488 357878405 681113213 669444191 432251035 106885967 629061588 409573091 50381254 687024843 895022388 960006315 560844439 41515461 167917029 499799439 510643462 305623388 949635560 562391304 791047020 722231667 430725102 667434084 168118771 13656249 934765012 70893525 60874933 104607756 650374714 687045886 94740582 533755059 465656151 684313042 341719520 412508310 35661521 887144755 982432390 395259787 250662130 208013947 957758072 445716160 32461513 203198044 4302363 38081289 193842662 911976105 48613043 104781220 374172687 649171810 636639089 396975967 841242960 8038300 150970981 954687411 51928121 782406210 92903798 373657405 680528957 568719382 320203437 78837072 229695924 481447422 12201658 17676805 915536143 322135324 435510950 74130087 798551126 962918956 689824454 203165636 916771872 700254844 942481030 482471172 489133235 543164321 517388868 979063267 859572347 106389501 639821517 472061737 347078209 900869054 781417246 151820261 356281937 373794558 909579610 629587423 982727395 313206140 535886485 820756391 692459745 339603666 666027806 751752110 994842530 129469518 434280803 271407910 315702122 499590296 545523930 18756261 756328808 20371051 851127068 321514369 973051161 982917395 39683407 452956276 764563646 723103047 694848782 135161508 42071653 18148359 436410473 743399096 895533552 938443544 946304800 941441746 575543705 234905292 892343995 749361956 768438624 539411684 828972664 381905753 157033244 920769087 979829351 698939285 7228517 605599204 970270151 937356578 672701876 198121864 109941193 179382555 249165508 946994168 950798829 368329526 257594009 924941461 745458324 522256226 353094399 853263495 252021045 56399896 969199413 12045898 881004743 979708071 899815845 88049733 710121001 333221776 488618492 282050007 923359932 278215622 278855153 279637283 937620612 617917595 368903611 439923416 366110025 624381625 257628615 101291959 613556902 115034954 28272186 772531428 74344912 133999519 706478882 167851788 269073721 190483917 954826344 454052331 577064819 57365298 548893067 229504971 278079836 902016901 714422979 731069349 296275648 654906625 25705677 138454364 452571541 983045190 977656697 64471270 668958455 398735123 934602118 928137550 125879437 88392576 854344501 177614693 716533186 653296783 101831302 387243285 766529944 412466445 495194631 531329903 498334352 603142599 882787706 613823467 708490116 658038825 704943949 871681372 257744016 243499717 685843446 281478001 272853996 250401958 572621924 870477098 156038486 476805780 925779284 791476485 965279677 577657678 913962488 874643231 870125515 894680343 927394356 178706911 451172830 369735939 863494753 42195160 18976771 359055554 315303146 322118336 772379669 848728985 593518111 294397480 187677119 572326381 214489956 265652279 992226270 437447047 910245469 857443549 264109589 705470700 672455377 279928487 786525798 485213494 183796397 232342367 491391122 898608146 287994458 97430663 522269154 181476319 922360569 128495016 430061088 900598537 975324493 523511380 507790239 598948964 976119700 24116891 466581456 923204982 360632607 384218618 553397219 758743009 698094764 542425053 781479970 269291192 593927519 961966795 375700956 330001184 652791330 397940157 703367500 28520407 876732642 806420735 552167172 194461067 612072766 560264036 614191517 390634355 520864546 423962646 802760820 270689725 225343995 234711389 944254645 665474826 688740921 513390967 895104642 680278119 198923776 873650325 606723936 929901462 174259102 413855261 6284779 613258202 244587510 451710876 661805180 234985358 760986450 139032009 419376053 858413256 545443942 683639770 79626469 24543112 448207113 548081803 327821783 418328417 468438709 833023653 937563348 360504984 770518657 837242934 678072848 427995016 263635537 714597430 374540650 866321869 217774152 874783676 130771487 719640233 166739976 313798445 778142786 638052650 921358237 461061326 281313222 152772510 222435238 853965240 988023284 734468928 238655062 135780964 826774112 267461014 555076012 381271552 997135897 996323006 174336555 872809507 914196354 707951729 845450499 363489869 373758575 586283500 426920384 346673856 603678526 942340449 245417014 480093755 672281236 873543945 596275130 752345795 530792398 4499947 651027830 559108239 836305275 205270244 842845759 572613399 671326732 615380859 316829321 207698509 340315941 196602081 185588854 565087977 657065809 846992111 920954893 864712902 333997543 201688112 439404617 794912364 644288409 975597706 174316492 986073643 44711037 849065408 885868817 906765336 613050833 37658436 16428641 942909447 713183649 241318061 723385076 628233472 463381623 944451080 265055978 885512639 758779545 833228747 847948647 932789400 960031150 865257865 669387222 564721636 516777835 44225606 84584327 975458385 891380628 960696582 374754464 69982243 722382590 75319658 728662404 89429566 389788404 930636379 996372626 944228902 349712640 67518312 947029467 734162928 879324833 344396266 723519435 569879929 902288953 680583164 938537169 661571156 358832790 612454999 247115873 810179242 870938783 304238405 484551374 716926809 214626812 497096804 368453356 277767874 671188132 260115381 387979366 578151806 591608037 531010434 370997587 591245355 911795398 430605620 896140111 631767858 751691940 298968426 906274121 305775 522011588 204958763 581179957 972318629 283461815 241538941 777246182 884953833 167736521 148907589 137640131 611526482 848000854 873693595 905182039 287688100 934576171 326649833 95049208 714085690 694419796 251684351 692138098 109194361 861904981 871456619 963036169 836681011 981064076 55485177 787229414 314800768 635388018 326763329 352159210 409989876 183816967 661082671 668157656 166045473 340948950 933671702 470243905 576022662 510564025 993488633 820041064 235425910 199747221 173444820 769426454 86044550 510314560 692731482 987248335 322149047 774349711 418171956 369959252 442662572 761634595 840017572 103025771 480467947 470545559 810543858 565140568 673034053 668602899 94070562 183273316 386754048 284293196 84404438 922609320 117505738 143205985 784179906 133089099 605795935 298064717 332194864 78482131 519046241 465219319 29526461 583724615 696885890 746717536 382130370 953899337 175049831 234138909 521458312 41527967 30627670 958907615 660145646 571261028 28797755 43913694 277772394 333485050 121550757 532265423 419900846 945762614 493705672 163322861 351837620 495478912 778221314 30754390 921416896 697570572 520994035 102325092 642203813 365253789 770032626 655260439 696818602 984123347 727696771 734258759 471033857 234279716 952429039 58705798 765805002 131080009 445857435 598522462 851652434 833199421 853198939 491201585 775175617 174897110 117531829 120759843 733817703 723995440 636436235 501699647 84088145 422439541 585043624 834180967 698870193 910940590 915720679 539750838 898608042 97210529 357305022 337921245 169922900 217553569 569726104 627692750 407743170 877137369 478771057 454635327 725957565 185695538 785190569 721267180 254245318 764128280 190896110 615860881 74420746 922146957 143486816 13992082 308722631 58674970 565666586 687876735 129686127 611488057 113406245 37955267 515117404 189618688 939619147 521492626 970525540 659717941 558106397 930198567 847052676 586191041 931904904 205107734 30456858 79575160 3550910 293719888 155080393 806314842 625764381 668386318 772587883 266606038 281108641 867999826 625930916 765307878 339196765 237188131 528423499 963475113 209929507 610193677 582274782 682097116 534237705 81776621 930118290 437226630 521970670 958606874 11630120 457025201 707415357 339233133 280469901 566568059 643396027 353386344 419268121 583506485 308376518 886533958 898656982 644095608 668365587 116061415 743700128 651765810 350868616 243294344 491611939 813766283 617731391 0
0 489479834 623236364 4450364 32383515 973119154 493554486 244842258 162715183 788987487 168457303 400063443 434342444 34981129 998140902 857473436 105172667 907770893 142056212 547595968 946006141 685257946 158401211 957240123 786341986 714713833 42629315 468033219 292847205 848239397 20885449 533543682 436679164 330959208 361477752 692710640 194337139 408233487 795516883 587742322 220269761 268150824 557836664 115683896 215079652 987234801 803209009 779550058 675779270 639284596 569117000 905911180 942954272 69402262 209452290 8541287 474199214 327015078 822200117 903111168 344332855 516128251 446368963 971949912 36828531 193800217 665812970 399064851 655264654 890541539 396632929 367054826 125563340 172087042 915405301 210601179 229254588 623896549 265417023 745816208 516099205 262657964 316795445 639053643 968604097 257419065 296890463 44253991 487386325 936327573 575173670 772345859 406134152 788824942 161991213 53667992 873426408 76479785 701689736 469126553 899758284 487092678 198002822 486763182 559390731 797451612 629279611 823463719 158030629 762620459 653474418 639369830 500370667 249405179 760368646 279648067 646502987 860234330 548233381 323997904 872264165 968465276 309021162 411488659 725764035 238690546 885499208 611183970 974729892 300947878 432404108 703639930 455985893 134753025 252572083 133348372 135951850 319484751 457685536 405539332 840841023 729246451 567687299 726472761 790292197 248767383 982067994 812614748 526988525 985836733 463125236 592033555 402441495 631005864 682882205 528072682 611118442 310022563 69664560 813592843 484833337 824969114 780572864 154291898 351450499 117817644 572713663 294543925 642350510 98362084 454917653 350545868 717886375 569318711 781331969 640538031 813960755 845268334 201917862 486131710 45564871 313463276 981475686 58273530 499036588 588239182 502203426 926265407 578877364 414338317 624410979 117710176 658052028 507450519 362439420 533499973 209874867 697275972 760519912 190908888 338734897 998024868 215236436 312968245 555211543 953707541 738859183 801243339 467625266 62242310 330119030 631350500 529150905 56631573 557598336 575025602 894009627 908188126 172749051 564763135 955490180 816196126 563449224 969355163 989758888 424278283 874160293 72498555 854494469 558313611 803116956 77844202 506496348 216254262 985439901 930609587 687317390 513625978 108417706 56969989 844006452 309190107 958513401 718869231 598368741 776147997 218818151 263670997 75688824 164150619 665095782 350567311 702722936 281779617 897197552 547460964 194523146 255501692 971688370 199670020 858338441 150176171 380267805 680770059 970885379 982009215 376384928 199811917 151139538 7920154 7267555 789680569 117312295 600314223 598182314 833247781 818545052 204748083 741080768 882511507 399077268 842235840 565696933 453186207 136863468 194282102 285668204 452632665 745725081 958742092 319509356 971371324 600530342 235910317 469373651 25460993 611923539 674045846 72870670 402952699 415927470 468767450 380371351 654325647 3491615 516416482 314891239 52156775 842238058 77048013 656106913 171699045 952530866 710407004 230978786 881395266 772307913 473178737 752045038 565489643 142192757 846316912 213732334 438988400 274373851 922563329 588307510 298129484 52035767 348843145 959888024 536650024 96905300 603116695 472961520 772002483 710813879 448711549 412136572 792998051 691152809 979747902 639404702 303235712 778631 138634889 393678773 639992516 963279165 978689978 540882478 528795486 260791707 737276047 591867144 421718034 751153015 306809924 768906083 117019489 89590611 331297889 147851165 392743291 103005472 347366393 693083938 384861863 310975072 586947668 839089680 423947609 412667421 675138549 528399745 642521298 878412461 599650149 335668584 743485756 881050184 953533719 322633755 460312345 343778232 134896600 364373206 494646133 559548149 620163096 442228838 906497438 296046463 566201351 776391201 114341247 94977033 796768410 764025463 743293983 414697713 682896059 456831045 530967800 264780419 477988346 440019259 501463947 896056767 370732836 991712591 862281691 96386807 128499069 58485892 522168837 102289955 979886583 630556043 293492775 952938911 120225340 564374380 329937013 753696153 477948734 477417081 628158112 226858992 811296400 64587995 195061603 28952766 698393266 188405851 414972137 38955902 946473135 559095449 530517031 360266246 10240112 459346437 930548098 854362462 571112218 569922800 177776188 36261569 290685004 866817396 453115003 83230023 689615299 327295315 345663563 48114753 728798168 109600705 847002930 431061705 462584179 425327209 556762384 631642351 302251478 697541443 673576452 124709576 934383041 512054291 32971105 807083670 936821561 866918684 169428462 124408824 69971999 442557369 755992577 599334634 236613684 747906586 716661716 831573786 540290827 388246806 863066403 331747814 542793590 596100264 681345037 749943773 938895473 403661989 954180356 185570544 741139055 678691446 18457366 754173736 839567714 108807572 615846197 992679503 805899930 100033788 359992180 619659251 386172199 67232470 308945071 730442483 152330333 820941480 556216430 356882856 288269667 263054547 900935976 80199130 923849471 689171 761070491 603547496 598705788 801424077 514618946 623189601 14558400 816574994 785942653 290232067 405799771 812966661 583824561 525801187 681192300 562332359 850119814 682901650 597670715 283264162 295074401 27703368 625103203 884125646 861988530 61500032 752811104 966249105 741036955 728987632 526799688 703938281 73088198 486294101 249857307 561073783 360962818 29593094 225346562 747741293 295452348 668871519 40534134 143400654 146220675 772372686 510762649 624484358 107279549 952232405 168939546 653841595 805202729 983573241 350219249 946014703 191206579 767081580 312025963 92398511 328626781 404521391 263223976 858989447 752427589 500545063 942487164 71115909 930478137 575910463 263118192 223697797 254943333 828714640 794910629 375417859 360517316 313201829 696085347 80756659 979465376 57462856 442120361 766406439 219581787 572676495 736915541 583024071 335912924 902567383 76882851 400451561 38879830 368410034 552055904 428024872 850294646 302597201 187341224 383629 713945590 619088590 400743494 511248490 843852863 798430504 972185428 840413559 104770010 924757236 38600905 311815345 822251382 408418664 923924583 858899284 322169522 178862376 948566469 719637530 218989133 948944925 681925226 302647791 308547883 732346124 667555405 914538690 713327264 210229887 827900839 405465886 933900694 433893613 994782812 383641821 82199929 426029844 969615205 493743978 614508211 28806963 944504998 387714494 940528536 593657524 68653599 758887211 394408859 341504567 972260619 988699154 861971397 202681833 936232097 626252693 624224860 526875399 406165723 185113999 277976383 203917370 12274240 523864001 594923665 905350977 911923590 400776222 931913297 133935893 794898587 84560947 81171557 355910027 271592035 356404839 413971958 90146173 529563798 974041498 73907839 338539687 769510602 376616136 943695709 200223620 608419990 39026777 51757781 254244521 788438073 794989169 77110450 332097643 309462623 312777617 377113241 366529803 267938932 751435341 133222783 126466379 960266086 604872345 374493011 821278810 16244727 746178053 785937608 408676846 656945492 835122822 576205262 388355060 660798498 699473070 614649610 589874928 215853102 380718536 718726082 406258546 277051039 541809715 967165701 843268349 643060429 243944201 811665278 452927475 406734944 153864170 60887387 191890797 961367087 491211190 442222258 77778403 892343433 380801420 148991580 186703891 84958194 76638101 921998730 313751332 169888167 769623655 654995803 548842376 42772728 744318478 688889247 690553151 296354722 355427179 925095229 751715127 195702333 941379455 779752972 736781931 72398124 631575631 811011842 96858215 546169684 659388119 895377088 488696023 688805262 530985243 151780625 505960018 885851352 581861176 282120263 521653800 305571828 821824148 104284288 644801259 371606060 421014276 8321119 956426627 670729537 581444807 28863636 318177308 523001902 747748245 140589994 357658480 530236412 129440054 452190217 227174393 562218497 605027255 264388255 433475194 630757037 367647587 938724812 745839267 465017009 440458332 162776443 175145395 155660292 743054878 933479852 255582119 694893951 341494882 64225167 30275863 319735798 269577186 168505026 487571325 866462085 912669629 800288265 527311886 90365240 308145722 398733812 468691121 892515135 684093677 299428567 57803030 229450963 182642231 950234919 891651637 981360430 642433914 630912171 372541615 639978765 301415140 366073442 629370228 954278648 235345895 949818183 162832303 838653383 901411957 847305068 750129857 403755866 477176051 230350301 895889845 964279087 651013847 880270110 173240193 734507028 638875942 712155225 689758602 700388000 697175444 425075549 128158327 229672357 524245693 275399008 724293798 93830641 849728510 726381587 566809726 870632888 920116785 326363449 888598162 976937867 443122858 623915089 540545367 819023044 845641230 528298647 676851374 68853724 578672732 966886473 959740295 845650104 181220756 71076445 280240487 446489587 988612882 153619679 523491839 949308662 483983802 788824992 686408658 508869920 203736967 829021733 933046277 392282779 452052770 479182497 894859800 418309849 377682166 641738503 289017176 754256973 386271885 514133825 343404236 766431022 214280323 124771439 438431620 13543209 870614505 113191181 91711311 453183881 47332334 106814860 641676432 584424162 155345018 903454635 984872488 413844740 91992649 24166882 222133093 737593536 46286938 550920596 317294783 505746355 129917054 415162062 15326569 179662653 641624504 641883715 650698111 575653360 909351130 378930332 379215583 493982741 135771294 543429507 324053385 30735627 374690968 791652919 291508628 390624345 88472780 204970665 492265897 355961325 968332011 884439043 558901492 868624314 618928931 0