10
2028037 288974909 111681588 291303632 155763712 177741457 164199418 280452914 745629015 727272894 383855815 451963117 263419161 854025925 625817844 903511050 636159790 788165373 442332844 275132246 358996390 239303569 23523747 398318281 935986353 142493592 695297770 499848367 7061287 551242323 622426888 79384002 19141560 513456960 313082157 130997331 463541289 120030523 986922531 112618850 230228300 678849560 504459522 679335110 334404235 867470925 674397136 958197434 404243924 86377174 618061916 863589554 791513591 435167767 915162678 71459492 341562698 951473804 52898442 401242089 794478014 364178763 453002785 706324970 720922658 653545259 112784412 626625485 423006839 483894301 669309742 618420173 342823400 63159789 669473697 552010351 785773594 78145328 581004064 943346726 856912692 227723599 266280591 128456734 832249497 530649785 552244092 760049622 285284864 907915613 571051694 550324427 172354129 844757180 27279851 835825143 711708323 241389523 601591618 95282135 388198169 895143571 122021473 420267989 870020617 207534299 532166635 503056550 66284175 660803648 200677819 118884818 741997440 706435381 66950056 578541378 975233884 175415879 620832440 628486949 510176861 446057125 926002845 368100055 867115953 621658024 257571540 500057709 658107225 864636173 955201485 957474455 167265452 399008442 497916596 550847494 458109739 758608226 568056529 253805046 617776915 860690631 433527490 86561732 438782170 532703055 330922633 464996346 459050659 396169942 448906708 277614808 853056579 626274617 597214909 510226327 461020001 180426754 43412191 868977854 542275936 209267734 120714502 386859145 84098970 314300240 161552223 119634118 30107399 809928697 130763529 549763654 582647216 556636623 622786608 123862180 846344645 760720366 770611024 160906495 46147265 639857947 431937569 294403014 260015621 152536706 121038459 919321994 851501934 721753845 474964155 587182878 550621781 433177566 989881169 949027832 568805827 195162271 969391498 910191630 114548429 474202086 64884460 459208762 935590236 364830411 552865817 688217587 560792314 523106616 739024885 980716431 152225730 99227632 423647480 59551364 975997760 587481860 689797242 942223509 362895767 204797314 532352218 634094070 322778310 715453291 14371406 894999939 327962270 842741243 434672391 105983829 375024120 531433894 614069541 528901509 808264285 996866914 745140973 56268139 759836600 78552171 111933668 204658092 28006754 764401593 732123932 688293139 672712383 468924696 777760359 338013330 700743486 608345215 815071559 180352086 336664642 280134951 168859884 576353231 761089112 310076619 304003094 83056178 307780515 98992432 243035791 476132273 863471204 819145862 859516181 701455874 205980989 942428387 72726621 87302527 956897892 985380244 582435991 6608577 464022604 175084790 683266391 501862907 967413623 484718004 617253574 825068049 495045358 880548117 527208105 822668040 975435310 978633468 905111292 478112150 284212393 980064651 937789476 305802577 763536091 336975230 338281497 114673431 807004526 389190500 962890489 108514522 78431292 878717496 403000081 793108760 281288305 928598933 885567777 339577893 88841466 159610396 205321258 373371890 104693224 424187352 804486637 75820195 211866651 180200905 882036385 726140430 867745814 843037105 208630878 944395334 271708931 623265243 816371134 747264388 708077556 90765576 209724128 622903804 344839669 219853290 736616736 916270961 196958284 440001410 214684343 305426945 229904901 346811905 237084800 907324872 574395368 291432308 35586196 951947000 458646504 304064857 28039240 686130638 714159284 611174939 286421937 348381126 625755426 433820206 861275723 289979777 682086095 380623619 408305347 229586856 502129048 25446519 452060401 897933554 141870084 15243388 702028202 224743464 311700320 571143618 455987627 575524419 76108177 804158521 668871654 211336246 457775452 443110257 863389868 126489395 928121060 561958531 797463832 366334868 587464493 566463001 681172143 945114716 413896427 630528597 337985086 486347378 183660185 550253103 663568049 242794950 840665883 57760879 456838764 471916299 38786344 900175864 72535530 813624950 691649051 820683815 949829213 255672671 519859899 145137747 423646247 221160680 214783203 520235535 60772917 651799233 475281636 498349028 328168952 607442521 522769178 519973516 933593593 617144201 133150763 81723895 74330508 227500971 915828242 631320900 620907419 433606847 43215746 45956407 294506745 231641038 546614342 603609299 563751999 781857813 545181668 764184675 352533199 986305865 72715382 320611471 727155376 840677449 51268766 183594893 45193281 87091168 870012864 947432470 883101076 962033506 676294055 373156934 114102533 83925882 781464519 753373998 972445777 785060110 455384569 274344623 791371508 617382207 838633726 570282763 514430966 372484525 634425797 551526698 455824776 379011543 299972613 892614481 81335454 646920332 282117799 105985216 146743806 178845514 330235168 284596920 301422341 623894365 588608851 330146608 533413148 76470245 247849260 9246293 518634012 233187234 326891103 274768935 348647640 82779480 980656692 449516480 753554428 882617980 535805318 524334374 823734889 973035208 680272033 307300651 414219239 97026390 983962743 944504216 844795215 454254099 469367460 603046378 417499075 901499443 989010486 803124886 121220623 798998019 548236217 281817041 240553645 261052324 529457076 519427722 161692015 976242165 226544419 175029763 190714064 287964252 229891547 20904054 8696408 529348415 607373762 514539007 169566498 657279947 966631504 284016191 351748042 911413982 805263381 713580376 387302907 502855668 930031589 916421738 390890643 198825250 458864423 263814886 54240430 983167857 247517286 570280523 935108008 308153722 276492234 353591171 940800475 367481590 126401822 485594138 346645790 189381340 59895031 846516944 54422822 349828943 704698251 45911057 756238549 763158411 970495810 967629623 184391923 660040477 561200155 898560071 319304770 757944538 143115213 663391954 69550558 517196077 965389227 869461847 546809021 781250678 857579872 768671327 949232966 578716138 76163112 509062848 266371939 565850082 590791380 422058884 886502527 888402029 16414169 407960965 379599081 8122209 272522925 855444945 102385502 402157115 781034555 118599642 862078786 847989979 742385707 813864068 689336981 129251103 436653166 305164406 633982232 792637559 653151242 222757680 189059423 847572863 734209400 717560536 346612591 543939555 517050858 24589830 952920737 444435482 5765982 833739360 29103290 771252696 499383243 628989318 730863911 668912710 92465847 365769391 443637556 878870393 394177327 400684388 574053282 890762012 741521257 524423569 794659667 828836522 125485645 430267061 111038877 62745536 236639111 51750372 659612221 752844565 14852799 874034905 867871519 243779566 505721960 707299722 530860711 481744957 50580741 484149522 379745349 46814191 740544648 722766541 896329310 361788372 311657544 610996108 888091496 430365405 420512486 939326259 578918892 252382134 371400837 355009277 576735036 81606971 619194106 594260859 641632566 292458897 929186387 895851276 909664680 812328304 538341043 410907375 941994331 620296175 472583135 345793905 283994406 355607742 153994991 914308831 368325515 537456926 275273408 653684611 854254304 767981759 67449960 340500187 719738719 851351537 297097408 790261126 197704876 549323752 172054250 739248108 227473335 354972145 973791991 287017167 597143956 695845980 835832999 924228916 952414871 318174198 660733491 652354802 96757942 345279394 252615446 903576476 343978817 768224079 507129553 757838074 810269014 440470426 624330802 742222123 450117276 977013510 898986217 976646162 491907006 562769062 518587755 381270183 114441560 827240641 154476295 738077341 71542195 152230062 372604976 763760239 903310376 700259064 912266932 856858638 659149431 458318474 286193931 662641044 234686172 613250184 442747050 34144278 201890138 317002777 168156013 475319310 575974608 414690587 683797231 684662482 120433262 910337844 413813309 175187201 961781164 816651631 27580293 583134523 419456212 503352024 375696989 504780461 744261654 948566844 20546462 44708484 86797739 370187103 560483621 861865499 528341411 44202244 851907148 49543740 2624641 245147211 982513114 994952889 742844587 779168174 353629233 99930807 618251865 238446186 491431305 379364414 608071386 334568773 57735655 260476618 494415944 875817069 910943462 340084278 196282012 376039495 639692848 593471189 584961746 764578 540554830 278067627 437613621 108548066 451481881 386484282 650879013 16771650 327974806 599323037 322810004 442802927 846346046 488250817 205601782 106686718 909395890 681940431 895001824 705408869 491246676 26114517 725216553 981264140 720284579 685457622 244939119 782462812 606993113 401836482 557809667 278191703 631159636 265852919 4893381 823009355 967949958 936113153 80948787 517564089 3705161 235569558 868546767 203145326 215798249 293701661 33485587 680057930 844260210 932522190 652046446 791260430 38738491 628698930 62304196 738594186 611435427 705473032 406018632 654534851 63791233 833300133 635402901 726255392 734492223 753785395 233947497 784785662 887052363 66930935 26128454 225313059 703351677 435125464 325242292 892188133 293895915 64721009 294884590 561010055 769612201 988165342 384774385 65483742 402768782 348058905 867762245 959633039 883795633 30240740 662547681 760257430 828874928 253763168 914879411 623847413 362803244 858150668 317023509 652282203 960531293 110181973 706402033 729093676 149989169 477980908 942605819 897030646 450162229 576438068 853182073 484318300 77512525 455932472 354179841 430054535 16586155 886014425 657239849 839924221 131376520 856009042 858278041 967237220 369131235 70975543 59588081 620901497 585246979 998198889 444414348 304556314 154086711 694457663 393515271 596315558 97938864 231792465 571774243 139853651 56361304 933263032 487174132 860831799 46380721 234895474 246192641 729409762 265981018 853391349 225681732 197695833 493900182 387415318 886509792 347299546 311874252 913796254 175048697 627516190 17702021 787669116 162813001 426633440 292151786 155821378 115540099 726492303 70147847 922100324 860280508 446450229
801616369 245616013 853893597 94989516 135767209 957243505 392040834 692349034 825547009 754696782 621250234 992140983 789617230 65211310 110453295 841214656 456164875 101540948 778277113 522012836 261644220 575194085 851798996 159192545 450356301 36273279 125232829 885496679 454299088 183561275 182729218 904263356 417080962 177443204 461619084 202304988 84420143 487923323 257834256 133748343 561886833 388138416 870264293 527080065 317172491 866707298 812980618 630548469 373637382 286401206 459072018 720965021 585966380 932670588 491329557 751243917 166094065 137151442 170507052 921100533 121962836 677493160 769773508 345091371 670112610 241152273 879948736 904060581 11664155 345025415 335301368 235821675 242969155 552124787 457963172 662436830 281475226 182954029 433686943 113723641 340926210 211129347 993049717 912861217 890320626 259695146 347086245 36293419 878985001 370746945 639883606 976484256 394522229 82547243 114267292 941180525 584170081 724840614 505964067 271211267 344378474 611380522 306774272 419738113 699166131 77386951 378682755 495408250 328353431 694044872 130585676 474737164 194385992 637912460 340924827 494379799 126328174 111182340 435937675 325441569 664481975 258115640 771724737 470101686 578701581 742127108 754220216 396036721 894375153 654620792 757225950 580164875 837007508 942431706 844150821 39086392 154012290 308156964 102616744 716201384 657005461 260795795 766449993 807890232 751514915 382097010 637628393 660105891 869093487 981528456 254801956 697633479 183419214 379631872 369352476 951676443 90970654 955493913 345295021 158324730 537412321 321215648 256522534 464105562 594862729 848393239 539193011 190874781 147308304 643658286 677508645 844950704 933952024 983801730 804837466 188393542 669323327 165837528 793449930 501288078 236332297 933167257 371019562 942912202 466917556 894298138 984946209 766651297 326787475 741091912 786668297 513513369 582989041 756199251 112203765 339494645 337779579 105737295 81873520 797842699 539615230 340335924 155391663 868437441 568897165 215597145 760440260 833038624 128258 176289572 257766566 639709358 729335421 172758280 633303077 916947760 489013666 685824385 469488410 775776431 154367658 356882314 835785617 353635634 723875827 56090078 279034344 955495596 895679794 703811036 731443454 735589433 681474196 881502301 245908593 513738856 255164896 929925657 353460885 914423278 631664904 395618384 330915559 72673733 848685348 305633267 200317370 994385016 598153863 358760597 275810710 948615695 82905156 503528324 324146325 667626192 982852566 4976594 972537500 273401550 173831241 96762746 795302614 509840875 42016199 952161724 699907088 701341470 499692603 335225062 507531979 160659825 207671534 183191834 652880394 359007647 240140498 82138311 221915225 729462563 545443505 324752557 94821154 682475087 81584420 367592294 341935859 768335439 182493834 770796680 993588165 912371438 697961499 112230373 740977150 866764510 150065434 82938852 721875350 509999149 715349064 50490392 354625010 8672210 589742956 218469565 769330344 843376472 458403219 861979970 502477152 563815354 169266419 54934515 423962069 590724965 734297010 735412362 276486270 491768240 187904868 894436612 458949571 587954329 689009390 337916162 866559916 727947851 157691725 300488211 490705427 654886776 110388030 224087428 679993118 975364968 922835629 642502812 655568858 225728267 351315953 373356243 113081597 138454344 537234243 816460707 916378949 161132075 821979038 171570644 755674767 825121686 114698758 961073918 627855851 847545483 22290054 473366666 252567286 737484348 288494966 121793 664563471 314068722 370243858 84374181 913930703 563755869 793183658 254405848 21718124 659512811 591776115 208575080 760637832 477365464 110209022 463569464 696565029 799099894 475323861 380306104 561246603 816037412 266258022 759875755 10920697 175549577 692811963 82634044 424431051 746647253 983551974 354673442 768917045 577769620 286333823 492817205 672653511 676648358 518936665 343165129 856009013 772538317 209047857 296976106 463732753 524122623 618914966 957521004 421537295 839928596 364803493 207387694 644306509 752298283 613757709 197276768 750915000 195108692 665595047 814320540 374106389 840989793 508871638 317900773 638083423 81505502 489612888 766408136 302921316 29544803 793640062 321789328 50108394 697284173 424634317 335393825 218136501 774076873 183985956 57965202 495551114 133737119 322838698 856751254 612159490 900322021 128998531 747048967 370431949 890858721 910267853 184371911 664979797 467553490 53258533 491816387 556316945 903575355 137710787 925480168 936463604 644512977 300614129 920936078 931217463 203570971 48544085 282775903 910037197 81941724 578579685 47788696 659003054 183416527 384230227 177716842 724129964 354690883 364273509 321516065 882417804 542339858 124096761 537534999 398263015 253507674 13383963 65901969 831348881 564669474 76826761 848142994 529735745 324544888 568633616 583455315 988063437 283386683 777709999 563133578 982458068 687075482 351206547 2188320 156211275 2923605 68611613 700439537 433732224 295725504 118328444 988154385 904353904 769067307 624502763 441964570 784205020 814327856 776138031 950801488 762666511 462022263 879757837 319623627 63994635 887319965 769136867 264389059 578747744 97785294 297680229 563709566 488383413 114921171 618079688 77039814 292716908 542900098 213986600 399434404 441537157 990258624 704595457 500955350 129858962 156760992 118854636 183490785 583866524 813448953 384135442 879965705 838241018 316399854 345170534 635085621 954980109 368390735 538142897 737200850 459089971 108667097 770698681 653326136 243042281 250840088 79115219 961125936 505410550 621160719 796460858 110910278 565080888 38990527 758579820 913070089 966762001 637670682 963781998 387127990 2639234 586457843 395829185 850822563 423874899 51037346 988990733 302521658 456388835 184724277 761926983 554630039 992031137 507972935 796874202 383275355 944971461 383101472 537796772 395243429 405084589 474295775 485477222 146933050 163479400 662105272 430395920 83931051 90729002 320661961 193845034 447236497 997373637 776739816 125027304 135381826 442223274 856817713 434270290 346899374 944794916 670408978 814643062 327005109 239215592 827148972 578543558 355141343 159235278 52141651 393452979 145510325 434146433 450694315 307604118 353069775 41393010 701290127 58250910 365511286 544660282 656416753 221830753 520020324 700827113 740371297 684591266 279037785 368966432 25212962 407268235 627109941 419201196 844276368 646545973 55778846 525065886 539807928 460712235 288395979 484265422 588638150 220713235 441767864 483790392 805211749 531022350 405047935 886345240 612416729 608160812 957322865 670217152 379076957 313042741 803349376 178027541 160574140 685742817 814557701 8069699 825309174 913768337 489130518 498856412 937889446 477092258 335236300 774127232 540161685 538460412 23737158 691874099 526104534 45907502 437162938 402934418 59462073 702135169 965064130 437455251 996436442 330077983 198997816 13803840 152114588 44016557 496291830 357266634 807406894 389043558 690277338 789521226 880535546 319424831 860348620 372972338 212529947 598754430 425466212 770739938 927566744 289282539 613009066 386921759 95526534 839905914 463183514 245802781 755160840 130003749 126401762 732278439 982142700 141510978 393406903 285866758 243693087 867095867 272861427 81467582 325530485 590887790 837796832 3950083 859796220 271711840 732888658 917832099 633602574 994403486 287201390 937688001 270388796 661902701 447176165 239976799 339604960 753148198 798338445 649599845 778239454 582868572 400503667 863519261 986698041 982316512 650600619 442967485 98032734 256540808 428699977 181726585 484276348 888602040 916817675 765119942 865234955 575117668 559960518 426837366 311485213 25720454 302730665 861019975 128138853 658832227 695519885 843017110 825595059 535372429 404756819 557946322 150803473 134496758 641624642 71637757 99599742 320403156 351386748 648749317 652732796 240310986 255793095 925308162 579496577 756492085 355631725 151651901 561223183 920056113 551879193 600197100 38875461 140078053 837794599 951542626 21197528 377356506 837358700 410740931 313784048 669944935 747815440 306804400 84537757 784806327 86792988 954016546 983683746 373865992 89960101 634750662 364609046 463411917 809714940 930471606 280324455 103669290 37551426 772588612 171394420 713335534 646336792 422110944 774126169 324192725 770447192 641214101 130694881 986479257 427036723 83062946 26656091 857907483 342029453 308215944 865849344 537585949 209476355 989312803 711955010 79951244 871413278 59336506 749198799 30675188 52919989 866615738 653977534 728120897 619028467 309277966 376997052 243217323 129640193 597216553 610756116 137700306 591029193 348438381 520573690 236249901 282268718 184012728 929943645 776532688 158223415 746008461 261748694 910268942 828836887 608294155 41723008 160248577 496064638 172517437 116218422 256748458 318070943 378511426 468724141 314116798 566898670 45742215 475115790 278131290 556911579 121551852 40625644 106313155 199175044 252241222 561139164 911083610 735324844 335108676 509215929 830680466 137909211 723275452 609667498 425888968 827442002 837869914 888891700 134512119 696737326 185707674 78499341 299460902 854589946 510579442 408804740 552063151 725715884 73341907 259092474 789756378 300046275 44417620 495689088 219242027 840088176 389095662 473846510 508287608 426359813 714716599 742191536 839814257 587471749 294520464 963640121 871850081 882527791 122612472 952974083 437826576 497875500 483778916 196046 63393520 642032320 234910533 180902473 601516217 904565660 457912723 166511117 434873396 830685064 412160424 287248921 137102610 142160342 62002459 827893500 8622541 436093928 357318722 448968716 303916631 193434304 974575739 36733809 263634573 913227686 931966778 563568419 98663564 930698710 274705582 351094784 192615314 380905540 431309989 242298079 271338189 828095812 998172642 330321016 480538553 356173923 808428242 810658604 832672516 318946702 971527653 941914233 105938333 369187461 310628583 899215082 523419338 133003094 205179617 139718032 485136543 944119517 779830305 567948880