400000003 755555561 142857144 490196082 588744593 276923079 135632185 593582892 534850644 603948901 365217394 435102044 596086657 994555361 492332103 299766902 995031063 306923364 755577761 474254746 780574561 887141080 697323272 439301497 487089889 221563344 694412015 784039751 6518905 195637449 834031752 515563510 764448440 920765901 501947861 817949935 448143180 86325440 586309768 177210338 265279301 230281937 702677568 790135218 634205578 454112180 823057650 464077777 554119883 22314172 379966851 634221923 605897069 482729467 350536059 186548674 638807675 416565793 706201473 347964750 879475699 692626511 262332329 379181374 47117663 896382472 517912712 172214648 383216895 275030920 378800150 794248902 425042375 859873913 496248711 506225226 933354219 717527121 938237810 593428924 177781974 364428482 451205700 486085021 496184257 982457911 505247650 526688117 945683308 19344669 851755377 826235998 123711489 154070707 945170473 913437864 984153985 454179102 728909034 530067869 450684185 303870239 894386550 18484734 940077232 767666396 667295500 722214541 656447556 568565892 937149198 729601589 547480822 891527244 791907303 337145233 675842676 716737590 311991792 423288277 433354549 146262678 420469573 169531245 899157866 951653433 663338346 780735892 446091577 861524778 288017384 171366410 128113780 227534217 831076801 679994628 897883762 326515693 469785014 36862238 113562026 180174515 462830877 502149890 163836496 873300085 481413488 251355604 954958747 890503652 211837549 756214170 221349588 591514431 625518435 394596808 815343080 245518563 212172066 375484181 5270358 619570942 906969018 465503605 460526259 131061890 612756848 544591959 77781119 192101491 411389418 739374440 357498412 214677724 822187276 911409807 53250959 832337429 51852543 224380575 130969888 44884154 856199195 587277953 828082549 940273861 595667116 664081081 897686681 489868632 915742596 471055346 120935582 706226246 700416875 961485234 603561635 734792157 597884301 963125900 846825831 634247437 609236883 785553330 857902807 12599604 672803644 425430607 794159166 718777278 68356485 460286846 270084097 363655406 112880669 399599517 962615247 444832389 592543439 50146582 556804534 538549820 249489569 594282356 139180168 94795898 384332502 749499695 34677824 450684325 887789394 107429657 476627860 332775066 402616364 335387096 758600194 998748305 928737384 875482709 842656546 185669147 159457299 22783740 465759827 984932205 762014488 572547069 584068844 936813692 330915999 228837494 571507293 863935886 704295897 855024016 123983131 134898449 558003211 571611901 906919051 135472333 704487590 182239925 592497932 485114820 332283646 394410981 666296303 531697737 719196142 479293354 340471442 355481835 381026326 299424777 853285573 549294211 682965974 246549031 123651866 516735779 731122293 890002835 738679782 681836962 757230111 463090036 763374703 257508441 162174340 263996551 607358065 762868684 845185551 525139287 704183310 162161746 668005578 699062489 722422471 70282797 712227915 926465932 91214709 646060530 83884711 328206890 160661511 699001252 223620648 557159972 83987267 807684287 567295600 268978266 467828227 478374059 47313552 392412327 954872292 164538343 5630126 167432728 62700204 11691398 18991247 558229905 816381560 260638976 441694986 649742872 840428254 703074398 175626883 843957871 714502380 271862628 431578802 930445466 404858980 378818790 591995136 217488642 864490282 883771189 177559552 633858990 363582091 668359980 890406652 427009753 795115277 721839287 928458106 692052858 383898959 136966757 872880747 974709356 865882742 837755414 824964908 741975973 795641542 25779326 367942469 440885743 361973355 36752532 550772874 892462404 17695251 752653510 826484968 347392713 881692632 120282956 544624258 509793253 330655955 318430178 916642222 740867874 632817982 955930124 729426274 383908426 820586648 73133461 509234169 378404845 923461436 955022016 27647371 66375741 121387211 491192257 447708982 953005346 125664274 554318299 663605269 626020814 530807508 187202575 935884493 981027784 501445141 48235643 289217669 553049970 360498777 230795552 85202324 316290843 868574182 922827313 135464531 661340538 99442081 700392030 146979961 226313603 111658243 16376907 294815547 802363155 935070991 137168719 406480934 397796183 889928932 786730033 196777788 637667436 333371235 494993112 204302894 206666578 886347412 833908531 606395829 367824593 781967790 234552591 812924426 569829037 575308128 702886119 936323680 81921883 466398810 506725690 657738030 5667302 561606424 374351005 774366003 262481859 697259736 518429542 916885130 294191300 958358904 304637526 982679984 492394025 14140118 961930967 368848224 971210664 401816064 292470005 486307780 165273361 902787848 862546374 627022480 732918550 422283182 181614680 663251505 448012287 252275815 28141835 9936983 963336469 746358250 633222980 439363845 868815891 387537740 7462973 882783014 951873702 393401399 510776689 702913735 727990156 54943897 389901169 22727643 638971620 639866471 571468689 894285575 846640081 59606794 437453365 643654628 892170131 90713427 352422908 277019388 80762443 517871598 634422187 299287816 26549159 319245124 292073543 75112339 998277541 517558812 224759032 377503323 928833139 797282939 806195490 119005258 806600120 684165159 194046016 996023140 476881370 745022785 486790261 12045615 420052134 162090593 457051077 658202135 279123133 355642076 87971092 444300376 799748605 905688672 876812668 516890858 976526721 872996519 530411168 49997346 790653064 440289944 46629443 388392794 877845017 475362489 148385160 760794545 289116472 262870863 357330655 924020175 121945860 194158250 456239694 467219555 789901967 335922873 462420999 441711026 882034800 355744417 539221592 568922434 170111046 848590692 767004946 815078987 729888843 627324303 520685942 133160513 663990117 768740764 127395108 916630067 858338282 508031065 190060127 935417923 21721046 793957317 487743949 418468251 891228023 983709479 816405291 687593546 527609270 386082966 889910172 515864718 450558116 812175777 459553408 900381749 812537568 307758810 92269543 171674715 362993674 486293361 914849173 566867811 321255728 578634482 161209887 614387169 277350597 714165498 959886459 76004631 448960239 485806606 518218263 210097914 722861609 553210958 109021316 193845638 783055980 519391076 847844957 820744116 466273820 149750449 992644422 625554180 163217736 74278730 151668635 643540317 691719393 173745808 784538915 192917571 21146371 895900997 747919891 775701223 985186385 639118234 516098319 932312468 784556758 438459882 674190479 43302275 683825373 313377048 342266526 721714853 868372084 37208506 132014695 538526691 781122049 737971446 281224260 575536767 154947793 573836294 656721470 674002003 645617769 108824437 165672194 683105863 607801063 319140610 566921786 887081722 368059037 766593735 973739438 751185088 353670149 784303586 898716269 785579517 917023699 689470801 861581560 766461723 121348780 870614160 448749004 858136069 237335524 384485502 501222658 85836872 577798812 535182803 452834875 842073054 180871837 805433301 696921835 191169421 375133633 257943682 898341075 674427777 196500513 535567754 994582249 894277856 456007777 642521619 937464070 607988248 489705230 975088020 376828937 592464382 399172454 989687439 628977073 274528452 836662189 214415230 72844687 936552618 369654943 630836500 214621347 737118266 88364049 161751006 227130968 580469082 123211565 559065407 733598466 966472608 705230493 841505440 741638562 30816055 895067657 19687139 757500069 548319252 64555178 912757107 373862543 319207644 751186584 280156310 86360643 73097902 228365680 538879823 561924727 230690599 19486203 300066399 86830318 93878330 860339508 245059310 274295893 147668758 626632100 787525124 114517291 21113531 782353677 413212984 282496260 45211229 414421875 68682982 692167613 21077623 565567265 657382881 270696023 586610953 659721648 98535818 605591329 994958539 105398630 493890262 818553160 592634818 48799949 808258619 623397689 951898389 840973417 175872017 464017952 955805374 468888987 257053252 943846881 513767583 676127239 795855054 845901974 225993359 172420532 916269110 250704524 188072030 134231959 880557648 70348965 934929463 614693570 203885478 832754950 486667906 803373761 486372576 697633866 762782052 706547948 690530571 700554035 95369867 595383308 483841654 581092933 44157455 17777944 191781535 950663657 279472284 519748538 710980663 32476875 841280876 762031165 668027470 6479666 245882560 898086004 534663273 557041267 279381567 972372672 923979598 976133900 148687203 265560211 342477399 923722101 18895728 664384737 834470939 274077496 46577456 933942705 797384291 599459837 639882613 142223359 55819509 423833035 998096801 437416552 658165366 753332049 702981082 101154029 110484730 506926579 494153564 705537868 682343745 66209030 557503589 198680673 78719947 819068419 660565858 29739550 252225038 398330337 171512671 736653452 275873700 676241534 881201460 644504573 9868808 184064212 114353992 231992374 990830460 507546690 397847805 495956186 437403875 577476366 216988642 698988014 531239797 726882947 701062841 511515086 905014175 237290533 683875805 107870926 219010998 619667422 999062243 928964751 623641031 823462293 735343231 759211806 681550260 603283182 20577446 850867616 325855146 179592928 7416633 683527085 802587214 235556014 14335113 143240559 698310506 102717724 636080702 501397787 269621414 934488439 751617446 977568399 763461632 692767727 570703151 577598479 692637408 850371291 570079221 301407011 315793690 816536330 740745899 252788083 251767568 114516511 977176704 848366062 626536103 71139720 872539585 423488704 981433370 409652848 634805232 420876910 720287832 574345885 782933992 787604272 763103795 519967726 72234199 90738425 774841912 251739165 939995455 493057977 602769570 609844652 250298790 51533897 654070998 268899998 277453895 224842534 348834988 639670630 598576125 410838198 358848452 982984936 240104243 737072853 714527715 5457755 555637931 391770761 296102607 502440844 531950677 628862061 105197182 861098713 380606883 644026765 37354963 705969476 79936620 634912991 469878429 189779252 165478319 588123267 657837260 899319746 131886894 52381527 21442579 952031005 304861393 743093211 918515218 296955488 370923933 316871092 545266935 778488990 378210084 892944194 880655985 410588096 219058676 994097814 146504618 604765604 888186313 965142530 926417410 336192208 938157745 466868426 498695461 607751170 239784958 995015203 36628678 259579238 25000917 683394536 469266511 36477949 700487594 528690466 648582051 337267956 634512809 675303782 427844374 366348706 366973172 917738557 504654378 312950547 742590807 828278926 813002392 409497538 909919343 779325127 429139286 150009852 530355785 59841531 806196083 686385081 849505102 27313241 582803054 477220818 792264279 122672271 940248509 876298757 450796036 823924178 991104427 125657691 923640558 955162917 933247093 191127560 953577735 648428188 879547865 266602645 574174389 483612733 433669221 868181567 917665418 68845236 991002065 492886138 842660463 805455542 945441910 731453799 6597641 619817430 615831040 670974318 423452706 424003823 60429072 466136546 74296640 452432111 81279596 557305073 234965705 964950590 30549871 440928095 421745559 284969126 524779999 333896080 963549848 381760015 272981753 231590401 288124567 20068046 35097983 396146111 759686899 759130174 143133207 547676860 522936327 702842060 259257716 145842101 663406802 206207645 840692668 298349604 739288864 23239858 82579321 864607577 329391220 348750378 753019594 918197819 917655172 764605605 902640717 365422821 537414230 370954678 587970812 952220050 950247350 264060728 908051535 772161073 648432687 899588849 846002894 524263791 938109153 577618780 974549613 669469647 66881488 984474612 779323418 874801906 885821155 463420851 668491347 354108650 356695135 388935287 836729030 472702304 925808599 470702284 122909425 870077227 391540794 323459735 592882343 961325208 921582792 982337896 708341643 408254695 799865731 750059582 918409306 1819579 353653789 779564807 421997450 532206374 857273005 327947860 940539812 121877557 568998892 647217935 309505604 516566480 918624314 722984579 36260254 391337358 929709077 229243222 603079639 582148106 176645427 647573715 326238037 264026926 537374621 813261788 841934336 871394064 898750630 298851066 81953099 779363010 773792550 802157337 412330914 688614060 788690670 951814632 286349707 576568395 925256342 615502354 193843791 613360410 986419907 710105172 821370277 991169261 435086597 128505691 397729137 888070378 276388868 878913557 514834554 43706751 470777779 80082055 117941260 370860455 239499379 235741317 979507198 333674521 913215327 950570199 92911801 791161398 653488898 560119780 696761075 434672668 447375676 288753672 938129996 163780035 560419657 985416274 816219727 718266131 989415770 648918983 946169507 770287990 302927170 327929301 198490872 301754371 180504664 300958175 985137420 813534037 390351476 594257727 363363447 952115685 853375422 710638577 163125781 55322246 276273648 200582512 117201522 157493114 85223217 899904015 96253635 882165327 908008381 150173763 907041093 206411268 210045272 506209907 674512681 487064584 778370462 287471572 253004410 802859601 169448504 722423861 893206338 792338471 772987553 423386842 159071618 58902534 16604305 131111736 200750798 257589737 202455395 921477748 227496424 868488983 928674984 336818259 217339107 486939604 50753537 402239129 927801419 158889420 281858914 258986238 457936556 352914991 300292167 250219426 381545914 857355417 611772750 479970056 364699169 750936118 636389815 53123200 488989008 866125581 818653703 41381259 379952750 118730281 961701544 636775089 196296508 554953460 93513755 337428796 475245306 264656745 419636162 649375076 505214623 933336728 880684115 371693702 841586420 207454081 561760801 670276518 187184584 714862964 373629011 753468604 723450428 393198495 91578200 602723663 237608937 450741703 659452969 390490303 741259252 678285487 859380992 282251004 947700184 180329170 370541418 712256078 874841190 779685108 794812403 641763688 104586277 778022306 965724152 808822082 694585497 996893454 407413762 446418083 598089266 411514873 120348782 68192679 272150267 239855656 188981574 334690334 568280108 995879253 993940867 954808960 125131783 632689098 661986858 418566054 918677973 447794890 293634030 940795823 653407677 719744855 688731956 466375734 389337810 198199760 737808180 451532758 543948621 166166456 983598380 532704393 2477388 403251894 74948371 2829005 371479910 776954187 338552397 160507216 467803107 204146964 455286209 384482266 760708412 953619411 535872773 711876885 383470354 486507750 901949419 836602819 718300906 413266212 944073326 566427804 682019681 793262813 720515595 274552729 843115700 976541564 612088073 179558141 877845175 792828089 576025675 163353122 540816938 54082504 603216929 605930847 623725185 131358828 394280879 53333778 912146772 398583805 816849414 909440958 336814787 767405184 422704435 426352453 745645992 854369545 105042661 432804229 152732619 329527903 147189489 289684754 765396837 496360086 457067419 774995696 195465895 188360975 335712344 18894945 950545894 262874391 738768482 495078643 554749680 188729943 721474874 878052960 894168785 206581500 749444518 749269257 184996678 605144081 911131836 455750584 282967153 681277770 932018595 954158401 102490831 384514643 77365792 566999045 469262740 376089837 41806544 927593480 202679318 347842854 52800559 374724535 686699442 482118961 943847756 351457607 570162267 174605468 326354928 708849846 845022342 964087586 419750844 300108484 604121423 356753162 435426998 986524429 211752947 35215732 997017077 978016802 798285870 392293695 210765806 887351077 77467542 439077648 572682610 968022571 164007668 551868861 260345204 380013383 696798800 86262404 805174641 610626244 14499892 530557079 872758022 381813957 187594654 768086888 363519129 719849265 664271461 785780295 265125895 600925085 414665401 924683831 217510977 579914625 667754711 676570552 925689413 857205890 989650354 942926888 812387671 282620191 602394679 857067476 945522375 665420132 89857560 941026237 470149736 736281690 446821695 958787458 837092282 370521011 139174212 83322428 469970341 596549276 268214195 741810384 298507412 266586914 757882264 576525219 527662049 327088747 295729979 147421185 733169604 103925974 276655212 907844068 445185836 469334984 656247306 792451187 504982179 841283662 667181482 330784584 315137371 672746216 296792237 503490146 32244470 164346774 491061859 488216453 418136007 422809603 288112573 287718737 234344057 600916997 896504905 28979918 560234073 394611645 591856379 738081538 341718496 728229948 137394275 601004433 980619979 411997056 939006900 135323922 377592366 922507987 467265368 746257811 772678497 471569685 228426920 652128527 314694578 358829148 217995480 955874787 707857461 109352214 811505935 942656272 480108739 488691972 804707822 359136238 201628771 251239621 225351670 371348227 893561309 186009980 401613836 410944186 881140988 11427576 686284007 902798731 847358436 225514511 409397916 621948009 618444931 572888768 569861784 850864101 360450160 703144431 885664334 914947287 669187961 913259039 831119995 642775722 404124489 35209207 183023040 985498269 909845795 5959074 601088012 373486103 2159192 105938776 15739725 415234968 859539633 365834082 968485344 909178871 990093871 356836421 609302584 892598278 251765993 142627488 486869619 482528648 878468747 478835906 989829703 752536974 168677332 800432552 683883903 945325894 794967311 937167675 353769183 974834547 997092580 865941183 483827526 12825495 697597159 616107728 367085369 27418499 189019147 14304800 438942493 445306108 485797858 424106013 568533431 386086903 125828619 944792079 673354332 437637205 192324095 964142351 598487771 678754719 374612643 985705905 137743392 306158418 121200393 849816519 253251386 778991387 241754836 169298107 988643756 153828321 793867666 287986899 557073153 784237251 392320227 977160713 834640429 144021961 285928876 178015439 183387081 454918513 105161827 850782039 520111140 647030622 372222769 262171576 100104241 611078158 832395310 563087623 310901814 368098128 305961352 478915506 320986471 453226698 451576124 663807927 617714295 875578390 659802089 876210961 811935790 312663945 660864088 862614394 211566550 738755491 652132385 476181409 881810883 35974485 380040482 243434784 683511335 624759968 653033915 836359690 443917485 184435969 72876793 562543943 870681071 552161029 641991379 868631706 367215621 521698394 126844143 290833913 763962362 433945195 835713328 511848160 624867525 911536180 629799933 919098183 376539468 591525615 175786550 237158024 691990510 222544557 159023533 401907646 47676853 193334964 114722589 798419483 228777286 649358539 50960357 77628019 716287420 910963255 992322546 681687902 192585133 792970728 813768560 118679833 181042449 687998589 744175731 399424060 637782263 489459659 258758089 530789869 30573793 374382118 548092633 463266720 537953251 442240829 683078100 51834179 625550066 146521896 930557988 656536856 355475316 631065900 69222242 846797483 808254980 576351283 996834701 169982792 336255675 287682682 331424261 723340097 688921962 30847522 737390814 992074980 389904670 281338380 709694206 675361 291533781 819632079 851812453 140941643 907869651 489836564 977427450 847677527 724292047 419325876 739672446 440213562 362213164 127946013 58961179 65517683 565574950 686228455 497578442 647171227 80624677 140587363 801383639 503513682 267934251 920785246 611221548 868891137 880192732 681099666 626286618 306293638 575021901 152104038 723142211 677824168 780662812 698727292 476972917 521332043 247843154 322938652 654541404 738500774 589986878 529893870 244721005 982135092 364192706 928601505 589869349 558541902 351361213 695576954 577119917 831229923 922819016 780353700 533197796 434833028 90575221 557879146 696969859 357726670 649333847 25526822 978502150 993986876 838196466 15207434 680668629 75635376 631121820 24032276 955159895 380751390 441673736 155988458 548615166 742020574 10039561 629046339 882161555 949845201