1000 780645752
407902409 900511804 621704702 779195958 17584505 713177983 634416583 242310429 655332436 189062633 991193668 957323384 372169229 777213784 244839638 965775240 41311109 5099009 930187318 140394802 194891303 790397717 110316816 143492582 237126406 568142890 965778201 302541880 456235968 682813291 304747321 444945576 43355136 712438401 981897596 984726587 572111487 343635615 783166791 495012659 605395678 473227750 237032814 776900938 716904238 90773841 670833591 602310666 604415251 636944551 85754990 899018601 275164838 192272891 990719252 114264646 114905371 685150314 924267839 512477124 839570227 941616990 538250040 576650698 926658032 558979259 791582095 658707995 662408168 255255306 493316177 95339939 665837016 567031713 187320120 506184183 35240779 529970755 117434704 350696611 957459406 310779455 146967975 324116410 478399979 651572137 178591555 306901913 795735123 893592742 782400590 908799184 989272148 68530909 351670693 680413387 374590842 698026306 722359988 621934919 273323788 233211896 581598480 591748188 9460740 444944951 397942149 199872018 252450672 744741111 815591950 532131975 650117958 377182440 286754395 665720348 174106177 928843517 160956602 624968068 58383584 112332751 865094798 354127803 248697275 237989056 694964490 648362488 928069648 586999278 757907278 998719505 555928566 823051296 596747265 918703591 171498580 655761996 761125362 873193118 968298399 905864164 494647790 760335988 245370853 630182803 331690364 673424527 105559686 509782667 390274429 766314385 77013998 70176541 276031564 321445670 249003722 275153488 141255928 454695017 874253764 222114142 285931969 928063246 691786680 848200128 64394874 906151149 576198524 2756490 848438294 562957886 398689846 624500870 308585186 578122763 280842601 90026809 703028613 328199371 801345683 914108156 430693051 715060669 819184495 62049995 134311743 509510690 177093102 370992357 828449067 946242849 944928580 270419718 83303305 761512327 256339149 839178188 245573427 534388975 816091286 729231439 64826473 398547620 280703142 306713315 19538228 22055728 680407393 175135561 884242311 69658015 818723673 845789213 154166191 512354264 401445250 45751917 790221855 16680450 159763171 598504944 175031393 444249094 149939258 255212455 728445220 136335919 421863602 373796991 21168004 494825823 87418653 472593572 94612077 834057146 910434676 430915586 830331053 259102028 571571820 244283076 455889507 85785707 948024524 832930164 356743262 808486646 344764222 189168575 986095187 366866535 278471282 918853309 500562479 438363474 215896402 724014878 504053344 633814803 280961065 132603295 110946049 322255307 828711162 265562647 608630096 889293824 9542783 752223277 377041874 784618022 865666117 94988497 713523312 87713049 443537459 82911892 170988316 521803033 200288744 117775630 707099522 562965620 510718469 256331605 277028301 171594985 247803099 979087295 973880121 867970342 381753510 936386046 576511002 713292733 159170180 89727299 117774046 530874672 398942472 860277877 620927208 251819760 140121978 988528619 204395938 996037925 501403551 193464605 533460539 491041535 892647707 699528061 89612675 827461999 391640843 446814381 482615719 789427253 523113306 486137818 489279474 353199917 310871660 44030128 893019581 522376087 650885648 834054410 303675306 191140414 379320940 149163145 173781490 398965842 227703518 181243278 359284852 544377759 107262507 292721227 824757189 95711638 973445170 200469029 835311700 142500837 208660721 386407571 960013886 182763455 136356793 974248749 768134496 257012067 619445415 986849093 903030358 201457142 696249711 353647968 100389156 644653317 140043602 512117711 218243355 322117954 89833469 966642600 42303865 670094078 905745417 954005882 281714071 450612709 347673871 992299395 166018332 292333569 842583720 405746797 143667239 270989071 508689258 749049999 911412 621339520 112087536 195114354 839404041 936080188 93113659 740341054 138121996 380600421 816854579 46942761 609623217 791107770 908871916 71023305 867888657 403108271 583576893 186099179 994574689 19123880 264563045 196741266 242417878 368429739 690025686 854806225 732508665 552593529 231409361 995610088 696538270 37883328 973523157 466556480 82686837 396051902 41930575 878283270 313080605 561627331 816423103 566870092 735290413 963434938 226403511 92748810 289727202 853678321 237215564 159227467 443877114 201030636 238705161 916187934 137800021 679027939 13795798 578720612 192517686 140691475 120190700 263389068 614820016 934241115 947767139 667614394 29559594 710199961 713299881 393375041 487594381 325315027 367456703 419651866 192696365 732177585 330566510 312732969 62280899 138032650 221775569 35393472 423491063 850729160 62168844 103395057 192585007 619864127 589046327 516480480 468290585 159297399 597942710 449698322 291047154 893197949 307875038 632026049 597389890 561216787 217588669 724679778 458677240 341981144 21324020 229546602 48415574 254180289 820617518 974411097 809728404 962926563 279122549 479035708 56794110 250407648 693872968 255435529 578570208 553522595 285573695 847658749 887935851 554147319 342247576 725067445 340024023 916414779 919623968 154535053 616041723 166023725 762230902 528513303 538050739 803888287 790448428 36474703 171690395 606556981 775686551 821278648 352740655 544577625 957002477 860245654 523133470 106558632 724131341 960690606 101812633 309693118 933174370 89870167 914078567 877428459 447115217 7815682 501245087 279047011 25879527 256781606 226036095 19513001 984740359 449479544 142092660 903509205 912861104 977274835 349722510 961982956 984877295 53038332 827347728 109506153 316097630 483881377 753477838 867855428 703507573 847727483 131644818 352402970 637696387 187532420 976848344 788818047 732372083 494427374 236814795 6670864 112736552 2475519 981572915 220347187 348902748 341363858 621085711 317516732 854915988 643645799 314868386 808015475 469106075 978082168 51112668 790299491 406703170 699461503 823809589 83114401 224219139 681948456 167655485 814266875 231646283 196391027 394802647 161413900 718170037 222436920 358878662 833670030 431253941 306872659 491615630 344731120 91888474 274000439 794820606 621499091 179375965 883099573 847089942 743180827 923113920 285372094 860118656 652429252 10345180 805216032 228354080 993405872 675711187 58832571 53040833 231286325 154683006 649397707 752211158 925384351 713056918 593888433 419781121 470818833 532404943 797906240 177566384 792657716 280871864 355889189 421434296 212464680 805623616 22240579 720511860 56489806 205340051 613139155 845000455 987805881 969388148 847044485 469492111 745164620 811118358 344582466 724890601 513537078 974268981 274325480 308812688 250241791 638704665 45965525 561742592 788570483 440251497 227090969 100512812 424340321 745027289 843859551 853187763 600418320 631652457 834838502 551676637 580870955 970002492 346048190 987040680 59416318 808780379 105087593 143531998 238637163 740085225 927724745 228206997 263556965 325468920 503361706 30490192 33135847 681925694 661380391 951924528 933737043 491551394 946944039 495538140 867764968 505054083 511913282 935441036 931354108 65211676 597708512 488175033 7372327 30969066 959010531 239812051 801184779 359481709 979680280 89395821 580148482 328093820 337395813 505128829 370362184 88862476 968962525 338518847 894970573 453785257 790039927 257891615 827574592 352383768 891987547 670289623 654578486 200055851 763527477 288125420 205293909 114174445 100790854 123487415 525793448 942046000 56416234 658024748 772392072 94055386 169678939 101653977 734022824 916985979 434884760 987843227 237688793 886460548 396221925 321284188 660667567 618875987 514434931 823774682 165359920 737616819 796974126 181584371 856037156 635678380 616470893 120090948 131249612 894996823 814602728 492257396 936580938 780269831 48169143 194561510 814933657 151705155 579751599 786917983 999111729 686297712 769821865 926419792 34920664 371828404 417407414 255608750 267143243 137322456 79489804 328989286 304335613 49374489 264499161 819455577 428862189 889099286 991293755 744570374 341463081 248698679 917738366 673217348 683114964 962528289 980188255 525043973 205982233 479998952 515286352 884168954 790407669 325287671 490814067 475758696 50787467 592294076 363724155 353251198 134770189 133960533 75506882 12886873 878572680 132442701 960829 334476703 217715572 351474008 965652711 61727788 398586630 346816353 715481474 595933515 482901513 777607003 843061893 233880058 932080704 110485270 214961320 659601226 131237554 790666731 73001693 523001472 523099831 440421109 119308305 978526566 978478639 891377262 920916233 690171658 963215660 547315276 617869857 475122173 317634173 271241332 447986630 964080193 694308730 370388607 888195727 769569407 685555038 790909844 11781190 125106998 817620621 478166181 840913597 769456901 942736232 706032463 918782201 377138229 215101299 533877266 193674412 434468230 57271719 212542722 380601862 979028466 123668985 354368848 784906605 680722589 734354731 620793120 779104589 799733255 70849507 17758322 611128277 482825805 923730418 358559253 605819316 295812499 629711107 636627433 848256832 398058485 377218767 294861197 620780878 71486680 825448003 621357072 166669112 80271032 198681416 533287771 38838627 222682933 693312638 809960096 160370146 357934779 290132828 705767709 701621855 397066504 127969238 754798965 709050881 871920699 151931284 456621105 934531384 594697251 956346677 882667458 762404295 546419197 50580282 494643977 906819460 728582499 106357961 157753548 855163356 966263184 220221209 335927141 755630100 789625601 174896032 349594469 176178133 816180694 188919566 483592865 127442688 268136091 90933572 160280938 923939282 862524408 863009598 41850067 721294793 263559812 491040804 866837091 456519514 900839892 158604139 546356818 821153935 188653842 995785645 699690857 457028552 350118846 853297524 243686756 134032275 790663568 515772835 894903923 833546094 480022588 651348822