1000 990675483
875667814 352448844 580710574 473836400 804058470 577694339 791677399 754945529 171484864 510193819 101396582 20183765 629372531 35908349 29231794 190589474 522729376 247724886 863985602 382627567 614776065 994713225 562361839 101388386 186735998 971745450 836473977 162832880 139892676 608830655 974254185 509031722 134525185 634820399 90269694 651878822 792747759 992429741 580663184 22959811 272186098 106215853 17216594 613175733 106511736 477006866 238906762 625729681 846809819 785296635 247402160 215944210 8175193 618157952 87874011 694348602 867379141 883243053 486456093 682609007 543619417 552979977 696302782 83738281 170087308 236755014 34636110 478660154 631056638 947139424 604399765 43614198 81335162 724621676 982675713 826102936 923462342 1590701 394404875 346889772 399495664 532484237 637962700 312549861 929115256 230887374 387934245 926446160 550070120 295257471 220051863 122280453 16080291 120343078 441915541 785845796 642946653 773574628 509681335 349732612 403365469 826879883 847249370 1979974 894422854 560578370 839672974 242447530 274867697 209155892 958537112 909647351 169403754 604586637 269416079 25976410 18290761 45530854 622374815 624367155 175820886 682758896 655754234 102650434 522660627 894182548 850215066 294316814 904592953 470945856 327700997 279448922 59902952 999347343 931181402 340439783 225484249 257116411 114005092 229831810 54308361 624306502 875857004 670699525 374223757 458192817 283547817 151028065 940938192 738171317 596526584 100501626 590759924 178087293 681375649 31038601 156156692 853284727 971762720 309284941 970623611 232582821 511956814 494231471 318892464 921176218 790006820 374517137 390390047 328153914 985037626 148212460 288798931 961377933 934705927 175647355 848239402 854905002 868114985 726424446 890582959 813695863 675545304 382712096 83726287 708846701 625879148 939324234 638789417 459117588 22419047 904954522 18246115 26182686 334991199 468773147 48161833 431820285 123566109 572634663 45591304 768677272 21740257 806650463 553512288 683396403 467172090 4065259 132493603 358159609 690474923 696847172 836721890 518411508 604051178 488707316 824952090 354792879 234811259 359954403 286524320 486207788 584114206 194502836 316530217 214409962 539828271 890051451 512025095 461529230 853550874 875233436 947449074 397613053 376960912 192770323 829896286 424047348 154186021 312679578 941795925 152445711 382467863 101275299 232370220 791255677 222291324 227463871 462305798 693939003 109568973 510932671 31340243 297183265 243421005 8324931 304706592 544879504 337171134 972710135 150530878 647049121 689120301 118025011 94590 343521167 789611258 484787397 325811299 746375194 384684936 193451955 937209477 60897360 189679782 647235315 823178811 772905679 357986497 310596175 302578963 863368290 833242138 310007867 397668901 71980558 739257420 263836536 371059513 569271426 484599929 660335392 596140836 269177163 843591577 601183172 8545074 53820547 343390030 358748191 319013959 609663515 598635657 162447186 308497270 992227058 94541114 757500720 601038559 242307303 708786698 389378898 356235285 118268107 830326062 77296458 855490132 762031793 791272234 720610651 577148420 419443964 372086798 208776138 714403649 709562088 526477964 852315439 367537385 965065973 636314957 78129448 898862907 966803409 253371544 638655304 767546069 968150445 698157868 178631905 706053347 997092753 23602717 401167825 973784461 650226587 194535140 210547250 303700517 841358116 851908278 778140854 817163992 9988696 945204965 12709589 673192292 132975873 503919579 130315983 753801424 993901422 317263161 806580741 591806223 71042283 429278188 41218312 745009641 622368387 904814955 155890336 860000238 307657191 544487840 302204102 452350184 728098010 549634582 774391016 709141598 643469738 64786614 264541568 623810298 818229951 424543748 837530291 616618294 159280041 281526750 652453888 103705631 277971435 580872377 986417817 666868570 227607490 833512988 56620688 7256320 485403876 99954859 656780598 612615150 836293074 847623137 856364949 5954308 646361614 989019217 866541427 79947380 402901855 628359405 261720646 436837168 19796588 595055128 945874441 153266832 853879428 576845514 246052092 985267187 170423090 155391824 470249739 593481654 102117831 139531111 611547601 76571387 596313336 226434071 570451448 323727411 214497352 42414044 586547469 358666728 557611035 87938429 914242853 65765391 734263970 569112197 855816317 331997509 588708063 983890681 285283159 459490403 360419160 170507001 712342534 560520665 992149950 183309935 748259736 161903887 444095502 125087341 789457514 123025715 885810138 456063166 498255213 183860264 519137450 948824409 618291832 500875646 499155201 159019963 806470410 493726617 262146760 875901916 333275526 181246138 658440529 261694223 653754291 349699642 362555570 212424036 200558268 875322881 958991558 887886373 283243648 451065750 371606311 422775970 102080615 432978254 414427891 106100718 256276179 827917993 526224877 977641831 583581791 476917041 53687923 493235794 758182538 287333867 521535082 646894592 529051935 590775766 951605312 540649944 116389743 767692520 136423203 793336733 714998600 671064975 153266028 662816232 487476409 160255290 56651730 871631176 367134094 148467608 706953744 716190261 114247540 709564278 624356448 705173117 786931563 952140335 280301849 350252425 523469299 639387861 7852713 409156706 652489290 562394624 373028434 689409133 178063443 244919800 687690033 134366241 857381421 281669421 160697733 265573277 903022058 531492370 749558177 516940136 376879989 792209182 926763265 121213443 690067442 318226267 818605125 677234691 550642074 121180947 109281942 928518491 419794677 171448393 170154065 265624321 540848426 146922622 97329591 87913481 28205686 556319164 109377956 700069553 900983538 687788588 971713677 228392397 544801294 79848873 142086518 755223886 618277359 247307288 100717070 207039628 508192024 326630895 112051644 665197884 734944986 950407132 625502178 29820684 224808959 274524020 423837338 200510243 24274647 137284232 292310668 430736386 234449156 757523521 714856282 575749214 384186471 711532132 286997755 66772203 125038795 478401226 893448471 786947128 771705855 508155050 834874205 787796589 291130676 40518499 330679095 264166367 413810232 720384832 801112975 367276437 668878829 279068511 69985565 931287038 135455475 893806436 663975663 848392787 77309085 123678493 435266831 964298187 491598136 418857006 498290660 467598256 905899188 75296771 546974209 560131694 676610742 630731462 237168428 249552192 103383754 655876070 949771249 77806934 206228253 47423200 930060295 31235599 271784760 647220817 716529028 246027833 487183457 316145201 429959403 98513565 571328506 36637769 533429914 156212242 111141983 418535363 966720581 3287954 455885785 598531633 105348503 557149894 748098275 498774928 934752976 410335875 677011454 671452564 552191215 452262657 809628193 796858878 117853106 212599943 364109389 850961504 412039552 285389550 637717678 792646110 327920029 91257243 838171349 441494502 228231422 471132018 436723084 188906513 878111780 192705042 784214933 616945118 62609127 246943864 909760382 797125905 368694980 118370403 248296640 228444059 203991349 51454778 871957282 281813094 150432977 448959741 639245211 723627238 262389225 230054483 973746147 586848508 254559591 344517700 826569501 541734381 746863122 983116854 232244639 53161920 55779718 357628738 895035287 842933251 409753896 69552355 963833746 315978029 962814738 80597275 408379291 98233169 74428365 533220335 430779658 724026665 430308666 946905471 815396262 269783569 91083374 822001632 198558268 581918347 82988421 201034453 852648710 671088667 396918530 397672836 434256254 676593952 843330335 907257253 589476764 489973811 656204868 201773230 484398208 791970439 110783235 477174527 357792797 703135225 911861683 888652565 578456222 882177935 137077808 402786879 598539914 570619111 407964807 492560829 21977100 787331597 259256483 249035954 866076458 533030390 930286183 935378361 332915506 150300961 608019956 59398671 772429681 404500473 517032214 79185094 964140478 270018944 172644407 242230356 494963898 362115441 419917233 480810858 24749554 718749841 922055164 245019715 613062069 42756285 96891251 815267540 682293262 707621393 439920946 599630312 50884128 137457710 619494579 408064356 967277463 235989026 307906730 104762092 117255491 81739468 959133889 266258318 484263081 153083602 214614978 4213179 346950927 285444071 914897996 594356357 411832125 748750245 452205064 903912341 445414596 824753567 663723088 554029372 918159458 108136138 625053168 897281598 593789125 351071738 191435000 521712781 728711190 670472260 139301922 90426722 528139703 60345654 9255280 497553442 343437472 862445645 418620579 131084407 182324631 654550924 808923582 784771157 310071913 592441760 433421860 924355743 740287579 733083535 736851809 263442210 639339870 226731632 164898940 992438561 854745534 519814262 269429162 977431172 447408041 870093876 395692045 613538091 16897582 999706968 194265761 838171744 909543856 179985413 846475575 510448452 484941478 648959933 66663512 115587320 238590412 452339328 167615511 838132584 481771093 118161849 464438647 641783226 564518190 395048829 188528040 66919105 943121666 883033979 928338443 738214246 842206099 48715664 598883267 567737034 59136690 691897550 251688566 520036039 759266456 250872716 502424576 393296382 986779632 274871408 168108191 263951929 489212167 721914445 928802389 155408904 748989222 530921530 246930621 541214231 553806971 751647034 377996151 687759288 956256376 249186830 417407776 648535979 572346035 113135073 893393099 800010457 423981923 22289404 255771265 155749759 111905149 602062625 873806319 214793845 727390827 294926086 118801842 139049694 394727231 103446950 57379941 836109412 469902097 250887425 500703123 56155846 367834455 966866269 953356410 689486151 103320803 398244982 107879320 813319644 443366773