2000 100
484046702 267135814 995006323 960003857 746771687 580766382 679707975 116939065 653189759 314526044 462319637 377553976 94457404 80651779 901675936 333301035 784880338 852295426 122010006 629653934 509185691 547387975 291801879 784190955 781355592 34061589 704334110 257753604 197566985 610031704 382104915 710040029 926470145 999490044 143485213 283398116 403013153 157217793 840388844 817296443 992230856 780050621 309099486 78531397 161691496 215062437 523984990 810484764 473769995 730484184 540109389 639769102 303426159 221625791 839881593 77397691 599099820 838742419 659660603 184735900 45277066 659194291 154971527 633359730 194827325 251674170 401404824 547917389 786624479 330633607 238237227 218206920 319797687 732425439 120137609 386082553 863927046 439264198 862257864 218642048 715429735 349961314 93925951 666417129 828970994 689813934 986820957 191139817 914918713 418562847 870779569 200715312 477675022 424273833 13491692 962934929 540615742 738590938 695827841 366612020 284114269 29223878 892856686 210314046 500118349 37865601 71440277 354768401 588023913 786620877 753095605 509459105 870838612 488750533 738710974 910887696 477317060 124710448 397926811 735369439 330727058 906769519 286310516 439864076 11324072 702122477 245055721 140368878 456021971 260857348 243227041 865859069 180024679 771179825 427396637 103823203 920382680 435184166 337941096 547446564 218768199 483532848 525835903 981107039 721844671 798421192 704253899 669403915 188444702 293718564 120217459 650476626 477195834 753560976 851313352 103719492 11429137 119904984 58466664 590570754 638573684 458727068 221707751 694046642 762850151 221246223 203329787 810695220 914328043 204352925 944903151 501476356 983295828 308893255 130667272 999473500 106626746 282385458 682637240 191212610 910543389 881941289 959528460 849026076 726680540 219646678 909004907 922121425 921810427 560577306 409567867 334520144 710721688 906229444 672926299 255908531 535928583 335053804 466735785 667610565 681764770 391610929 80853984 998641015 529155919 739581212 5138370 462727154 173771622 380041867 803860296 805004931 104002193 497685824 869826232 71392720 693619108 680590734 904444339 12914821 441553749 590183101 376831067 28320845 571628513 984941750 366459647 641818191 247645166 695910692 333801185 980652236 153082735 414944424 476236 732495495 939557165 268242292 318316220 174811182 199470064 724985983 6802392 814887121 727494928 565597658 765387100 989392533 713909734 178465135 914893156 148808834 228547149 672207809 994278129 238588014 241977116 874132964 55709822 933496266 653968481 718548032 930178122 141657203 242859411 297705598 843015633 396392230 490276708 289740165 422660614 80764229 928870820 133414194 32959388 846871020 473574540 32991969 944177220 886070992 439248188 705983458 138662517 757037368 423526644 375986950 346937007 519835012 736376750 766515350 934865355 10819347 786768565 585684004 625344762 246703708 648204089 391007684 573004922 284494733 815757504 693310464 160574645 680692067 187057237 386362058 804343597 46380514 120975538 751319625 837221975 489305910 125708627 565257975 81710310 764734155 870884861 143939129 766009220 81878085 842590188 707880159 270649904 493099112 730603443 562047169 297713096 590757078 34821024 217854182 230562721 541274392 120629230 865411862 102650725 862049533 559694273 415843803 550646272 694238994 543890591 80813316 823246291 742610477 338767751 644634241 269109703 675778984 981189111 449133111 564763246 33456987 948557753 659126663 509724459 249254550 748083790 149377314 724620457 781550020 649932056 804152019 553443170 664008287 820701226 47723149 818879274 232542720 974515671 798586195 346647910 612806095 91084455 597317108 183709397 104851931 365602642 115885343 418921530 585860130 295771124 251515442 175165410 625452208 420970535 422986114 272805732 689050995 45801886 84488910 233874857 466066654 203538198 667755359 572261799 807988101 971898084 527242861 212092608 320733876 891766430 823753574 118919332 416427677 646490858 901930241 248343285 494720514 121544283 26963593 374705478 670182353 217237023 216844322 290074146 548339642 303161721 300750532 875698735 881558215 187712215 231542107 494017245 867165495 863710569 864954045 87316729 695275716 520854209 220672260 392362475 905159709 689823794 193284036 217529018 89006429 538269601 921787467 109094567 313346568 940196845 301088137 957897098 119492181 561882074 376221313 354973780 876746774 926983345 802356594 467915524 109904452 60293424 417261393 412985030 389855339 209413043 780419146 864727327 34042511 16002204 901775265 167449422 29204841 155377752 806574059 817358147 349748977 494705705 57695637 635978971 186361240 311238039 516658853 275250816 672684291 951204866 276079615 770407300 315181069 158413798 380122375 361884174 79008798 321384685 614993341 182465651 589221106 289589315 233370231 980598238 56471476 151752591 449186871 207713057 367596280 234736591 921863786 650383067 329731113 853262449 978683431 750893010 918787335 873504731 888349973 537221169 508979287 706654078 208205091 502338555 361437102 670124041 430508506 340029444 447171056 742634299 932220562 335633032 793001196 705585359 783272813 694221391 805508377 212955051 637938454 243230061 191042854 255850035 422133670 735768837 764333193 981593897 327122692 276588555 59882449 775399300 931155247 239797814 549520400 633110386 728626133 781963157 857815518 83453013 102720981 610691452 762622816 663823887 509048341 780814839 698177330 455265984 517907366 746158661 184291676 677559958 363633968 578660864 958440223 928460199 231096133 454295699 229324645 775778092 621512523 63513989 919479650 927125967 240846340 228590795 506867438 465048940 114561764 340440368 670594363 799742629 694145935 380308542 654378143 847135600 117356743 825936773 24147057 748064258 813496339 650049837 672048367 59655420 492813260 408676408 608506173 388670960 584426971 260425256 648647733 2584877 786202288 688063269 184910081 392571851 890100544 381666740 155260160 626665618 220082151 647088504 848134925 992197303 504390597 606997587 571438089 634517854 508529873 491772592 285614129 126189842 263885311 474727894 98762909 368087028 451307356 682879506 406366844 863692971 86488035 15676740 881613847 370694549 245954031 593413646 230762883 937535290 871575801 510439741 806209585 737303510 580881461 456427646 194607930 735096904 342772613 459203380 240473024 696798078 996536118 96073293 515605286 800379055 690479929 918994510 459428348 476648769 712454059 156488667 507152956 861030924 46586812 882510439 128671538 309326415 825135512 638893404 293654949 436375036 455053379 250956697 819216409 124067637 215659767 534769833 368740010 145688617 401647770 513180058 430342865 723286154 316088346 424097553 711276548 137449013 540112202 706304589 591974580 66417903 450617437 337247558 212813144 151297835 97175593 386544152 719573366 441505559 518031230 654624371 895546762 885602170 863064989 757404326 572359448 604378891 971369925 115515886 844276095 660760954 4547707 780711993 639333445 118335686 504725198 174451767 459094641 804316778 903482755 113560785 894057749 138740210 659091790 548613419 646337709 164134036 67072201 397926679 255271446 48362210 888595028 830554703 853883041 646610156 172481949 834958953 192732565 976521896 558106442 235486830 861024706 375518967 677990443 293687834 908973222 945489720 777580224 5424948 845405504 51545961 116644840 373776466 875902233 97704365 758808642 418456779 393357091 411608708 14986703 386861774 634254623 134989768 481698556 1898518 667360301 749502688 175351498 956888244 177963394 431645029 722149291 204589258 296042634 609524020 478860410 719104643 530818938 643664804 890255837 19604542 788473882 648045273 223405588 927551880 651090049 693347405 828056919 905740964 620283739 741748944 908464394 672191946 589658147 93372404 305692878 361457935 12797918 523517334 769060124 119031314 817635264 816100544 266014421 963545620 377745292 720763780 926326500 213742616 96779472 433406211 528552462 643813214 766358656 720784502 62534807 944473081 994407132 590092609 325609563 616513661 720413546 398572428 458143436 829664763 275034209 752677606 554264993 132612818 959074340 174971091 879016776 625559003 460797493 936938310 183084711 351954992 998223043 251033988 331155023 736898467 599358197 262982496 297695774 985054716 402622770 806953717 434885989 261956852 52770838 488512646 345939219 608372257 639592140 571251016 878231488 33987323 830469508 388096283 816279068 665073627 920650362 66479809 850633802 798270284 151605411 300811487 196925186 389260626 588609335 311583476 952083477 479472004 681367283 177274844 422069275 308033082 850072282 631835465 15949322 48785253 508582276 603048828 633711861 876280167 199867548 333655444 64683276 86749984 177723795 521391410 8384097 791215741 341796369 215465785 323798219 859182956 329680806 508914202 51421396 563737241 50697983 408390648 983425705 84123535 262554117 796346590 448258469 673430883 789738372 20004045 879906318 927492568 164631548 136817358 445303359 539576050 623992608 164459099 582928918 129671796 862102898 222269165 350622612 29188049 347729954 787857084 334309024 157595755 58878124 227738839 224206621 877852600 245599864 516059605 311877212 724030175 162603746 513371881 540354643 851444 39927028 372471812 153499642 192197330 777415568 110160050 983738178 169837618 49437561 19640874 398235099 279723098 90871596 195045678 811580002 394610133 680259983 136174127 252085523 34295328 868474725 117686185 244037699 343219242 464954203 97840666 180526234 556648803 50780320 387474601 67616664 426001620 128758760 522133225 382971698 776263687 205992882 160186233 152817586 237534 827813474 286917161 722834605 413400391 280826573 421863648 370393710 968875497 192751636 895508377 825486977 189631553 926835286 70375380 205715013 817661710 648414833 5892944 72273475 90740062 864226025 249241234 275033672 189279730 271126196 204391106 56211573 995573347 509577245 362083802 76004175 242136081 872093859 271617820 227115992 619317086 600493430 708700371 860234551 810198139 679502724 378931399 812881146 87911410 211171102 702792377 316902584 305915504 879446131 954399046 708262707 452401641 39058032 641471653 435701085 580184200 603115209 335392261 48327651 425932514 205386566 308546216 731214819 765526767 683979103 426490927 135816419 891556839 948980117 719239610 75451875 853776026 266226725 844153429 190704529 464592011 842269714 463067993 732888062 625794875 668792274 26781685 270683201 301214239 553943413 572632442 183925706 911716344 161896329 688049755 557415353 238548970 633421567 207474720 40838906 213560380 288593665 660898241 314722867 700788585 694754742 973375552 889072054 439988479 707213879 270429968 422545994 622748540 529222125 986052444 755808573 342742276 190168468 217388908 402925333 58753805 36692202 738431120 924421259 101660645 559461717 502673307 522166638 110530463 745301538 825479364 536749954 846037388 575676921 649651541 133335803 179947743 643493318 123916708 680484265 779987042 93930729 562145164 312589873 18684893 107919530 978529405 462122406 728243001 91917456 329446901 535905013 386050564 969303167 85504481 746816137 106833224 225316885 569334327 509356067 743767916 814833818 429690176 653693363 8729526 713255091 854783124 540258222 675852832 881509776 218818728 724106253 743701374 164455485 808303856 858212940 440370732 423864238 193887574 61544036 840952067 672831024 460472919 377449933 486411406 63076221 775707766 547467843 420091854 652278342 410321424 204614369 360647127 374420920 644379648 565999332 369141601 199714272 194430849 733069959 347838426 631974241 734361849 340898985 570138880 988984491 867272601 981659287 96163761 631294751 653186849 603731063 396199987 376336692 651234850 896892052 538535471 675436618 59518110 204551404 294387276 649571611 753152095 281623062 507417185 678693372 827036603 930338596 726067395 452325121 724631953 358461984 882347358 249047753 718459 658136538 836539143 874920236 242298624 131504638 931594195 773266355 614573103 544911408 523149122 757174666 866703005 466309864 371717751 597320915 609902756 286567288 460642949 518540434 420878304 224026630 932232501 426943619 881229645 600602086 323006988 962883816 19452659 198739079 338467182 362756147 262286526 995092543 139260220 728645295 497393698 185320766 638354746 385975095 712097535 411104787 688234756 90637015 230902735 661844646 907816033 2882841 653779751 811271794 432500584 381100655 65749831 286064079 418177218 449643973 263292128 834196948 235619034 776145735 18434030 269739483 684461405 526536087 922244586 393437971 292400565 128097347 96135608 73876473 14170229 597175211 956424586 854321550 355045994 922028841 576133608 900220325 786629666 396027985 707078562 527950910 654371469 166453865 422179983 344501086 619126449 160098238 562325795 390329240 837581354 367378332 602303431 134523070 740215235 684336127 261636955 73488719 759121570 764982062 834773946 743092131 215415475 749552114 127181192 306756769 447539545 63026125 483356532 863625794 660737632 525228557 112358332 571389705 767612078 929826224 465789461 561549758 341443511 4381880 653294373 773982435 288135698 3638157 743045980 381915921 627547613 642922082 234366430 604117323 349234231 330130521 246542620 143701754 788597094 730934828 77381211 234224365 358154603 651543041 976999354 621509294 130222128 392635812 443869220 820927957 187596382 223486070 204911006 692800972 985431915 361298652 754365002 62331819 575099201 212448213 130959998 599679621 344795626 428066384 746824793 604837067 512389063 622828303 284764684 11169010 681155226 447280215 215990732 525245777 110882591 83555208 680219461 661758333 390535873 490213081 346762115 976720665 683580055 762139679 186973543 83078760 688885445 225839008 485462596 36330067 577327877 32930773 787296024 622002214 877409852 627114791 133397555 63948708 586266391 933826501 318996983 311127000 745208334 185661290 237320195 4089790 897774677 612926644 421867641 705254748 216909027 236897610 378150250 303194559 853265768 737248795 838357019 970639716 952081204 800206953 998873275 597948116 284138257 940961774 34358781 642447561 732987687 198525980 766851091 345439533 306683659 361223312 667908417 446082201 65211051 46139163 21122205 99468810 829258314 59121978 323235183 191994936 952398688 658411501 299955325 384822328 190558331 215257232 474877399 139985263 433148041 410177283 683737843 872769643 118687404 141955048 961010457 901080234 25593323 335013954 495690609 309942356 104480936 239786159 921425520 937047554 472266330 553525673 158350671 156943706 590268151 605840893 334021709 895058659 288662699 425550397 667789490 870868548 56771341 683001921 221372440 228599962 234321489 257011643 424259391 117889810 312126101 298991507 125149299 498772753 227615538 355650588 982739328 833526119 861390385 342887844 727645519 279071981 508891028 739285916 213098282 877803071 762164523 143433165 570142260 265713768 18254722 991889858 762382257 853758942 919336724 321325884 782631720 106546303 679250585 833383044 714145832 321554012 875224970 183853330 894065750 977398240 423370628 692087118 706639374 164489989 462819057 116643103 705619310 168099965 16754828 818680863 597853876 169382737 81006954 328526774 205505019 828290538 216481960 930604015 545496599 129317403 789398329 959453559 978945417 256628898 997436716 387277483 534229396 961261215 721807372 960814528 329060189 479756173 236196693 461069116 540171258 620786137 679153537 719567069 994524694 796863530 534330205 9986549 737300299 145025945 647385192 666899570 655642788 832440571 973473414 153519659 414624136 868093405 253850698 92404164 273289276 774140309 368438643 200783130 464407122 160150504 105782513 388636861 120490666 811509568 908438092 640408038 558203314 823473837 231546829 305367250 807230561 874485803 630851208 909423281 412815022 206756220 400434220 82152898 859352616 172148930 418467652 607065592 508616591 952090546 15098661 997846754 726517180 530811634 123493658 892369593 636555785 444739188 407643310 265701262 844789437 821379112 315727551 268573572 137486449 993361204 995062373 502849489 61951518 241832897 954340228 818298288 303302594 778106329 910114652 459335676 777689523 935922684 722626151 248321308 673178284 989601413 666732892 850439070 235883896 524832400 694754193 205715574 175094127 938250502 25939314 669716379 671440266 360062742 524194356 750476745 329319277 691840649 231106145 679090096 784626940 696864446 527435405 600942038 619443533 598012261 275375275 186623985 538532945 977178078 936712315 184522975 907734919 625027699 773367927 531264174 186404270 607925020 319763586 278761881 743115094 177229387 384865988 562684869 492424897 680670114 262348658 802900663 371450546 828937463 251780939 748002039 397937432 484665873 760624972 334998145 362631189 945766998 848275124 652572451 803628233 301138389 160979449 52357735 234881852 922822632 566298717 791381700 78968876 411150619 346600687 969465797 84573218 264431956 373988002 886934074 444723725 919540773 808555244 126177044 378909084 587359292 541455042 947147087 273240399 814514353 57142888 200160047 225143625 133228766 798877234 770431409 799629969 225285395 134317756 258692688 564142029 80288500 153786944 648057868 208185390 755313001 384746116 443214778 977414747 826215899 230622457 367167085 356850964 416195540 956483343 55106212 594821982 663328234 832684396 865502254 225209815 243272162 310390513 144323063 377685189 863600632 927392991 836265506 95038636 864326868 761740985 125294282 605909441 617956888 594980377 990329110 32998605 375539991 640613689 646562254 800279345 597800607 652338506 676925431 337565070 869019991 180693441 783713294 132745779 886336871 55883366 73419210 848061856 671832051 526432693 822797268 1198028 933914854 385987784 785136869 514624332 11792478 822945364 626206597 675451953 788371599 703563609 487930417 906311495 161087249 561562285 117305963 869508663 412489681 202338561 517086601 705687070 67619202 3695785 163588696 586778377 867538189 475568215 329238212 649686809 563950682 919393045 736293385 563236906 740907315 900974737 574242136 799170755 462259015 713412005 68817768 979064462 522478660 114142815 961623838 490751218 360763932 830627872 110671359 681513690 683889198 876250184 739480476 535737621 919751960 519366358 903599092 735292773 293835338 764003127 447341962 158300778 432544290 178632454 139815285 443347410 986082849 605105989 56213959 678569830 652577676 345295729 593996204 167962431 477875617 283780622 398807239 560706743 111098330 529486799 352059791 420436265 651727973 942557629 487060061 768770441 809798900 304014797 384358836 577517344 679033407 862451322 267468494 764178971 800263480 919449055 24007169 801180123 920392332 831249845 281656227 134723065 983526703 278837738 938085534 950268307 732734210 394992780 945995771 739784791 819113417 724382692 833807754 61029888 895104703 245294699 13869119 662871721 187700192 395254900 685668441 918173203 84606236 983059963 114096859 441988411 542017867 201173311 678256255 181177338 282865630 950637608 945896551 677682017 374310540 692066698 88502058 790830126 133690068 188033939 751293008 40065258 53335327 842404347 373116312 298025198 364127243 916407198 874501570 429272277 864933020 363573373 911105898 947261998 264781079 154934695 519439443 934866901 648753278 960519568 315925116 601626253 656578198 266944581 902214226 173891032 814298831 307777583 47001063 444135495 792935669 878755155 905185798 342752643 16291559 370356916 257242214 699315096 825264850 855701772 329286572 123789245 939719406 860940241 671291654 429740247 222999686 655288729 205174640 969483529 211381309 625271825 760674821 168656456 480853828 411146650 333781076 225720849 293449118 36023583 901779580 895755032 109705974 947762276 551849517 459368968 545276287 982818677 116160891 20847363 138521666 566217804 153883847