1000
915203485 175147430 52675669 907172628 923355333 938224365 883014564 118059903 378167778 231597041 118234914 806750217 272799072 903522087 614905788 352404850 694754348 69826574 324451650 15387054 274277563 762633685 896487544 65224646 241855151 619469307 535761450 574272855 4949822 756874694 766121533 772669661 932022124 818797202 532358643 707893810 757021567 267889560 678470068 135189344 352002956 649221336 794455915 624802028 552743422 409361702 829723232 100014124 479188276 6691236 115401178 753465839 769324921 864405076 818690486 11180071 336390736 206968289 437969281 193856912 963842983 204090813 966526574 748381461 22888015 351401570 308791624 632425936 471807484 987261692 620131634 823810440 488999381 267103902 301128822 41742803 676465604 130852053 994273282 8170233 137543289 962190814 614152426 906868210 826595890 285359265 770564636 15502979 492327554 61050270 209359892 456170537 265141083 28402819 57068351 140545452 379804389 365859975 625487742 851611873 205638021 98135729 527938667 694637402 365239631 829067489 588896559 41705234 959919542 583169840 902391822 949979186 397877008 516544248 709363749 76989251 801903513 332444738 92492230 146747421 393495008 301852122 602917958 658636092 330254941 659986309 651697898 710059330 25846283 277185640 414187557 84000658 375321369 942126224 778638061 740561001 623710066 367534619 634782589 436145961 803220814 389690765 386125146 201097821 906235013 95488895 278087072 560654879 280449987 370579302 707402300 673944996 672431425 162836611 185097441 2686365 675339274 836795339 565262050 553701912 113980978 831965961 637702570 341818702 626608538 416340630 934896057 250318603 636391604 422194999 686464564 439612417 811885764 925106065 493226592 570637130 873111314 771313664 131292009 153561300 994409320 691210663 827506296 519357098 706563629 12603736 374559818 381902902 701915430 939821868 935604814 668412762 624304182 425823738 10231463 250912719 842164368 797643874 353747676 331072325 219838873 40212239 770684742 31724636 817834658 116427687 454878121 690945971 887741351 438686484 697023626 734667025 129897146 377046275 254024122 688977129 242166366 628583940 70880031 944081796 420922161 859001199 612494557 45226342 137341290 475242375 148655415 979505659 125402602 502403091 163094337 345241475 395131685 933779080 229482466 65482696 50206766 684360587 756428668 790464472 123047070 305968647 377647850 105460570 683014922 631671972 646954054 925181288 112772266 570350439 869263083 386210781 281867991 334273994 283953478 419209282 662032723 432608893 251231294 787435325 787528339 414325631 132676800 35176377 200621064 214675620 100659073 103344185 751552561 857087741 893808657 727115985 15572741 123972860 685092909 698587664 755644832 332046962 623768951 720933452 902397401 345548388 107144233 36781746 532338736 391097711 455991028 194371458 676222958 707222322 981806783 463751296 121547952 966999937 498927673 322169017 34191910 599586747 425513202 785744471 309190841 171838212 365376809 324763583 295811072 50469718 23351246 903972258 235033034 499636551 624905710 137430435 697701293 584566297 26728535 230040028 975664008 482719563 276927840 504403319 189941884 111250977 968154616 164006190 78250913 319598642 486175207 964959179 771701743 764204763 603220003 80892584 936042975 968596813 258172521 84370400 19066530 134040121 988342659 106615918 486193026 465764722 96562707 183894319 50331018 123291242 266450701 878511380 606010805 543378542 235431052 795952689 654629519 56102021 959958880 585396786 375700664 298650440 550355964 147402406 62855203 6092321 80811344 851414532 974689134 191500219 788301287 846272018 178056694 629160299 952887936 664249721 94925020 49450643 848144040 997772393 172741885 114594740 728800126 778752691 510489636 964231178 427221733 165119154 20333199 239696966 750515941 248550217 390863761 153388258 248468977 306235318 159480579 181796676 10166203 134169712 225813249 798467490 832958084 403869944 427627788 785846020 68119664 375069162 687813017 768780058 225357908 860554902 735891152 806674388 491823946 246380788 623421920 771562034 264016296 496271473 11258999 14532236 744821690 254639114 20436849 845807021 560874432 32433782 27603696 571040636 19119849 105933300 369508125 852077933 509803244 649652268 490440306 577922908 24721429 178253322 199219319 102595692 891324579 935110471 909270080 235664878 34007612 385208353 7226911 298023909 881479826 871002266 165072499 478817869 125641379 185509348 324624890 686515812 217943131 204744940 110072801 237062980 310678240 479580926 89140912 820481484 129233193 432097573 250920745 6470977 610350895 450140064 961583024 354191827 237766889 723369457 589856706 271774501 108577810 597083617 569798410 990057636 320602236 734870910 321391859 446243616 920380258 646016749 985275782 990839743 703278043 95348582 80419076 13956283 427445862 22076343 686954121 409195410 454173916 790391221 268182741 64524810 93047638 229765764 271232992 330814527 953135221 861089698 602589029 914229385 310689668 172387438 756803375 631291905 907258348 78195233 77535520 680154960 576728336 915327656 523511056 280006378 10676237 603930133 146479015 290638453 626006476 685949491 699833863 80180391 476340711 968016604 997221556 569388349 50298721 268454547 900202877 3433942 129544244 355308259 770179681 292750267 527695697 526983055 924042172 287470399 457694642 854094046 820141713 34422977 769421701 343652768 166945710 632614292 947582901 313424725 923252745 426105730 999374216 475602962 506286121 328231280 443619565 356024031 750135984 493918287 624478578 502855214 349868583 606539177 858163473 120048263 899289444 238375523 499547673 675847969 525845922 957242315 529942014 198503988 844181647 151880068 542156757 11127356 637010714 342256011 177068435 412779812 768361742 28959005 888382774 127164216 357190285 184518693 483188247 107326268 678436980 960183180 462697836 880821917 419238710 320861308 853386534 171044507 559236832 205450560 846892476 937599108 15209229 229350843 136103096 859390876 381230911 530776207 870518232 18241624 873032218 47586666 283537790 493910313 76545671 171920564 473590884 286252311 356439257 956779131 246094933 887392591 769478664 708792770 768214507 188717373 882170432 474117394 359761880 293923617 679567955 59170709 231522725 694777184 288521552 220142175 554168059 669752463 750918382 277202644 540510441 476466953 177305664 824048232 970377267 106367690 848485150 296484504 245136355 57440760 105779988 491231288 944833351 875258653 52540411 565564211 63976025 934710844 39681604 276254260 81150814 719249559 335424969 312673539 266543096 623946522 532815714 820711155 146215338 136250449 950430153 539242134 612717403 127735817 215806719 435611023 86619861 64291868 732095527 331756216 121732628 837875515 675503858 66565978 713134167 728044270 484646543 629626547 515271467 524328147 758397161 596422281 96094060 93822129 761612175 362637156 570285005 146944242 35864665 569016698 283194692 986294818 108258831 895912095 966546989 324065550 331523117 905683204 240873772 63618643 89955773 362606400 754010512 765459632 281688732 319661033 346020255 766335275 949287580 861291722 143179775 560201094 310230356 91790189 506539577 71842530 454427346 76824582 71303127 342808365 498357634 354497819 181619536 606616465 250409913 682879 783198369 434449384 906366083 24072140 350584381 996321857 239194894 104594892 761781488 520883626 424255925 107801742 139735254 226059858 821609818 135431383 786260952 984356528 227221573 145316883 908715413 681648919 74657819 980018540 24457283 573015453 334516358 58593173 32148271 437442625 59276052 815346640 871892009 965642136 839418780 222476389 961963992 78613673 179587635 576261833 452013653 603843561 536579929 444265261 682419773 210706100 579696644 321197079 47578981 806918217 466513962 956294394 341083489 541171781 936312933 218057126 114187233 123345644 276650300 146335504 560788269 335926352 961682144 285196631 301568487 653617277 507673020 116048832 584747304 687260656 544827019 889277311 143620570 81406947 333542571 826040343 144629401 913239215 147237421 192208383 572673786 466267737 1019130 913757275 7439517 937332064 131814401 121626750 913194062 408464701 120478608 326498685 744391053 934677106 611695316 898475895 440810736 119368336 14524726 25558039 659145346 411868100 767351704 655282270 345791401 100894274 333838966 490420803 866649844 333592742 535145540 291839983 799860479 536164670 205597257 807299997 326013087 189928012 781443101 239207149 598392713 754438064 565705834 195300120 689115169 29917503 93776014 129925905 1802193 960817095 8000298 660947539 225201548 627868357 168746162 570992950 581278985 502585129 61413752 300445182 836177871 449075646 592285165 636038349 985240316 797882423 295854699 311253403 987810435 929814155 402976906 438719502 684252218 968682740 486535976 225883740 998600243 432828344 208325999 402436 246161792 68842652 513866329 471363341 696711009 682612492 42356290 130506347 37713974 956286397 430951530 873891845 405362042 23236694 362446547 243118711 673635471 658301247 554372114 513962260 440631755 957349020 952681762 124883972 778548113 291734091 203284066 629664710 724562435 264126420 482583500 970724227 332969072 848966183 442087567 882196435 384095028 336960211 12702781 421809002 293246607 443654311 295700846 551125003 319407360 658147394 794243715 993042831 168964994 201132182 507005090 609596749 10997556 312203205 586997075 789545669 603937296 642797495 271726732 181016084 906923915 606826586 151740311 92409340 455792769 446344232 974605775 839887797 783304444 987308557 114213153 76551050 283479221 409913999 480192408 602886581 920577747 274436122 448445766 89542740 475568304 955450856 551655843 486565860 120170415 991169272 128627883 576624065 633966767 252870969 757640150 393407035 859697556 909380461 485816376 168006678 208241046 460422150 7894474 991545490 300247060 122107627
