10
676027708 885017414 258968577 803276000 539178217 218210294 214471501 95228005 706694825 253897318 105924640 459209387 313248309 397260411 327948991 28297343 708719202 793529406 354985821 3536776 987678103 237109652 260524324 423197263 559246332 684597022 357375108 599512401 451155879 691136314 348887542 685196118 658623661 674943042 976128852 910233067 542233703 107118637 536940167 957055815 262883238 442610528 558006278 206618121 815405537 900496535 95119400 73102179 670977491 666252842 173268750 489958882 896301343 412173799 42357207 866638342 792886498 375499063 247532100 616421305 698322477 893938516 437804545 518952812 935882945 782037737 236519871 622934077 456617893 360263910 749440020 957386885 728539835 514384365 313355677 337432629 805978895 445927373 181917958 803540214 667831155 850875004 108866039 238455566 265899321 681137007 355917466 734842005 154972800 414846830 330246309 376975417 588564877 486335929 405119467 779026744 72482036 136863562 867202186 882551820 709661901 782721187 387835804 479772318 448223964 59219021 676083606 243642456 640648496 951932948 938022990 781275299 61854280 900243231 294828814 68670390 165709123 923698540 913586868 20612773 65715085 12864313 377809045 541511147 850105634 190410485 698988387 147351133 680938023 450876114 770802665 487111164 409500300 807230381 971147330 167067001 55298411 866562743 921890104 757422050 432522473 63369727 559357267 954676028 803974175 384777200 266891125 22086232 409327098 473387272 157389005 343379742 828137478 799407308 494152291 446031516 967630058 387825038 787705622 559901371 434439895 797040908 238395435 72468428 275307492 669691147 713032126 208918993 497981305 210258582 346928197 121091328 613822994 563496403 243748089 851606139 796425244 77506818 74851249 214250352 826343142 700193625 93829059 25382313 336464333 440620181 49275710 136601124 549493535 745026568 734607903 525080425 668170383 256786912 470356980 316390156 8935168 539072650 776016001 342118456 934253162 369118504 427355950 647079944 689958958 607359564 123243961 597104586 518666117 832476831 66116809 497638993 293896751 424195388 284216007 356429268 497765155 473327500 555202661 80518657 913949557 737078641 894070759 162090890 374918228 510536044 135589773 783026074 925175425 929828138 248618022 212857039 564469378 39521668 444620308 796921220 786210185 899703814 314885527 939704359 911391180 236184551 101237772 30520039 325913797 763578721 656454938 561006213 462841474 85553751 936969109 371473826 157568590 799127850 493803094 127591639 783400144 692431981 251405885 48401832 309936006 383872224 215807902 192934589 965143904 331576833 866601881 642849050 7810200 503947223 42719380 549745768 904129517 783844301 318416361 778054607 18750757 596669858 626880332 283752357 235642877 340163216 285663112 902854402 74235242 73772272 493622607 346449968 362751828 841894013 123123858 189025102 904503020 757348622 884154115 480415029 965800431 256655169 514291437 312848315 592984861 35285618 75578532 9831777 618185719 648124136 585197326 7686860 693272124 602344378 939531882 378896783 30233400 371593 681701547 783564033 580080510 805483892 430935852 721842598 183038956 747657830 140170122 996598320 682622818 607658770 163228137 316328097 32363114 427842171 882428906 667637249 470537971 727985594 889245257 381681876 279435469 616500064 277058750 834568223 339431420 119576413 205160262 191038925 394096836 581100316 816235935 440306514 920079178 378691277 541816072 54672871 238482199 390532891 252622330 546561759 411929114 796020913 965015462 512676664 284839776 311683630 292331386 90351610 173000945 629244929 394467876 568381651 706327359 269298917 847199089 819802824 516837854 487485588 777396734 723154927 887500827 540490767 793653727 494086696 965487577 917131936 636558626 503984638 52294530 646316381 765111022 239499212 420345650 256191004 850799823 832532582 160877570 3956152 535811127 416802128 105343735 106622916 475583818 915722626 259667687 201120225 703452637 690785073 377049824 886585617 161444044 538208637 404053144 226955999 356461361 975659836 352292856 699077805 936108773 933857178 76514823 19992691 279344318 950738142 856680302 926034917 188317951 810274085 321552494 949833699 353813794 944883481 897144022 828038875 473620563 122531410 76479355 207465249 194804084 963027658 881896804 896478923 657229559 754853714 313394595 552790294 223350445 148446284 425733259 39636442 553776126 400945179 400929130 464219426 687210671 789708995 728002202 168592983 772405583 75835094 515522871 423916228 277743537 628333074 184905147 413842165 452975045 783067586 757204976 753378102 231119110 38553765 372761667 311101131 115238334 911746416 437735789 782058470 612613548 534251193 930007818 459621649 775644826 679102943 519062622 546436844 421688556 83730599 213026601 923931487 920245543 531873673 142616417 603712342 569571102 695026903 784117167 198249484 890954271 861812500 288046350 69804306 552395588 696012576 333732802 162554769 978032214 252718724 509403568 143056973 934124451 465958220 262710100 668493870 334509424 955864331 508001524 597425353 264401991 95279543 867930953 142834683 950478994 372290183 421857648 14452348 555584535 818946895 883907837 548595343 717928983 697674671 899505485 372099004 476528944 393493995 597628799 304146446 988235783 829619609 790551389 913854275 813450674 173178669 40367739 867893547 700499788 991371520 299359646 725813817 337060971 911037204 617185886 457323563 931008321 291988136 473923296 81603592 118552980 299122277 850083669 863210036 197931389 694555753 240820355 391364243 362625798 311110551 591361127 586681337 883078175 352700673 864844138 333920099 775107840 236663295 136897168 547843622 17271190 560942101 787255405 867441915 491483441 707803422 169308014 437316449 508678114 323606286 631947384 139655453 193393893 580237143 212827300 990903504 421548354 695994573 722751836 375080260 302196355 425396318 930579175 996640841 768511075 968670437 354235810 484492286 216744642 558380674 852208644 477720635 16099714 103261576 544708935 415516238 600213785 37408317 545664363 475784070 650073195 687893690 721414161 546378333 930959337 107524906 375857372 225586788 948147461 628842281 702806621 176355663 941297172 824069762 920719268 776976197 154435190 377930696 532804399 600194714 301252552 791249291 248903543 365343622 1670052 393145519 459446428 784859554 760460353 316013781 269997401 809010968 176936723 86972895 616443911 466804225 398747833 98164610 244039320 442738097 647972809 188863999 962924177 242942470 378192868 487843104 743964648 458033225 246051177 207406600 826816301 507311270 526892972 61109453 752929810 783534406 694437651 80529733 791071339 841996429 593530810 292389079 677098269 878355932 502810786 273052465 989949105 39425101 56684453 516099698 182193111 937604507 662409935 73999654 959609811 593515617 399017052 814236627 206974840 18895254 281370303 351028039 162196736 949281803 440912532 824487065 505127368 362685708 113431408 459399346 596200553 129775077 553858772 751235180 416865643 741867153 802417885 555814318 518980737 928194139 721445890 943939589 330650643 927436668 331103905 28694243 280927303 543016793 664853609 562348337 325858837 746234125 943613965 991398863 384732480 88096133 314758188 172043431 305956567 937344222 731586609 63896136 557283169 612931829 261075039 613994437 356585957 631248271 512212954 628632558 582691003 4418315 951683784 467968880 865715250 237469197 871364095 996885480 90133260 94426628 974475115 6422799 704477366 122886665 823630166 537591373 705307271 419363895 516704090 303745560 921144269 93291789 400110469 724700912 76595562 902970443 713615466 719003092 841846848 279751855 542694172 665296663 884103125 97802499 785735257 919112427 272238881 502909265 652199717 373067071 948244946 16560976 753458535 919361573 98933613 54157177 61691467 365127136 127016098 696279762 879292023 754979480 245658751 87643993 645470007 410122456 616248707 776501346 142059611 76964415 495476713 601235840 978846206 551719019 705343958 789204048 847298847 65636650 884701915 946946185 863615577 917874907 159227776 813311077 193811905 641042376 58502927 204286689 906396533 847160417 330011893 388980954 155923099 821932427 597313349 877553886 953524016 181320558 802070527 683585306 557301739 799644395 711488261 175912851 836222992 404170914 722531412 823599612 156496665 608943572 990728909 915129323 938158777 724277659 456307170 171556502 895404166 270901861 191761976 243131465 70313775 55820415 308128334 156601023 821221285 186541861 652088605 18611549 10182116 203688758 377163825 962608833 718670878 869967619 525433264 665339456 125098486 93247346 158499743 961158698 718036976 815426614 83454428 988077885 771719320 249491747 61617093 926714446 467376198 497902421 301571419 157593475 161846955 880166897 187756582 980898498 480665928 121844313 471593919 970710035 801186191 626740652 840522090 141033597 40667327 93765383 661829783 346971271 904773686 272338908 278341201 689683970 166794536 33631053 500122222 619954074 649940805 379027776 748018818 506024293 579822002 383500370 70947920 692517013 857508900 101120570 275918988 773223118 8908610 973919132 310331446 642459576 836362158 487344859 894244592 861664481 698441503 149628645 957263474 199340524 749019562 215359545 338729349 431987652 890238377 774748423 813860300 378157513 429319971 845833964 582662058 453049163 745366091 861191509 707709547 329100159 667717485 689758701 315601706 197600006 850852761 291408323 105853145 435161276 393410259 404630275 457530769 546836206 116499715 504687889 689230084 655136075 507456924 16527782 768384430 227339722 641533557 409425634 103907183 771235967 411182067 358226766 113027632 647299404 163134407 195499183 128798214 299494209 908934533 36624591 396474417 745855535 772295330 472231890 688441005 32140883 820048009 396092691 244955632 408386594 442849089 717237340 850953065 583291976 919931261 455210060 180330446 139766884 417982230 39088486 33752128 458107762 603696071 353128794 117006716 736969441 567999405 197317540 606339415 888536028 301462260 605128261 416372816 435663655 955090548 243061194 251753526 702366546 944184098 504360881
858294883 512336508 374973446 632997569 704225642 77447366 288832672 745163125 557234681 618325436 323197650 183936072 189754739 308570791 940669622 173095761 355710955 525797441 616610928 745224950 397894437 842385803 168260134 778721787 61578325 12544150 724366682 13257258 53278014 108749820 254038281 533306621 252515786 677253620 572418273 558454944 357119324 652579886 994066785 882019123 22464666 322804781 944331523 382169696 94725706 493760614 113686938 319973467 270190162 155831658 23532050 822921435 563718938 407644864 506900990 634436922 931973138 878191106 9687889 306286979 707748818 485338412 855944657 157473605 707020865 266313308 827975352 409116987 198669830 620130283 929032716 412506291 50439185 710179806 499134469 732054751 577016159 922325501 830282847 447231774 600548657 475461247 879451206 972909402 884214529 565915060 317608174 923148088 645058387 184223963 531772886 691604779 302845023 164418033 610501043 45475746 130297222 880951823 706262074 826662835 35376109 262415860 690905531 102697566 461236041 550839469 93147762 592210530 369457558 194185276 812597986 728471600 586074263 875504932 342250288 368010352 289604868 193568870 951836503 574403223 369717528 867904764 781818440 745517287 6998030 391112825 685989211 813361802 747477584 886958395 413042638 267597366 601934564 523954934 602710669 759223453 986012741 914321275 874624381 834066898 845872612 128400282 682514452 370301179 882021366 190597618 854884465 732315127 280916157 178247878 140513102 693828676 448979250 869740463 860201452 50177907 824193070 471221742 252582567 159513645 523425514 446601876 252710451 901444721 281430277 52337326 845356360 730720582 841770415 772575981 609159525 135825786 465579707 209161179 694521792 873480358 270063515 402235072 179637809 110242072 814152566 700376761 765052513 176819633 622287437 557735358 606829851 758130381 969952760 399600614 405975029 236027891 288849692 21707533 588477404 695281820 789253947 417350101 444067261 371148521 576677958 643680026 529921967 614505707 231158051 606300265 11909366 452765014 323375582 177215609 701063138 410887619 9583154 753847714 627849365 527016337 648675338 660668459 115286855 10870645 705486379 405536149 351751682 422693865 628355525 325345802 206306941 92199529 577892621 7427790 365666939 859334629 287386128 971578360 344931261 500556704 945751084 807418015 509758930 864762426 677282614 779641331 246987195 468533631 352333240 336898685 140693115 879987295 773626049 718215975 701616310 232254276 560038027 950918935 780214895 327610774 734593265 297275349 797626779 249725026 345829722 580841205 226584125 625352527 839590425 987458681 92541244 930397013 475237516 839223554 457389106 54212676 130759297 434223286 859256446 474325749 429750150 943523031 340586427 844095138 22150592 490986866 491828579 960763492 404722776 318768674 25376033 566708353 250110232 291357016 335666789 271691731 347268594 141952768 961764402 293735860 920105501 417504282 324212663 280510479 465489265 51006333 191771689 913873001 253250808 576287681 864293960 508637588 703477145 990350772 248123991 279875441 599250648 280898570 738700716 860059538 965381266 24880840 994673066 287296250 211723793 669256460 127998063 953721817 872312435 449977878 526659970 139414668 849426344 652458127 478292870 705005851 971593840 142667720 337558193 295956734 724739480 332126420 9014677 309862822 512287417 17367827 275353567 143243999 439571243 397168427 124015142 754507635 339876500 711882896 738620725 783774236 581953989 936245228 619836611 986268186 970953754 878556204 844252467 59631228 971611633 747255722 236435780 56501314 252045224 700051282 294359034 812386040 923838198 957149282 628274195 983597336 739131423 995466858 657032169 745507923 398813555 309766093 541046362 17170005 906086171 463216630 333471877 997537472 969729409 378089247 403450745 648596147 383703274 489789972 33706168 543155956 810781182 973055010 183449631 557378119 457527480 770211120 144733330 754828498 889676722 264477741 185060368 128738899 453898042 394629474 541828460 926183602 893846076 685341141 74134433 344072336 802280448 113032529 333895037 967753450 718520826 904728439 358991539 588664492 958972229 222692124 889830902 841433655 481390405 734203623 134855422 886483252 931483088 586078715 221700285 486264043 850916534 126085835 998121081 321414728 452847256 641053396 479480916 942327629 505247589 30565440 849991183 611633313 172414786 867974056 629152585 625378686 726563274 692152317 899174268 687752701 444421351 368312486 638497043 784981297 218034921 370090043 483403572 69123398 592524729 797722661 12831896 553769601 39036914 129112361 576246976 502817429 983280 449195500 615417493 903934470 552375984 676753440 831155677 234072408 322321035 576088719 614643495 870344224 932971183 984184975 877728829 365957496 622423295 951230272 706942219 273104117 861150777 908374281 233860831 901188835 653872735 100406403 701087064 718537958 935954531 838603418 775113601 210876903 382561159 903611016 786851859 492118873 303077458 216922138 644754564 137019012 445495501 173559269 434377928 320464547 761885132 748657249 421131576 194485438 97767442 547772142 196275671 862986460 194240627 983494222 111412533 286926142 736202501 949699525 12400182 262080463 796711289 114089736 819396775 485669310 430657288 585582445 573919823 979765617 284226641 451014462 935142276 953134870 42158839 107168116 821930497 743468867 795072936 893680005 361791250 637357675 864217595 986207140 617682545 514725243 360628917 356763650 686743727 353623110 368721944 682689557 644325057 923934303 623816636 425563769 827132534 58817011 624579161 188765822 188060758 440007840 677122699 218304201 278345767 847261291 251292581 716766177 759085273 241759526 449611610 952015595 468491541 575727721 594649394 159568502 92127912 823716876 93236697 761366274 869130100 394299715 608706601 504186611 231418511 41493717 824625360 918261922 448403704 438832205 1864367 878527997 390189814 720395389 129214869 606411512 176381784 942547461 978004507 605944445 117714547 174429905 146296391 640325527 482270119 24821976 339879736 780022471 719692326 830572150 447147496 168165099 545814744 383116421 260888933 945261350 230782160 28209553 750861141 128642444 104705272 914915841 987168123 735723656 729649043 941053137 746981022 543432336 618942919 231019923 846617701 46506418 867957102 945553627 266883032 485091888 841546769 471521167 540283429 551502185 89725709 253861544 776175568 976637454 410528717 87104860 671194021 700679312 319900371 916083892 545907794 604318909 854616904 819735715 715695600 682346005 221748223 524133086 133540675 591791296 231178739 752956926 87760067 513300106 620599678 152963305 846766785 469630535 938652216 366194015 73955646 147562904 222722956 756263650 92155526 695432180 310453170 146004707 321587439 452042579 358743785 545630220 240664238 763090029 195154307 603276125 346392781 847468568 399749663 707753801 372539217 335848457 398216389 74765895 851413063 747931963 395266234 501452538 94056470 487369605 247601810 245968893 756934217 901412711 243859966 340869015 483636091 24874455 231453662 728641167 184606877 272643879 221469812 268249791 292074841 448757598 793730609 959052579 238572859 262302686 673045052 294848305 789653338 784060394 892890466 530486944 818213365 563617956 689327855 508851672 417289422 949306887 946998268 26738515 762201344 557743915 384731143 98434141 403225650 491267922 137721143 866223464 585676147 113652735 884796665 973044558 464440473 852559318 492007154 299892240 8706017 921692029 963599522 573017059 444457512 739104178 570128502 438650136 865623939 565177860 558059258 614966191 658784880 871488869 877569438 429727493 964110704 714042282 582626295 173849810 702797623 380606490 177969159 229934746 148817765 365278213 537156193 17862697 824334826 311158076 492509416 370721109 371904059 384443399 185910681 28885409 681246855 632576414 869787186 324424807 431646154 451340929 314996855 395494433 776117424 742187433 754175111 359874696 193789545 987934935 9093585 596406945 443130089 416210533 621824478 127498445 113237104 883570168 369937424 395181255 80873920 420230413 618863192 754142925 70647491 88596790 728332369 522047978 174821309 599258965 844795856 866108628 803444214 146424252 877815110 477279482 614530878 216341506 568673727 409601615 754211429 480144589 932360277 433219526 266341666 724237426 790154834 98936962 639632387 462875582 147552462 244662336 706244830 266407488 174589141 716408975 577268443 696597499 172450972 990860215 267521391 445635109 227338484 21250758 858781862 119350874 749118008 805022933 443845314 195596805 363633084 616184869 231713901 164967430 295576147 315354524 702149599 449518476 657534193 639552345 215721880 86574517 619192259 840561430 532074086 966122224 833733266 989164773 29384760 457425024 220264192 421142255 414046132 324424011 341874847 553303044 13071849 119275759 215729291 884243047 246707599 458091899 516277162 392926084 278474608 460609582 917298491 43485604 649485806 126267054 811616181 47282550 676271544 840133200 727794042 127980240 697719692 105277503 478437219 795912841 14662743 368924293 221958540 397761204 75812496 628951463 111579121 922917103 654102730 964906098 885437636 754953316 593027523 179040777 449976632 657298524 263070917 328444979 926504620 182224428 170851601 136841751 273999574 651643829 893603926 104230303 83519337 764307983 634516388 86229135 72966951 687246593 831642398 760810895 851953750 528288700 9668781 710359156 633147493 844229997 940030403 474857553 406314136 805704104 552871287 814648388 633369763 846412283 535069315 277525462 492490061 995641138 555238210 322184226 235106482 731220349 730159219 45638729 650745855 85803272 544004426 812154269 134233995 968219774 730128135 318472755 34603882 503768108 401823654 457152555 355942743 883922147 736735176 457877088 941522703 549859846 867156823 343276769 559150402 912367315 324172037 843018430 597665366 227273272 565895725 934561873 555364453 599826825 334619018 728576934 627054901 267722084 159303258 208031127 964236161 960121554 233172440 761229913 543012734 79463036 870914511 61103370 313059357 293270033 704076371 747387516 261401924 629703775