1000 844
221874486 523186598 54490162 760840984 153199210 570427251 656780890 644764959 523054687 856364134 846937743 439014497 106252750 697542771 829516635 833946615 650917903 648488912 214929551 62349635 736905618 485944612 741333290 595511533 108001585 289625450 266446809 608085258 638864900 903997712 380574665 604350510 765244950 18931438 536042444 516773991 856997077 286431654 111026018 536943110 733746773 727236318 464639975 120644850 519390958 34531057 284045557 996521133 269063155 175795012 189803815 867160201 373345684 271647912 238987846 574509115 189728076 338614453 961795914 189662722 447414285 469572681 678122334 789393544 374148155 770284576 569793739 722307395 499202107 887302456 612688152 244170079 722728752 382404620 663909208 194225905 762103390 325663972 146304410 226367808 94031145 39634313 338899431 928385889 481827863 773754739 224402585 307867455 773224527 646434331 719555950 2518073 913578917 762494279 728960201 530386717 107145322 129261633 664994821 386768115 412059339 108837742 259614775 542506685 601951421 281164349 302190168 684224282 530856323 927315173 575977387 41917740 529066919 333889784 10686517 468654501 348738916 724681620 790462266 181755595 346895649 210391429 509379501 149312697 346632081 188076386 199237908 274574200 199753465 992809453 748859588 41458461 627952665 268013441 932057046 421362608 421004656 934161780 636567264 272166851 468539575 347326268 473937871 509638343 854087380 66632417 454302747 90091249 928166802 185759876 620507259 261867923 85424296 518593277 67982919 535167133 982314209 763012628 399359386 450405486 587458827 704517782 431586071 707582933 158896434 962037894 125551707 330027006 212696151 359663138 605337812 695723850 546533586 373263824 328588433 828576532 44174243 89757713 324028052 694333456 398303330 155474193 756423783 550575757 737483988 506183148 221408095 677870963 227673952 561449131 627882825 542202617 651776347 511534500 561102774 778677850 111971380 268620379 285720149 160942125 31703216 12608806 761594150 131876492 806503428 645074238 920480597 721052723 87915564 629586856 906212959 68620879 918425221 772602168 997705992 516232966 777888571 240079771 262637835 586579524 264558868 415923918 688216876 697355082 679732661 495689280 660329204 35980361 353120870 644626652 519797280 711386749 301497476 647065942 596790715 914672883 772402182 333112088 698696281 228036438 432505329 510280699 524728399 806849547 772418497 686794708 232852914 424754576 221298599 167570807 484986817 169079505 494136483 436752532 23472743 897352008 581946339 425090244 417741426 934847633 576379705 468482396 914823676 36715372 333118087 261242827 107835850 11921540 206518691 198876031 306537060 460782360 863470098 474766820 549074288 990713212 995082072 139332491 285032015 586794491 68726823 112148388 301188137 352765756 992594934 657481026 743099167 569849680 915061350 330607809 594844732 671181706 275363453 684220650 954431385 215566651 229156450 394284758 397114037 404799053 293387801 881051926 643459048 650478431 418009728 699941878 957108208 174152473 967420079 987324092 96914023 309239177 928333095 507756521 797996021 109378525 712337437 247207137 362785982 167502284 679557235 780630376 810666430 926707629 830424744 677366051 805775616 793274639 320023597 164222935 185012990 439988283 543775355 103010250 254226017 924272040 784985179 686185061 44669992 101004731 425408543 737970476 778588031 303423208 80559103 920359573 686979146 63649195 231063260 311349483 127393888 852546247 307886855 103309284 19336246 273823059 630022500 174723624 332908881 892526602 993711197 479863722 97839346 856047984 894884276 326443476 497957745 669049774 117700722 100630207 856117338 430378990 111045569 257830994 645859281 271720212 245217565 119173528 449117544 388313241 573019923 172577649 919675462 683210200 284513761 517383460 387694845 458335982 199595772 874006025 343621635 185302181 125811830 699205690 548083399 185161072 559231616 628539931 623373141 39073131 230352382 34392647 432355654 414040834 41429082 993196484 40256693 147488954 309462855 753230276 489142949 573863299 692974021 280776462 758673460 768150044 401780983 295376712 755606428 168736024 727604016 194114366 632474174 188358472 141629756 758561666 287243988 528452971 533876747 653564839 813931932 894321376 403313821 168234049 967066244 422352866 665400565 680091022 313055640 349784392 561434078 661606275 375073681 359732019 911981149 178712075 48347197 534038827 228915537 15382963 96566530 385079532 805619694 685365021 191079402 264391873 742847383 726165195 561596495 493062027 830215989 287777318 994948796 431357803 154236791 65621197 150417332 481496627 636215532 409610454 36304377 461123398 817417953 102105087 376639293 27585498 398934726 131466742 572045815 310287152 342095396 108029070 300235239 767325079 204969219 863414603 718821470 582659178 768612561 627930875 608102664 960036944 236033804 551417563 694758938 868687719 157858904 727294236 878282460 554223498 446326059 511447173 475861279 29845786 204148190 297517430 615511126 237191103 985048888 292487006 589100482 666049184 652345157 516051934 288489170 404483993 325851407 653042691 196355593 179366410 514601672 236482309 147974574 481281700 618481277 705770810 465310224 109150687 624311888 846028709 70720846 757321541 884057070 642268285 378581381 442931631 206931357 814251083 500783713 380419286 929820901 198456351 694286148 197620411 340086720 912738755 303843549 593474068 661286562 241020363 88804656 232174851 365410185 479750074 478677786 559970191 760517477 896615252 325517314 255661454 792151826 660134125 782687491 726125216 19463211 882006995 190413119 875304652 653394277 571459952 496042059 326481733 27636325 289281163 359648881 688036210 625773595 797787872 991686341 411307894 206874491 724162739 152719009 94986745 364368463 121704197 550912630 416083694 664499318 724047335 360814751 914887817 228441639 672314730 5224436 179463157 183447003 420079244 100063568 273219396 242109870 67438599 322574467 825785358 78738404 343530482 405845962 517662328 167626082 576693490 581367550 920749125 377877419 100306577 639652063 972419414 776154386 446019762 84702998 519528395 382478671 991466142 977775181 175757493 2309593 735277523 458911007 683059592 468909559 224161889 823721553 966258517 290226911 36582820 776030652 660602282 2200221 873548875 490750017 400351053 319320489 443244087 808155537 65746180 402947283 263290202 69878415 716601057 708386960 982299577 13222992 345021593 334416539 148130148 498329999 92895124 741742410 180369632 313063918 111040287 104097451 829841153 825256539 383421372 9822665 397937503 873131127 843657340 106497539 742037884 125700952 526942379 166228868 499989548 148343008 696597307 794779050 587360265 810981370 188490416 169467989 125769301 112517625 405840017 572480629 494081185 699706962 82204914 559039855 535663240 27689864 967712640 766088255 698201590 714190217 142570234 717259577 569578399 207213230 804421429 70282707 343660627 997284426 428933383 477797235 2256943 726242738 869549824 96417381 470183158 504932263 253546594 504096665 197607184 122858017 427184240 351607645 223447971 891463332 896778737 690214927 226740308 731670801 402434518 878288798 140783646 310285601 118861878 789944704 237731237 96538727 2972277 577548730 598633844 534148082 222281893 431192198 431480764 209169154 808628917 427526514 415781970 844283141 765100664 730703370 712108420 440603234 861631073 967588686 396568486 785291917 742737995 44260618 563138014 750736522 520852204 718537784 269091840 49220653 508512693 926557272 54646938 467038866 115455532 239127497 477518465 448225795 298660571 833780464 903334674 250505818 953817776 914092790 878741854 64739812 41289066 89357079 819340698 599324063 460193678 509796962 46924213 671505086 117989870 43445926 794470703 260242368 483958257 703144681 589969056 344401571 20343401 304654677 37079094 819776960 428285071 796063063 504846751 744990945 158912077 627625421 371580478 954405151 3612131 21057001 133346730 152643104 24994235 459888275 880283219 280689849 61379306 293359342 560567123 980296266 585199356 44220491 4409706 25897875 612265699 935144855 847942998 160090038 577115758 42977284 185632870 458545278 550640109 881890568 697783208 306064738 684106817 932251452 612118139 865276155 382576300 280417886 121414445 435439199 71394714 923738068 611506193 123286781 362525630 61893340 2056758 188719603 149418413 225621271 697972783 179389011 758119101 31712068 582815584 717658928 605034428 161951950 273755975 455388959 488554532 120388353 937987080 365518109 384787361 397467622 609975067 912985978 365288572 705316757 449846995 906142169 782850632 489096334 392030875 169341653 437488873 409633249 287117996 593678486 822254320 541245169 303087670 896305492 730943757 592377797 927582702 256630818 768658688 952586328 869661979 173926174 141737195 476438264 402568124 887650516 25635082 709921839 522617180 535382428 998725395 687828051 538493255 437793500 861674912 396805881 989817888 627838046 331424575 737008231 428144022 937460229 546766894 836545543 730273553 960692504 509772033 115886128 184757960 989473465 502274991 200301783 721211753 80903920 753096383 656810501 418932152 673487289 608203451 973822257 993217364 771023684 338556777 392658334 110837762 600105414 141112984 609454344 807744566 765418735 638602005 581098043 366609450 386440681 52885457 681458102 97735657 240101504 579524869 349551241 570228021 71631123 558962848 816230166 681733186 70999090 853601437 298796816 541662308 925632912 469632960 559409684 888544851 217879918 789054743 992887169 508834380 880729484 78466405 68180278 292496820 230285062 858837875 642260594 618177222 198803159 52164813 537177932 749850276 165860763 468252450 672705513 13700581 531236116 654299286 969432246 185961280 133813280 88958550 530721252 263325014 311723893 230118418 612688764 729672775 203255542 848007576 925392461 533936316 437921819 339566442