1000
587517153 182757601 998433851 357182401 546439111 218384641 553112081 156804201 363528613 154834023 130917377 243131761 787569257 810449541 807640951 550007381 970223511 939307201 934551278 87473025 841517119 545934316 515557480 349385559 951600497 540033544 480038051 524438751 755834001 859635301 568232801 81524965 220231026 478098205 908190746 696617501 891240065 745124901 201899377 69834383 46411473 483358381 872769907 469034961 275354926 196274921 441996258 175354465 819936899 24154881 974591373 185896513 373176081 297286897 375118001 88333921 423299849 38687231 385911151 187433376 413765577 344652801 724487241 844373573 725756731 836412751 105283841 760893475 431042521 506065621 186141561 22120801 44585369 185070401 915157761 922923705 42408968 488899037 389000113 688596241 141493453 133011941 695743296 768588683 680639521 3258481 334931761 62376938 819323201 47487545 644800201 669898641 354170287 401427005 859334891 547987451 673520501 969886600 636680321 60456721 812576681 177440555 797324665 539846465 655084261 461768013 205929857 359789501 647692546 461802581 22088969 137563395 181520717 463892626 353675573 554194259 987264449 109555201 408283249 588167113 566531143 678187481 730544129 780951361 783942993 330400227 275356001 530638863 132984881 527070501 605864555 152344321 426105649 764669531 798487161 878249729 294616005 988167331 191202927 668376393 502715811 448974081 102809421 591965409 22975881 880858409 225226301 16384321 299580621 586045851 241515626 252875425 36370801 379651192 335514089 414419971 312228101 787799381 389940985 764477697 509325356 998354326 834010129 645508576 281336001 938230907 454364257 714019937 718716241 895988101 174720725 536562881 381209 521095033 13554557 10899642 914318112 471389505 801482281 831924161 555677505 288158145 27219710 565738657 594873645 145696217 67620691 366577029 180209873 986949001 495197451 7586141 368000633 813128551 771820670 904422839 656774049 675066529 898500289 256627201 731631405 407737665 157946807 705073176 678625921 33975608 741787017 349000501 458937193 920755310 774289921 98630605 622118207 574410314 196193217 316225281 363896401 603215746 992410073 595301661 940004161 138650681 237477809 323498715 524673441 864848561 418830041 80316929 396339201 246203747 744784701 908822601 320149251 18796935 18159473 273286501 114341151 226131501 481488481 346321601 137685521 920619161 622746405 114407441 564712437 971415625 575576153 858368835 566402505 187231801 236216481 855533897 577725721 278053921 555992197 72581116 899082461 674548001 272068097 190640967 406017025 302783385 566479388 958345321 545007723 414476851 173449565 561380499 664865713 734585921 952323513 607825469 194005907 2442081 188430155 530387271 777299941 114706169 94976123 895755729 477860651 258937971 552549409 363645001 714323201 361895681 625051981 332193985 685748685 702355776 922574785 601977857 26219622 325524233 613672037 548928889 261084177 560303825 980351086 750081469 580381489 435177969 488714001 788372301 228611216 325826081 349059869 7992306 215673697 709786833 594689313 14677633 784396248 699959297 616942961 183544531 812751126 185158769 668096926 862138863 651696321 470280289 280686749 380755434 858657281 189873873 572333642 74729001 888391811 139039441 453406701 237290321 526179262 392733751 648639327 310892378 292496322 449953923 275482521 482308589 24740471 197123435 300398435 44396957 793131871 722761521 350672379 664755464 985112485 559420537 638374201 746519051 743120801 318765481 883691393 913493777 501196801 56095435 756808300 849621841 443404833 368902911 781438534 518278021 431245133 805168889 371200517 542126523 686505635 934149121 311928203 157429617 363642137 75975997 792419841 255343857 57819801 367944947 197819341 353276701 406245381 703500701 442278697 474074051 148299201 710484017 71016345 755563729 457706849 589865149 597556231 766308673 501462433 247685148 177300273 993399377 913009431 995617196 166392337 2917501 501722449 258886465 917147281 398707881 107672136 28824961 121807044 343044764 134861205 91506265 540532069 192456469 199141297 511929921 265545745 190445345 437869801 16397267 772325521 198502961 564963731 143956889 757766915 706405013 536048385 112439041 69936476 972126793 747892041 320499281 1 847753001 775953106 271430839 213084593 552630323 756075629 875682403 242596861 362423299 934930641 877409092 511607377 418587667 812092501 523112981 866790481 78430113 459842312 583685741 532544653 639169441 6912561 701841817 956659089 550737751 68507773 664791315 740052737 885399321 822906901 184081641 869748385 939681217 771644837 528147461 290223126 489639939 547686081 959093289 559378951 219603681 503360550 580908101 48531961 968772701 868430401 717540776 294687501 706119341 925617649 778275277 122783601 124037793 182746657 163011661 947634588 937733901 580616049 80934972 910402337 654082236 988266876 390944565 765507361 1946476 112158440 318035201 2336009 470823137 731673803 873766499 523249501 105926093 683236513 164104346 327296001 481636681 892544513 845219973 533138175 840070896 558439981 682487969 465031745 726412451 931390977 755320321 442330957 509660249 336113129 460495255 620081665 741898549 851166070 190386257 708287971 452084441 68235265 341176632 867921473 305316401 31526761 926545921 541080851 143494745 999825044 50182505 880835001 110266413 999675911 159381121 125455931 222703949 23278769 902735005 16267937 888920184 640213811 575042913 152981051 587012917 294855315 785862906 887571429 850512365 675032919 513709951 735395921 960478441 54314796 390299185 72604041 1915463 479464969 546556801 100892495 356221155 617643919 67614905 608782776 156897897 522581451 233968939 789517340 859070901 108209151 980831651 986350289 212613049 362156803 800328731 620945441 643986991 675167811 671185345 818422621 242446849 894012681 786701505 398152705 603836253 529918951 759055589 762290667 792687169 874271601 50139135 113020121 587686593 127279481 684455010 878641097 979128545 567606831 971810793 408153281 83092161 782213321 577939569 900400251 202658055 832608756 481512415 265180005 763532665 11790957 881335701 582239481 741798081 105518475 444354129 463784901 786660933 309173852 297193401 569578501 937299436 61956481 924706197 827787426 159678861 529940103 217425993 508422326 201378867 323584455 972530805 253414449 256936001 574837501 724375335 348945183 739765898 991440839 59550851 806759783 500001681 154987101 153026001 915863311 193098145 266637025 535580387 673271001 173542801 745833501 131148993 593707181 741804961 665739161 539990001 382341745 482426003 282213731 416120178 183283801 932906369 962575847 119366049 545310209 892529769 284895705 703011261 266662505 946273068 780952833 426187051 157492852 834278131 228341327 720916356 365707521 690898259 347797111 715500001 471352851 3260631 723688121 259988225 647360641 596545823 928353421 216788001 953171781 906190023 388424414 67247809 836187801 374077501 833038823 273647456 433895949 483083477 774095326 588073431 334512161 730289853 609177201 190744321 336249483 933666801 815770801 7589656 500623 259415461 554538121 229504865 920758141 742678201 65104331 177475761 398777706 107720751 649071041 294425345 766060745 730905461 360636901 482240453 759453621 622446977 322046177 568814347 397599316 666242206 123663909 414860001 358633811 32670801 209830431 437769520 74149501 469582961 903581631 914721791 946413195 55193269 237593729 96450301 877834129 512079953 103239781 567980526 218090153 861565897 55002802 637184577 391196173 82622221 873392476 92638485 21227561 974046997 118007041 445319917 471236401 233389393 722860797 699900001 771994752 560292289 299449561 733124593 996291861 391323961 294638065 886131021 476603521 168838973 733775083 279362621 957075521 829053791 159677401 129897421 58298915 878663401 990470004 853630146 679895831 882736638 991560947 721046157 834031758 849377893 272691461 934554201 293561621 122463953 495320961 382500257 542115929 444363133 742315060 825545123 876014921 232406957 565741941 455107585 314201001 117979891 756614177 673334301 647074717 331148801 716640385 203366401 586664961 334184801 529706785 87003041 689736538 500949360 145507802 852358769 264879228 78881849 568934401 568288031 281434501 279426241 701198849 420602561 4056281 8713031 421592881 308248701 758212906 627622441 38025985 243117761 918253430 583196372 935647393 822923281 623849839 657274561 446044737 188436029 831886483 344662175 413143399 772673711 886299776 30241361 891416409 500135121 671344201 978037166 518288605 158522721 694272849 386979382 448294401 640338209 102519387 257204401 481878037 877548078 583542251 459136989 343949761 410216452 129095937 894217345 114195569 96343829 714542935 950702426 333770045 34016561 698906401 380316011 434549409 981494931 381083174 486374866 365537001 906328749 529254361 488153018 17533425 32596689 28038509 364811589 319592328 579925761 196521925 194199136 549658501 659636417 60574657 343805313 537538341 66079489 426841307 891091692 234165405 549851801 926452001 695466401 266221451 765168721 560145257 422374913 620078126 261613462 448367189 124968849 506201544 497132220 700379431 950904727 360577397 751524991 988344801 200877201 876167521 56330537 391119601 468013131 231488651 924907601 121687543 746237838 740834791 17250281 749800449 447988467 104128241 151097102 936161801 774826445 477716151 35541251 533410321 35488501 343399275 635335995 277038811 112524259 222676461 60629755 837504087 912806489 761567001 363365441 997170177 579963341 970426741 851067785 773804451 287312417 503434012 693150801 201162577 444683417 839376313 469321363 140765561 591080473 418843916 689533313 929352243 485008009 558927181 827777326 777668945 834674081 18019649 762402881 174924738 563011561 409733857 928841913 679262281 399559841 799466257 144939073 804686315 626055021 959832003 606554801 736485321 859663041 850392417 557675513 80913249 920211071