2000
841289343 492724210 865415578 499573891 443083411 438371165 400747914 588180369 164248164 124635317 435026352 322271938 813707839 125561556 49604682 220531278 454836437 121180346 252463408 37011284 81506636 165028143 457704632 603385370 432803181 940930619 529602281 408148343 329684416 908172544 268331666 605236319 37432334 796301812 484472318 473254270 416185454 878939765 265644108 662996451 205767717 349877143 73278387 908640277 363963334 135038130 982210329 76488463 306518356 468351211 636515417 167692308 823134571 845841806 996775671 979252168 999201030 379713645 711044424 402955247 618524718 320832635 762992548 735675549 598693234 858582442 572034002 354633042 503766443 66009686 590536398 760967356 67504452 1871783 97944297 310986667 11899616 118115980 863182805 590842096 560697433 660881178 293440306 24066557 216821893 755200895 408109625 974679886 155413663 183403080 717723449 502577808 603869411 758024055 478704155 138821921 540589809 567503220 178995914 854234049 799399074 372662839 632481392 223308275 458970670 79988834 69484215 110853882 623696902 148266448 912928233 944384414 151699828 598527383 655328001 441894581 599370193 256903858 51314114 635526858 973370547 104935916 387188668 292954791 510302625 159027577 44826758 100664928 406258173 554833638 430102062 47662599 596976445 600380859 726620610 881169603 758496707 227402046 556078897 738002578 849680251 835233518 477549239 705335681 188028902 970991248 311306009 573544269 877157365 743153737 983382881 437519467 244363866 781164083 102906660 42464662 196058957 2451734 507228127 716758810 692220716 198874763 404932021 325062556 117484932 7883591 148130471 200838418 911342040 663883094 317476414 13439731 238051606 690625020 744249661 763709048 4943180 620265133 764102814 580841421 623016455 820876722 755618678 456038849 901990511 661112719 76556493 28707627 378809675 357888782 601406885 772974419 806863249 615909285 196378047 485903908 28186246 649508609 128055548 922921758 442902276 152181341 413033880 333025750 960708941 720083254 556574216 962716958 927156115 456581984 170305608 916187200 603880809 237520329 825239398 774991343 492444844 689533909 341783077 336062259 699680126 571103016 921660908 900537092 709707673 439874809 583212528 211050409 464974862 100361343 380474771 285594953 304517011 933926510 656696252 776367945 633207088 152836514 107814166 646608783 878335790 89600884 835596089 880937630 73307473 498163340 969595865 224015416 541875383 541713186 391312592 687874898 354512565 662481630 312967884 938761690 12068342 445294089 803438095 450082562 800797037 271012763 619731133 507306158 439080828 34774644 74305734 379843019 264862903 792361419 875441562 957921877 922635197 750532610 327009706 412480099 648344910 718195088 930718894 804840522 853065962 847621012 930748952 648549167 532329703 66537180 451326697 227181356 303548982 480324120 813088028 376404190 728921829 375500058 953448513 515985411 9426877 743515204 288144128 960057681 424399689 851788199 287230919 32515812 277656106 129990586 141594176 334187974 725868877 819344439 214663146 386951113 404717218 502316979 867985294 781263168 415043852 329121041 94129023 227685106 595575161 406562593 213184156 559935136 202052963 754761206 252182516 256951319 545727084 603551913 174890457 679732763 708696186 303116561 235905380 91842334 683363543 740218208 224103916 264946430 115774977 227844259 658298477 640740106 734084258 807621107 705051510 442048526 312312634 397053155 715156744 903522828 670917862 936795767 391149885 15460216 277887510 606169777 650797102 326033000 939928500 192793577 460800963 551275357 445420723 406090020 400449738 554947375 886647567 659771106 160988746 176060800 349361329 781390908 377370579 982389539 714503195 869769387 587252891 625660407 867647789 460532717 881421862 69433309 324997085 591925223 898575967 524701423 432038876 726376964 387398861 342008431 173659040 378664957 884679623 74321570 930487407 774719162 179719152 334690583 756125511 349010784 863684654 330469831 110584442 7742371 257370305 625834502 566736059 528140032 168670388 736032078 545987655 290131835 34552463 481722387 568113209 796974134 816858747 445586947 271870754 429355118 286597489 163286092 707525733 521108823 149498346 281412086 310221414 560758700 704332756 584571601 842444055 995858343 503323521 512977642 187353675 583073239 542113452 779327419 448227039 728253851 671985646 645141924 224233452 577425675 631791413 690782134 615375354 342072070 117414796 620802269 678663831 606021924 822345948 802930420 407022635 580636478 734880845 293421950 809520445 123491280 244368430 831317645 33214088 275628911 112482301 279239267 185006703 334601802 469696726 911445116 867335181 997257054 808319273 516485622 712621958 261405359 800509253 713794983 754222556 646737943 515504743 120658365 106755305 844415429 129132738 389225518 271914312 613659494 235053388 119721172 139683901 591296049 674367127 75400881 953920147 420236297 519782520 319977358 615453676 770481088 480390526 404989843 476100551 245226878 467154166 825475558 768865772 700844987 491463539 267871122 380003294 472026135 713233759 599580718 841501029 145736905 772053965 173740589 683131382 606986546 561234934 216633527 496520335 935413461 494584203 440812512 670669915 68213124 202006250 333101131 490281905 764589410 945272326 55372193 61873319 514917387 582713691 397074802 932465367 479047653 851670095 477721541 131269407 459838665 601791367 546460953 718607378 957663156 958522410 74520441 599593946 659893596 640922824 536744285 579843058 98662487 568359149 326298868 372996297 267776671 859793927 743582150 112016485 633817073 302266742 593558512 719105531 614122879 947895938 807092210 551854211 398795604 291189426 585031290 853042902 945036548 496653318 265331789 474701183 524132832 967481429 308298793 975804492 235204725 445666366 651424478 40777683 956059608 738927376 627457045 775467465 419368603 544205370 910775898 516526265 405703641 469896487 888568962 763311256 683526657 765315926 22343016 591351925 181286647 32199772 737633043 524203134 494878099 838159069 595820821 590215997 437299622 965103309 479373140 380032687 967064744 265560405 570915286 39837413 564877838 277203607 848500818 219079199 597829828 735314414 363586362 427266501 124423845 684920288 1342815 811823175 429877136 428034672 633875267 748487538 921390412 655951838 191244562 434980765 867446333 268171587 545442059 207020855 340663040 611600568 720061184 872146354 87442325 11837175 131725038 631546391 192450061 167734914 848642804 226459770 779955483 973413716 212816395 564083337 231514775 736116000 156208726 214668995 420947491 580214204 667709728 543990662 437516355 594479817 288671375 936016060 571119590 911641047 515886531 340168471 483771151 630076640 716012244 715116144 642992669 852412749 367620176 22610082 567094526 441783761 990602563 102943697 220890204 978237235 978947633 100014232 847792414 24299841 84250065 643126054 577593336 457303765 101247847 356769344 368577004 668020545 373753682 928393229 373111364 179570189 752804749 755890958 98100206 867672794 705858678 512555260 642556713 805103606 446996598 71118491 459460135 299284812 44332807 364467215 827356030 582651284 266793258 576175230 398924315 384746941 517706014 610423029 901961986 655611063 512523933 742162877 156342620 943891370 831496742 809400937 689873796 141970718 809948135 32309098 823389080 472764027 547807080 161355204 328487591 820753804 502412684 988151481 359902386 55152463 877904521 784421958 596453530 777707136 161019825 608201907 97973066 47258826 828418481 454793021 887096735 881335756 668408422 501051659 319364698 449041170 533766044 31076469 285571615 714287614 563091678 100825056 65714128 203100140 551948363 189020199 63135992 867958985 48446878 923888055 257283694 702829509 170195224 914529954 557081243 19868354 867852408 965451342 131672960 368177371 834097964 195749417 271233817 231603725 633475104 331756778 644443265 300584581 39030431 80559385 722516153 692137603 733084187 743224480 555474181 562693073 798683751 295763053 781612915 858365905 195725934 832918979 523780137 880185558 231625245 888510210 264188856 785321625 165913277 794314235 951612619 321703104 571113170 440130155 766918676 273209050 145891901 694982343 981026608 684602613 182070064 303139907 55373139 607569478 111207704 787691543 868563754 765285502 872473295 121484795 949842932 202810386 51334094 88815494 265147475 35183349 104508695 855184050 429188498 353423802 941987864 227451318 874708409 830579310 217708527 342420144 419905153 252626490 456109289 13857723 789606508 548859985 681141020 139991554 89054855 25972663 128327794 441280548 390435657 257185069 364192597 663439711 530893842 672833909 913092567 871187380 353821071 426361380 23364500 745060835 785324878 222443929 22254809 894544698 218784270 146508155 218050321 736403448 713519841 953259031 561069487 506228963 402728759 624669671 620722754 648560173 892791874 114394645 679818863 433453250 129102266 796853852 684021326 720379150 988478075 639697623 605909806 566336761 921283059 53730560 32562259 603637987 522441963 629136271 940858812 250068761 782406239 812208247 93207901 397356434 943526275 845749825 412069645 548251365 982933126 957016403 885716055 357148419 500706822 199520758 522879548 621184531 828836251 978053358 129235503 551021380 300434978 487114335 100264430 853850523 334441798 181847264 58655318 768994498 423541556 793718628 415629203 46773701 20958731 646152147 545651251 40059848 303016653 36597306 663478232 725672940 762542659 197386700 144202376 649449038 984226650 739666027 949680390 124753857 730768552 722581217 380643821 974819229 761782854 518560155 29813513 106108464 496290101 522066504 216161119 908262548 150277465 690032244 387537840 904631448 459346941 815294662 944842273 501286109 215177370 867656217 665734763 293348802 910820525 77439094 597901548 709414436 963431755 83850301 989758915 534564734 460617964 542336990 446440279 377344067 338956840 878314776 960208516 851811640 959730305 905024680 432571077 414283212 149360367 693988308 552475799 223761509 741436354 535673730 649684714 651988597 506421 989743236 577563549 657576687 970448211 680157823 890931912 632825093 844561837 522644467 134689042 905627109 388388106 697652748 224323563 485940236 947580120 142172427 296565792 528052652 562827590 548822658 798124181 133349790 351559025 136192676 537570283 14820268 62538007 537507009 678205076 819280084 829399840 567765334 435171892 258550641 566933314 217564460 424964310 864620385 512039777 62073034 217890557 51251438 473549146 720007568 775903371 378032454 120375949 620308605 673507622 498386056 467315260 872720685 959954128 397871008 822884305 597661387 272117571 876993188 635141415 573173263 219009463 755101164 963513966 520838677 342681453 188341075 707842272 343820500 135962409 902561677 497888590 785515174 23126558 925678535 410708418 834997339 299962904 837911953 169450692 959839369 953185506 863280152 851290316 259179166 455758101 219137850 81073688 770378897 923544906 363753142 194178965 498280408 881954921 202937198 845087901 734175363 868770217 469618748 779200362 525419996 260342021 315573479 143690957 648648383 22215825 111714377 850750703 795352272 451033136 242292764 200528833 690910064 870124089 886182720 742333265 558047510 706378415 613491900 973257040 64096084 909692328 954393198 645856489 753139741 307740531 684525734 842413005 890190125 115782129 255258186 131890795 870446489 882675659 978274841 702450885 69442927 373624154 365910722 347332661 244324281 627422233 391324943 170018776 106928865 836405113 335077092 232325641 266176924 937724364 27453336 958176141 138855527 795906387 504876834 404342883 163210943 747968635 756794646 493509622 522802454 30872539 671154630 423470097 956697705 994589867 258616382 745882502 612289645 29707199 312406839 570071464 482805299 41520914 320337807 591023918 382435645 340719690 904557059 323604726 629764522 419158448 913266666 284484784 14850119 454808805 118079069 789775780 645000071 865988002 26710064 797596295 460803125 408985096 532400729 69039039 782374252 275493965 385449304 586116694 36271301 183163207 339948739 203963824 326947155 471978976 415493842 590719742 848828183 620761508 749047166 580011301 286391191 385537909 588335375 287518941 529383902 253424879 424153987 878492996 323211200 804131837 200056233 156208868 715306315 844139235 813580635 952905644 552524109 321890255 762319063 132759283 446917628 740246582 539624306 152741336 765558885 885841355 704882026 106564485 652698512 106227527 765125071 661654636 585903760 977732137 271939363 230389087 155208063 947206560 967085503 747904414 218573958 788214662 831635087 230315736 394855260 368650364 496849834 279593805 699128208 552763126 220561681 452850387 366152699 507678134 720979912 958590626 704053827 428288006 388952221 257200943 518252006 671704496 276945381 583141020 684738551 404300702 982124327 106944235 602265364 377571113 608375402 922857090 577460123 139504692 680716327 600665955 407306227 7185050 716218170 362676214 657412538 226137387 527132320 606547344 281596692 254440426 962529960 599647031 274857717 756981201 615677875 849851947 824244371 847545899 414780606 580528043 831464182 604569830 539226282 139519701 708581325 563929842 637637187 800654434 878725166 925741463 671703243 33104247 639789010 85298358 72816646 428044097 801072285 80734519 972879223 827901073 383427491 815266398 169403056 449806408 95314266 192518400 248907593 442969182 118572740 642493589 952050964 938953972 560918993 677746249 903273514 798834801 794913901 69546433 796769540 976754591 624917361 157700941 781288089 634084851 561110480 130539960 633894589 485253318 351033428 769674065 970314820 51425800 355073727 756928150 388040667 161796338 806719010 279483104 931449355 752940502 25855324 717406597 738905003 96787907 97993852 556035412 813833391 476040326 26147784 553982663 65366841 437961737 388041572 147872577 434018400 314567770 205633307 61015215 804161888 86377795 125272292 27106168 21930940 380927259 439883407 299297398 461738152 416057416 840768868 109833352 82675976 199229522 891318558 997730803 402254321 695316007 437462473 620510627 901603233 167383313 820970496 235237812 141789830 623563406 388243713 172651217 749770385 104225156 830695049 302308623 914937826 547692242 580974572 64882840 158473894 830816883 784429641 496019464 239095739 470105835 931114755 349581736 132139026 460206706 501610676 177771005 611492694 715165866 854761793 560226635 836933190 238889361 517924640 500633045 526922389 36907448 508729980 46856171 377984382 985563009 10988081 780759361 496992704 40836528 485338763 149563728 198063504 415246824 680219834 502879061 93280304 542811153 48246228 828824924 69514294 649952269 98152923 696336173 135583336 527162590 256938961 943302978 353686546 967832439 282625308 427587030 96108222 546451675 554488417 922616329 93355538 451164807 159680794 848402218 856803374 625329457 375080115 22843280 276617789 972508204 133000963 548657046 752962370 889404376 405296498 187738135 387621971 123554141 382289113 972514686 595576384 865580274 240442604 498090941 462977401 894148157 140428462 402911543 99720530 714553729 57135055 580579084 42679377 293928719 418177572 875426036 353707484 924486692 662848432 588570364 38341720 488026135 941313211 439976326 179499155 79128112 525586280 255709262 140905254 429604642 691208962 669500818 730765528 474703765 857682651 108552895 872845212 421094390 693562395 892384211 744799933 443997990 787934020 652251586 488422327 888648173 958767895 12440545 646511167 47051363 670925343 643235238 198513998 24926985 916181529 426274681 971343718 576968999 547455525 749191298 503453828 949250984 754258950 879732642 264133667 793540368 647910494 614341403 7007587 743743054 518624841 323541448 799846238 107517030 52216005 643498691 87811126 299903479 890162588 17059815 548786273 300265444 876702589 474931093 738120604 884606986 280968717 637794652 743340274 419869119 11508083 104195842 645030792 101308497 308178676 908564482 426558669 646404428 559519724 941786026 271534935 33010795 596344070 337137390 716150741 288189563 834524538 900532388 260076443 48852558 458555623 914554735 522798318 436549501 141373046 186113337 213521015 828242621 643269428 82573437 416991659 489626676 132084154 484730567 270727924 83013097 873028544 580792883 890848539 181312698 386100984 47705224 689739666 915844092 504383959 821163125 238701874 867839559 901910332 353426805 611622389 418943469 989932560 658805023 122207319 443992643 818052595 511115739 296388168 298147957 975471883 630136036 758475206 10023237 396212482 818672489 644338885 144244869 513718075 742253050 466904267 746701804 101769130 578146587 419139125 671747033 927124202 976532383 328029098 364794378 723982316 862592335 886179300 374179769 768593322 164339125 438431344 735302381 764711294 388980627 909926354 203530085 347660896 596104953 468148097 710593589 730521654 671306682 355592131 756765091 573635653 791405032 462694976 641919187 120509798 121565009 509485530 230693768 343253982 928628881 301593210 584585460 66272804 267410551 498087743 694106709 672586336 19402043 604049633 820857763 325782443 825363729 665790422 433961500 979014952 561366337 854520500 882120038 388584454 25994839 373455933 846840850 742990128 613236502 888571981 945031472 24861761 541523125 284091094 510544577 940400132 264754220 539755567 798564254 326459762 403235777 44525454 992334912 858709220 643888045 23398983 858450648 473925145 517692778 358698290 264067824 868744700 732398916 532046456 272005415 954644759 568886330 514235059 266215945 592978625 864157330 41102565 926217967 363796266 973477715 182920989 939485289 947415293 253085493 269042784 721486424 985608941 43213035 678950651 439595098 170925923 971929944 178639346 153053903 704234487 972879933 716974733 219973417 107815242 629489995 529991658 863138888 247753781 715772681 950680546 819201373 180602772 440079608 945947499 754118427 739497625 328247419 961103340 505576190 566493658 424794304 452385971 700849197 756480296 17030694 262957778 282119264 35923733 387407677 838249112 787352273 27109982 658611401 479013445 373309434 330283950 709012858 484065260 430976352 766303785 401867583 60537913 893966993 793396200 109858259 690873993 426121824 37700964 773670523 836114846 277129216 435756647 224488777 602935489 473948145 161218807 441522599 969434281 752731114 43519847 657573610 982163028 779246319 580040879 861737101 425409057 395087821 551312719 782345996 358016469 21156132 404477008 871873223 905171209 452620906 827219968 901967544 651964376 248458210 579754791 593040331 62512341 445739706 57798867 713934097 175958921 233957002 984512786 969460801 849903325 878593502 812207128 994472078 430925971 432815965 285457530 896304367 113029294 279244475 59047093 220622088 650707856 899271473 542852479 514513742 595718850 687024544 25981244 563384651 727837650 858662966 856210687 791537060 237264996 310691293 489191467 273222603 629714779 800748419 468013972 491679981 814570311 541474554 464018292 679482954 484517090 673759686 806433919 453412925 572983931 151415825 53598037 97109100 149809976 691806566 785655130 852016277 348966372 597480255 365090090 974090637 788613485 697178587 985144701 466724149 985296996 857084 401831496 483771644 701075414 56834134 254181708 312796491 968017153 646487857 665110985 103953509 269278737 121458139 387685821 642883134 271895224 999106826 72219012 976120810 951942008 429996202 746589013 334009464 24506050 907253504 38579082 644357505 118732094 786831247 567768679 858287758 805568043 628005159 563829929 84348807 545587643 223014392 136646165 251157665 370721300 579503260 268813013 571601901 231783119 974714834 954437173 271722576 693142216 983952229 701423651 669361898 936879194 342238122 760946997 273034487 267528065 552287647 635300177 420049393 216833734 444218657 777557823 131727979