2000
847610491 847610491 385391555 385391555 854269194 340564592 992890121 835569205 53465608 532174430 173649004 173649004 422726250 422726250 893553645 893553645 745062028 958311505 644894343 66245371 64381230 402147688 488142 972721344 91716946 91716946 91716946 949542839 24282982 24282982 365753603 365753603 365753603 38226152 25025297 617257410 900466443 900466443 900466443 631174798 631174798 321360919 531525258 644407253 586669830 976916879 260456859 630280557 630280557 630280557 330829528 330829528 330829528 394791179 394791179 12288821 12288821 12288821 821716911 373653467 905547773 640598006 640598006 903481318 903481318 828331220 657742538 730452062 112108121 424281329 424281329 424281329 595253689 569416131 569416131 388673327 388673327 114114239 821525438 530781153 530781153 890734451 976552889 976552889 976552889 262082233 743990580 442218448 591028173 182632446 182632446 182632446 182632446 109192521 109192521 111654492 812114450 161512811 161512811 161512811 161512811 941553078 941553078 922031102 709626992 709626992 363817039 363817039 363817039 363817039 363817039 140516742 591400200 591400200 31198569 611122582 911075090 69760750 533399788 136520796 136520796 501164772 934119250 737538307 772636530 772636530 953479616 183857017 183857017 183857017 183857017 183857017 471000036 605837601 35404188 295875452 140471500 351383781 215544379 840632354 233642553 519255742 586931661 814504644 814504644 814504644 591612112 591612112 591612112 993541009 21070345 704404427 704404427 377861585 377861585 149238900 989194344 989194344 989194344 989194344 219698744 219698744 565769197 358804081 456191619 456191619 525043895 525043895 525043895 995986954 876573483 914625596 914625596 914625596 604733296 434601157 349177762 1910034 140650669 89595159 289747366 289747366 289747366 238271863 238271863 238271863 433373678 756554673 855925568 855925568 855925568 24288924 259382401 993297426 993297426 978970654 150045310 150045310 150045310 941222077 38405015 64714609 646007470 237085827 696411380 923435333 518973805 79609127 79609127 79609127 79609127 976913658 976913658 122239600 609334548 894709165 730997115 81662092 191732512 806222840 806222840 150283370 150283370 150283370 150283370 773955428 773955428 747256973 747256973 74631276 74631276 592317727 994202194 227494811 227494811 227494811 227494811 873972167 978771057 978771057 978771057 786154173 178448808 558280233 558280233 558280233 558280233 558280233 639708387 994668646 994668646 73174033 73174033 490521248 490521248 959220307 959220307 642555865 639356551 390639583 618801897 542006684 900896466 900896466 900896466 900896466 712846069 36371773 36371773 933553104 933553104 933553104 197764805 197764805 652774069 906654379 954417859 954417859 804929398 622462531 622462531 624732757 706273444 285992793 285992793 285992793 285992793 262533947 992913590 992913590 992913590 790119131 437984290 437984290 437984290 274253161 147030770 707080677 707080677 215453442 822322566 872542977 872542977 872542977 872542977 872542977 86680152 30750781 30750781 30750781 838299100 838299100 838299100 638744689 189484504 545433348 356353925 599969239 584345421 584345421 816670858 9322663 9322663 126141313 126141313 126141313 677928892 677928892 378293270 365992664 365992664 365992664 674747533 674747533 920285267 717750491 717750491 771415529 903237615 903237615 423506955 156694336 156694336 449452593 449452593 650296128 783899772 201373206 201373206 354252523 354252523 347049551 599526336 599526336 982442161 353552143 617160739 948220193 948220193 948220193 948220193 948220193 861631158 861631158 242044781 910669135 279133110 237079233 966300088 361491573 346031941 346031941 346031941 346031941 495374473 137827813 137827813 137827813 730997337 920163543 920163543 103303198 103303198 159332815 159332815 159332815 54990080 381439281 555136245 141001155 312529856 312529856 312529856 507769725 507769725 414620861 379414437 838377036 838377036 235585284 339798374 339798374 221382303 315889749 249793298 249793298 378879546 378879546 378879546 82143988 82143988 82143988 82143988 214292713 300238765 203199660 203199660 6967498 352889595 352889595 352889595 125021100 125021100 4192175 4192175 88354124 24487788 684365481 967288426 967288426 612889610 580661808 152558426 411686079 193045743 621328800 758627246 607856596 607856596 766759791 934560162 660488298 164852523 164852523 739502235 20761334 142185383 894849547 123228566 542232623 542232623 542232623 261816752 261816752 261816752 148075122 267569309 585833577 873143495 40428939 874868857 488125270 604928304 348944496 348944496 348944496 348944496 348944496 933032102 933032102 933032102 998470337 998470337 599190658 11550287 48037063 71470223 970555467 925729241 855784273 855784273 855784273 974390429 897008809 262519901 262519901 16008357 9867536 605085319 730933887 730933887 730933887 582164414 582164414 582164414 859148267 214423953 214423953 114956622 114956622 114956622 114956622 114956622 561975188 203657981 640273434 130464259 130464259 796510799 796881808 147395914 803768220 803768220 109082032 214555782 581304412 581304412 324606971 11249138 787915510 682042377 203863086 203863086 908260936 307444752 350526704 350526704 541971742 813001924 428112195 428112195 553689999 167545843 278583848 925937785 779971565 915546388 691446510 893857841 948883229 948883229 451204962 409518954 437750554 437750554 283260318 659400877 912802249 491017789 126013658 740300530 180907248 180907248 85277034 85277034 778794373 152990906 160802617 904923274 475380636 60423655 356295825 356295825 833374433 318786153 937119402 594270187 594270187 827466118 827466118 827466118 827466118 827466118 419076452 42520024 42520024 394378779 944102868 1394053 458787436 27257382 27257382 280016186 938905815 951347718 951347718 502654836 939228761 33603454 399525198 960272916 960272916 953873921 214613887 214613887 420373732 160611259 811716994 521319350 744290608 744290608 744290608 787018599 591348412 591348412 637294801 637294801 637294801 401468756 401468756 401468756 142594105 884047451 338600524 669578747 16032716 947096899 947096899 947096899 468766903 441223233 325125147 325125147 616496936 125927811 849427626 672868659 672868659 209366106 614964306 181771029 941441307 941441307 519945649 229740772 229740772 229740772 747180293 549469544 340239894 340239894 340239894 918620704 918620704 593684555 593684555 973510200 420692771 420692771 441068266 441068266 819938203 906737639 906737639 906737639 906737639 906737639 430143344 555093693 77025148 77025148 77025148 77025148 711305387 711305387 742473277 92603208 92603208 92603208 786472502 786472502 786472502 446594746 446594746 785110451 659336988 659336988 323039778 802374830 802374830 361831266 141021594 141021594 34190741 194977266 562350261 562350261 562350261 562350261 554652621 134254641 134254641 134254641 261948191 136139775 136139775 136139775 136139775 696410275 166727299 467353287 467353287 467353287 393803762 513549660 468235328 468235328 543109470 543109470 767899771 207696567 561720948 625739101 625739101 409976603 409976603 409976603 759150730 921050189 43769701 43769701 309297412 507039452 177392220 177392220 177392220 177392220 70962385 848801096 898782461 898782461 898782461 898782461 898782461 621745004 532274639 532274639 532274639 151161986 151161986 524920448 934122338 821787193 481291665 481291665 481291665 367642187 226053167 326990577 41128516 41128516 416516929 126756012 126756012 208165873 206807983 107935393 222800693 222800693 523287098 523287098 523287098 10532017 566149606 566149606 566149606 566149606 168052215 168052215 168052215 115478978 112691652 408151897 339764818 873771305 873771305 546914426 115771609 337211898 337211898 598590141 598590141 135044266 968038747 968038747 254310455 254310455 451741218 451741218 376618363 665231668 961780116 385155480 785005608 115020046 835892923 835892923 619031536 528463694 528463694 528463694 996266412 312986373 312986373 933100942 721507834 985346067 935433982 390265888 390265888 702019219 258480814 675891022 675891022 675891022 675891022 675891022 391634221 180955614 180955614 180955614 422095876 422095876 347858379 624467683 384757749 384757749 384757749 444843426 444843426 940969307 940969307 940969307 940969307 208290233 937886974 455232439 455232439 455232439 489824154 631223551 631223551 631223551 727446606 201111069 201111069 201111069 601741683 601741683 601741683 601741683 727559828 461872439 461872439 855360278 787761548 787761548 787761548 549067022 549067022 101228092 222765047 732974106 313815845 500100286 182361255 182361255 452396499 722654084 722654084 233522237 495944911 670107813 793945383 887880078 887880078 733599641 733599641 711922295 68828887 50642382 143405074 430302602 959298559 959298559 50468219 50468219 994454843 994454843 994454843 489344347 358177513 838580797 704447662 164227424 164227424 998008870 680570458 405446078 208524982 64919545 64919545 215461945 215461945 479945467 70485335 198898338 516702186 516702186 516702186 563652984 259854077 259854077 402196197 402196197 988560778 640393714 640393714 640393714 640393714 640393714 856634232 202096410 202096410 993373753 490022829 83741687 774302556 774302556 320208398 320208398 707565127 707565127 230757627 162620898 162620898 162620898 162620898 65461416 439593253 439593253 439593253 325944816 446805125 446805125 400643326 400643326 400643326 936824704 658195043 377030238 175836189 175836189 175836189 554006716 863330650 821400396 821400396 821400396 441420891 441420891 689297407 87858475 87858475 87858475 605982213 354256673 829448480 89765484 272669783 223429393 223429393 928270955 928270955 237262015 248991375 462897223 831308129 504747915 446861482 446861482 446861482 204274948 204274948 204274948 140649769 913068472 913068472 297428430 297428430 545650357 271132065 215354248 215354248 215354248 215354248 763398686 464823649 464823649 389343614 389343614 506789454 974413707 974413707 974413707 974413707 984620371 151806023 151806023 448331427 448331427 289129768 196986049 170840572 170840572 894154561 894154561 486693722 453227702 124200464 124200464 124200464 124200464 124200464 152933492 289591297 289591297 906278206 906278206 967579564 548894538 548894538 169531075 83527731 679056421 173159331 973422956 431571077 99468964 500487216 500487216 500487216 500487216 926597584 997126818 573342947 573342947 573342947 581616661 518353054 740571072 106166779 179279703 737979179 315565789 315565789 315565789 315565789 315565789 620528076 357160960 861174086 495648344 694831770 489461610 489461610 786389327 786389327 682730490 682730490 682730490 682730490 682730490 244465515 244465515 244465515 926973104 926973104 274274404 69999838 539513829 373027988 896864325 994356782 854412691 240182700 240182700 240182700 859486104 953202651 536655861 442201904 442201904 16102739 60940298 115139188 912198780 912198780 775652523 969758984 969758984 969758984 969758984 969758984 587686049 751200697 15641234 316917316 353954025 353954025 836963488 836963488 372074703 372074703 399916995 399916995 399916995 399916995 399916995 887216975 744315179 967464155 55127065 719333703 901216693 950975191 840192377 840192377 874974322 831984023 831984023 712989886 90805957 90805957 90805957 920808997 920808997 30375385 279928338 279928338 279928338 279928338 653873489 653873489 630608343 822866635 566224235 566224235 566224235 566224235 566224235 373651450 373651450 156693954 326027335 326027335 326027335 924561746 601499098 14371024 272477736 242477796 720250417 668246534 403045723 655618757 824633746 900909329 847933926 207894506 300417426 348375725 348375725 304026249 304026249 485143930 775687748 775687748 976516062 353188941 841373384 312467617 312467617 968314641 861173370 861173370 74640323 702676901 396341374 170827930 289776640 442979414 313502637 311857119 311857119 357741316 535337442 535337442 753488087 753488087 440037282 440037282 808657255 563689279 563689279 563689279 991104806 940404987 940404987 133065585 433188528 433188528 755509587 712741361 814948831 782105448 397414201 354313415 354313415 354313415 789025329 872217571 289409608 782082177 435997479 538988158 750216122 750216122 750216122 750216122 151678747 398165781 241921532 185582754 185582754 671492975 153901919 587748436 437491554 429820474 172416562 335395390 494234708 35726156 35726156 490171082 276002134 276002134 154769236 748842417 558568450 558568450 558568450 924589340 984194505 18975711 18975711 18975711 364180212 364180212 41290970 41290970 237245945 740850859 740850859 740850859 16655027 872619181 902183612 105026097 105026097 312555304 494495957 933733660 546420582 191005533 767910200 768183598 768183598 702949550 560739480 869667713 339753110 133273095 177982996 864505842 864505842 131880040 131880040 131880040 300993994 779268426 779268426 901931886 914425825 162046778 162046778 148618390 666153487 180418147 180418147 398708670 398708670 398708670 391172736 391172736 391172736 391172736 104169547 104169547 394458759 646056732 646056732 646056732 639507743 639507743 343442506 405085641 405085641 950686323 745576687 247833433 792781499 872129890 582230319 764858466 507781004 538782159 952767296 952767296 830322198 537272055 775060282 368876064 473859376 349804239 10161349 665202863 665202863 665202863 665202863 596419422 596419422 686766168 714349727 714349727 657258026 657258026 912774538 912774538 880706609 880706609 780495750 729706953 56298768 950749988 993637742 132355216 839727303 498685717 293137459 151962556 369904574 129348674 129348674 115567524 540926867 540926867 540926867 540926867 535516627 535516627 535516627 262457687 262457687 262457687 279467500 676362733 868624067 753532344 675481367 856812533 856812533 764350287 390556985 139762590 139762590 239091627 239091627 239091627 909580916 866307571 866307571 597195399 597195399 258194473 342660947 17725504 610050415 610050415 567881283 999358822 999358822 941147812 889979841 889979841 819851656 117891020 267325994 498552213 628318704 628318704 615070370 620293745 706465629 302873792 394619237 394619237 954858985 954858985 954858985 954858985 448251659 754075051 754075051 759603428 920981779 606619163 425653654 425653654 732961590 732961590 980654767 412169387 296833868 905217116 637191328 168483207 168483207 333960505 333960505 333960505 333960505 660520479 755564778 755564778 755564778 529115658 737304765 732617545 732617545 662181590 372740396 724923030 724923030 839053664 59742511 856584297 954994327 165713917 165713917 631265598 970934393 999240653 51739896 51739896 440943701 440943701 319376911 319376911 571820934 267272958 862506786 964050843 53951428 561366004 731237241 731237241 1880192 1880192 163848645 924055250 924055250 242507574 242507574 463010676 326685056 820931934 850923382 850923382 320367859 320367859 320367859 71151005 954341463 823198183 138192 689652131 1190557 613297366 199323341 199323341 604107346 964797524 953445513 448427980 407719011 407719011 407719011 121163079 575541423 575541423 928292335 564592167 564592167 550987651 550987651 646049980 575598656 820264199 382663940 382663940 755533139 214954288 566441632 566441632 566441632 566441632 231379474 231379474 709399161 709399161 741880670 741880670 741880670 164753989 724364749 543817515 543817515 201708064 921329563 691219750 76840572 76840572 213900807 178790409 322462671 388503501 392152289 431556908 574875058 732767817 732767817 178474309 372558439 101211865 677820297 95502629 95502629 95502629 313477676 999911536 999911536 403401616 224546481 224546481 26736351 931842978 931842978 738848460 738848460 738848460 738848460 738848460 698083390 973749415 863504282 863504282 863504282 695160983 607312751 607312751 607312751 607312751 782870644 782870644 782870644 467597986 196690677 196690677 164589623 952118406 530312914 276647059 761742620 761742620 761742620 761742620 344841913 344841913 957779630 957779630 451026242 280581791 825605995 825605995 3479367 343079887 343079887 343079887 451690991 451690991 987043732 623532398 509988788 75892766 179887570 309767498 428168566 428168566 769842086 309054251 850521651 27523559 773490913 618582772 618582772 806531069 770459420 770459420 552875350 865962351 785066922 128978315 843782351 980236183 980236183 980236183 103756705 269751347 269751347 229224987 357489126 357489126 328614078 328614078 777636039 748390515 748390515 355863248 355863248 355863248 536897783 391483763 611641152 927321862 939817115 939817115 939817115 939817115 117863570 117863570 117863570 117863570 294922217 363059806 992441426 438214716 523937145 761246857 141628133 762326736 762326736 570985206 570985206 407377938 407377938 662360144 64533336 64533336 117731079 963225285 963225285 963225285 919991321 408243569 892428105 892428105 305871925 65077532 175526810 923475383 630217571 985357169 682440440 629965676 629965676 965838401 965838401 614849632 765701733 765701733 765701733 765701733 838800289 838800289 638712607 377909643 979380845 979380845 771064886 958866536 581633028 581633028 581633028 675953834 588464735 588464735 61627890 280888473 280888473 280888473 928003600 382148409 199010433 199010433 199010433 41748269 41748269 41748269 491117993 141281271 141281271 249690375 929206043 97198522 178408012 483532137 448649667 140942313 140942313 852013543 363643378 650927906 513872468 332140573 24568199 24568199 24568199 931598425 949945954 152994473 409710201 640329328 640329328 295075002 295075002 937551356 937551356 945308944 438969268 203699289 790160682 990419415 333726520 333726520 333726520 333726520 132818132 132818132 159623346 159623346 885922093 457976111 379193569 374092388 374092388 366487792 59617114 59617114 833204268 137860674 842962822 842962822 288574296 195614907 330190272 330190272 330190272 330190272 507063580 99407987 931306776 931306776 931306776 583918755 125415021 125415021 618630460 618630460 618630460 986636278 993878783 156269750 626968146 626968146 626968146 586397147 248485909 248485909 491758033 108061369 881016722 36197803 242045348 242021863 242021863 702437803 546153929 811562023 173700308 197512512 268112896 582895143 582895143 235308986 622287072 622287072 536309308 701103409 624043779 803761455 817851233 651018099 651018099 825256110 131463482 574567758 239898845 787516184 787516184 583744698 568537816 383288383 731211935 840730084 507829972 507829972 507829972 560513348 25961601 17085396 17085396 905760320 180782060 18603306 173478161 173478161 819156595 819156595 161445166 92813494 833820268 833820268 833820268 195695682 501188690 578641241 578641241 418333553 804792551 590420471 446084152 996089931 996089931 838667631 988176091 44299605 123429303 123429303 34679248 641248680 510128116 486442141 486442141 740334404 740334404 814313794 443729684 592032992 901294007 688012710 688012710 844934875 10068731 392184676 392184676 212046743 212046743 212046743 246127 890938721 124415627 124415627 384202960 384202960 384202960 930728023 619328241 656524307 656524307 656524307 631283053 782263013 782263013 782263013 908136437 908136437 908136437 226361324 226361324 226361324 635067984 635067984 635067984 635067984 63108682 677715872 49598824 49598824 286312261 286312261 398087767 570375774 477934330 477934330 474742409 561865228 561865228 252757414 252757414 473654403 41171351 953527479 953527479 877330289 401552190 353798767 88450357 88450357 88450357 765820133 109120170 247574342 212224487 82039458 999593509 999593509 381306410 552680007 552680007 552680007 335063081 662225295 732678836 608569498 256671284 842537469 842537469 842537469 842537469 506052829 486309246 727399782 89441251 191576309 530723124 492234173 930405969 191637443 191637443 191637443 191637443 692225741 835164814 991646739 840656502 675637074 484390975 31507830 67715320 612435576 990882009 990882009 882810301 882810301 601123835 59453995 59453995 802538993