1000
939014526 179534087 1200343 32546791 11511331 796365857 835715537 55912408 398002513 125607304 91120014 683423802 769356093 376593135 74546425 260324785 319973345 836479820 536048670 2010977 720924330 354094439 832974085 145162891 93511459 102066503 440569712 311790464 449734644 172238428 301366790 733708045 1486669 561869252 489839240 124324970 25965750 851868110 477263705 212026919 947609459 821497525 726375850 255947668 152469370 179726252 591355756 859210737 869028357 94060908 57918122 536048670 193023145 693398293 413812154 715542009 171596948 910385409 202740402 628009382 612856242 299906943 851868110 882537281 957507013 126560511 375349124 398002513 376593135 2010977 423119403 939014526 944022482 354094439 63729050 427132207 769356093 636896487 116697288 492196310 868621279 124324970 141930233 624441485 204045617 447560623 333669398 344336186 903441014 779661914 840778489 600024912 587101870 477263705 672047729 715542009 636896487 571898104 89357511 332611976 957482366 333669398 932064235 412823297 471924995 713176666 622410995 980002701 56705242 835715537 351352727 32030255 125607304 1486669 797345731 514233055 27085761 129661304 311790464 359490352 133784259 896168449 552635993 752830304 826878036 532834564 884102797 415571295 34021362 789861995 160201286 752830304 46688332 134911999 154422837 718444024 766458317 195863418 877665262 346522644 958482503 238552491 837035926 224156703 174542008 918785135 806960540 63729050 57918122 864308011 990803801 399074312 219377233 628990215 224156703 860299787 411656975 346065060 399074312 114362192 102066503 644834170 789861995 754933060 408316512 992312683 501638437 933300771 572728732 137160845 19860993 84977897 332279982 36163501 453789263 137315537 785014600 190747803 624441485 935988681 231235452 149370400 765537804 140513271 858459439 381050076 130107636 152469370 516569801 933969573 306082392 161449518 600024912 251011566 928624784 73600040 826878036 55141939 424370431 622730106 297509433 645997513 234821996 836674705 78041383 95967922 476008356 39552314 850239844 502688497 616315486 991574964 19905169 466377460 311642690 881556340 355680221 614754593 839726862 55926938 684540662 423119403 424503287 143547856 905359526 2179919 231488197 650882280 427132207 838618984 533607577 877665262 804351351 107948796 910385409 115179093 588792662 305219847 73101092 82289822 1029083 37253245 760167289 558458322 222727948 234821996 613456731 720924330 134473504 690402074 145162891 806960540 440569712 332611976 216374980 20274014 64818011 79404155 466377460 428041883 826545337 431832866 765537804 114975161 458859543 175863405 368011825 802635645 600576198 471227367 938293702 146446525 795358901 250509572 762087896 8211034 124761311 795758559 82289822 955674610 105544372 209742945 139304268 222727948 250095702 160201286 792230160 12283680 454169564 519404368 41729213 593842442 317874758 528708784 91788611 458859543 546702618 145581476 766458317 154423176 314994134 613837008 389971787 10373899 855547965 869028357 843317907 669329005 389971787 411656975 242579727 958932062 745752988 11722918 400593891 441030014 976983039 881149393 146446525 599077378 650882280 561869252 339100677 143113492 203321965 139304268 541928378 398570561 631399458 518168509 882537281 836479820 400593891 431832866 649544425 232141648 745752988 154423176 918785135 33372958 588029553 291060654 698834533 209742945 8241841 251011566 786828883 327645868 843389040 603870951 990803801 529617940 507418876 514233055 528708784 217465323 322647017 993029041 868621279 84977897 161126703 133590081 157370175 988254710 928624784 342121184 133784259 850239844 603870951 125777644 507418876 295938995 880627778 792230160 616315486 825320618 39552314 772575615 957507013 179534087 37662832 745031708 856843636 242579727 413812154 198798186 588792662 110923749 770340962 788886715 291060654 663964294 935988681 697531852 970068657 312610069 976983039 207832336 685715167 552303254 913972488 114362192 245447529 849765629 448097870 838276428 988254710 55926938 594439918 754933060 364800836 140513271 269627467 631399458 795758559 202740402 296698117 727002497 683423802 744913210 622410995 511407690 587101870 208177611 823789247 956134518 959282376 433802409 364800836 344336186 664615501 24282166 713176666 959282376 440478981 760167289 721381785 606493137 229211260 30451392 129661304 120210604 93511459 781678497 33048530 161126703 492019005 368011825 506430954 346903091 314994134 663178414 403978702 157370175 471924995 529617940 616958805 233469064 672047729 691420109 691642718 61871996 112753108 684540662 449617955 35879588 840778489 496980371 533356694 124761311 989151429 511407690 678592419 127323738 269523202 74546425 133590081 86604780 996940874 578945081 109091649 301366790 30451392 397219971 229211260 788886715 814715923 892114866 433136220 97862708 165886305 19173151 839726862 130107636 881556340 351352727 482304506 18119387 971157722 320054464 718444024 947609459 78723703 669657606 216374980 905359526 195863418 198798186 858459439 617781758 998976319 913972488 140131251 836674705 8241841 614754593 263090697 849765629 461644109 70596433 802635645 403978702 443302054 557197542 174542008 77051134 547619249 302537807 56705242 779661914 134911999 33372958 599077378 319973345 147471585 275986529 826545337 154422837 832974085 168968195 354449234 275986529 932064235 613456731 94060908 826158326 70625234 14760183 993029041 71463776 8211034 518168509 772575615 476008356 884102797 138182089 628990215 217465323 397219971 594439918 204045617 148912005 745031708 125529741 252472228 364878888 217068761 678592419 97862708 958932062 855865755 190747803 78723703 461012137 591355756 541928378 629777196 346903091 54814219 461012137 245447529 346625394 111121260 107948796 538075719 903441014 976817406 644834170 855865755 533878539 152792473 464608302 296698117 47399646 883887661 669329005 492196310 440478981 711151594 582118169 834021459 513169148 36163501 607475267 54814219 46688332 804351351 203387650 252472228 649544425 168968195 12273311 424370431 322647017 992312683 781678497 24282166 324907496 550921873 513169148 753553432 769604590 145581476 420098314 275482408 995761998 329409441 693398293 140026480 238552491 489454059 359747311 382759023 113125823 196227629 91788611 933300771 685797300 612856242 958482503 874122769 996940874 623086921 542512820 519404368 11722918 433136220 19173151 709050347 327041790 345859324 412167185 546702618 575227489 71069144 521685151 368907968 116697288 860299787 834021459 852251071 178799278 72713300 855547965 538075719 516569801 209821795 253585835 944022482 593842442 70596433 725131269 381050076 299906943 506430954 614165714 91120014 819363724 217068761 70203199 697531852 973645434 137160845 970351024 25965750 161449518 71069144 737509236 534734728 179726252 219377233 43210736 691642718 666409434 796365857 89357511 297509433 874122769 149370400 856843636 314064731 152792473 443302054 744913210 398570561 534734728 973645434 70203199 970351024 312610069 884893838 971157722 617781758 821497525 843317907 19860993 859210737 89834783 601885968 269627467 346065060 622730106 178799278 521685151 375349124 382759023 533607577 571898104 203321965 250509572 773348910 843389040 764914070 386166935 883887661 212026919 269523202 991574964 970068657 976817406 111121260 901020120 71463776 1200343 838276428 433802409 14760183 61871996 623086921 322009569 776056547 582118169 551232931 432552136 33048530 208177611 86604780 606628805 41729213 322009569 355680221 492019005 354449234 193023145 27085761 533878539 324907496 35879588 112753108 345859324 305219847 143113492 77051134 663964294 64818011 664615501 95967922 823789247 114975161 886537705 415571295 143547856 607475267 105544372 952654819 408316512 616958805 185180963 342121184 275482408 813384005 461644109 669657606 432552136 995761998 231488197 957482366 980002701 663178414 449734644 428041883 770340962 306082392 147471585 725131269 448097870 19905169 125777644 375347871 648841337 359747311 600576198 884893838 346522644 955674610 709050347 578945081 138182089 253585835 12283680 2179919 317874758 72713300 628009382 295938995 449617955 514476152 314064731 329409441 110923749 332279982 55141939 428432203 464608302 12273311 320054464 471227367 613837008 454169564 685715167 263090697 141930233 698834533 37253245 728130265 412167185 727002497 73753536 260324785 424503287 989151429 196227629 557197542 685797300 7238904 283999552 749022878 514476152 175863405 998976319 502688497 1029083 35614470 283999552 838618984 185180963 864308011 364878888 79404155 606628805 550921873 819363724 126560511 144748897 501638437 250095702 629777196 327041790 10373899 34021362 32030255 311642690 231235452 70625234 614165714 933969573 721381785 144748897 813384005 956134518 18119387 648841337 552635993 575227489 773348910 489839240 691420109 764914070 776056547 339100677 901020120 690402074 43210736 551232931 786828883 165886305 47399646 441030014 148912005 785014600 109091649 137315537 37662832 753553432 938293702 797345731 607425181 542512820 666409434 7238904 825320618 73753536 607425181 952654819 601885968 203387650 249888858 762087896 127323738 20274014 795358901 140131251 547619249 327645868 558458322 482304506 737509236 816867896 881149393 886537705 32546791 78041383 89834783 113125823 420098314 55912408 896168449 386166935 447560623 40987790 207832336 892114866 134473504 868908206 249888858 73600040 728130265 880627778 852251071 73101092 868908206 453789263 346625394 11511331 140026480 814715923 769604590 209821795 711151594 532834564 552303254 588029553 359490352 255947668 645997513 496980371 302537807 533356694 733708045 412823297 232141648 35614470 171596948 120210604 749022878 837035926 816867896 826158326 368907968 375347871 572728732 40987790 233469064 172238428 606493137 115179093 489454059 125529741 428432203 726375850