2000
785063179 355013077 83923738 859536339 963108322 807004018 907256127 827826871 785399251 745303772 517697826 607531896 767006487 665274220 965813910 280446873 110758850 3957209 196412266 942428525 28402433 955312871 896690039 884398232 94288657 305297621 609706119 642655255 657430337 980751748 827014996 164029585 399882409 185087844 495919798 680131693 869643186 397339231 976666718 104110141 661623018 823976608 239616641 216660303 135020300 484156302 434299547 561672420 208886068 465224979 357925466 849571911 461704210 375197540 411096483 698851993 814465977 934829875 408240070 801265954 419444317 518272644 314396246 373950008 714320414 63519852 794379694 385464021 288878318 707146254 453003779 438972921 433144724 579086728 887203811 185292374 376420381 132035356 26183002 735672640 761848635 263045452 62759307 123532485 55450688 971374768 515478271 986808980 296310354 6556379 682762441 667819437 706525887 578505801 33945471 811682902 933825207 870595842 392990524 858742920 252891590 872034149 255481583 864963576 612385602 11327573 67921377 477978296 575534738 892825521 945835285 564138359 316767657 353055669 559121672 788110286 206117206 738045687 364381212 792438517 45529614 861735566 214030558 924589336 877318595 262076425 836638252 981948353 434417046 990845851 103553649 770249708 210351122 346619903 69914302 928516866 178078403 633662806 745393961 732179769 544444353 521873415 659082415 841802204 257543516 321593065 252139294 581389128 545962889 174445393 7029047 377624273 780270520 821274184 556804591 923465908 41584171 315861345 348408132 726913459 455567017 15569794 647675090 797704139 285395420 232614671 379195097 542444812 357661912 747338574 671504556 672529420 802641676 477743047 679967459 700756330 436342557 127491451 138572129 908997192 385101033 554668844 301748417 982485364 874205192 647072120 124669788 427287694 157937773 430808483 849816591 433851239 531481160 377445906 655074624 712772751 983297202 376425432 340984766 580853594 475489362 392068672 698181650 119365528 163197328 713182241 368298203 232623979 870153795 226721600 239125410 748120484 351386069 362985548 698395947 986177044 816053584 743901835 280475948 234851444 869522626 579094864 533830463 749282041 734948144 800982737 12466763 74083317 677254281 136332292 129179174 945961302 326193948 891966268 77386825 782783956 184362038 901234575 315035237 209470518 767762444 70926532 204508119 813657444 971996996 640281253 221297217 305400817 260003465 651868388 352426971 8755520 479776029 301176333 977391653 517498961 67094948 312144425 395545643 597522184 228142117 203817583 577716330 686514617 497934046 179129812 749984149 499575600 156412773 489447227 765928816 475996133 270763589 489508295 878727742 823448735 644352248 131929361 768470250 500361775 809282616 878779731 658535368 629591364 974491936 108401144 86041895 567231292 888051875 375932592 933054464 143554021 611003318 990883667 41702823 684034043 259830971 409887728 113180901 544154270 775774424 700506958 740634612 12740917 243381603 745958483 941968617 171803404 92723016 684069985 914986770 65778395 428495980 123611952 913061018 423742282 870463181 811820219 134814886 954863854 133706652 170522220 236908354 603246051 854196732 375433339 963546109 516740250 28609808 878700385 199269949 987948776 452070464 319981878 856310243 14735867 134902201 206645789 941802566 843984009 522681948 396973287 732447209 562746211 277195877 6442642 556216273 193427161 662197382 492660752 365340124 736751470 938592452 368035405 386926925 864795623 327458881 857409535 788804650 936114743 367974322 870873017 499015393 204227812 435334404 337021491 544425096 883375836 839129459 296833612 869246775 992985335 738372367 460532101 907815866 372071395 78754385 87495148 751937014 177206316 624689122 566012652 12332297 629630921 180947991 809684034 201963555 2447623 842400197 32910571 711794896 290797373 668082954 780654391 942457518 694861069 286454661 525396342 795653544 687945968 919528136 593849978 979017374 111281372 704538568 740121489 986754115 481114456 357672245 147054215 601269157 857205022 886163586 129844226 706669892 889775734 660965049 119141980 658873833 832705018 299287573 853144627 5641463 431888230 413118228 321885394 367863666 912344253 582815342 715802462 741491012 6220757 974800680 233234740 638418110 855209108 5028029 250888579 471824518 14885713 192901458 433938204 508103941 620583390 479524987 676651694 218079883 390396015 236300546 290851705 289238355 743890009 338097458 467713713 524031985 178142245 121136430 797274337 742099029 94916830 234011939 725180520 315165517 714753917 546570334 211498226 709140620 895210599 720391435 362569872 723731998 402909973 586536021 294702961 968206993 480106267 386973650 918062798 50047632 567739421 951151941 582858643 38551410 588291932 136374395 720114499 264252146 759338600 632599015 393667601 108449201 21247563 808682531 575592840 623268501 424474957 320537587 210531390 929614555 337016325 995792724 827862985 168671340 593386168 629641543 80554332 470242642 93810881 240734440 650348782 472767538 382795372 707072634 431375178 722028875 294156809 501392678 685304450 883251957 16583251 259715785 857244681 995793764 421310131 809645976 50730708 853662177 151713830 505717049 224247430 10273006 970829967 668481900 752420155 908364398 219507419 677183130 962715683 397252716 910710774 681521920 17104530 325393965 673243559 538121651 187475680 39633651 440996403 312081585 27762089 395986724 719540651 516270205 224528591 651481028 19716976 133864959 581601518 655407604 749055533 325680256 1569837 414451501 633598485 278286602 880790000 165482077 732462734 930651886 847005691 541157003 662388692 961155846 675328715 584437502 74289736 962185671 606307054 854800771 476057411 6518394 17001824 927069588 188512621 416614325 803631032 842086299 644414886 257480980 17060494 995190458 930756730 519204213 198049768 192085796 296124407 705752604 347492267 852138568 517696105 998918235 943669343 427360296 686563239 391068860 92533062 266267176 638343224 544144087 236789446 724934938 869333323 351217432 300481843 513379437 454565767 181924083 803388250 797463991 82991409 572881073 57925701 730488509 813236589 912493738 615846275 91625847 136758516 361352279 472467285 372170005 828452590 541779973 758373225 2994914 280997251 914703792 791422952 782071371 313813658 282060419 565381458 136469415 678356291 324365599 775515650 981479865 629288784 517165494 126935169 536383068 668843342 392449881 478734779 664886432 476754798 502916325 338206747 573194453 790298501 363315194 658075659 896389700 835464689 987923877 145313622 836636234 62833700 621230803 359440910 480896156 42267321 513822714 124233118 506716136 131474171 809436548 378106379 813127134 338737100 712467993 839611699 615907980 684482797 273162964 654543446 218932884 155698603 829469252 718351484 726199933 95726174 165059074 773678420 342202439 551363089 191329828 949684151 30489119 306631954 82588406 870891802 393689293 41007346 193420176 268339084 237678565 939159208 472578546 59999968 980784964 475836940 146089598 361021140 256506456 339304067 780856159 154735271 106045935 346976524 302113591 186074898 265023740 693017358 581812477 37374358 172530987 606734868 541282240 910609263 512955409 917493144 625641894 871042188 589743168 263185657 542882828 828691437 812121696 484651679 730253250 667759566 580171047 958492325 629845841 493698206 526844265 538988295 761302027 746363488 15435972 879321849 62561220 479082979 876205614 746607734 790867751 110021184 34143619 629603020 314417255 811172476 940512484 786486688 826420619 256168161 92074194 90863407 119315256 66238518 409661699 224368875 759230196 171187383 970595412 456077436 266867421 298533816 650710551 197202956 521918701 762868150 47347134 630246768 460804791 614362148 873372840 515601955 395579389 646367176 363468924 483206987 537836260 979074931 571412448 240767911 403809692 670233402 401192177 890526364 470809264 757059397 582326001 672767784 695960577 191106346 841888345 682236685 805478986 444546311 337489376 440751028 140665166 191270530 158461169 361559730 802506587 857253575 48240341 289713964 121047053 942263439 404180270 697847550 713307949 412670545 333911355 705369217 425028891 713220721 204796049 737584007 974142606 250465068 243832615 366040750 598160537 204383121 713295000 885793137 76812000 94832459 735156966 819672055 558122991 748731558 833800251 511212997 712867346 516864353 53244765 416328330 359714984 400186065 795951681 706436926 268133209 180711455 741975717 699670118 953297572 799017156 293338264 822866782 768481552 574427960 22377816 718691261 810031038 230981038 209321728 676092372 504823138 264083279 135012186 142804538 937136282 971761543 478340298 482937058 852027792 506108251 704774487 384303236 364010164 907348386 654301476 563515548 172763915 879242146 525303115 656572781 57563887 889288067 947513602 18186623 167979327 155502730 509408271 613648786 620638203 488294596 904149831 499827001 598694173 732147065 914208213 633749633 270399953 978070657 620198409 650070094 577435771 594228575 286559067 258258121 552496358 455331477 152153280 766650750 672870178 277099100 834154406 789986312 972837288 613350660 751218307 215049466 948981872 309057859 974610166 103344307 608176737 699354950 176359801 99214339 683159070 531431650 61015121 449067105 699137492 486399055 883274747 601783250 430074317 578747961 976804482 718241984 309082849 97623360 878789813 98183182 312722509 985809437 100474215 74763405 650013200 895973794 352395668 544433148 201010881 472959265 177547783 837269063 585288946 722248860 248595182 300267923 672557832 442015950 733842988 614060916 879019413 992356315 936741107 785532357 105219605 900706995 460893602 105783422 824440697 467059638 554277774 145308330 542922066 266699626 166781529 570735559 925820048 919510248 571397678 663374970 883765712 628470158 682292766 588557146 921825709 972825452 307840169 844293861 166924877 794938426 598391023 236083299 829608076 530880 905612935 298627916 658974596 586117653 93628436 917999451 818595618 243523915 803019095 29525670 16776184 653923068 571596207 379580310 517331002 945493880 995831277 342654793 199753931 638741118 438944166 92360168 821909985 224906517 241006171 797267544 987177484 182452463 131763016 372358839 260026344 35781735 655465643 720896158 775371643 7367787 507818705 631920790 500495952 50477905 392009293 865255551 369946337 575103193 50010474 171376199 708873530 310336379 748597078 73426502 148714772 624223390 62994223 881201222 713630613 967792146 471262794 711190543 965372028 644571019 485167887 43345153 132023886 524374071 470646536 725240034 335002713 459957810 613460300 918873449 474400899 637055588 352281779 40428668 517584653 895608083 973178482 703508534 57107786 410144186 184837997 325984799 427170654 425833216 906935251 321149048 185869055 429851982 119757077 921289918 339472304 949207271 786701147 151664972 232037151 202971953 916299952 143567226 525028168 421504685 359500180 353759211 644102673 866776428 159878275 557890584 540722574 970781710 212784992 370115857 624553658 231130451 592483453 264829462 171093870 105569886 337159564 420302691 415691742 56419915 221612012 411627213 55636345 896096401 870582097 645165830 641074527 335310749 457569798 857564385 253807928 580025500 315581853 181083058 336810164 640599060 343576906 71143663 973176145 247768747 709006682 207620803 162668551 39660917 20615958 19945946 231603448 44199802 202612866 90698985 523169366 371558040 325581022 706802878 603518976 311675079 107794365 188698050 755701953 916627798 394590414 453356486 451957147 221320569 400491584 625574486 567846503 668765330 565857075 364532306 292191729 590491235 780916186 405988141 656861320 410230887 388789023 44582026 604257731 894771965 341797290 802090505 205193922 197133418 911665996 637831906 876397949 345763433 198964413 425688818 458896280 576109782 265637025 270735609 632785937 42843669 893128508 6920430 256764419 685223633 320634489 818964296 423214520 617195108 295908022 551988329 594139027 738382123 830887964 562387726 441467259 857237050 328965032 981510245 995814467 827385795 55630318 488445606 552732794 947482470 894774993 131019957 194560665 176033077 238366296 425744457 285216779 57890285 728273462 960236570 767541310 819742446 429563051 762618099 298738712 137186000 128122067 76767800 532952643 823257433 509043750 759677929 803586989 25726468 802349118 902162766 653738351 234349790 867415780 963180502 19753659 821937423 418960660 154526287 456373932 295966743 737587166 434216143 709231465 310504655 852975782 113955959 113873533 158444991 632503129 353754530 960720986 103231169 485534376 690819637 868685586 246385814 455798489 63067251 86382393 157464966 920327860 749703336 828023025 440235531 219769782 687386019 546565911 627477943 641368951 789510359 46194179 601112742 435220558 604740941 721447057 502689523 52889028 136185962 624186934 297971589 922633859 410969561 558589038 349402867 362813280 775400854 653931532 580801187 726944804 775683806 534103423 183449829 65488681 760618368 658386432 59855244 258545995 614657499 171051598 220260302 435724624 155031816 523970318 758053392 64446592 390256584 92152120 844759902 722817524 426725011 58949487 362454713 437252051 519558953 992918484 464137553 238034142 807519417 165144901 299556446 216828036 116049043 950384442 326435331 74337562 336868749 770557292 262022165 436207652 904876151 814430249 52867256 386117996 634880615 10645956 666545080 308646162 275069740 259008289 421414658 195062381 272375418 383789133 489313208 629878611 595685361 857519045 826798514 794076449 616474382 981581827 161898735 329414846 248269318 827738589 758912536 907665174 344504379 352822253 516269343 587072122 876063241 873275999 365494733 4400330 980441385 827098370 871693965 283098155 358469365 419757794 865900509 74290999 79466869 51628535 383395796 634025763 649955357 392440135 908481695 284302 118722335 283854486 376934208 953888013 683534349 371319288 237524845 21070109 115393461 829199434 164962350 984585715 869314457 877867765 192422921 61956242 666136756 586010791 888671989 772671811 819067069 177066937 150826809 760605432 796779759 777145565 883272988 220221120 532485196 325715238 390945439 813461816 658477750 590551819 982942819 395346620 20302872 17305352 32992800 873373121 839339208 60661306 553105503 874308893 187927877 869275348 447543739 659070891 688882521 353377947 38185077 918753873 251989577 73231606 940855851 677879301 946049642 226689211 643885524 572773995 701063854 306617850 933264079 71330843 787158228 834539435 685178433 154623452 934173709 203347979 685256416 304614182 685824582 616094574 15687000 934070820 516481643 917859342 257055768 682588211 629071055 912985109 135749821 454407858 571198150 247949518 196844972 491151270 445251515 277393480 736112449 759447915 453938602 599749369 474670240 893304556 159484935 698828544 585124498 220544184 457224143 382195485 517498341 239953326 163166765 267809426 843547653 343843988 810051978 590633769 756866191 3794271 464709879 719079600 24718390 487850339 697704990 136623309 912017654 663322822 171205095 894252472 429885384 321274537 474447382 659535553 374533619 45407489 792476561 258359248 597166094 884308400 733371594 528180202 719686458 996268486 916828338 415171420 620649275 49302051 612451198 907493189 366981220 125413134 159071719 760446581 133661526 219953983 377595492 130981948 318177513 938500184 579606407 438823525 978968711 596494553 979660545 109486155 342492003 478004994 228290118 315408009 540186542 364280198 109875198 382804242 849928486 322186283 134672097 553370113 81657340 291416258 851865408 584134668 316880800 240448337 634260366 819045128 373147606 169113902 417676898 564128124 596084024 769141546 575567900 723006623 660992142 12505950 873710181 725987484 821150844 657635141 433211083 673211929 523570090 10076169 375600536 944987069 657566331 346664770 971296938 931648798 561865512 602652945 168052240 514950057 920194061 888289257 358804066 594553858 280432747 653689159 443029265 703866192 404864433 602369803 639869548 391248923 271284993 770663766 608688153 729095994 259373458 946213715 252295072 674487252 730502753 238286019 184102157 194728866 652164154 798207499 908238482 511625089 187145429 978042562 264746784 287599033 177006121 51376106 133298796 884701621 159628830 660001777 369520926 909002759 111099181 384923749 130968713 542784210 54290582 54049879 973731060 409432333 70542685 294700521 776872558 390845727 88664843 771750076 313861274 888604826 897036501 74292972 954387435 321112983 654992348 255362981 508487870 856120935 367594363 264141520 34501525 37641221 535363344 5444034 209376162 708088104 210844971 628442718 456679287 191173628 483709322 681143684 712058128 135334882 933831745 568595671 186067638 57123685 614015930 597502754 765501186 355478110 912433838 750194663 245084256 202112527 457085125 822260364 190787209 409065646 653082348 310068083 826602820 874748420 392918118 891565951 92022676 878912665 9926703 497140948 464786309 978075533 138113506 202664912 749657396 54928382 241694341 568001363 236342412 712362260 108387168 448955191 395826742 830746228 877651469 221234748 50751310 113289583 622568187 609101085 66173012 499822745 836256766 922724345 154456216 503360995 330333174 958406129 144371487 391180064 155789065 583054580 980136709 128637890 241897832 343611760 991070656 758531066 295034195 341883815 990213706 343658746 175582360 944551340 146443439 153211579 24888248 577288348 608637816 519720232 243781552 65026017 763331169 323854693 316578625 404005004 98311240 968813595 834664318 491718887 799124614 730836443 329000977 687807334 191178862 334486193 10752062 700514656 978935108 241796900 615403218 331227645 568069503 316493372 173432740 565768089 281855349 328620041 404738537 10854521 197460105 286930938 918050487 229995001 253817037 279905000 170069162 857985928 71647474 305263549 376330754 18558441 152680901 383938382 278274679 535586313 9715118 39026734 422409894 601056059 401238115 997017204 499517572 789006446 29855022 827664324 146872504 460344201 439284738 116646089 893402772 658771894 28176210 727301660 215136587 652475423 543380578 87853223 916821164 92974332 418156533 473085952 661649577 599303888 638106713 951784935 920719730 352071679 736140172 695327644 363677463 630744869 690168770 129801172 810031507 367370439 626830224 239123312 389963765 464653523 30346005 536750238 336208499 360549066 343832926 710115153 911748629 518633628 526870306 552550254 936740861 810351770 616782654 451994918 950968528 607761375 941020976 456372974 247663465 917569862 841238715 614079675 316153640 67679697 148357961 957789378 238839591 135007282 921824820 158243259 548336128 66020992 715176377 25304060 512557601 624899423 781351807 434470024 82956478 142083187 281243349 78135457 834551730 291079057 199687157 261948330 155492946 731809718 26491585 256689962 373872811 852342373 139934089 725792894 458268939 355496372 269662785 543196120 739790992 520538898 504496109 918707244 251913253 715947892 87095919 602477096 201506050 588920104 235004040 104058948 43303668 404901309 785846089 264564969 935387093 456316916 114314008 114320763 662769218 366127726 760357195 984125511 806115300 571905689 452299387 141967546 832825149 527527786 968999450 370169458 432234873 794759869 503417410 678546040 489359340 404598612 612271694 901105792 429768520 264287905 767209414 365813946 213877616 573171505 457690781 168897120 264061926 860482953 775742060 534330628 436936950 833473095 175265046 502908019 835216595 802102737 678697869 755696393 181730593 694922567 703064976 800091908 807254559 583164630 210540334 161844432 658540242 828240255 668334764 477206775 253156197 126503360 974193427 672377489 867960572 892230911 708724483 97630666 897012057 157852802 89899685 996861949 322413369 635651056 131821620