1000 885 78 324 561502475 90516500 503188889 519603562 283524791 185833119 844595221 101143899 711196130 984970786 516315188 432201453 825357620 229847757 373811927 725279187 187621300 419616883 504335272 846582740 696944507 708970142 930536011 540652941 884419408 11379200 250057772 532178119 550476652 297817594 201622964 810589507 273813569 41394757 130990345 644277760 281936954 250456054 701276522 40317475 804937998 992578329 103930132 435893466 719175746 221151654 128753529 732667409 40902949 705577868 83067564 615436136 687134285 472814151 831324927 293151553 536952975 469018098 630316769 280422015 689456816 705216246 597527454 710940401 366535146 24269458 942358175 772968216 717344639 387292788 256775793 178038769 706000725 635434376 985173674 721614952 405503873 354807891 269701101 484747526 834608523 150034900 361966959 157874549 975726773 763800650 702494931 50782636 233761831 465696140 886727393 823993714 842329240 228472678 68170870 143652787 868777093 663732587 42344184 806206516 339743600 149613395 463640888 706204541 361136958 151650063 529909691 44518254 928294431 89655120 718994294 735580904 619991707 386561380 980328863 561250425 274685051 430713770 926733364 531018795 973103557 686863973 585558956 407556099 627747184 65701945 320455208 97505629 439456264 203991880 112886155 19132760 434729462 414534291 934907727 747848850 816027982 164888843 133912608 171929142 952771564 287153945 236281003 901886374 516450674 317649121 57380315 271881353 78835876 920755917 131474936 187366980 253565628 148355569 7718859 49271389 534682698 13461840 43583908 825826109 972176551 525004924 247789891 211096868 446530482 159771648 75658846 293029813 313538668 293532594 606128494 793779845 771891631 602733645 176400870 832436943 9059894 755945379 3419464 2991577 337620644 180604729 956685483 193652780 391960027 327545364 975194818 253418788 91044064 422385433 401249195 446290478 666052964 111628737 405904349 348294384 286903958 648869158 1344456 102749605 151919304 869401729 741909241 47905506 850567572 277248834 459808258 645140198 575028528 407807977 884824238 579896581 400571799 262572769 474033370 549422963 404647128 18219602 837540331 473446796 658941791 112880550 947188039 375426495 708256279 818973475 683062260 325567897 223138111 593746678 492613309 230870798 765701472 370250667 703815099 983382941 552857394 637325915 362896099 626440055 48902918 299180317 327180324 428554626 816423645 770719428 652386612 664184042 552869768 632095406 709918995 693269351 898456106 672373013 857412226 157544485 906776591 97523703 466300731 319246001 477513666 692870754 810814327 887295333 290980260 830868396 4048027 113255106 9811301 622976061 526662123 329350436 758487135 442699567 18379774 91494757 817422062 258616847 217553727 193167318 528439753 380246395 863629648 117143751 235028731 42244708 555725840 365120023 157770151 604151957 451562709 796753646 321149135 11663698 267388067 779804224 274807259 450571210 268570605 159191016 471736588 897018995 130837673 155454382 178870132 207669443 356356480 678852793 376989970 745718280 604759120 230642804 651284260 282551847 884586246 710069200 275335223 300770262 107181918 920822493 56393529 13747522 776161865 961487560 345642429 154522563 585647305 196313676 79473555 975681358 471791620 264017802 121364598 679530373 549850805 37815769 856572553 944125579 541819301 40244388 578041329 976575107 450788575 976801767 65083279 427305352 16585950 476571861 57399239 117321617 39803348 256467650 940977291 200652899 68076683 221873113 12535884 137482835 708490327 636634230 29634664 173865728 675832730 419383523 406767952 53624687 918095319 198122893 573586994 107553967 849905949 943746977 348527799 465647551 285282756 361180004 265619672 574223569 371701067 202622910 366662640 78837881 252920036 101639075 282967208 623931101 865322935 92243089 413446736 333875924 990102489 665487366 294062149 507908598 426228212 432208857 579432030 514408263 397921362 140846730 330475209 675230856 500416651 968693269 566719320 988689450 120256631 369778316 816385782 283877870 678178904 652514918 288954732 954134749 704387232 854287246 879178022 860081975 209605643 608785636 430369109 923639439 87745121 207397173 46560965 390790643 151776877 117824536 395577309 481756215 741802942 481341582 852246561 8290339 285450498 624757902 242596881 358026195 778507634 302179637 142441953 423648367 863063770 159639571 35877464 858905179 45737051 993340683 18686244 518780590 550057868 464616027 262591710 405457062 80754149 827690587 55469457 281654094 441669462 80549539 123077697 992498315 337126377 200945298 748247054 638033612 286380 274015057 496362288 517875214 567011450 9611441 824493064 216305948 36013729 769786370 431276386 107457142 964454128 792313712 671722534 457095511 399010496 914184422 409290243 170212386 933089434 987886024 124523877 476851531 441227504 832260594 683654731 742015605 810504132 505073241 292823958 149302421 554264458 674727682 937424918 176717627 830357744 126514507 650707419 347556494 254422450 570634070 261573147 206771475 859029269 525875337 582623962 678675851 486738517 759062771 77438711 109937064 996437918 976415960 53058175 258213468 557152736 985698805 365656832 506992260 232933630 308527541 96495791 348225684 624221194 721312575 605114694 263121936 257219159 688313199 279702239 771684518 803761609 445590546 798744854 151399847 968401168 380880097 450727627 15938132 743663805 48616719 607018491 965831030 430654166 816721080 387490869 137465804 258352799 714876257 430238074 758803894 888434168 358447947 645406333 493365889 795414330 618279992 620371681 295479592 672653963 246873959 54029486 783858044 656648673 556103824 704151482 522903163 671918189 435451100 725609045 710346817 21680600 550045024 284111232 715860554 857048053 485884597 120930550 792424068 714005297 162469420 34093396 226618505 168914450 471880808 506873782 717362207 620408657 504443998 393793085 329066192 304765625 117120125 473437934 449324827 228423934 126991105 721274411 382097607 158027470 842153357 15312920 912418237 316041379 420349172 764404586 916582900 346229332 248007315 409044586 278319443 306829977 726629422 671486653 712177671 176080912 505331272 434685724 514954216 408845997 956568296 212266882 130045769 76340461 965549410 240583199 430225803 504105373 384008217 314327120 823082817 18046602 836784485 580375128 976019561 572019288 223005455 952309441 502997720 281325063 429492432 222366367 612029682 242192766 754004875 779349389 45143948 51082388 921662347 975480563 872184939 135116851 889041880 417452500 318488876 722497955 270226400 547133508 571494796 331847160 956206334 71508777 928905946 7806407 866309931 356018855 864819879 789545854 835456129 414157915 978608203 800857204 565048490 554382350 946780496 317910472 92129728 163393430 741193810 198817298 354712820 688974988 225421133 7917899 247804746 247785813 753211731 463240365 913062934 888954837 985575333 446640725 729762898 164240125 111461339 547388232 152262561 792485346 949974514 20928523 855960649 960689577 862985718 69581877 678805112 658101445 701658451 503979980 150756427 474058068 440005991 105844510 187088090 229975494 97122458 211541553 202930835 154417019 554405511 4644602 952268950 909221661 427289139 272829361 644968938 460279950 759639339 295634975 674117511 61190548 179758084 880384403 242006658 236530722 968116788 946677882 78867026 813747481 212426716 308539097 194363183 89346160 720337096 830913121 265592111 862126226 44143408 529796879 251421237 508312017 263594570 785224943 546669955 682296050 495906678 198508786 792934099 740433282 160509900 527650344 85654405 46067454 579651036 152324637 241967744 314309809 858348581 137747217 772897485 839772613 703967078 350107845 883219359 26399836 700678076 784453317 357899609 925524529 348729763 670030675 797518307 108352841 782451871 23127840 50162712 848037169 504658906 219307943 990124684 44786215 972401265 889095577 286688696 939054370 607048089 271243201 74201646 460535306 172887542 674244421 965261446 952476600 794145858 377261627 124787531 825895255 103701320 208429881 811140250 216677730 383036238 484347563 247499872 236500838 150293827 206701609 706681867 483968488 473723924 186808715 468921601 655071043 999045707 754437797 685850997 664869284 969843409 523167520 578492392 255994685 212634335 780272235 37780152 457763491 104909957 206215404 690271722 607647439 963392352 187343527 242221072 34610979 209516182 166327249 787468979 973097197 686602678 7319745 420236655 236699886 336232811 215987208 191257768 775443935 273092442 135503093 609068931 454326483 528696390 523008328 799322502 20983795 839978456 435980390 909094374 203234983 615491358 577710779 628621846 41384123 768269485 271865176 772710668 291327409 440866527 177952599 526980740 535065089 936083866 923764172 287541923 232340526 63620039 917145732 541872665 657305948 472801565 754424087 136539612 972145559 46477514 800958962 724084016 24692538 198213078 41201134 77985354 767281542 876002211 586166594 442301572 199512539 437779376 448840981 363215343 812821587 479309589 845862274 416870160 379216319 270949500 575906322 160801440 901922006 384397115 913160546 470778565 965453329 15840468 179829877 733410055 472293414 238117717 408733459 953191954 711554623 619969424 826487018 910815421 107727392 85563178 558270376 751771248 459281438 858412267 335970785 734503320 803990560 543902540 541947902 181546494 938246023 651483119 781769213 594395251 726243120 623472898 320862514 535496199 131792825 926198478 131215497 10783965 275697877 884849057 525823276 48315525 179302737 665587111 290442071 285231553 881713819 293931296 53801649 950454087 767248710 923665643 448436901 428618259 708691712 711400266 417485070 124866623 571559732 391253242 961855180 218457017 412312349 136416600 664652725 193909824 5847568 877463768 392434402 251244110 262668307 968389411 158539095 891326580 480405526 477736356 592078166 361154894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0