1000 906011316 702916476 1000
426378198 448666835 928428034 473805142 373675324 45261623 502895126 736498316 231472510 191865836 242418084 544276235 444104055 477445639 356224464 953908838 306690394 584707561 294817458 752251380 852722174 469468566 503286490 871710527 705395858 404720545 938309838 127302328 676522687 464639770 950090704 559821666 796891358 571297793 402638020 416247249 439550647 183986852 964320110 269021667 994097140 367875126 271839775 39656239 782486706 64221917 267234804 353412119 931475061 145572000 644738470 990732754 730956270 501835629 109409817 604800890 848465382 866267597 494126345 462234272 249333288 803984522 600762733 624895563 350968494 663650575 788079784 651545218 501379679 273006341 318778178 806888607 17603850 588922294 264874638 14449038 179337958 139769944 840097620 889470541 697732626 457807545 924109328 903757398 298769761 606623247 338315003 597308391 549836442 478956056 622305028 835253109 136004079 897972151 776629371 404240334 502784656 416827662 530867123 562933202 479135962 848187310 487687190 687280361 880240340 184567003 51522398 501041848 726967852 40487360 792502051 888400866 973307497 996179686 260128255 772626719 777411454 663807433 433988669 119361250 354819258 958940117 41784087 38006043 964929945 854833697 524363855 784182327 645236653 773759847 494540927 987654602 536054730 777964751 299402104 496985410 196149266 293332323 487657779 192961280 399942796 214774068 861508899 227382650 173057116 878107380 843130282 319821651 90928319 297650995 57134085 327384789 503053512 177266348 755700850 845905995 800323228 268678414 593753087 925375826 714952814 884398894 284157150 899347752 274026857 290721414 629516576 706914289 155195002 243517735 772499593 788280015 795610568 519905137 710857276 926726277 863404478 692067370 804863841 347091637 600736335 181224377 706309599 729588407 60740482 810557052 469866622 750962741 669411374 130152991 269242074 403501892 976691844 968583070 486375952 124139765 136675697 374695819 16843508 694756182 898570538 96293041 268228879 554602703 54867920 894663683 269244261 440267204 416008696 725149266 614033743 332469749 66630352 410275649 996928328 707003205 575855987 776526706 826241729 291592123 231137210 998921273 916441695 882859984 189500544 217411313 88529027 774939644 996036283 746788419 304791644 884679419 703981935 263236801 404618393 414379732 190696906 997306221 615799915 694965809 126812636 600398298 942287459 407185418 608687563 673535663 727593107 885471734 61768031 900703919 518547333 736394608 635927398 5675470 898352225 722073744 463343017 630399503 513891253 864811163 711910451 373827503 455442025 982413073 488514758 637563628 662247492 928951966 689595678 65334093 705974240 461918811 316089378 713391998 578117588 132549067 811643936 483523414 499915656 52678311 601118816 167131603 72258151 40758285 479270427 960665322 46275287 359685201 62723708 856648309 957768278 747780660 875267182 352562730 614437843 681727508 968978614 181336876 449596645 449617352 797631497 125920488 516100 84174918 609882083 348730253 626497911 438077339 118161236 587278607 556714640 116712904 941216220 656474141 663659727 98985977 431247644 221852486 643129413 790857343 89339097 431150832 742225252 921063571 179576800 932770371 441019103 168273307 369549437 494697341 395287633 358594239 366102388 542203267 207696862 26499838 853679143 447127600 828309153 329209600 34139107 397854406 548683514 429047983 833113881 551636333 664961438 502006284 830124755 779252952 475359841 733689250 264132079 419161807 32394668 70097368 231691999 659591988 451973308 665744923 785136797 580894994 641513299 472374932 775448502 958469697 725378138 165718153 928418592 315113448 417063840 205351878 342809623 976467490 419082459 846276479 584605278 723239127 722582275 420288946 722617245 457298575 446804602 768390885 452701363 17263426 236125243 7196251 688323131 152473134 667989073 921602025 639438590 888033296 164267625 255753559 261563449 197870337 228334982 72782091 256683277 854939942 162539923 209303683 188803201 308327571 183453989 598426257 10457481 738974339 382587309 578880051 62371230 301251277 437523139 467406651 208419437 359666208 817250181 218394258 502749886 442933283 127641862 574933246 300404248 160158845 992715030 761072473 932468985 744333719 924579861 222062538 952247906 308693681 967955641 168107245 363737489 523793244 857591258 699784768 588419787 409174077 746082848 257419906 350561663 268501303 838265577 163094898 946833920 583885976 445090472 950028806 593235400 814545005 923408040 928361637 431612587 986740369 202934632 518336991 422402084 804647436 69318220 21453445 864556049 719168344 726091269 340142408 171999748 286792580 95863175 559655378 149572589 236902912 192577252 388035141 872537478 645317609 148679692 262376966 985748674 715377539 663117050 641881646 220740424 206314378 413419771 162759731 682391269 313649682 511610619 115159348 600404292 272972264 819787862 993276112 527492832 759549414 30478313 74165184 953749034 842090036 16276305 825443369 482351566 132010740 353908232 679703260 233447410 98005204 53514782 701043207 264167590 114846770 715623367 499772548 868687625 365356052 883427594 65645403 569443889 382586374 563157103 583046414 293215643 674100666 559922116 337679264 649869657 257504960 706322418 945028936 312290946 223912960 913785982 271714760 86004377 219086614 328025523 534451615 677948130 799748558 273876136 978770634 473318021 776558862 292937394 292537017 5843315 498106073 777521308 362639964 331293165 692877710 465612919 125928368 132955260 122336923 974823085 698855035 219867800 572516743 488427620 246785489 932799669 933422186 658647170 678536131 302433548 980599013 64379396 766500710 896793247 290134262 424937727 471517993 588267727 993707 595123003 327233921 114907086 655612555 141635934 239421372 644394952 585943249 661939431 176991936 438634063 885095320 177828874 546398920 686590674 26097570 535203405 428380778 356826085 327934750 82580031 648153458 404377601 662355882 733832952 531856349 8993812 835151397 436420990 197191004 621953713 299419425 788099457 982189329 12924405 324643294 597653861 987433211 36361664 171397679 905237132 472597159 472191286 93143120 110214024 162464233 10923677 809041425 766527397 271579832 79694123 463079759 500789591 782260150 551470922 32382408 937785371 976261870 184460993 343273309 179703504 914792449 7528049 896143000 98851168 312996428 269780472 862430893 435160031 479089561 68334107 661335430 762973768 675270942 901398025 373235220 164618056 776738259 86837303 259421787 710187505 407303315 442707199 622806964 681365276 249662911 975249165 343797234 395367987 635370497 309525178 984282015 761301667 489556846 972067468 556098526 499111544 496611632 356521765 581937628 985193761 601630537 177691862 391130287 279298545 845143699 873324641 990272672 514542457 569725521 821008104 27038532 243832790 698911457 943058935 488480668 64612998 397682230 876146952 106471591 614168792 454754645 167027245 465788489 929249711 325078372 393817042 338441646 578322049 347699624 484585484 96506743 638692922 314947331 846352488 788346718 842937662 303682781 501629978 947992350 726266163 58368799 678136744 748550182 923713151 687653097 702363351 976991328 633293137 828807430 113808147 439355782 130116267 725763629 202214449 225389772 310829868 363628551 840355925 935835382 415051452 742885114 200204146 797965603 372522509 930228999 677852839 271934544 558696998 148215685 942301128 636911897 446031214 654952247 854999437 88722161 799725715 963704062 652512763 656772738 313478792 860687859 131016827 829090020 568339387 72823856 958619228 17320185 116323529 839449939 741322613 782787023 816690845 481318921 699143931 555282159 737075081 261477050 893254394 942182411 789118925 936527233 231822747 709589977 28326631 418067809 972931509 45650084 589316615 449785147 396544995 16249307 371687983 491738686 61288525 357847745 319105194 934345805 75792754 391022210 610332053 395183278 752191805 925186972 762109107 101557220 696455805 473105064 418624437 664493490 153388609 172009779 455383597 413677 510235204 620887963 640970174 183047621 211058626 693092564 855438626 832809211 799748357 270506332 177058031 475750905 863850957 679847158 504457449 150915390 256781026 350323738 564663122 562863764 385824916 232499498 272583976 736273984 756083477 834267043 605468841 263557780 430603329 130268516 63378698 53905180 820019856 597423572 338199862 809617251 780766971 151673410 111921284 939095642 449408274 504883022 861069860 108848290 830893012 806454873 244020873 638805371 57385623 260025064 112045809 884512074 38889763 785234859 81539381 337818084 835525346 278939295 175946470 47356177 272592432 878393976 291231733 616521824 273715999 434840125 471146940 794430897 20527463 333953700 311341272 368860991 735145478 42894134 440963376 305403038 422951739 379014206 655271643 854370488 255394553 670200548 508890124 562698293 825987693 507805863 593134666 195250491 219998024 613699460 82884485 396411122 987462863 534722828 941257727 280348870 244344975 717270164 260202316 943636526 532376193 156077332 40452516 206878943 238378911 303622101 555523041 490611561 445051473 294581016 870041087 564413592 663988751 260183228 622816107 835023274 430541376 162766268 792258628 18415975 279663463 535877988 691273001 338805940 258551962 49682436 715313395 658790665 942781353 118118884 949210366 796366429 338750678 403513755 102339865 965468438 241609137 906939308 90039956 399327987 619089037 471183547 335934519 316969676 476174955 474666542 892581419 368901417 340843436 143017286 657333212 69680495 741508656 688394657 280868793 392756248 763279484 444739040 412220299 404336877 207947832 936765909 664260361 530156800 435703003 930919372 469791792 567028351 586828501 507975862 229090792 964512299 277916720 169389218 435021230 293753205 45220385 883549883 978202656 590996590 767829158 675432086 388519763 427636440 731639201 168696888 610190979 171636207 619209934