1000 623
926118204 955961753 234963883 958279334 977640969 824266467 830148181 607741844 966651672 487764558 974703023 13316117 465731557 606261904 626675448 989088078 266289702 818101050 208639520 340604644 448406816 152047026 250621430 784058612 852609355 743937825 58463876 967046797 289153372 874842361 177651740 555662629 98577911 101284244 509798589 483500655 854799274 313695056 435712652 512408486 265302840 301701574 882156681 861822987 921126695 844327013 505798636 315465156 658125166 599581351 61498642 430180856 341405296 909092758 389629783 187360904 505473016 697728397 848648386 970375323 809566374 175275527 9777523 201966432 155371184 693723337 377160975 779153923 512017432 490549058 606989172 609686469 144397820 212682406 696290847 476614225 890779207 112071882 223717765 321421928 539885506 284779702 989764866 444625356 644128674 930126364 93253995 181267661 773355018 401388248 507873667 615597225 112014699 946557086 515152951 133148194 755239637 917876621 117141890 81053794 356255965 480741404 82396351 454589869 151497063 209602735 52497186 347459669 226143102 454165270 454232313 865211461 791420934 955064144 686300906 518925680 587538453 870099789 986593761 608171587 463694689 349087339 915144805 194194210 336640134 413134771 426481210 522824287 397268046 44443389 596819519 145841161 932056728 600184422 767777595 225001595 833945602 837326376 792105293 326942249 951900382 104834210 114212462 83530590 814397456 937123017 672272831 118020314 32737891 140909764 398847521 862666057 318450486 254288132 103193127 665951413 309852508 816725687 112391087 607180642 3860026 957488541 887599634 708882905 156843016 112751509 487838527 558410029 55407693 718186525 811902995 801957237 756073693 26321330 819757012 718878913 714835108 825680817 850405166 746833811 297325111 512349151 272635459 458020964 42150998 549418583 971480033 704643703 306022807 922914297 227423891 617035218 68253231 887834306 429823428 701256843 808608130 68336377 319592594 500828186 780370000 286486348 773888457 285174924 936517148 355927554 256813041 314732772 585045888 578609979 929442372 683601502 234845635 268749391 134832004 129762627 380449679 58808721 910409553 575752840 749536821 186130167 37477678 9247992 773262056 927753081 451831354 537140419 666320403 92448178 710483166 842921110 552984334 983202735 696678260 448600660 635313905 42489611 681335676 117545946 103901457 381653745 757437541 885522640 490956008 148038683 188781912 823990094 311548231 14976261 620533575 457388697 963907927 644397144 188081014 60379479 895292396 614762753 646775445 944404119 497479853 160259918 370195241 729611388 153942799 609093901 120646280 185116395 130934798 6203419 228132893 9284447 852633985 532092410 245116042 942779414 356484887 644298623 931952899 714299848 480295495 493865488 592088211 581888944 828734307 126367525 142856052 876820619 533723122 760792633 98805824 998198955 542782646 297722944 594378659 227017771 546089373 125161657 364284569 964209755 848438515 780885185 309633860 166324610 763927543 552686468 448482118 413768207 805421168 151486003 791537475 162072980 820899985 963469997 690870777 304964182 757961809 941439290 779748167 75610675 751346431 460803044 392079951 129619048 197441312 4787381 970130871 553766073 256310145 113894101 980375075 722024537 102184210 698116373 826974452 176332909 211517982 941742141 830948145 721043408 69184803 297970263 866702977 709233768 418363424 731930272 924824877 342226334 642279332 375588561 516363148 359106509 567240556 616618443 536455634 900410148 136769942 173193235 671568320 875199611 178717114 27653156 838175494 660338601 62906965 414438872 954400879 791281558 148958649 721198118 155473223 480107811 70088762 643864042 149815501 501773127 573993701 811518475 356903921 476083983 933839991 523155993 366327161 250520584 926141381 605043020 58567408 302904811 219939970 577284010 842678016 169678121 163673081 159469091 260252541 417029743 371217390 426819515 584198474 268109264 392311113 131596851 268173105 39210540 486944177 25231826 531859092 271550290 962410275 461853438 675954616 726243287 192173250 474871702 761330274 904050816 981141770 35219810 150715144 180660621 162251809 338514495 114680988 577496189 290761465 852736159 695974224 350201957 332776846 267988689 95456622 61889170 629901869 821303473 775138214 379666443 405041493 571550197 666816945 983555416 589031123 1594568 643644017 145450141 421882131 779110997 477099480 805127485 814949602 769247118 587122006 536998892 94288097 978856987 29853706 396184561 511251621 601943697 544659827 63369004 816168087 409857451 730436825 722500087 225382924 238738839 793597040 943827585 629115619 686783367 233270982 287575380 515873395 768998922 240027665 83164770 721722871 974774426 301865547 49285260 496744419 933455887 898196284 252853871 987361383 757824108 957898658 73697 770466395 254240090 136203265 749100610 467947096 532336065 968285522 114952149 353009593 393629751 159496546 375549355 191312558 568162248 549348321 667977077 21701808 840830242 770261444 497231395 392569028 392021717 223358215 143976533 291596679 804822960 803144078 713370409 37181144 408677394 771320851 518432310 762296915 665182849 81541223 164805585 831036390 27197798 172042167 317503702 136432372 595585026 166401199 486606093 2758007 692554626 533456685 819689807 368975855 488442469 143253234 134267020 868728578 850627999 506201668 574990328 348708066 739937482 532720576 704664649 809211897 968211771 170934809 295307317 865676605 705306774 585444794 365676331 615531899 395410721 588542171 230594636 221319119 344010178 184738532 948296756 477352321 292570847 356342734 245990608 240836352 583137981 581269295 258035952 856184589 473385723 556897735 834176256 906523229 230400314 716795009 426691413 900437278 610489740 201710727 545628925 587336600 974723239 354677751 680370252 743705102 739946242 449879663 966955952 412181158 414438030 142978783 355379818 354554480 43862426 667803451 184204309 508772567 237189635 519131917 183504466 648165869 754783896 275837553 535882981 220746257 667633799 967758578 820462161 137831304 230773944 80998187 325923936 703650346 708360266 647125321 392758945 370973257 29270945 76786244 434955221 279529938 908273093 62224573 409021505 989121305 332248912 695407346 989525082 431893097 644415559 919729972 365998029 565445753 102019531 711274970 787849446 506769745 708074932 826477946 921915799 982446494 217275631 412127863 114924356 147297324 724072527 401844519 203395841 797711921 176103842 186714 319807331 954594780 816825143 662514472 539536610 310647839 45850356 489821374 463894680 264072744 683979609 435931286 538368441 638219103 572450214 674077294 224777329 322773338 847739338 22966241 561398721 377194318 713246016 375377993 981864217 412024421 428198651 965725471 881066611 970096978 7281015 148714139 33407291 913432607 590279918 978459646 311449400 256647511 248276563 741023899 277935358 175454855 318402936 471965640 728947696 607204595 569195972 179588478 789035971 547184090 830196581 738831297 842934861 667417763 414644146 630746493 421273396 120432240 926265880 956389513 661763595 140917047 80467186 612238013 542186955 129531401 356007261 539703338 987434985 867433631 13655406 630285429 612180869 908586688 723623095 658544271 288906773 455399695 973641516 466862266 859536627 211637508 915652836 953861032 19232061 310925997 569872154 399945881 294650244 29789542 849028634 388006108 632849658 116705756 538877010 191425543 114588168 789538305 540222802 472190060 631904143 837739079 955912309 322848908 585051011 383196094 967400600 832134584 961606123 67631535 650200334 820422452 505907983 205389955 466021746 654930378 890378562 532869503 28256683 789285492 113808198 766497877 102071730 575404004 756935322 580689302 339651024 734361029 637968542 610563244 603782901 558991637 385827967 497695356 531567717 957509802 645138539 221239946 940950333 437094244 575634073 418787391 614367510 586556408 67855818 683782926 952215816 222771104 528081925 561857618 801273420 920388799 50291062 234347098 420910137 110803973 256975460 279232417 266975899 552740736 791453729 452481485 623866727 440385724 439745308 654198572 10585737 916485396 964927949 185862647 962023258 348573637 217552208 385165017 41346374 153370345 530199364 890504750 951410815 932443411 910395844 999207999 584662868 237208063 303548853 71751906 329960889 148373570 897913547 820865648 491784031 929678187 131116234 355898082 248425470 962496171 276794897 796951594 123546687 353492718 463044381 850952914 916050908 641005702 668782545 446483587 72473927 451925586 5494811 962119770 276247669 293022837 362692933 669694830 776749667 804210184 967005522 385383452 387567175 464290008 686690030 642271370 994901909 587781225 745666583 733225870 636189545 855646526 78074857 541743323 323215200 959419589 913392163 281135589 201005488 66756797 843590359 384353728 696323680 964092941 366324373 763933364 529174273 196891991 542806465 979705635 714053782 702417341 516555939 799235929 133075997 53869101 773454673 722657414 406272497 483626304 963093887 794926317 283513779 716057713 263078783 176418766 333507389 918720046 572317013 577706458 894869742 385726116 176281645 227706399 279678798 783539194 581679836 970702395 454334242 735520375 447322887 609863616 820734262 950336205 923878298 711571600 481306967 456472647 687351795 321653838 801058716 188705365 518366411 873680752 294316407 722889220 638084594 978078917 585109107 75203379 901562823 314724060 52407035 406462539 910131382 962542350 534432029 590786586 15676112 680083786 344702178 270862367 724333568 257488310 488433089 342771713 980159041 83996946 422610075 939515595 326635233 405161057 821671936 200501619 547906698 343814035 682326580 195789034 805702341 255839276 671427548 757595969 422407500 238022045 124796448 698843430 580248169 593365520 897433332 145082892 418892428 763708607 910725236 852872497 503527816 955987460 620841562 958999349 832988475