1000
280138791 86060640 12424340 605105970 326944307 916888861 205590300 545022716 231304759 161685420 175731307 615593499 8176159 307015873 88410284 291301866 645364043 411746646 512786183 115581708 128311015 618196146 430585693 157084053 43941429 469045984 136998670 209703901 131585533 170821211 96821031 185674713 32959288 35393979 183976837 245752611 54201213 816080929 71448525 90392113 202904582 191681654 303833152 706286395 78522306 97874295 109068587 88015847 238726580 409245457 31972082 122176646 3507298 603097432 444599747 105204571 148691351 27606481 628819611 19549008 162736139 32416788 213071067 593293566 119679620 291211055 178477513 10106316 391019953 606685888 37871429 4351262 8655875 42448630 45761817 126834172 70710390 712685599 31058589 207849986 400012787 239768374 99891098 72550946 16377759 55154517 296906105 121895037 356691213 26127928 66615511 141639656 352045718 229722044 48583845 327392212 15897575 279362500 323986866 6331512 336507626 428431460 9183397 559261229 143397511 128587847 183582121 182945891 55085434 53504464 49836924 21913878 316039336 316161054 6411522 468879928 13933914 60589871 344798045 42785642 393838461 326245655 234639090 23622875 205241873 273520622 694882387 31945863 452277534 138025503 64469354 86666044 162436936 54821749 41032677 623453483 371638139 352456994 124918734 239047999 797768346 1003121683 268657218 118996259 661789923 961738320 7291447 110389244 679226979 207854487 32873373 4243551 603381425 1873433 35922610 179927832 144222482 611028 425379631 287918067 113087437 402272860 127330362 122332186 827683518 242219048 573273849 311577047 394982252 276432967 16831623 120058077 183635278 26143387 111477372 265207019 187787265 301045794 18560955 279500261 129305530 248421986 289566659 196275384 68845966 12836011 484281169 109385054 170601266 772154021 83597589 436251482 195931356 9194442 57662998 80841451 51858958 165475888 44188412 2552566 38354672 85945095 19820649 36614054 583233092 270019756 26822755 56341684 448943851 151131127 291688896 3950567 294657449 39579847 69792692 372924534 125963085 17727765 551757276 504979318 762463402 764095752 107053295 803787056 247854823 705521085 676915525 630825880 617168520 466556866 64825228 169328793 186467935 638435824 39923793 47178201 666261326 547322984 688911043 554835462 658959901 148209189 146896171 41255045 400800426 261056083 111243460 61072536 82576917 374046619 240929265 350815313 7948430 138482177 84999109 212178102 501895755 437535059 379656259 4994134 17301199 4542345 104988427 32754556 8024244 547287802 12467219 715299564 221038207 324316062 129926603 108921798 493340781 335409663 273821575 336474877 29706120 22499942 448612654 225742193 5269342 547979 378606360 461483966 189258795 341578038 11696651 294179238 106634013 26428109 589476152 245961876 98630780 8996550 133630134 471856124 119095563 99857108 123949810 172569005 3944910 579167620 667170002 451426147 696379610 11865051 142794579 67337951 287053584 27697213 195900427 326817691 280381428 241370645 76785319 11978395 38174041 45797227 399534814 460410265 1184981 278482579 382699170 274045743 26264407 456740446 268679441 64507491 81997192 614132577 165059818 22010668 48037531 414488729 648479758 370809191 40234670 20516813 665943796 373490924 87812116 206171539 807436056 40699161 614910787 26541796 369550347 857552020 254695135 792012660 100076908 260587629 112088251 78248359 42558582 6497546 57957179 377323733 39346837 541235892 50455663 482739769 204992698 266433513 31044199 96585257 92429621 523626896 18915248 73180532 841412069 103240665 56438404 167171084 301390172 328043040 707683149 83507876 202886282 28049236 330760788 98484881 462178423 250690496 238911553 60557998 96794379 39489397 532487122 98186462 43814574 8191165 577942735 43419527 49824636 556134644 170628734 33389318 84143258 574266834 636727175 524338413 387883511 409523609 435700653 120313620 13632691 48353882 367013006 428359194 24037395 115724120 416809677 28943686 709150640 33544893 62277421 300933741 208999991 8837155 503187297 364721144 129893312 233130356 154428276 157102215 112448318 479474962 165117057 35782412 10750739 528219601 208796219 202606548 42817735 697705910 385967000 355653326 61747910 158753060 142755672 4180998 75559722 205366150 9791303 69192911 356813677 20738093 271004970 6986208 74905908 48592206 367801232 549511986 21740236 28131517 248142853 177980873 96487037 101772370 453197508 257781487 288515999 49231669 26460247 93446804 153795813 44932589 32663510 35752383 562611573 175225421 91186941 232353026 661486823 219698424 24751109 868294075 13830960 55495655 804637239 163828003 332985903 952388315 607034655 106928647 27866320 36492519 350683417 74214587 113686863 803862740 570420 433478184 83209429 35126070 3929300 319164103 220944038 216858741 22856116 240072009 572083922 64607437 318224444 369116406 631076984 134763920 411100194 466930382 56248049 868304125 91665937 374276304 174284844 66989727 526894966 163616218 15809645 539805096 910321 95534475 646625165 516489436 423872370 173749378 581120061 71942801 45366840 199271623 61277395 333818301 485118016 5353098 398787796 40252262 321675675 418056263 49721471 43964522 53034887 106401914 435603714 151632066 103060129 319610156 793309162 135850607 1396690 111918088 314811523 573031604 590017346 484027715 795622255 85247643 161157127 136576486 330455359 30968109 582564178 465172506 2925179 386220060 731806477 491223209 275719621 79472317 538008521 818335672 48571764 265085565 66755692 418419388 152119548 826924698 65942568 74576836 58583982 6010186 116216269 192914437 392310 183619754 354492782 458102649 490868495 52667659 666151532 461646766 357270075 372830156 715099037 161762209 284093119 35552274 153953291 59022098 108767302 262344396 180225269 34494170 923334491 262223170 385986784 126529660 5960652 55756881 169793503 4669574 179874223 8631631 541203205 221374612 39598801 2510728 141229334 510128811 370735733 119725458 119192320 205719991 395881547 66341257 88802393 84239430 272459426 202671179 120774796 325932745 39911099 402976691 72522939 128182464 46206795 76205762 187594674 155741985 516872362 733012151 205293020 210078279 337761846 182069477 45486735 518153029 153278178 118194459 122600022 520560950 363957460 15021456 581317610 314034664 7092511 189303575 149844846 932433002 226659456 278890765 141370004 216472166 487260072 406135304 290517716 183706954 46586274 862211743 86907035 915057139 422759614 157947291 151594171 41357610 376955073 874079846 62063284 893777550 182583746 56186076 364160468 98261304 360626529 156647833 25444955 16334831 807770562 126936929 236796567 187987596 984997575 480449274 13647746 179328495 24272725 41754531 95477502 308468285 508353370 655172854 23783899 16277769 244066183 127007976 80445684 21301794 722468746 581372382 15741348 162726133 121209301 63273502 31640237 80726270 449048576 636719319 309257730 117005121 123716389 30214486 72741973 25799222 167604294 49141723 99378459 652873444 249593846 61849712 89642017 174734408 61015187 244428399 500069056 6119591 304980306 435440411 159660014 269853014 64850737 535548357 35820667 325872809 302504748 456495079 495950393 381575523 174499 986863499 11927727 61111276 614692440 175178456 559720905 395316401 252046539 6849762 268038338 564768612 450559030 234025129 210239169 202963871 4400531 85384985 8433638 277537166 89536405 407637829 185757910 591405456 338512341 297710183 60324385 339860460 328498564 125405872 11735439 210976671 920464588 174588262 715524036 242918103 15825015 153168458 134713746 14266849 202132852 160182242 93159776 714015115 331651707 157792390 22168494 389390135 206868265 745472666 636615259 136599169 451296596 220207130 265603419 105082858 866942808 793306 102101021 235721035 193764960 539583070 638308843 391149899 671533407 178448022 120738439 195490231 59964312 91963126 232016734 24699258 80921099 359456428 431495957 43573712 275133727 391428145 454448402 56563511 331924678 42343854 295688675 501093026 2354695 39636971 447391106 153636656 117682003 589562030 251890008 5102477 165045327 196306523 674388942 73812510 241524771 502971589 371600967 234094138 592436964 273066952 38181297 517336660 541587156 257521863 311569741 184122364 138931172 206847007 595687145 8177486 112027370 125352104 265122686 313937891 271992399 749556480 153505224 191882044 95113123 585055944 288319578 76917960 771756651 144836546 647052270 9219179 517587200 469538328 71391013 110197049 482986155 7613760 89496212 565280015 99010513 123282393 187743444 237191262 158859444 176721918 704118676 140156982 10741093 7470272 495691610 163667811 268838493 104294370 808830753 149458195 820776759 710988882 423234166 184451839 221895219 24053221 334521537 492332664 153340073 182237467 144034947 33180119 193659691 54382163 594939926 601630206 493940132 460463066 470909526 260585948 59263053 275048283 76100317 83924421 60329424 1007338 100403941 514048162 467518039 70024555 857663743 141491097 114091820 46599303 365680357 189877733 223914703 269195449 406755704 332587077 376568950 11134958 123518717 177947793 5249697 231330462 256137896 378027472 295945547 646367522 74221250 215651423 684493256 201012816 1263857 86208425 88521528 79574666 398900690 693789750 400533964 539921999 302440578 144409713 445994028 238448639 67410017 202216160 113240773 379560945 331039743 250081403 166388851 35483503 138766241 1257168 4037804 546055415 45591990 524899605 444356239 923281828 424450735 3206821 485200444 647970470 256868853 71322619 598069937 87844637 465871784 398549067 23848399 27311973 70636302 260455046 64714130 594543572 256633194 118801298 56974010 220735344