466666670 163398694 280000002 42780749 353077819 572244902 758620695 916550123 226952982 309846434 247191013 23564065 501886796 960409881 64625390 479308292 13329102 188663204 349460999 685990343 275530806 344188411 247428075 349874475 571351169 94463432 710565261 305290071 847144278 626281682 30297189 33119175 155539794 749204572 649958360 75122301 719228080 251301834 122423232 343782050 726499038 52148263 994588262 9410861 929952104 813638034 634457501 839001419 208289742 337291103 995443981 756818474 343131734 10663999 312719962 356525615 583069768 549974622 99446036 596889265 540236221 224503650 553101401 908215205 996492164 125177445 700033926 478153043 277155785 807093338 172527982 608606746 517061933 155347745 457460161 915357082 114537931 66642812 22400965 124090572 3048477 223943227 511806547 232018379 587147592 486161422 370758020 923721703 171496931 780168362 115049703 622596556 609575908 190065557 270075638 454217827 999884210 544551956 831088148 870841006 324460928 944055574 860773357 960220066 13503323 68919837 275925943 740717409 82201620 603465454 464549238 273311436 676550442 815070912 97644502 988756561 982735362 36896093 864182627 223738268 718581176 216821246 422188819 411090919 24663959 541891299 316766253 447462562 205748034 290929844 752858510 912405019 834935573 245299819 265700105 724185985 905121276 83660495 923692745 52059134 519165684 770756150 441775078 431154658 268455144 93136804 991518255 68061278 396087734 219018817 231750851 2995333 85676999 870866152 180931695 825867740 369000057 387216907 66522301 873950374 421801652 613230964 592780745 799048509 278905521 515909416 197661589 650206316 826583745 439755042 896352504 673263752 737943650 32248762 662089749 664107641 508048056 591680327 276772551 471201521 916868239 624147373 603566627 611476965 639580439 518953763 854626036 627480779 702064281 897856645 456984576 846035339 129321729 697180950 289470211 877542195 210150188 18746047 251447481 870214549 789478444 190395926 239975023 735634610 761485716 243301176 350159031 486729470 464885053 404881164 681417881 982098951 479956548 527150131 71267617 228471135 137442505 80453727 892257033 140326317 249103680 723497286 662477224 816973110 325247229 992229162 76979245 286313075 678078085 542512482 221225792 427547009 532217274 111089966 682951789 856875652 450888295 139844063 934064410 81784061 144117735 621089078 773087771 70220814 389438082 506130818 784115923 239574758 159282666 333505078 476083003 125712908 800866275 735240223 957812452 997377907 399538803 365976999 779355367 981648156 104987392 13887923 62358650 542548475 400102030 957522880 746266617 200838554 276420673 392711004 94293916 801201143 676996745 223054961 397067474 975817979 97236577 312340170 231427667 416472116 869104497 111633015 671764392 753370709 597451189 276842543 857382379 870370049 733244255 79109179 89973225 937714162 173355729 576000706 563534378 504182188 738321026 453170050 733863498 189977741 748701021 984493632 821576229 511803435 468960342 829740758 220019984 940163759 536776985 266860048 273730682 893562273 459345319 122575971 713591247 213231809 598766627 813644121 91406 493766618 286875393 94733113 761177062 49619684 936108362 43554804 23476984 128288399 525254635 193972876 812700562 776092970 702276043 457671821 629558243 674594145 277823177 536432905 645795067 11258125 147130335 281509271 954717914 375172423 357972759 870152924 347642742 271741371 680681666 5898016 551070090 229336840 861998766 955094977 668473679 87200311 910216231 281397965 448173081 495926918 710984158 905548046 785455938 795365773 653068804 81220979 584418701 165342205 389941861 182449723 938101806 67142925 293875497 925739223 778303973 370085317 238540914 36381553 810870368 393604956 647192688 881452111 554996604 600627206 451445203 910629330 333970089 717325881 921695154 741787007 589559081 737343901 178303386 577707700 660509043 851888918 978439677 458235553 21521915 54782030 875633665 409147105 330706808 596180281 819649770 986825397 298663145 815466987 279463359 685340286 364860489 738024337 315017396 771303812 535321633 376830964 306940199 131362170 46720770 375241713 389085688 630983499 74886862 618078474 918559596 913455419 133470089 688357733 82501013 909649023 24584820 824441341 859904300 430368098 399710848 803578013 983900444 922142362 365380658 551000644 684229180 331639540 363574924 464958084 322025640 189256225 7986401 298225007 252491514 695723523 676503268 278998980 238075510 829511057 516396417 819176286 519515966 609353311 852883848 491101821 776516875 908993061 99852230 990116817 251338925 82656694 987371101 686615011 316887178 378935667 405631171 788666691 190626107 914198275 558136993 890130096 514582762 895805725 903551938 395296728 274008498 63069268 228037311 874289679 319494930 39697096 47905712 467907743 79142531 536391674 888239929 801570655 910646330 63845404 940378184 480778683 580194721 780487924 160834165 908202491 660042092 430632483 38481177 260283255 32394209 747566757 752452520 867166785 182356820 176584143 532271630 29161430 751805776 584158324 828101677 176659629 21512473 453774624 997341697 313058804 151108819 366582921 722734203 209204183 724578512 60506358 58635524 376988552 887626424 81200993 563309627 319480651 950997479 426734192 15823587 727137731 467046661 559413037 439832421 707029941 644847339 398409137 458104886 68450515 601239514 938464736 668382209 511362424 8957852 375453477 764375286 877759123 643481844 160890139 982109228 464822852 129442066 43468105 255446354 71650136 111791507 876347194 959470694 924310331 415462720 764154483 649495903 555259067 960278119 947066327 923184937 591968050 73566747 610128836 34646683 887174256 428824954 1487433 941157161 341197788 129040863 541885500 410331658 832493062 412005291 143050674 737590723 239004542 371174489 556757814 372673583 984828138 816234541 214387018 622155589 872491767 414439816 308219334 850353319 32569225 805656586 623991777 509621849 855758252 261422532 814902260 248872892 472215671 546694497 781830513 486227631 602891267 499005112 646936554 812097460 814479859 69186206 805595237 705703460 11021640 944101970 465281560 582174687 849671725 116860835 117535981 728201283 313501100 32908904 42545770 489275833 975760325 181227697 454237742 527135962 509497008 104026608 633829192 84829204 407790817 264404335 338241792 730823761 916240577 335185788 158078458 479502554 657504353 612496789 725376879 806176161 667164278 530898108 488252847 93292177 890750571 44215422 742773316 931674601 570043456 734748052 375552651 940143667 866705053 97557762 788748603 874740370 440039941 542839942 678797189 569610982 377461254 225264167 996360386 172662502 510194931 691258667 225100652 823480351 554619702 591361301 310269847 34914128 430856873 165762047 588155152 894076295 841928669 102871895 344998038 981170014 538528657 949833923 992493594 478644330 500164127 880367903 271912165 587391376 454027791 4541212 357395827 682381772 552353235 774066490 243269184 81169 967650653 795950013 642752751 74225690 502324449 508037394 767355387 723223819 823279198 70446084 305642494 64227632 10442152 471975088 212769837 698879875 730321991 675797085 948207148 708032134 108755454 298414782 673094864 49542723 345874621 488980645 934951022 637447947 218951164 788750635 438711536 878092567 647434385 576915255 570610194 576971384 426100132 103367011 194355259 734783554 537083999 143006682 770560127 170345869 635262076 33717625 791667929 219096684 682466091 994027746 836789387 273324049 769970146 86734943 125986613 813010664 619428154 24492617 990763731 8995483 367127431 4117673 702633668 292260594 521629627 864220332 844259680 111531252 515076062 622336698 704269676 806227439 318566370 309313774 583541567 196661598 19211368 442948195 679339584 678292475 281291563 585054721 489213259 620060974 717598886 527543995 146881156 25671753 120260101 108697606 442150253 266688363 292101737 695382449 938721810 137644226 302427970 916644103 115760656 26376938 173681982 291014492 373888769 92506105 709241901 841848682 365503850 300560487 279693029 459266181 308745842 225607069 611940576 774155910 877513909 331777471 885537470 568368534 770205307 206333423 67705244 918022923 875802741 611569973 794895199 213770906 380840841 806856584 918979631 301125685 586849983 625819460 777538963 825428078 221039275 197108026 159488665 595222985 708446387 328863145 976273148 178412505 413063253 857497630 712815485 248398959 31036697 970429046 556201101 294873490 30508354 522516650 852848917 52114507 436832099 448049648 655020054 254707179 600347874 659908335 39170091 39284475 242661820 168343308 581299991 481321456 423631527 875508426 802156882 175140836 456893190 35212891 600240104 811369779 875673955 501085292 916858691 147954874 769189005 117249905 576458946 353703013 812795720 963252762 453221945 381899589 474110641 166048520 230621150 749023823 394404959 848123361 306167598 867998380 453875015 620391842 889936238 847379154 13754782 551543685 177911927 597596676 70078632 652939577 928617251 741839413 34760600 465005631 438838183 177841765 565457317 105161779 631802649 720035439 54060056 641586816 192540694 753194081 740888617 988305312 245668356 999912380 562083503 935017382 15814672 953443319 760676609 620572174 32003610 446442366 702078076 779972833 667559430 257175153 943481907 40960949 778178400 707116148 929772057 726590070 483078658 963915595 278313712 786085955 645039756 514612636 649743694 784270875 630009925 560193373 840073294 838261705 305559547 402428311 466523639 663000308 454509041 863121774 439560155 693012401 158978058 405888497 807123082 599477981 228068090 756050199 280432877 835983213 971951934 847148874 902746957 212660244 850081879 405780706 468338628 642477394 293111136 467861112 504966586 937633413 653102549 115996585 771127672 908228345 563852188 512478174 962761492 463309977 50208454 143653730 2808045 886594985 184862797 568358238 294891216 712344637 245317213 828027910 443625234 389473388 206164576 713462986 541680785 87353424 355710700 743481319 131801642 513515785 945219208 625331102 893784842 433770482 477141368 717271706 522939739 948712799 593568187 447068807 439499731 612187188 45408626 410260224 836470715 589409298 114905774 900507436 995559876 176599344 981639843 370541862 696291696 747347489 467986212 430601965 279238771 839585528 189389125 829867247 438357682 290203761 281927500 675040122 592516900 120689060 951906140 550361906 14487112 159153912 535555610 62353086 424880776 56263382 345516390 11320464 623340649 631549569 753094235 621833417 742359644 418686661 946414119 883245572 532143933 882766665 767204795 744778837 341467348 244821395 391214431 163640322 16339694 80991477 477892955 51557169 202883056 60252932 630688141 660623193 432937458 462199560 467834036 568237838 230722008 306275473 485195420 165105333 288771758 966949000 572928152 452559790 708355312 705528829 843613363 208713864 381386799 399360148 736132678 82878338 673811099 904342477 95789146 351915096 761095113 607081336 115994378 123941613 44975504 832578026 811620715 511381062 665446629 438201660 707108229 828166687 614482133 879562774 752333043 633692326 690737997 794509957 634923882 617287216 361909133 228835600 754631089 8146550 430945966 479138810 652687438 682740216 801349124 852682822 101328526 848058917 435467064 934719425 493279809 535367996 290428626 712323321 185299633 392105527 935193409 879219335 412439272 729972783 508035935 893494092 446320294 779733291 727569168 73090420 80193311 138834908 661835008 702950239 500149699 507265467 213329138 41393796 419603438 170057174 116880252 383975188 63533110 775366450 319269455 56220746 183810606 929686491 997025807 514270578 677651892 579911894 120743860 929570689 211814766 703249774 116478056 591840864 956938616 882504429 572409165 865733928 671071988 417660319 727595989 247586976 671167077 197471657 159556188 597532561 406572062 478864767 132075888 647645676 278811862 738318532 101713803 812121975 219403167 807210219 32938532 429397085 21937630 516620742 596278987 498159998 137728967 198304711 817232099 647011613 139117663 814240132 350116210 273956081 733978548 631246635 831040454 874227634 814027473 39960455 100449075 603455890 640681783 497363983 892563096 661236500 268477749 358378441 700296495 862171195 395843856 451430830 401257431 878650003 881121913 64865140 394074488 468056670 680896492 776636985 566408135 268672598 931338338 789239008 43830768 425129974 956621292 742648611 819988724 345298515 33540918 672304659 517178277 386744254 917870016 214727462 61145293 526244726 292848291 743054810 98922623 105470215 223339580 889126071 323560017 960936414 262099422 316839992 262907136 520084511 519705111 141682273 471429269 62173407 347532849 49431397 194243776 276795352 150080926 848333627 501215315 826986613 111292523 82833357 113887098 574513786 957988869 641920609 585785729 446445393 543127490 746104392 692288491 501736434 460271539 908729981 343718733 787467757 324400657 897643409 730156686 736215735 142477187 468628588 106500641 242174031 535434162 978991187 917441436 643784159 520983473 294550252 57364923 727984941 66294523 229217895 354233951 298741098 332146784 687233902 880627289 255905117 121455374 863631307 112956014 558221117 121495607 363722615 642554021 840846258 911056140 632110067 895280991 250166876 360627897 65526583 906051034 438871236 48187559 188534500 26433587 652508252 850923333 734140756 726047268 887160023 274372486 663437028 272169940 617784275 298332504 829864172 180195611 41716581 958591571 612819827 30628696 209568653 178867066 957275509 438538951 692459628 125774043 443345579 456816443 465738022 504601647 746056306 964460207 183564689 106349899 602762087 495540136 372837540 603859577 545250226 671573065 959518443 286598941 16822117 18495632 70129232 880487536 217709412 818181804 858368507 380446360 222730182 770243023 411627458 26906242 184662630 445912796 197390817 803084021 586476104 461207174 354047996 199310080 843965533 884333773 262111985 585231797 949840251 378097625 425696746 887359895 788571992 290044327 380348151 411534113 289196214 347666127 872736866 194650270 65305909 245503900 483836128 905143105 3805515 390641016 385935869 336532719 541525570 265677169 938530119 817371620 115021186 598826531 526246209 228243753 719170122 566632052 570981429 116812399 596002666 463321910 348200459 616146836 648454313 373084587 603888347 460679372 419764032 833108164 394559308 65517212 983754171 466284277 753721650 525639177 468667225 728908399 231047181 212092632 913450815 294697324 301346463 546192173 457618999 967582297 594449830 537789793 130039989 201455160 521721575 440247680 425583627 821725404 367066225 127184356 107095652 195521710 181472307 232302934 646388334 528898015 697772038 715201193 127438526 359880567 769657156 68817330 91392221 683937146 334743852 602205267 202433124 867866135 976919881 320773272 839579615 358337791 171489895 420778739 384354827 776063655 122776282 543671341 836775088 424685441 195428269 722229810 398248433 158126836 441339608 796319160 871627339 909595677 979121641 917900957 529436811 71405578 329337380 366487390 336150047 385823697 622537235 955587270 428737106 391235285 893499394 71199750 461977471 504340724 329518194 35170753 822463361 740777210 776813545 79527045 597710963 347011895 827526619 84294626 558506507 90185668 168511918 222587516 775102748 527022443 635526613 611106386 700892185 302573347 65482030 56111372 637558998 73910435 790138896 109675609 198878898 532098875 963011851 489500030 218490532 965725530 431112611 989419380 133484451 449650527 306948147 613514281 79550116 976680216 280200530 935607925 831937341 438120091 44354846 25476072 861497990 384102225 120125024 292002704 556522630 168984228 863957426 906044324 267851722 778481023 7641553 822553428 946886947 50218677 930481982 42609684 558871058 872822791 695800926 394117047 10739168 967142405 522743079 817831542 560336207 457544144 231753882 837672441 673245578 387116751 246285725 343482919 643319544 355794316 494230850 688754326 963090620 85775561 462524214 699526316 933837884 999327023 264953779 276301919 476040343 969678634 874527686 575569057 625749292 876741551 265969336 296777810 774010888 942833675 17563057 151800933 527928301 34876814 74038631 656083126 890515436 192511716 473764964 477074332 415681635 542240872 567213996 357836378 277845345 843259773 675075862 935972984 410559814 969861436 133495838 821870365 158229096 359492405 157002480 742750056 711027511 255786515 901389364 631127525 558411129 437951239 385441080 100411454 70037813 961130022 727570567 862105678 498282109 428873735 427292292 866649475 7971747 821770132 695777973 303122333 638682232 838703676 420175960 603473417 38760599 593707903 30096665 428779276 177646650 648615213 323966205 318845204 895289901 340528804 129196454 473260035 450656265 613773164 195967801 946256715 16320325 91699027 552438339 60858742 667415766 334003351 183105504 446229626 288510412 957723999 241151036 97627586 699458905 513709416 682361458 344997258 591186613 494732666 229824915 95394328 208788617 585502609 966007392 777664302 159407471 885490036 759154730 107258369 806002245 141135329 536136069 753086370 619734658 370085066 469910640 133998332 857578808 824790426 695555258 847501896 690248162 414773982 57835882 83925147 385609575 62874066 32637048 448718613 686098092 939273513 406832559 190686973 324115008 57166564 557704989 257464613 478552584 505992683 891703055 205685444 214595437 598181646 816071755 217360148 44402808 963193982 602825263 543912210 447791566 351269900 887490444 566421101 627324161 997008829 917544963 351814861 956185363 328273310 561810526 782926365 738812757 907134944 954645446 362621770 270988313 835169488 304071612 91420343 332505613 189921424 927320285 660796885 510259808 563703370 511537435 565362505 970463046 196888849 290121047 900152828 324272563 351234417 314704908 133668976 811269648 13443284 625111243 642314822 383379800 316103791 82835678 413858778 505239026 696259227 971822748 993735785 664239079 605455893 326154538 573500609 71607872 212646268 952300612 410657960 43188318 735389639 607565749 336833054 996178425 468150794 68665650 417330972 469425935 637973228 359773045 495089463 32878197 838901941 3366987 496976717 987282192 198460473 581444968 719025316 179888080 415471623 72225337 800018663 15114327 140283889 962648921 924717547 174113781 312015042 84077565 3725727 626694242 932180238 412451615 583741201 655481463 737116823 352902522 587153191 570574547 447441524 46362545 562228155 864269709 998809742 67696896 853250887 758056394 39693507 766316839 378708265 360634803 411424847 797193335 987728016 89893703 237212193 410201577 601074253 611294529 975697827 138404206 256244615 628469074 13038983 221359110 242788656 216951281 341328531 711772074 484214668 30605340 904309095 490187086 268530118 29711421 340477058 199900883 337748320 273871401 692227344 733924078 958641855 331004108 435960921 543109789 663756458 513815805 209260986 217812472 970864431 680504976 910578442 91450080 750016466 654217978 436684754 521006306 582306771 336559764 840763629 683417707 630996417 980344145 607784040 246893262 206245226 439535859 343857219 623382720 221003074 763800558 624189118 577788253 752852615 292604829 775887050 463429520 423142636 357058983 833607203 149479442 774443159 695067860 160118895 307943419 386766229 295200139 827846127 938945162 340414458 157194628 568348990 223629236 467091349 155312502 48662240 260969040 376051425 953644134 316437577 383605841 877248786 139029503 78664780 62805028 752436567 24578338 353300226 857564681 716932137 743377801 310407160 16725562 387885041 830091714 538577939 117062719 251499295 635029670 50144669 215656760 232824615 297817890 901348251 843152869 564827078 947169127 233949647 902154124 262836690 345523141 282536263 469949904 406011034 312709241 487529104 312565229 49120742 251996035 359714376 600982040 618120567 712028404 220491776 2230686 331029534 762220141 582419344 725214721 803134963 132529911 314797422 306768975 521437073 297289323 854883879 333717706 770301527