2086
802254881 738958845 266739127 879503682 167136414 498878039 655292035 463694890 460136373 536558136 846490571 217221633 532868648 299950042 725526650 228606325 381104486 415743904 655474140 84239772 401779298 332386668 389140005 93690233 856771551 237281385 816030632 267453571 408883261 793728399 429276465 845652990 46485279 856769885 352759537 469635593 311176568 251533909 734015445 870724657 386362188 458050114 276476401 248639712 817745661 615370090 493122080 313357756 703034538 775659488 85269168 457947522 357928760 713524339 411886968 622398416 614296171 661708065 622835834 479782083 620527508 270667406 305780818 391979129 358070148 466010819 903464871 408603750 995581946 365082793 100336619 497150582 313670658 715566157 631555279 869165586 89052407 335216304 268708804 488294868 467579109 55146428 104379214 255606037 299314865 440066623 814037649 26822107 67766921 413349845 409923367 411959085 681993560 731161283 486267206 620392651 811693041 950026125 466359041 102181188 301569410 965862536 944008541 488073988 911767188 540615652 566522975 769264464 512651380 700556376 294638705 958793563 388901392 634586140 562221681 2216698 560457868 966203591 671266086 582723583 263952622 362820467 361421347 374348071 258512170 531059610 602667443 112773310 194912608 285021940 383700699 623240694 769837642 569736236 270286743 819726490 302259498 247730073 723880267 104217637 152121732 683278019 908366124 363027380 931933664 786046873 445473916 706966460 144648039 718775233 996829344 742067706 895713769 478117996 587297969 215591821 922546164 596442327 626286891 538194330 207915975 357066359 35044742 152547625 163398212 450033864 933168003 845488314 686186715 71374709 377889971 492244162 448089578 115730235 413330017 794139000 783441177 941567365 221169760 58982389 736205967 72156921 279497714 114022113 172632103 656828582 544730252 284878478 258900592 148431904 912090527 810196902 844731496 849191041 780935952 143596931 380216664 539746082 359538024 255806519 162107287 706466005 312695890 589918276 340906496 203578401 516321855 110441701 60854995 696745718 841749377 993821957 998857017 881404540 220598551 571648260 253445638 52564219 175399577 37843335 787721905 487188284 489069728 328567942 670298999 517390815 320863540 722467811 640857157 484528283 257903593 113013558 507265288 759874411 197992178 824582210 704657950 685722063 788939164 17725047 968574399 445288710 877860026 561972344 494439249 238797060 681026164 331373648 752305008 791791324 439229161 81323786 945508212 405559181 85251470 941277529 69904067 83734866 696614173 183148206 873355563 753592518 60085735 579777941 228838273 420698918 559410786 788595744 644659584 208634054 109665824 372978480 75642092 713777399 989439822 517744856 328864077 600988275 562340267 570326932 632119141 396876557 643706899 668535317 275163538 428724562 535328241 464682724 263410559 14323968 122790433 698162769 382196577 506501198 482529063 269374271 422028203 173444839 775140447 667669856 899487414 725425574 217495552 813022569 293013475 240006347 315344545 929502509 847447267 213521412 702544267 34153347 894902176 27619686 603810157 606320304 762406270 329399428 712873054 523963960 25816823 290887564 127429823 137317006 678407609 61433052 260237134 221589567 778528064 649524327 619140295 450508796 49175250 184272754 67596687 286556370 96812224 543109432 644658152 845822938 345465008 578768659 422696415 696836217 524401028 250954635 419618624 62028941 97090147 930093744 360199306 152053681 282607316 97277185 941102930 648815627 747176213 350332378 394558209 317688324 531579974 642185617 994693388 402046968 825560046 371489424 265157989 250071382 948795398 494338077 833327096 26509330 125851303 935100292 50911710 908079963 530270151 971853986 460315287 481415166 581774642 107183561 846942880 575231100 243206517 247308026 600912424 290539338 804952667 668190608 825278245 251005951 758590299 910513197 263972815 264810377 542763196 111139249 473760487 393820423 712356477 165004910 678958718 223689626 414648130 295562319 63595305 870843697 640620866 789599329 729773219 859947328 50038471 417861663 836854435 393996337 132820727 689060546 147623561 413356311 817724851 813546719 87644685 694649625 112470414 287677424 910780563 280182964 533902387 120409618 918242969 419997513 61345238 694798853 448616647 864871481 133823806 887252750 279756139 731229272 687089721 402309902 239002672 400803482 454692494 812149512 281535903 329151913 416581929 158437744 701977038 841653006 358363244 733008245 666604780 430183929 999462795 779076819 353534958 949691630 927493776 203043011 764638239 97879544 754003713 323657078 845651874 914493295 824371367 58824466 441267174 62626996 722518815 909464301 106615674 211971267 588103730 860123086 419988796 850289175 940793567 804474374 150504723 893311861 307780373 303218065 580053597 12743618 561481197 217663551 110381910 523780061 134392620 51571453 292209776 232050722 542591681 302596364 843031234 259147629 960492999 634117301 4316911 886953485 251135410 443539842 6690583 728936468 534387697 150509988 248974508 366896652 979422680 710796135 678796479 638569478 383672443 458667439 620323055 424416817 957549719 368466129 938775663 623929047 531979823 830813602 932770921 729120556 78398667 7230982 35753791 487547524 807853452 902133462 984441286 980176307 459910468 107523845 130407217 231043034 517305473 705484910 870270378 109535847 109430357 48535787 327064742 372442857 407202632 236075356 925302993 438951939 966662416 754482851 557915685 462645172 250694800 481615460 277391579 802980559 505573728 318057576 956334541 635677246 798634777 667143707 299095028 803961420 441349634 569392567 247670823 17183451 470500253 464987466 270970452 746974401 196214444 127670883 656992013 727184782 929642334 141314671 806044465 111265859 965226587 150377881 623324901 295811195 936600126 120714065 460298060 813062310 795850685 903032978 706484207 984961707 77475332 502541751 379340237 671001534 807661345 259739854 573508596 556392490 78925730 555993194 969870843 262946730 945951069 479856519 989833004 614034387 862663530 97423619 951332438 793325075 210487120 387486055 416598979 762513499 597652173 38975989 42887967 987484977 301281029 800288793 819287559 375919962 985146003 757505272 857215043 45359460 533069721 218846745 53557844 859353705 628250538 786364407 30781240 785746243 953140327 346913660 559615926 16719632 262975020 419643931 479305181 698450393 310333864 836912475 853040707 654492047 216876081 971711188 139047941 466897366 712487695 596619903 301625217 209847040 990421080 16616822 505514911 236645416 755365607 437007988 911913684 754019644 170616566 925879199 376690918 500888482 562330878 596008150 595496356 867771710 917478683 527593235 774912958 159872935 481477957 358863709 594471519 680093406 666159208 367421709 138503651 245526975 321578262 770143142 188805897 98655538 737620823 789114423 393927092 450999752 335422938 202380900 281800112 360509638 878936991 262607729 633929049 896514088 346470148 963700507 838732313 16319266 6651457 37794698 982799480 619648700 739327815 404893370 352101603 813067235 973573683 399030838 605953149 712366747 484735793 236747151 67397229 296609093 766156894 369193546 338767276 409466518 898376272 494205136 102513405 385252203 828905189 949922089 535463547 579144900 603138076 509399654 361376982 506337721 633926014 752919215 844468722 514820564 505568102 432726588 364383895 320356386 202916338 456591266 953659435 636318736 392361779 997810798 4890663 191975309 358276521 968008914 689308848 17582285 884655862 498296190 197121843 7719019 7162382 335373415 944892599 322129170 999099506 787922649 962477562 513390037 518206626 88206628 232305739 126247649 273377220 194534143 736207829 590478438 417309911 63996173 373377396 23872203 546934029 339888554 749919832 198252482 685001916 593087042 670632801 53879561 860531514 149405785 819065455 477572955 334991159 128705493 308926583 666072155 706259261 960698084 231163750 937024964 661806547 271541379 60625925 578215902 614301663 92286917 275308899 941874177 926355887 163143202 672655880 565273501 432577239 233707956 446921602 957592211 920823574 714381437 741963798 338951779 277597877 211392874 529908235 66918134 532486803 610050638 374274497 861064165 537841418 57021626 255963439 892086867 119700363 189461927 979815312 265265804 513222614 105488246 69239217 285784187 72843846 892212662 997752514 594756253 469471977 582684734 53541257 596889684 609964834 500152519 608589656 487836815 694279527 287322173 231558098 73587910 839230667 922051909 548007099 124623510 385644125 393296199 871657212 730766728 658437513 789626431 572201401 119068846 174499392 339670551 224425526 118901283 861150772 81149450 843548668 541128268 164912258 526608441 809693164 385052957 935974908 900441505 252069227 54997659 805038702 217277231 643188534 812900083 533071229 933698471 307599411 185710097 867294445 886177872 552198740 960186014 177446427 27665029 576477339 160178976 907058645 47528701 903146360 808202633 403812220 118427251 387753966 513082693 637954149 328102234 718398726 352477374 232192828 813118395 465693049 669831539 754760884 417902661 61938517 659333216 507805219 331674009 426204123 105536321 306093378 469711151 549198235 543044301 642879471 152913196 515880534 921231088 866827067 357072055 315300479 841500028 491935187 899238158 494451027 878261137 72064391 627586996 382526673 961939395 893322436 900379773 173195353 38455591 460778215 315551727 803216377 929373639 891917087 791511612 620625459 414047326 73770884 646118809 771972643 756716253 863891249 66286216 910168770 701313109 953535962 732176089 421382235 154351544 343004208 364586124 424780250 606012006 883986287 830632308 296942172 809348960 260950102 470397343 720687782 260401996 812316654 660769888 465331586 742190344 412129235 569208108 117734434 253523475 42094031 765046663 487061308 170209441 540240865 14083474 294321116 606205808 341245309 797834843 578037228 753016429 754067748 440915888 353376770 117658608 775907252 800648981 915705409 460064485 557380162 707117874 804820275 664175562 692155314 372756768 949475327 557374037 616527719 798102459 432703429 351355046 614981528 507108547 169487861 762485702 234339158 293257599 559178060 732654488 961814764 204992324 526282808 747886432 256297193 449104625 620162943 631620031 155413291 264788229 113214925 762937050 558755805 211293734 735818366 385255333 482134022 238137499 685684049 962752333 472468118 348799971 462692900 632380952 215501784 291364836 865698929 976785554 834341272 993319166 891239765 332465266 196410776 87755269 403657977 764286824 755941290 524355353 336900751 889108510 702424791 247696482 561052032 468725861 513460666 621501097 645836253 355145147 649553704 716817401 843277785 624906774 508039827 307781890 155529312 91764708 216351542 413020379 785637645 723624081 924645115 296815467 586232783 852675857 234670880 915743812 919766829 406420958 530771336 4296863 659286771 664413005 225274474 630387927 275237250 193109777 547528666 540464594 692935354 991969181 330806229 637071219 716645089 807754884 469454062 140886398 143191910 419997345 541384818 319041508 159220555 266899381 821074410 564451738 335891748 525960092 409048775 499662959 212413072 78103921 855038729 522484125 923687512 667090299 932724595 439803797 661810059 833136518 402111586 61325282 132436179 304445233 456681704 540414438 780763171 530207197 847269844 544100245 781686410 233090582 353468584 885927711 804990932 842802444 197704118 806590272 54901458 630740877 70252177 564115332 892780346 134009444 951029406 529055690 343291597 873033681 672482279 287999560 262767243 415890936 315459776 98181614 393723438 562542259 896574883 655499184 758215499 679883211 107547250 220261002 222774516 14378060 128960121 862061524 180358713 982823838 834616386 253364827 343245542 260716188 536248658 370185572 352201498 268848826 103355945 461446252 121071279 13159047 523540810 853081262 325203280 518587046 455700287 626676828 674174594 385252017 798970373 43834335 727888283 802947213 392718336 722918887 421996107 291040093 905312403 464255773 180296743 107940129 98662254 252501778 107092672 780755231 102475096 735815946 685681535 998162527 205456833 279429297 118232156 327492829 670958114 553558507 857084920 254452461 249885210 281003594 473114235 606653625 81457252 903343145 512452891 694858316 764755737 806409401 175581261 718325909 131633258 527443989 160404681 64006789 802073883 378763230 719725981 749286468 10460471 322563061 513391158 531906417 559784707 170435284 888380719 156416623 625493144 556289831 517958995 280122344 744283960 563767036 954768356 625679254 790266934 267444097 857341276 377376213 274229057 834699195 690065850 651486445 690897589 69638342 928805930 186251574 193523542 365795552 143227598 504037003 384197607 206507280 352156026 67257876 553699480 98387599 890649203 116160851 534406196 991510405 953413800 269009221 704967690 446794723 569835285 347596685 672993611 694711921 132917721 180912368 692092716 298632820 555758971 611303824 50314916 934583861 368333877 718712222 652509058 404133675 907291898 450494543 75783192 861144822 937127685 817218564 203377249 395902805 822207824 320210938 31563675 670735676 545147732 60139028 356324008 8955931 484554238 183523775 267785998 62575997 581889533 499441815 791559039 362341578 119749645 719815880 107368162 153972553 439688388 831826218 354094267 429029318 774949535 487658939 429909965 799328444 450454728 175780473 146178991 732294439 61228105 25341015 32375954 683211793 805057182 25244922 126905606 477004510 555678132 415200571 414133967 65892542 537616029 91987968 172359143 361448351 150182139 539620911 194291384 233004482 963931754 941356326 46854711 745066638 175801265 516954004 401495021 987042553 555285584 998205733 914569860 608371318 676049846 317228097 627607917 279665366 439699954 66092761 567823042 210841454 766166325 237881445 293360334 601799062 816633374 251052871 42043467 445820091 820995720 954511645 864277977 325598274 327136596 875874857 385116656 195372248 404926833 836129598 661572293 872846121 851639912 176554077 876235895 112764650 803837289 602005750 923148224 738405904 826219867 793366380 232256576 964772526 649878522 242929154 113326509 354128377 486147883 352758735 240768947 477789119 934137114 208918566 738320686 906037517 731564910 710843493 842025204 625895657 920632079 552041902 27629334 917304640 293190301 389273535 958946818 37238577 316226972 448919400 172097392 206585460 624063885 939070708 28397649 462633183 413659163 478724363 594461142 647628902 7355693 666869550 200914975 948184225 552636716 127009189 768077337 641144255 58918979 72423532 856719673 94237794 355760400 348050988 432568140 160659896 874742921 858696347 405020160 568959877 801546135 777479722 541712543 386135903 919210311 619154215 386389119 353871582 410668364 457001722 57381104 20613911 309125030 751200796 354640101 256274603 421303962 287594152 817378705 975856858 428935899 297977947 59723421 711971280 769522236 403663971 164135260 604826297 102839357 303672378 547195028 612952417 737336675 102497307 648310800 652551384 394785999 455166171 696561020 473606058 826119787 858020824 457374515 58029058 693944056 637997998 868575275 915379695 30013165 909240178 700136715 655392461 158159480 716933179 69273507 13059368 214655916 403570479 922515695 740843323 823320294 360734736 660670601 101971797 228002323 224180440 155051136 862203265 935892137 179051787 537301900 733294951 451453705 589580159 895913311 341159113 29056526 18650630 365464684 315992130 145555110 965128409 658938379 20383117 980723862 195169488 683244503 850602466 638757444 57850547 1829134 928371555 554334207 138757707 718745463 722419201 663685269 379439837 715706312 820235214 750702881 188112435 706781706 898949665 988632185 820996894 623577953 631199340 810945700 824992408 618662671 678286430 719565471 89058574 806848717 961535948 993661322 571486105 160786512 472516102 249746836 165820801 638842344 786370717 701548946 421465271 816834901 632340914 933832550 642535159 214822908 832079512 252396646 542533319 372542974 779910122 441573555 391248662 304625073 715977214 784074868 806851953 696487909 592036726 541434582 144100025 800381886 227955498 745528025 26433268 965035390 736548896 582314012 15382978 326166513 84313983 416342841 837463638 905789604 612111352 93440819 752559086 945334187 644425876 383241567 17456890 993894035 478159971 953024751 383577366 893154749 9860011 17303692 760937841 666055885 357303702 529739676 637458217 47486993 57698606 491209913 935310535 543836631 80179410 898297368 947433069 28668695 913310102 631547543 158597544 2996108 128153211 611511404 643711345 361023700 352768014 462013614 179643539 521077032 975891976 739423962 564938691 509366544 318331671 244967214 275089433 208350131 275872627 704903543 372424105 505195494 995469581 3063272 431946827 307211098 438027723 727766635 812791254 453739971 812965534 441066807 683224632 546281558 304586393 973773818 851093649 736145064 376795803 770659038 347417591 131844968 82754717 670216777 916534229 735269238 765833276 861428815 589035605 259028014 103710969 453091060 23779797 809773807 889952856 736560029 500903555 105063765 37797513 779734156 301492757 687800470 238827552 259085120 199678351 276640889 707923031 763830924 281356897 173652086 123962729 470399201 860728524 208491575 414972912 359616016 994908536 277442020 970779215 623409666 943673217 186168396 20350821 994956860 341473264 986836545 178797476 735177626 255577451 975951653 104647246 209873519 5496532 402707770 306078566 381810627 297594563 531828253 726088084 449310543 880510479 452663963 699998955 886350593 261140989 933383816 561287456 552568010 740789793 13519213 836880413 744346795 438697186 996373138 468456437 431057640 46499064 720060841 365301281 637328513 338673449 276628305 136224331 38106216 500563251 775127801 291006857 925424253 87107055 673264319 130196342 429035065 588465140 105665945 706590262 170558281 55541303 968831286 411009297 928293536 269118115 169912033 254518637 202530152 497506583 774402005 836773973 123755364 860403218 380504215 395952125 313721640 261299516 987227361 233126653 907661770 358493574 198937498 878285158 108543810 578086970 151162303 346660127 226106948 211772654 877816594 874983669 501653033 237131214 90452373 841896579 179244248 151514320 9818580 773103989 50764263 725888183 527389143 732774409 526040424 857679347 472125237 602632840 772974398 722028642 984712569 902330150 499074239 410508949 523941395 248824952 575854697 103364185 123247787 940590040 98527167 347701877 65787765 336469045 436007940 304253405 346395796 765646372 803880592 490489912 22004023 173940523 814446444 724429260 464215058 798288595 500387563 795556653 833192076 290728684 112429766 881833897 676918881 22783060 132434577 981018792 761236369 705600721 393193290 144224095 894756542 316474289 710290031 3610902 505554455 186704008 634271895 911562615 230941784 564071530 367104498 714090919 343499943 203812013 508183002 876959819 531974378 876975003 118666697 993630401 184911568 5003685 868490657 222166102 183776377 911436373 263007017 174466158 526863083 601048148 539931854 361721151 567786165 803103164 149171702 759937572 580975758 310301028 285716802 801834724 721838362 601011508 122249813 391331791 944904681 552156475 902039181 53287998 706903196 913970201 606950659 562233368 924346394 658803928 328825592 897571513 566362458 422755730 454318343 82374439 7104628 365782869 734740873 110795414 972375558 26089213 124754044 596485106 888166448 508062281 766588086 57739128 640629271 427752997 604267580 829275600 458788405 659169497 578333030 558281494 524710687 146872002 133087747 741185593 144043701 933409559 99623494 416388169 687771896 513989451 670963165 959800929 79876984 98225368 399517838 266466100 888276415 434445998 658215093 746736076 247213873 935863293 398156736 874753656 730430954 460582200 592901901 949722528 528747570 476676957 943547365 26113776 224995159 535084903 640101838 659063563 186702834 529309514 771993460 653731392 875050261 28001492 680290214 672739619 89793050 651034308 765918538 277203593 625246872 212582116 297232738 416744439 115812423 135332348 831447226 51408948 518305191 4940655 731503280 8074418 898244261 883168900 923752462 254515852 578180514 593112812 522736374 513503275 325693099 381728060 543628514 518417313 414001140 338980738 709740027 288996971 801192659 753816143 853223977 878679299 765478977 458017466 830295012 613606656 51248232 745554640 378633577 523044793 534215387 63791113 590261044 748420496 161101185 942195042 890819860 102806798 265485942 493763154 58839931 983705011 439477488 662156636 355848208 871190156 243900962 110752172