1000 838
308482012 596819521 953612119 876715766 219932525 123376382 620306661 680046724 585894313 575045410 554945397 837791214 377687745 480361666 33705479 287480149 461235312 508182443 467794284 477176260 141683779 686123594 672231438 944157742 397031086 366611506 807600904 570804744 862053581 355204765 291624711 557779957 207339630 912601795 745986542 329530810 928616938 932381906 396813751 768672147 186137735 726682821 279061468 805755583 327303621 543930219 184651464 205706052 439550336 989690065 168758762 283271577 725660971 283221692 153494342 527610383 743145637 411210472 359196487 86838616 200946627 458510547 368209601 339623846 861214991 914676627 419591390 894149767 40618959 605632767 586709206 712715194 846454470 588085872 776195365 231020522 354107401 756476452 164727116 271631573 952495436 365629285 615019591 842905188 300519818 365047996 386347070 48148794 46470956 23781752 94013275 731237557 18735473 45261593 202945556 995713052 93425673 992798566 212329231 419592940 659586177 247580024 613424662 807596179 405129803 730269540 938717966 940042572 914101563 217242688 524528607 947733783 774110046 598582269 99075254 552783916 466377178 624289290 662923562 270976088 896994315 370974914 43932691 884366594 151263194 658321299 875224917 864214919 991984325 286972985 386674459 73370497 833248618 135156509 936880392 258318129 811127564 494251950 505742380 191754404 887455602 678584371 449783200 778166687 641670104 713075215 48985709 727834351 689542049 570185244 520931245 744472721 469370622 884778420 995664204 639040438 910257648 943391844 466427573 559947368 902154185 667475661 637234200 475914444 920387271 551002326 311566412 754524598 684927515 998339624 462883934 47602020 146405165 546828775 791555142 409379969 289505716 929451180 21327541 154916201 535173149 823714887 197514715 130418821 992032170 772857463 892779560 892748193 698017576 746510518 606674299 949445388 249920158 600314429 223815262 280963666 327106721 867424378 176860916 749724473 770507647 838434710 80176036 529068739 650958366 842288422 892963196 115174954 797595263 919636137 485279163 225921457 767325790 785528713 932900445 982489 206122869 929733390 440365498 951609349 508517257 936131781 685714643 548736213 920441698 177133884 380032749 75234614 163909331 622253789 649365336 533399829 585269796 472274757 483443999 102322300 537090757 874587105 541982219 727828769 786691824 874429900 304472389 390177196 639096843 616340564 522540984 479422160 157522460 983198667 458742056 389982074 761084630 815603337 340131097 589781281 257823026 314640592 157242850 411795575 683465046 352333065 990253583 764966900 515216258 666510121 350897982 116228465 596512539 773886974 178238498 461348068 648045569 326519804 399186252 373890858 229161072 130083947 654061942 312315746 340580337 173241355 75695987 457606452 913651311 527912750 346487707 990019624 567183640 768897163 992861444 528893895 81474845 374328249 613151079 159006913 10754477 379297686 735854800 544579918 247601392 177809698 877337229 899914053 244632072 639117152 267210502 405033183 78782818 794256137 87534704 134549075 278168647 837784653 741319143 18923091 736917626 395084276 445120054 558793965 912675780 167926146 595162041 669814795 458545067 961108778 953006499 80917718 104186529 9235889 97295323 708261822 135417783 793356081 497211832 416276955 400499258 345934208 647336712 351635076 697905402 838538450 784069002 57801936 69863125 796189616 307620087 141696545 624388943 820800206 283719198 541464656 542305689 835923069 358869999 146007399 344395218 144686402 913909867 215097551 176076675 517525726 189500291 443030632 16263247 261600659 112502670 280016964 157955844 766088909 778777644 77872812 228940065 898189936 885725875 394367005 683059609 753002517 99681029 154610805 726772956 788840166 457339393 254354636 795322790 2466664 573561245 777133729 414098781 590298652 11978794 671456375 36058689 598626159 794307264 232318492 49397013 329104565 326800140 7413923 149953942 912081986 444078398 438865820 778661116 168080469 9838832 423566 611121319 785187607 98305983 343741741 746572927 284430617 824480612 531497191 242906274 492560423 243474656 618882635 575236140 4212481 376780228 364865368 843911954 974582125 159430076 207205006 57405897 328153042 666561717 114065340 197300780 500400386 136153665 400672235 693393678 404383399 863326588 421528461 773295926 702094650 148844587 451913151 575293949 260580817 297127998 493116665 90655317 945688974 271908468 471167247 440069204 139011702 205008062 823451494 788704508 917478871 776941397 340490173 244984602 22069589 756684408 805705966 340293905 325101181 641066231 547739905 556385683 784637731 551295039 476798323 194047335 292398368 162286736 856626748 483741802 923081250 890288629 716941855 48039805 12097037 564103215 43142193 37772585 577723567 148549489 775802241 173484778 141435396 501563912 902519509 958847457 917018004 577310400 792197267 948017701 648503371 202885655 367326583 232807036 92645318 432225111 938958704 367385376 284330188 942034693 182903211 794288616 948028517 981733701 596971729 435918665 954902441 28000441 829549671 54286043 290981001 251428288 665931982 352887022 607767438 69948916 397475306 562274726 542063560 748020822 527900071 554911470 64822895 268892343 179562253 765538828 545567407 797506238 43503105 361565192 810137182 689587105 392352159 763355013 75613483 229885039 841363046 134005109 68594155 841838951 168529942 502784093 766663765 782122658 933658914 385286322 34591055 918787251 60497786 634812638 482627425 968220592 419883455 214656258 963407473 533890014 447429349 166784317 710307494 133333361 350398401 691513422 184265570 220718233 689566070 795640359 455264368 530089600 569243324 837756013 804655262 306394958 353438818 560970275 492519242 582933067 506853744 236748659 68285886 727412289 687512670 693934361 443877772 823456276 599163786 551846647 886955741 473255616 262232270 315151670 673687306 429915093 557579963 591374015 541071009 281607690 936484552 507700043 359088758 730077168 68329945 438018680 342278895 224237090 6135477 440147045 822620390 853265661 988934370 566993417 812790562 706456668 793812645 197916980 645225073 143780896 575513697 210652688 567789557 708683520 405323340 876533113 173301874 986172917 652850845 877470096 25177667 863542415 231757726 766388607 4238629 988544979 499174502 60581922 356436710 701699398 427118928 745096452 573342041 480395637 76050025 963662513 262790736 682803620 230016158 487688897 886328437 534200069 741239431 879231482 185893676 503472055 838349495 602478060 492727205 866867766 812457895 588541847 731584629 922338504 361661741 274965372 601758234 390938525 599528370 124613787 920067969 294768333 96167083 589715633 839542419 746960823 393626581 174151990 140596233 69848749 286134339 497405998 174276307 456619800 89220551 466078094 261556355 377758669 444746773 49988223 713023198 677257119 952870415 145288083 188125328 327899051 90596040 842611365 395863958 931734904 736336025 117062472 825428552 243050366 201861082 888092764 332367550 290394586 89037590 71669711 368509936 883393032 324973188 393074047 555297153 64203593 701826748 168311289 448285829 771698618 1319021 516312403 737967855 690984280 201493116 629646546 651191594 621830099 890733952 214821797 409117741 556103597 30863865 298850988 932290300 84011053 292631910 542534545 728528443 213937903 342406700 987229250 841614963 930802606 652062199 151774752 293016707 330532989 136542506 46146790 163363438 472069590 777695984 82860053 101299854 963121738 145780906 605378235 591293083 323318060 126505548 374561318 53407914 750159715 194029192 661438114 291616670 318880736 401386493 887595048 694494073 839048091 758008531 77781958 627165556 46739501 520826599 820832033 64544391 365794838 455551722 13486699 106184036 95567446 831663733 836459878 292559879 814435117 403675479 735623413 58315782 367316448 422170828 254143016 644867141 873777666 496906039 166269037 823265727 426252808 397536076 876488145 949288365 467506747 827952051 357009849 787129821 510992558 153421959 818697469 240456523 478842093 349665683 574648886 180530157 392361180 74733127 536361130 25845306 806647215 412537788 547829785 37836370 496253056 174914400 471025507 921226462 776467467 498545222 228173011 103346117 424629971 886522235 307607763 185677893 117929826 495015154 620277231 842868462 662121750 988007671 97179867 126490779 925281910 698378271 591321613 77066175 280810803 580680602 20539401 771095024 540953271 337518770 332663623 606820586 979267726 323543711 966488672 310634483 480426340 332453611 685127595 648596620 579897859 617922459 102110624 912807394 274316920 819395806 175045924 580819051 322548930 616076981 269097533 552549585 239067219 677669144 754605808 424479061 849470967 964999971 457120899 12351829 776436902 153220238 104561551 186760030 806871727 147559384 619524367 591308806 709993684 18596220 177887881 101977045 906909034 128501062 404160255 806076731 137118527 842595301 764902440 660904534 787763490 392377227 500167659 741967670 273776510 850391447 87330636 372034418 336880903 674165560 595282217 693648134 747713341 379830080 888596011 35591577 569965964 482581065 106222281 382701054 683054929 910593727 27818722 73445234 763542301 985169320 472447455 689946134 687268440 912854690 836928844 213703072 297312236 659927122 553723431 191540563 272672296 759249672 712816587 28975922 416384245 420137394 305882458 301380993 909263772 773532872 128783057 917715343 138600890 23035500 482453424 839534441 758613976 154117690 78451587 659496732 869532223 655851709 42667102 674864034 95840051 692858009 475051919 921766307 453113078 311977293 286746243 437106701 937679173 611672154 581367458 497988310 34666710 435231028 741562579 894580420 186524220 803229348 749233600 509243768 556135855 316220750 7450080 735324877 832399042 847625794 510511272 307966714 789193261 924725355 445438073 423466904 849143888 321140454