#include <iostream>
#include <cstdio>

using namespace std;

const int N = 4010, M = 250000, MOD = 1000000007;

int ans;
string c, p;
int fac[N] = { 1, 50180518, 154425679, 419049924, 641102369, 364780107, 448516387, 313981369, 578095319, 86051964, 119948046, 6473915, 5832229, 280841874, 929795683, 915960706, 259081142, 680500135, 59433257, 777579921, 974067448, 443699470, 261465122, 603788888, 316220877, 971390710, 663134272, 881294189, 690120224, 31722990, 304661605, 707692373, 251368199, 963306784, 704262886, 579475748, 980250487, 734818225, 386267146, 100884205, 682498929, 133000963, 681184885, 254932760, 134623568, 357323104, 427907847, 975779652, 95936601, 919157566, 140928835, 315458993, 933097914, 776765946, 391177708, 545976183, 167332441, 513852415, 739650465, 753653734, 598816162, 731423907, 292015879, 593871940, 336060741, 207290943, 810640932, 955078514, 248744620, 641859244, 892704918, 315949401, 626497524, 107592271, 118508240, 734189521, 288843364, 696506364, 406755567, 475021638, 491101308, 660970291, 668723114, 154792097, 245341950, 399096325, 560364972, 33884628, 565768255, 300395832, 913230882, 560677262, 246899319, 707244298, 756627904, 657076885, 968999, 69887676, 7998896, 192791675, 586350670, 769890636, 328019447, 800219212, 638587686, 931841936, 497857012, 655344665, 881746146, 840019426, 526658674, 612357186, 19426633, 553937377, 560607302, 807333916, 850500036, 880872897, 916364742, 810805566, 76479948, 322985309, 732041432, 174482879, 268124147, 86516931, 30473806, 914380037, 842267748, 398602165, 878381584, 680656982, 886294336, 909101450, 73995168, 580824852, 485348706, 122117390, 771153434, 264030845, 463847391, 968395514, 72518508, 576302511, 544075857, 901200113, 264638935, 152184821, 898187927, 796504086, 468116664, 790455369, 798967520, 965695346, 359622660, 448291975, 82926604, 611143741, 59761470, 903969875, 723816384, 685474055, 320608814, 662323964, 156530778, 584805623, 278224088, 543834126, 721996174, 738626268, 222176885, 243683233, 299085602, 286707267, 814440466, 541988189, 323604647, 533682664, 359932651, 601233044, 172827403, 152460596, 213590923, 33229645, 398699886, 91389423, 983975503, 303301488, 530389102, 73104194, 619965361, 374924406, 294587621, 222036968, 221896631, 480109897, 813805606, 120043214, 676243000, 473715194, 67347853, 391673277, 557470122, 974946838, 497478507, 689208753, 494243939, 581484231, 196447201, 50157541, 726686688, 817437629, 722054885, 293079212, 435396042, 404508102, 228338256, 222897920, 574429123, 926809891, 407719831, 758320845, 583676448, 82985148, 762479457, 415304400, 342545697, 427418645, 746536789, 828621886, 3669475, 949026022, 811667359, 145285614, 249780014, 631030761, 778773518, 442531044, 306921081, 242462872, 27368307, 77771567, 467386519, 4370529, 438371670, 995836327, 44635470, 827994736, 59469516, 28160617, 498440078, 25984366, 5974669, 824164565, 9221150, 855559028, 766196482, 958335419, 679975009, 667185460, 606322308, 9559926, 147307265, 89921971, 86609485, 739691207, 435993596, 608829799, 889750731, 353853362, 607649469, 481928480, 340941507, 977029829, 886844916, 534028979, 371263376, 983879272, 198057134, 300726763, 625544428, 476241984, 527225600, 339579929, 788878910, 401616424, 743572663, 986102459, 808412394, 818701791, 603835511, 513189131, 996952918, 868842432, 409420559, 163232029, 585237443, 711783886, 307534126, 581374971, 1669644, 79259751, 210601394, 908609880, 361786913, 893046012, 470618701, 839717177, 480748381, 749016143, 550969600, 197931559, 595143852, 997893857, 901560583, 985470745, 837229828, 394853292, 727223125, 80778437, 199888908, 897424081, 180269718, 288483853, 526807168, 204998281, 899715096, 147218753, 579691190, 249046858, 775147177, 337926751, 145404005, 681418236, 401312408, 424113478, 459188207, 732957544, 552930818, 232777869, 534491822, 416625292, 669251006, 48075339, 439729802, 718791818, 504703143, 192610639, 840398449, 453095025, 624903360, 229348550, 899297830, 656687365, 556957390, 518355602, 235861787, 849506324, 850796519, 171990028, 888050723, 761457408, 834568419, 471765488, 656116726, 668120697, 196710441, 812015902, 736550105, 330330359, 857549983, 190137617, 440902696, 316132690, 63145422, 646617630, 85990869, 660571898, 807209645, 523043590, 884343068, 406752816, 132114154, 39076031, 56305184, 162501223, 973762120, 522647499, 973478770, 593853757, 270603374, 435947909, 168891766, 561523336, 217608725, 67114373, 804805577, 449084887, 641317239, 125126440, 927880474, 251289824, 157803266, 765558904, 876297919, 180495840, 189324843, 640767445, 934814019, 239309967, 374934947, 791217839, 676405347, 705889788, 30657162, 591992125, 567277637, 324526871, 686637388, 156725044, 112249297, 982528783, 631678522, 545644885, 44930135, 456099497, 954976637, 73036821, 39417871, 325644102, 977168136, 720288971, 47401357, 288148411, 809639670, 285927540, 108819476, 519477996, 250361638, 878780790, 281863274, 402597124, 410799320, 511989267, 60168088, 681009252, 142840220, 937233252, 692636218, 292413264, 261319829, 485726626, 432775082, 541754926, 200805416, 311504863, 14235602, 63335394, 616435469, 84287295, 770511792, 96895351, 174624465, 633454181, 400295761, 167446553, 580310773, 744878746, 697066277, 178528305, 102309489, 314411152, 421835306, 676782859, 228266417, 783864754, 220108638, 166858810, 334251014, 261544848, 661224977, 851013614, 812005526, 665917774, 261799937, 495178170, 356438399, 981467959, 168203998, 393977287, 835330203, 882285670, 802214249, 167565851, 316146626, 825930120, 544064410, 533800842, 877125482, 450607735, 935080803, 168503996, 576478595, 62912270, 583967898, 34071782, 885117574, 713158620, 211768084, 315395810, 672118586, 939316799, 751231582, 479341187, 192990501, 837281502, 972424306, 244644804, 125666214, 522618190, 623534362, 633456379, 362493992, 106410541, 335160196, 422499436, 924982465, 657769953, 243276029, 846044660, 85322142, 334528202, 554749550, 632297821, 437447268, 194789090, 60050552, 135925402, 733942454, 866577339, 797848181, 28171985, 643938537, 21282665, 395891998, 231013739, 435508211, 494663390, 172428290, 410243078, 422713438, 411403698, 159554990, 335001889, 812391270, 604125905, 887420150, 668082332, 449205554, 377054744, 970055531, 969968376, 222343461, 415570957, 250388809, 217712473, 689850274, 760739075, 487998999, 884457327, 748359168, 329883103, 856259313, 572557213, 29781141, 601327885, 82104855, 861553992, 543656809, 677599921, 232253360, 758934169, 132581614, 976001516, 513365505, 321373540, 443711760, 719653575, 244109365, 90546446, 956163585, 405020688, 1559745, 915310808, 193109503, 812886618, 695345956, 568939003, 36042990, 235609235, 261384175, 768691593, 953585846, 386455793, 849009131, 659065850, 600281990, 825918223, 323214113, 80831393, 762863177, 858635499, 747664143, 210306859, 388430024, 25622409, 444090941, 87926617, 396611787, 546936010, 659224434, 324526942, 991836842, 83467123, 80729842, 409109146, 231753353, 641290181, 570033864, 905913526, 24300293, 747854366, 664989237, 57375259, 653829979, 473372076, 827348878, 439147086, 7704403, 815156180, 195888993, 907760783, 30813167, 961838486, 576798521, 348380456, 947304403, 20999669, 457882808, 867003058, 137550654, 815829567, 731551699, 546621827, 995246811, 782564184, 212938473, 898497340, 593989303, 331620540, 509096183, 79318301, 478919708, 139609452, 827544702, 852527478, 602197504, 864783272, 678320208, 975254490, 496537397, 197346690, 677711203, 252191884, 386677716, 241051648, 289752035, 863428057, 456967785, 708251942, 66404266, 932229123, 208554578, 45119221, 555972231, 157658774, 680796549, 949023861, 195290384, 966054139, 364911332, 546764650, 97136305, 604368046, 294375015, 272880393, 349551356, 845424929, 290196031, 428059156, 785113347, 96985836, 297880214, 23235359, 83489485, 754222558, 644670437, 527942477, 66247239, 110851843, 135500451, 445331645, 52167191, 633799488, 498572695, 973699797, 307390891, 364846814, 499606972, 76286067, 547665832, 795548462, 932668364, 590807733, 143066173, 632128211, 499761057, 186300854, 350016754, 288480859, 113905458, 709755487, 917404120, 606670553, 493905303, 102838342, 296269301, 353144768, 86726457, 811888735, 996122673, 798173587, 809339058, 193180428, 23015220, 55861328, 835803486, 44899292, 602139210, 37610337, 670821828, 611816110, 748566338, 411293772, 631823487, 565520310, 187348575, 940303862, 382748764, 237554637, 109838563, 15091364, 94904185, 780977954, 574053420, 392208799, 973865472, 274399323, 105574531, 163760155, 752194712, 127281208, 304173654, 363104769, 83284607, 258610236, 542432219, 808205344, 536973025, 450988908, 34538816, 503777150, 283727326, 256983152, 325636655, 81442440, 243291133, 67947043, 437843114, 645366082, 312536013, 558022461, 630621321, 389538807, 682680116, 722670891, 26853683, 278654022, 611209607, 558817540, 933245637, 629940486, 894820080, 809376987, 616368450, 871418457, 198631047, 829549992, 238971581, 352487536, 595959409, 672398528, 511371690, 267098585, 683585700, 647902320, 557301633, 589386102, 253427558, 525116697, 911398531, 20284688, 246476028, 596636467, 848952161, 140580859, 272634280, 650776749, 958992544, 843194652, 325284740, 731179455, 925152039, 118437170, 495860053, 451556823, 914456118, 788508590, 841108662, 450677610, 724691727, 292911692, 445713321, 50697395, 636817583, 734002852, 814845293, 36295352, 238087006, 954446221, 170238260, 30646237, 946237212, 230801891, 457433989, 271686306, 910291942, 763604371, 599284582, 5335057, 114985663, 532934543, 17739814, 19912403, 492237273, 629150786, 194710256, 342244474, 450387329, 391570698, 471822076, 948232111, 834860913, 785993517, 831422618, 574749701, 763017204, 133314423, 100582220, 226847592, 368925948, 541510595, 128260642, 942789776, 475812562, 882136272, 917840849, 641494632, 740594930, 972553616, 51595198, 252144386, 45060610, 568320974, 994271859, 90970078, 806047532, 844782619, 476604857, 257358749, 464456846, 976794640, 835245756, 168194948, 172115341, 804157813, 545338291, 599598784, 75307702, 202730650, 344053349, 945626457, 116261993, 700228825, 945918607, 869726861, 562519302, 306551674, 281653965, 856213472, 268838846, 459136580, 635794655, 27784049, 173784895, 195823038, 258300540, 900411980, 243624360, 582688934, 722807834, 617913920, 61570384, 534263309, 691306302, 667796618, 481661251, 926951316, 752609613, 431760716, 938269070, 179206505, 381369130, 381881589, 95182730, 966530892, 885113729, 173657240, 91068149, 588337788, 758827428, 271865096, 115435332, 610160522, 617737077, 114135134, 495022305, 492342417, 641462345, 306192390, 136026497, 267464078, 537165746, 279269277, 506496856, 174970822, 997042337, 90514504, 710729672, 579006599, 185163716, 682921198, 113570024, 146968038, 90871114, 168401529, 366384665, 439086433, 783454081, 674470294, 564758715, 46898789, 75276833, 472326685, 270239666, 395559459, 203381481, 419744205, 277118392, 7188448, 639320111, 759485230, 79874094, 468710311, 366910724, 103414281, 702807165, 281297120, 582981397, 381725460, 112390913, 156492285, 245293699, 729422905, 730341625, 773141422, 338718815, 97158395, 103056890, 875857662, 1840485, 343213463, 677948390, 297735574, 391004385, 737700456, 339464594, 96544119, 145153314, 860570333, 167240465, 74390429, 455408691, 244668811, 108312174, 396616574, 155105232, 771683822, 839079953, 385456615, 605298160, 927359747, 479334442, 702962709, 540479427, 267762479, 271788964, 212339018, 587614008, 63666996, 135498044, 781772889, 861409420, 835801021, 277717575, 400629971, 938160268, 979782104, 591048681, 455215137, 115579849, 737471837, 811637561, 817145156, 629027151, 248249832, 353339603, 639625455, 463734842, 510402229, 889410460, 312462646, 481429323, 965800223, 839849206, 152903258, 296744952, 72253743, 192345193, 970717824, 181445064, 467121659, 736265527, 368455044, 30430299, 396328969, 316439118, 575162392, 844263530, 57185601, 217544623, 464215765, 366151601, 57828926, 788132977, 693531911, 82871673, 276473015, 618898635, 574689359, 693326853, 754346899, 183011467, 349250965, 60732294, 504593092, 380858207, 18113296, 421458551, 660639183, 996097969, 181740107, 207173800, 751843095, 898554793, 303227882, 970529845, 606286881, 335353644, 485523580, 761545908, 763321144, 54062950, 600987925, 385459037, 185004499, 611251733, 345339647, 825396690, 247939378, 419363534, 628748445, 560597174, 752518020, 965429853, 643455042, 105595573, 424892642, 160398980, 783180043, 207103817, 650632666, 151319402, 92385023, 964295934, 434988033, 990918946, 26564924, 850425472, 10981017, 607730875, 173261653, 799102651, 332158901, 450718279, 75983084, 522004028, 907007969, 173539388, 815008397, 39280804, 549292472, 648991369, 445107198, 226831444, 906280520, 970937898, 912066462, 341918865, 861275443, 500780548, 270273864, 177947455, 951474053, 780122909, 999689912, 211496717, 46150432, 39052406, 528785595, 368878414, 319272200, 276894233, 131599333, 276398021, 252626758, 460373282, 887411171, 920539895, 250031809, 651081062, 273580685, 211855474, 382695448, 461415770, 92037551, 853050198, 608097530, 358700839, 658062542, 628370214, 701180054, 643638805, 597477354, 202808666, 950035054, 560006119, 595629812, 186304556, 777723800, 668123525, 549006222, 583546391, 101505544, 686692315, 686455742, 102543936, 348192750, 673464765, 554637634, 397417003, 360068751, 957633609, 928189430, 290432801, 802114087, 199866123, 84031138, 265595990, 42373810, 563432246, 269064424, 785424741, 829787075, 841799766, 373395898, 650453047, 974382613, 385330357, 288926821, 503167666, 630690705, 504962686, 418193550, 352181130, 65598198, 954061253, 255352545, 209208323, 268154825, 128487469, 88740503, 839054128, 697952502, 685707545, 64735192, 922908862, 673294371, 299172297, 700634351, 464643614, 121294519, 717975101, 615385448, 424067031, 859578405, 577786541, 261968121, 61051402, 168036384, 318951960, 784024352, 359014876, 368791906, 773206631, 849864532, 831641758, 642519652, 306832604, 511251965, 59719938, 26351537, 204355779, 517507962, 767173825, 484120991, 573592106, 689705001, 383865684, 560006077, 30977140, 856866029, 760404254, 681084363, 450398100, 327925913, 177740910, 611192355, 363172638, 545114584, 354990705, 485051702, 258379324, 334158390, 74773587, 956671090, 472935553, 622288553, 861711207, 123889992, 93940075, 75819676, 645018357, 862359850, 587220627, 49131878, 82698356, 736010283, 776264326, 304956416, 977544813, 487108846, 793270300, 511918488, 788636352, 957041224, 291733496, 10717142, 55908790, 359357227, 522049725, 23157292, 662927596, 980166568, 579995261, 914360545, 766145844, 337932245, 335416359, 703381557, 851663162, 937689383, 142946099, 777472742, 244577950, 736666250, 472012302, 188817398, 989345508, 64125479, 559947225, 118585278, 118167528, 176012367, 332139472, 194856362, 840577550, 827185666, 499377092, 806053828, 915199651, 519827597, 464599136, 546457796, 585779428, 28005289, 164752359, 64866657, 61316420, 392711312, 309058615, 102560024, 615081450, 836944364, 86117128, 882577502, 241930728, 400766332, 580204973, 55295957, 790715390, 405956327, 563781682, 128445971, 461178318, 298641073, 954840109, 777013595, 435208217, 656755310, 624577416, 634861021, 226031891, 82745517, 895609896, 409062999, 462654883, 333627931, 888287558, 262144765, 660966455, 22096102, 836813268, 792900494, 269404558, 50835004, 926036911, 924996982, 670433353, 243869444, 386027524, 597639870, 204891068, 902590285, 184419613, 505790549, 520697215, 474430451, 724205533, 976309799, 894659709, 758670815, 403351886, 330493114, 726465115, 167487184, 715247054, 922182249, 737530798, 422453091, 716986954, 348078468, 943314229, 21995092, 830567832, 186987976, 534311010, 726178560, 383388563, 813935745, 398145141, 126925831, 68409439, 709975950, 266372070, 973405188, 6734065, 988931221, 251832060, 888173888, 189239124, 781940697, 344955776, 880553380, 68322490, 423691274, 623974296, 978280935, 943653305, 851264493, 697868489, 897594464, 405755338, 8179625, 665567790, 927743985, 811056092, 369338822, 833885272, 496199986, 179518046, 939687659, 844330145, 527489278, 825132993, 799664596, 656058147, 809505297, 343807435, 2827835, 868431947, 340515688, 985084650, 139614173, 575345122, 127487658, 868553027, 58318116, 942820142, 247860407, 148528617, 946870992, 633107927, 35954298, 160684257, 120166368, 961130399, 565310565, 882148737, 228859128, 848419420, 688083912, 591915968, 210216822, 615889822, 780334053, 701445829, 465596398, 545393547, 104653021, 529726489, 144345463, 480474681, 936910823, 302177126, 989016154, 270945720, 512233057, 974886682, 909477026, 488043087, 154954575, 241107368, 783480311, 740529892, 778849197, 798830099, 644967278, 819011249, 424891680, 940567523, 160664454, 876883097, 329853148, 11633075, 541298538, 293918195, 299929674, 325334066, 591794484, 337883503, 84159401, 346091869, 921012832, 51918298, 566893129, 115312728, 454612480, 119960294, 684622122, 473718967, 292819094, 743143063, 406278443, 218129285, 781034202, 926604003, 506761150, 878471898, 773033829, 524012393, 795791806, 180002392, 751537106, 715754, 88166180, 699739374, 882641788, 389016352, 842593397, 917084264, 415911041, 465386262, 791787792, 856859395, 291654785, 301620109, 850176909, 435327356, 622828826, 514251437, 501105113, 808651347, 451059310, 801370191, 469440779, 421623838, 531057483, 382922882, 513049899, 105419548, 287343485, 127456989, 612899951, 59883031, 971839530, 114166180, 762268297, 322487421, 678396642, 900904073, 900364431, 79716267, 353442556, 786066682, 126560226, 715317963, 686146929, 683150470, 45365306, 429277690, 708166323, 64740307, 3484986, 398078032, 293926937, 711401317, 995439502, 316486674, 544257806, 52757021, 124863480, 384843585, 884700803, 849418710, 705409965, 940338439, 415576459, 509520746, 347282247, 937409008, 992696257, 102624539, 600200925, 940524812, 872682299, 787687576, 731881871, 947549662, 364196979, 668564391, 229334261, 833550543, 545504068, 822407919, 856956061, 593524514, 877327319, 192210898, 980344495, 996164327, 964207235, 961867068, 434012492, 987314628, 286430541, 967411361, 780595857, 697611981, 969047646, 394996809, 34672910, 636177449, 323744863, 72168208, 374786137, 274192146, 287472693, 338788555, 113323151, 418537348, 742559831, 463708507, 69008941, 925347821, 719644259, 458367886, 27763917, 952831975, 646388990, 15393104, 909214594, 893732627, 735213121, 987575845, 898028459, 1277567, 223248648, 230566735, 665333924, 358655417, 223197712, 123947564, 930759285, 141866945, 842098649, 844163282, 374795557, 581830879, 537439701, 446827670, 935741093, 987597705, 852235665, 698430079, 407816563, 347046911, 151905639, 651947420, 240892916, 775305697, 492008437, 317604388, 845163950, 125354499, 308887195, 110831147, 967725028, 951540811, 832662735, 952124856, 845162620, 247662371, 785880192, 57339735, 576679412, 343043237, 872180421, 770497428, 379863199, 568392357, 476950237, 330540451, 260929681, 997474832, 185692768, 684274016, 716946797, 209244402, 315395096, 711263223, 49390359, 380480118, 243118678, 152615685, 759199434, 149586983, 900793615, 338740524, 995747272, 392838702, 910032594, 86684635, 955972829, 309134554, 845568911, 210200531, 155663520, 990779998, 285326836, 835720092, 345577925, 263053337, 408703678, 530748609, 497144475, 325362513, 510483254, 228060468, 878195412, 780072518, 17172937, 542860209, 948969391, 551028176, 904864746, 635027430, 141792616, 990826116, 176937330, 982142330, 863774214, 989944961, 749274500, 935582860, 568293758, 155569943, 15681808, 991755346, 831058399, 596737944, 194068667, 25397869, 895257338, 711553356, 641663134, 512486787, 786465403, 268844715, 820872480, 112916884, 522558396, 451373308, 376000899, 944100328, 741445356, 379404150, 209267503, 440154068, 571164311, 462639908, 316069410, 669000996, 401973416, 961812918, 531236497, 346462698, 502666603, 654611901, 136802920, 301178006, 150416637, 382776490, 55375312, 211395011, 422051547, 41815820, 871852494, 183468905, 222665263, 843321396, 62920475, 401648188, 173838973, 675258797, 890536564, 133581040, 903661822, 845583555, 341196632, 836420358, 646836329, 934281721, 640140324, 86418476, 831112129, 741114145, 220487467, 94141511, 316386753, 275105629, 979797482, 390946091, 559432452, 666247477, 966503421, 458436231, 396240783, 325912072, 534810677, 928715741, 214235012, 526131620, 788809194, 530236183, 865388360, 252551589, 689309663, 503759878, 536133947, 432030917, 677830799, 620192986, 309402088, 554917439, 750984570, 762826007, 145805953, 818036959, 81443984, 601095260, 41179328, 754363835, 458536137, 821331296, 70371679, 795190182, 773892397, 739181445, 407722696, 909210595, 577028140, 599067303, 418444423, 278704903, 62993661, 903915339, 259072478, 719566487, 556335261, 571901643, 670199338, 628514947, 270981826, 651386309, 90279196, 424989675, 681992385, 942214416, 185681382, 321685608, 130556133, 250239248, 240820183, 50590510, 971807975, 287162360, 771773244, 832069712, 296532211, 172844240, 604055008, 198768464, 894636965, 329937332, 991921977, 702004730, 720914685, 805897219, 516388424, 99199382, 158987836, 195756808, 778775932, 707469729, 885756033, 310916425, 670767006, 747407118, 351493841, 795864732, 913233036, 302020341, 119640479, 385010048, 36845914, 497196934, 349980699, 515746342, 597954988, 5003231, 982508563, 905975384, 153520256, 726997875, 865823506, 226911103, 107356392, 382617671, 521947854, 907257761, 793284363, 296229203, 154085699, 176691201, 318596296, 183888367, 56749561, 430569820, 602757844, 703397904, 324673458, 662960264, 132121543, 552133875, 523366740, 594030230, 639546130, 732868367, 209466039, 138744932, 8988146, 350095207, 749620993, 303170656, 531576301, 26031303, 515158909, 963071930, 492695794, 863250534, 780437548, 212666452, 575216934, 216665960, 638556474, 757888960, 177684386, 561745549, 562296933, 894162271, 812475180, 352946234, 580035475, 269943732, 184110313, 784139777, 763098123, 389730744, 329325894, 733333339, 880022333, 504457401, 218497700, 503105966, 616431012, 814692089, 103728644, 459878625, 737550606, 100166031, 109030261, 803187381, 850296900, 84186594, 679420228, 16634739, 503893633, 625504439, 933782733, 180898306, 757778713, 815851993, 74501572, 68718097, 201382580, 521750002, 762252768, 985594252, 839800502, 804272708, 512439938, 404206040, 103475955, 625602963, 285113911, 749724532, 529301141, 904212599, 178132320, 97830135, 766268183, 927950630, 592652662, 611751357, 137238973, 336128288, 845919569, 31131935, 865644603, 493898122, 299277870, 662741752, 515476884, 174140647, 164492104, 864326453, 751136030, 214750670, 43701181, 864869025, 8887214, 682983341, 435060431, 167831173, 25604695, 361169784, 848139022, 559214642, 816554584, 316571311, 446465693, 718498895, 918502589, 129884877, 18640795, 91352335, 311782156, 262054502, 963775207, 608823837, 837833331, 30341256, 517258417, 473379392, 366327994, 86738528, 255729768, 385388084, 392405824, 85051770, 54276784, 152267158, 161185571, 883676662, 378084701, 681756977, 33883485, 914781910, 682883599, 46819124, 502392006, 499828799, 46917827, 313132653, 245193338, 300653641, 12075963, 56547945, 603678770, 652279266, 545875253, 442795120, 982609115, 841355804, 131639745, 796616594, 647409797, 186372829, 306980454, 256141983, 485445052, 284655550, 169597670, 152028387, 379850306, 2518954, 31181614, 636578562, 505653433, 665181047, 831021896, 385377759, 404687511, 115557610, 458459110, 553033642, 587498064, 707031841, 979834383, 491415383, 758063496, 267732098, 908178229, 919273670, 256434523, 771891931, 552471386, 996049638, 663866346, 204194403, 694757059, 326686486, 173643971, 524269810, 2248257, 160150665, 444690706, 18364502, 384810005, 141827977, 810647416, 541689171, 900740408, 540818053, 810402559, 444923677, 949493953, 693305776, 503058099, 895259210, 375967121, 593938674, 161454270, 261432589, 649856271, 186576440, 992074918, 525216705, 530065902, 688809790, 929706952, 957610877, 111794298, 565456578, 236073918, 981362547, 58735152, 749296077, 390533216, 246808791, 259513659, 519397500, 729013272, 633032196, 30284937, 551096742, 149403717, 997104085, 362551229, 696628828, 535204787, 473521307, 927742823, 775025061, 626473195, 274750982, 545251906, 370732451, 434042870, 684205655, 464031225, 164246193, 882721043, 919530230, 32662554, 915265013, 680768945, 925117963, 394623417, 457469634, 888387042, 591773508, 702969354, 923043932, 609091666, 579491909, 143798661, 912368644, 46998687, 657283032, 595858865, 777901604, 481276117, 580108890, 22361807, 464118005, 203547549, 619229549, 483558744, 637939935, 599005133, 875658633, 193870331, 956856710, 298802, 390856783, 726314250, 490676632, 299422881, 404533909, 435121890, 453019482, 603917664, 191649870, 150553457, 462528877, 698933272, 13751809, 486715188, 502297454, 776548167, 629218582, 133071834, 798895521, 924905215, 623841561, 573562278, 100498586, 621266591, 77511478, 618032574, 699767918, 877833437, 416820652, 161898173, 849974789, 902379873, 741447563, 798504599, 811575797, 479758433, 747107591, 499010965, 438952959, 201569596, 248233087, 931771067, 606870929, 196769088, 32074225, 891063982, 907720182, 619098899, 999821136, 428300314, 179111720, 143331121, 778287926, 278397454, 48053248, 31526202, 966053837, 787560730, 508038818, 626235187, 433786890, 94861131, 811944661, 830945967, 631265590, 87780527, 752550134, 721855051, 739608890, 572025679, 401382061, 623774744, 623047959, 697726795, 848924691, 957422361, 730897743, 247450929, 764368449, 745025896, 605025034, 608462543, 34629406, 416058816, 894517500, 139436117, 529840945, 278458947, 112657644, 298190159, 435904287, 372256709, 997813035, 601486951, 26011548, 291022920, 56222592, 97351796, 208184231, 772929863, 198012676, 767534240, 446477394, 859801172, 672903454, 975341439, 206330671, 94465568, 181069006, 614184554, 366033520, 740391117, 504590032, 494367785, 131772368, 267618556, 213456517, 302086918, 185646898, 928205658, 713536809, 715330554, 648711554, 850059166, 187129040, 469712035, 472759660, 502848626, 446982306, 969021396, 523696723, 656468842, 306339620, 286635747, 271198437, 423288002, 284132069, 954000323, 25058942, 495453104, 971058102, 537377458, 859369491, 443690710, 255041381, 196713118, 817928963, 508204070, 136849970, 45695706, 330711333, 666341116, 742765041, 843088355, 724464507, 809267734, 730186918, 11080649, 437605233, 463987622, 864978329, 838929133, 701453022, 731076258, 133269512, 421036348, 626663115, 582977276, 11085731, 83851975, 281230685, 390122869, 141658162, 421426349, 510650790, 355948203, 527887355, 873058725, 596949867, 345997577, 731147272, 264084667, 295726547, 503240185, 613729514, 601174554, 303076380, 851791356, 514155754, 121194194, 465070856, 800063145, 415213535, 965919023, 272814771, 184686454, 684096122, 632193883, 538771609, 730991627, 579671055, 420200867, 48824684, 665227492, 972590066, 931112114, 951279549, 725694913, 217176278, 345817436, 939889684, 574205882, 957342287, 384889445, 564188856, 592279840, 469432979, 694843199, 48527183, 21902144, 119648328, 44795822, 201307702, 802254172, 264639326, 903528535, 484458461, 669489248, 337340034, 441033713, 861754542, 413891559, 974596348, 841027029, 326159309, 390199216, 774336224, 497146072, 181594759, 924931589, 287297719, 248257271, 668422905, 38845386, 860780776, 512802592, 286273596, 516618289, 467363131, 913603004, 965656187, 126529811, 570457971, 138675908, 44135644, 636627889, 938561592, 851896887, 359960756, 176151938, 255726848, 894598068, 936229527, 410308322, 586418403, 220030439, 407934361, 317333782, 577750062, 146416748, 267193060, 662652196, 110628267, 935649923, 456152084, 60946382, 748372491, 293662192, 459116722, 659735093, 496690748, 950266352, 124804049, 126560238, 778806615, 438286538, 262322489, 907002100, 471005141, 129372756, 920251227, 970961239, 881907746, 895793744, 816929577, 476444551, 71346633, 887255104, 483924582, 100185513, 885773623, 143605973, 151834896, 361590882, 697422579, 807615657, 167087470, 267901776, 348461966, 711693305, 490222511, 680740402, 271101205, 401755350, 903466878, 715272319, 695845167, 295084907, 361583925, 258259781, 139849160, 325806930, 368114731, 443530581, 611223434, 833080932, 339383292, 872311829, 240693388, 46955186, 388728584, 32574568, 787495569, 391193596, 218107212, 599308635, 647286378, 307984829, 249153339, 932961293, 301439625, 586792543, 909458706, 91708783, 825527586, 50301975, 322908524, 78590841, 713473839, 843123325, 202649964, 664498313, 316700583, 316918770, 92255682, 127372587, 619301661, 329387504, 573074791, 824317170, 265672103, 561692362, 15570863, 251174519, 330425149, 586180318, 94331513, 649900422, 80303342, 696956978, 744158074, 791892722, 714604162, 722445437, 196345098, 534352784, 956948468, 857979370, 334326205, 254834284, 656410044, 127044863, 9416035, 458110400, 98875930, 119649397, 98349682, 16884564, 249359071, 176785272, 882121662, 92640308, 609122097, 999848032, 769795511, 193161253, 27204169, 237046881, 231988936, 511571733, 341541162, 842346391, 888146074, 354841505, 563593105, 849312843, 137603545, 930679925, 597887794, 412615826, 582627184, 57117083, 173167319, 362484731, 407518072, 14215092, 525248491, 635619282, 919419361, 264611701, 34084880, 852918398, 909433461, 393375325, 459822212, 345031724, 986708498, 340913095, 578423178, 271252437, 310317874, 87583783, 688545487, 866590795, 373745190, 776987068, 426767514, 278552186, 263645931, 538628231, 33023513, 922701788, 256853930, 140789737, 216838327, 640988873, 876379959, 95507008, 681776798, 876322324, 702823274, 123882694, 152276951, 59374455, 147050765, 233410503, 552142680, 35704301, 308186532, 301215741, 892943080, 434299900, 175504139, 940023660, 531982651, 690607561, 180350107, 345442939, 853751105, 822184689, 797736554, 604822277, 911931389, 232362648, 606241871, 718337842, 734505544, 245141211, 384547635, 263075911, 205897697, 323047155, 273712630, 89453695, 295898944, 583133449, 586444655, 558697741, 298511537, 290216431, 682189174, 96990023, 391491433, 343716916, 666493603, 464758241, 769644373, 201607244, 946867127, 756277394, 779729071, 972999959, 819114541, 674569332, 430345388, 896027796, 502371023, 314857121, 565093850, 557328233, 261970285, 482510647, 73676677, 360538408, 825871994, 50282375, 439985219, 848800658, 126925175, 182750707, 537175030, 694924737, 701506133, 270786053, 922419422, 363612940, 314738056, 979368575, 331629774, 609036071, 341779962, 880783035, 993829303, 536334772, 561011609, 402903958, 310187903, 183115127, 815463367, 875798648, 419922946, 683932582, 46765164, 433478033, 153796383, 132454834, 49187570, 922226681, 978824517, 383337126, 188054995, 718482843, 229507993, 700976123, 957939114, 682286838, 976365496, 805214934, 64814326, 373842324, 34962064, 155766116, 933376898, 187332912, 639423687, 637495943, 329837066, 182348131, 938220928, 405582552, 338121343, 926098094, 723473543, 146566000, 765215899, 131922689, 374248877, 438738934, 869630152, 470257565, 825793239, 320300717, 978119194, 184896757, 712565751, 758462453, 632627667, 295578365, 996588391, 145731547, 975266085, 364036671, 10259433, 272998870, 435887178, 323977958, 310651169, 121069149, 282092463, 531278823, 235000767, 577576413, 129621197, 25546644, 131119231, 514619865, 758245605, 694061362, 122477672, 677013842, 827722926, 886870220, 104141028, 532227478, 201339230, 727451710, 632232583, 195965817, 918513230, 473514925, 9760876, 116358524, 322096036, 694366495, 661083628, 685332237, 547838438, 677677736, 278005187, 584987581, 985546115, 693648786, 462757650, 118194477, 852304035, 218286248, 747700707, 456194172, 593090119, 296710496, 31738433, 342936417, 689189630, 469446997, 302579083, 444073731, 555842733, 886385642, 407991608, 379151892, 567033437, 317981504, 883930382, 954089026, 469928208, 20212688, 933753541, 975683488, 212842957, 481292014, 952917862, 414912172, 117842065, 28097196, 636059822, 178897316, 404149413, 822758467, 5021656, 61518602, 155133422, 742486361, 396892116, 115857733, 663307737, 575453013, 252202515, 853930475, 208761293, 499864031, 556478432, 625653444, 206282795, 27880608, 438269075, 346492037, 717946122, 869524540, 308402114, 369103748, 488906585, 980182828, 58731649, 869661127, 414236650, 804613839, 138477462, 873260580, 280700600, 81734900, 829290435, 459219589, 962670136, 178172249, 691030367, 72329014, 534279149, 537833730, 534216193, 794712949, 214569244, 36268977, 306753329, 394287348, 375297772, 463532789, 506050984, 263462485, 811053196, 792786455, 768114732, 421060593, 922377372, 205115006, 685756954, 595274897, 289594327, 518383122, 77516399, 73888244, 219932130, 751394698, 423659297, 383271365, 211487466, 377514463, 88929658, 746386624, 701050258, 309611110, 207594892, 330355869, 398782410, 640856244, 311095371, 24744781, 863002719, 670288657, 558395120, 255040696, 27236531, 931168051, 653991930, 353239467, 217598709, 781020811, 6140104, 972113519, 375472836, 849594910, 227970396, 31410247, 810551911, 757615675, 759994826, 516032510, 178598958, 377031550, 212759058, 9686973, 247844667, 999846916, 738789531, 86543232, 676526196, 879111625, 935116236, 119739860, 812283640, 848427753, 270258531, 565862182, 863066876, 705496924, 523449284, 801513025, 857241854, 418500955, 244920548, 387092719, 113917835, 21877268, 285558056, 97284372, 624148346, 682784756, 217519213, 561654530, 726089763, 352824826, 288577505, 891889167, 564827277, 832629099, 182270197, 483658324, 826300950, 646326336, 154134669, 534700971, 478982047, 183049692, 992035084, 503430216, 439411911, 219303738, 781040881, 156134325, 454039189, 142729429, 173642567, 668241128, 633292726, 858489537, 181058575, 104993372, 48562889, 527138624, 316466042, 124587966, 802100365, 876320124, 528654390, 858364998, 671734977, 858133285, 588427118, 49376708, 945204804, 726732838, 617419803, 974144226, 508831870, 677809471, 923976569, 156518337, 398781902, 99323099, 345695843, 816670686, 897162044, 471843395, 488776232, 369094329, 644050694, 330811245, 522005226, 973416962, 892168027, 191125092, 663939743, 193605173, 828883117, 830802454, 636309857, 402982516, 277714559, 159824027, 22220478, 49663121, 713448377, 210889515, 862322982, 571277611, 624500515, 407103715, 670822030, 365482665, 590098114, 680778659, 282104097, 753616208, 808691930, 423902795, 671075979, 300932787, 514359662, 206759980, 161646605, 434335908, 895205045, 549714378, 18763728, 153438911, 715264908, 899235151, 171766217, 192342724, 628829100, 334114105, 727088567, 359891374, 484492064, 908311531, 847440256, 548560882, 919717789, 208899363, 118695128, 679467158, 513196123, 45414561, 1927054, 42959761, 748510389, 348918148, 604018013, 843674138, 403652653, 273385515, 900440408, 632605096, 574455974, 821021955, 135656153, 880890811, 77123823, 526993194, 195346599, 56502013, 172096141, 676901075, 796894379, 81604980, 819801784, 373985666, 102159868, 259431090, 581418893, 78286032, 26773666, 206868336, 15655126, 476723349, 961808256, 851072785, 15391652, 408633673, 340290036, 35315014, 875641535, 719520121, 25732221, 241832128, 203191898, 473267301, 762975242, 420952629, 264582598, 371324086, 186922308, 355774622, 880691101, 557084915, 828454217, 24253373, 907800444, 689821082, 342392035, 736853549, 986598821, 535525460, 200084575, 149804464, 340030191, 768081306, 556841547, 186211491, 264688936, 428518660, 275811253, 679462627, 369832433, 929312595, 444094748, 947276770, 785804644, 808828689, 277341268, 374979150, 842065079, 760675071, 898092098, 914050434, 423951674, 628367003, 207638534, 561666414, 663560047, 847729387, 230631176, 918279883, 696623384, 677643926, 807827182, 838631314, 496709826, 824643649, 879400608, 268508478, 161960209, 118455504, 865140964, 638916884, 331910086, 595056675, 603116309, 914846095, 541120825, 194421372, 574610474, 924349532, 951524114, 552366416, 962158915, 717746026, 841656666, 644421061, 662109025, 66170345, 162683802, 287729735, 60582516, 452150624, 629786193, 372818418, 883014120, 135244193, 190395535, 460530089, 472550413, 758814521, 269571439, 548497019, 468747428, 742578942, 832671304, 196050185, 125435851, 6781185, 76770272, 232148410, 470689842, 741672203, 341080135, 620476493, 207220566, 951129936, 421943723, 936839332, 324979737, 51494655, 494210290, 713382609, 604177687, 795746563, 751040886, 498345007, 95589267, 846819151, 317076664, 452510575, 717683969, 205274111, 672850561, 783750968, 988189352, 450234257, 72482816, 971472181, 161579561, 491714430, 493689107, 360330010, 388537544, 582518116, 135625240, 854083379, 555187833, 347560883, 100228913, 66186191, 728822117, 985137704, 684748812, 734776265, 576796201, 401326141, 639655136, 796209722, 266200149, 503714909, 906233141, 878024868, 85157309, 105377683, 929893103, 195199702, 133047646, 120745161, 277813439, 371372528, 9837620, 432877198, 814362881, 368379357, 380021947, 581522681, 562608724, 989285272, 213027699, 50796761, 406024012, 909228903, 315587760, 994881682, 885537778, 911172977, 925665844, 757452839, 10065330, 370208025, 107125810, 3580132, 60625018, 344012987, 376366561, 807646193, 983737173, 493893741, 253250904, 575576511, 60517502, 409506874, 466459786, 65622391, 551060742, 77506095, 139998669, 857431457, 804930491, 157228580, 592347496, 711156492, 823845496, 419227352, 765555389, 984977683, 727416538, 46584186, 590444719, 2501513, 946421040, 856874250, 717927112, 387898276, 678171399, 956616948, 86811998, 489873285, 842203531, 988327543, 371706626, 890758947, 175638827, 925067613, 408502422, 11678054, 894247956, 368924610, 831246288, 350900559, 538609927, 385235011, 782723657, 164882083, 885362182, 925942919, 831257253, 553912269, 946464959, 199414022, 453770195, 782119525, 116667533, 629989348, 982647665, 842242752, 749816133, 490671428, 712106516, 78737356, 241427979, 482765383, 710965692, 975094049, 871117927, 221820501, 378998132, 134829676, 281804989, 536113355, 603830959, 739829205, 163928347, 136513878, 644386154, 878420651, 563796647, 542148001, 274795785, 472528188, 640266394, 516352236, 107234102, 998521225, 774625892, 599384668, 791185412, 558910407, 59342705, 617013273, 97826191, 293805419, 256473217, 514374724, 590213099, 867596433, 674115061, 848719823, 703665287, 830317963, 918860977, 373481767, 8947163, 890867014, 322633051, 191299885, 192270447, 697655701, 753513874, 694996968, 294830834, 459908543, 393556719, 970585862, 25181126, 760054479, 304644842, 873279068, 234845827, 204376198, 767372800, 771150004, 553063981, 315969637, 161362528, 710636564, 749473336, 247325286, 754787150, 824758462, 58596576, 839990536, 627655552, 912441135, 159512462, 448500279, 677395736, 931122474, 846532820, 913221154, 799289297, 355619107, 354655649, 60539447, 846650652, 51274689, 978805070, 203405153, 816701166, 998236923, 315419580, 613463418, 687265514, 875185877, 833548006, 646487702, 787113234, 554878994, 97846412, 527523396, 358757251, 221457585, 226478218, 840254556, 701220427, 488072551, 567481117, 449946621, 607715125, 716622769, 90197399, 877666937, 245795606, 515785806, 962901304, 839471675, 600624983, 71973421, 242901954, 724924078, 10475577, 344060712, 650859047, 446205244, 728620948, 966778414, 435811032, 970873983, 759404319, 144525537, 573183959, 729080802, 36292292, 729120659, 183555163, 73699158, 491466901, 67697554, 447239215, 828875694, 22556579, 971344891, 873791394, 697681175, 114495791, 481946740, 197736875, 876537140, 647630109, 234472331, 485056460, 898731557, 586445753, 548287183, 190508668, 602630219, 482254337, 646752647, 322924180, 428138881, 718623833, 15068830, 116698549, 312363755, 763514207, 684084869, 810987160, 277786757, 66547751, 626294224, 300695571, 958655399, 953634340, 880602425, 324833924, 688128659, 351472920, 861932447, 384343273, 415039162, 308474522, 373631176, 20450004, 569050859, 494166907, 415503144, 85288039, 547092626, 634359666, 539009721, 397059212, 840027487, 172114298, 201311372, 198532616, 747683336, 865440961, 655271342, 3739182, 146797889, 364380585, 303429350, 990631624, 39924750, 921648059, 141635885, 903288230, 72955529, 965683742, 871905742, 374214450, 116291970, 260466949, 154402093, 112429098, 728655283, 117483873, 241732798, 281744795, 209020476, 962540888, 345412932, 642772349, 91231061, 237120480, 741050360, 504371008, 861763291, 620531822, 300590108, 563045796, 932725389, 193781724, 947174007, 695511574, 538073920, 213092254, 353479328, 782794242, 828991388, 107141741, 609843843, 662565976, 12912536, 602742426, 937988698, 857268414, 72744602, 793307102, 950442238, 919116765, 152628797, 756154604, 504041378, 443183564, 396891083, 236455213, 302278108, 626871594, 103848028, 362928234, 140309569, 938420738, 213659695, 14162538, 575687769, 801639277, 444280792, 753042874, 616861022, 723950758, 50516153, 778983779, 837944632, 672909594, 547174121, 25977209, 722798197, 323582350, 885292639, 49389215, 776263424, 254189314, 611939143, 698308420, 483538711, 181353334, 59867597, 859637374, 303580516, 801413581, 463605137, 49031023, 384590208, 709178470, 570179364, 713258160, 257013268, 410465453, 889588353, 737331920, 175295865, 131731042, 593621397, 923333660, 470174298, 601117743, 22452361, 804861409, 490376355, 327520749, 38855237, 83868974, 148882603, 260831555, 618730947, 682873215, 553990723, 937240859, 596073754, 217298111, 395336950, 659873007, 18025576, 883278906, 788047493, 366761197, 663477084, 176966527, 144817333, 110744650, 724190111, 954913, 997271782, 246965865, 615769726, 105359006, 482858165, 338471174, 41442781, 390019735, 371027602, 549660657, 966410761, 10430738, 199841489, 58007504, 384029152, 706334445, 21905318, 864696066, 304787447, 315103615, 243608321, 465054749, 427738793, 567473423, 987541329, 85292764, 773918648, 708233401, 310071740, 426786760, 10015863, 48160594, 152922550, 142441517, 742843324, 946149627, 777188493, 394265229, 100206080, 346966053, 153650145, 71050762, 21945704, 281329488, 708954705, 246955022, 141203116, 462880311, 86073587, 253486451, 947585477, 31503476, 89564621, 411673788, 637772581, 185438078, 120790929, 521591989, 182578852, 965785236, 998492024, 16651371, 815104059, 992656683, 429962264, 545638190, 279864100, 916291845, 201601450, 65591903, 348671498, 881482632, 38459482, 957757479, 132384442, 899946391, 983226396, 84428155, 459565762, 321900901, 895310341, 674721611, 82386031, 512634493, 244851135, 970053019, 267715957, 303338827, 628232723, 860842034, 580915649, 121000338, 87276158, 87654126, 912934355, 967284733, 561438135, 580938783, 16702713, 492741665, 60154389, 671517513, 983550467, 152233223, 799829882, 335102896, 56859637, 165393390, 209582914, 160150497, 847526451, 680128316, 854476671, 685723887, 556328448, 917041303, 758337414, 782192657, 117871095, 532702135, 175289715, 56081734, 44529952, 741626808, 551426320, 642939667, 647693437, 496442755, 594597941, 867195255, 552272388, 536841269, 910558979, 412622873, 113175090, 131384366, 983776383, 994065976, 260276116, 377329025, 120671803, 974508445, 503334842, 301196854, 748347356, 574480664, 827155024, 859917803, 438877561, 20211256, 46268671, 676511002, 733823944, 437157360, 188284405, 373451745, 115749503, 83118246, 702144005, 847645126, 435308472, 268761837, 935072263, 823495900, 896878185, 459628134, 116910205, 576368335, 509039064, 494290402, 282151037, 73146164, 953270692, 98016105, 763638412, 954958912, 130224147, 486828649, 579036716, 847549272, 536884008, 201882845, 930801429, 241289571, 34140074, 420567331, 522704662, 646654592, 716556217, 788599446, 964261108, 216046746, 657890333, 682599498, 78982470, 205951465, 36722836, 383521365, 907252430, 3258987, 172424584, 433576760, 787672534, 780882948, 504605118, 510148825, 230771225, 822439091, 681956393, 128900492, 328152609, 598245292, 478087198, 606924610, 524378352, 869544707, 963814773, 933768689, 657395111, 698611116 };

int QMI(int a, int k) {
    int ret = 1 % MOD;
    while (k) {
        if (k & 1) ret = 1LL * ret * a % MOD;
        a = 1LL * a * a % MOD;
        k >>= 1;
    }
    return ret;
}

int Fact(int x) {
    int ret = fac[x / M];
    for (int i = x / M * M + 1; i <= x; ++i) {
        ret = 1LL * ret * i % MOD;
    }
    return ret;
}

void Solve() {
    cin >> c >> p;
    if (p.size() > 10 || stoll(p) >= MOD) {
        puts("0");
        return;
    }
    if (c.size() <= 10 && stoll(c) < 2 * stoi(p) - 1) {
        puts("0");
        return;
    }

    int x = 0;
    for (int i = 0; i < c.size(); ++i) {
        x = (10LL * x + c[i] - '0') % MOD;
    }
    x = (x - stoi(p) + 1 + MOD) % MOD;
    if (x < stoi(p)) {
        puts("0");
        return;
    }
    ans = 1LL * Fact(x) * QMI(Fact(x - stoi(p)), MOD - 2) % MOD;
    printf("%d\n", ans);
}

/**
 * $\frac{(C-P+1)!}{(C-2P+1)!}$
 */
int main() {
    // freopen("invigilate.in", "r", stdin);
    // freopen("invigilate.out", "w", stdout);
    
    int t;
    scanf("%d", &t);
    while (t--) {
        Solve();
    }

    return 0;
}