{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Hindi](https://www.codechef.com/download/translated/MAR19TST/hindi/MATPER.pdf), [Bengali](https://www.codechef.com/download/translated/MAR19TST/bengali/MATPER.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/MAR19TST/mandarin/MATPER.pdf), [Russian](https://www.codechef.com/download/translated/MAR19TST/russian/MATPER.pdf), and [Vietnamese](https://www.codechef.com/download/translated/MAR19TST/vietnamese/MATPER.pdf) as well.\r\n\r\nChef has a string $S$ with length $N$. He also has $M$ other strings $P_1, P_2, \\ldots, P_M$, which are called *patterns*. The characters in the strings are indexed from $1$.\r\n\r\nChef was wondering if he could find the $M$ patterns in the string $S$ in the given order. That is, he wanted to know whether it is possible to choose $M$ ranges, denoted by $[l_i, r_i]$ for each $i$ ($1 \\le i \\le M$), such that $1 \\le l_1 \\le r_1 \\lt l_2 \\le r_2 \\lt \\ldots \\lt l_M \\le r_M \\le N$ and for each valid $i$, the substring $S_{l_i}, S_{l_i + 1}, \\ldots, S_{r_i}$ equals $P_i$.\r\n\r\nAs this problem was too easy for Chef, he decided to make a harder one. A permutation $p \u003d (p_1, p_2, \\ldots, p_M)$ of integers $1$ through $M$ is called a *matchable permutation* if Chef can reorder the $M$ patterns into $P_{p_1}, P_{p_2}, \\ldots, P_{p_M}$ and then find them in $S$, in this order (in the same way as described above).\r\n\r\nCan you help Chef find the number of matchable permutations?\r\n\r\n### Input\r\n- The first line of the input contains two space-separated integers $N$ and $M$.\r\n- The second line contains a single string $S$.\r\n- $M$ lines follow. For each $i$ ($1 \\le i \\le M)$, the $i$-th of these lines contains a single string $P_i$. \r\n\r\n### Output\r\nPrint a single line containing one integer - the number of matchable permutations.\r\n\r\n### Constraints \r\n- $1 \\le N \\le 10^5$\r\n- $1 \\le M \\le 14$\r\n- $1 \\le |P_i| \\le 10^5$ for each valid $i$\r\n- $S, P_1, P_2, \\ldots, P_M$ contain only lowercase English letters\r\n\r\n### Subtasks\r\n**Subtask #1 (10 points):** $1 \\le M \\le 3$\r\n\r\n**Subtask #2 (30 points):** $1 \\le N \\le 1,000$\r\n\r\n**Subtask #3 (60 points):** original constraints\r\n\r\n### Example Input 1\r\n```\r\n10 3\r\nabbabacbac\r\nab\r\nac\r\nb\r\n```\r\n\r\n### Example Output 1\r\n```\r\n3\r\n```\r\n\r\n### Explanation 1\r\nAmong the $3! \u003d 6$ possible permutations of $(1, 2, 3)$, the matchable permutations are $(1, 2, 3)$, $(3, 1, 2)$ and $(1, 3, 2)$. These correspond to permutations of patterns (\"ab\", \"ac\", \"b\"), (\"b\", \"ab\", \"ac\") and (\"ab\", \"b\", \"ac\") respectively. Each of them can be found in $S$ in the given order.\r\n\r\n### Example Input 2\r\n```\r\n3 2\r\naaa\r\naa\r\naa\r\n```\r\n\r\n### Example Output 2\r\n```\r\n0\r\n```\t\r\n\r\n### Explanation 2\r\nWe cannot match the two patterns in such a way that their ranges do not intersect.\r\n\r\n### Example Input 3\r\n```\r\n4 2\r\naaaa\r\naa\r\naa\r\n```\r\n\r\n### Example Output 3\r\n```\r\n2\r\n```\t\r\n\r\n### Explanation 3\r\nThe matchable permutations are $(1, 2)$ and $(2, 1)$.\r\n"}}]}