Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef 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$.

Chef 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 ≤ i ≤ M$), such that $1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} < \ldots < l_{M} ≤ r_{M} ≤ N$ and for each valid $i$, the substring $S_{l_{i}}, S_{l_{i} + 1}, \ldots, S_{r_{i}}$ equals $P_{i}$.

As this problem was too easy for Chef, he decided to make a harder one. A permutation $p = (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).

Can you help Chef find the number of matchable permutations?

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
The second line contains a single string $S$.
$M$ lines follow. For each $i$ ($1 ≤ i ≤ M)$, the $i$-th of these lines contains a single string $P_{i}$. 

------  Output ------
Print a single line containing one integer - the number of matchable permutations.

------  Constraints  ------
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 14$
$1 ≤ |P_{i}| ≤ 10^{5}$ for each valid $i$
$S, P_{1}, P_{2}, \ldots, P_{M}$ contain only lowercase English letters

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ M ≤ 3$

Subtask #2 (30 points): $1 ≤ N ≤ 1,000$

Subtask #3 (60 points): original constraints

------  Example Input 1 ------

10 3
abbabacbac
ab
ac
b

------  Example Output 1 ------

3

------  Explanation 1 ------
Among the $3! = 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.

------  Example Input 2 ------

3 2
aaa
aa
aa

------  Example Output 2 ------

0
	
------  Explanation 2 ------
We cannot match the two patterns in such a way that their ranges do not intersect.

------  Example Input 3 ------

4 2
aaaa
aa
aa

------  Example Output 3 ------

2
	
------  Explanation 3 ------
The matchable permutations are $(1, 2)$ and $(2, 1)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

String algorithms

Range queries

Complete search

Dynamic programming

Mathematics


Solutions:
import bisect
import time
current_time = time.time()
var = 0
ch = [[] for i in range(15)]

def KMP(s, t, idx):
	f = [0 for i in range(len(s) + len(t) + 1)]
	z = t + '#' + s
	for i in range(1, len(z)):
		j = f[i - 1]
		while j > 0 and z[i] != z[j]:
			j = f[j - 1]
		if z[i] == z[j]:
			j += 1
		f[i] = j
	for i in range(len(t) + 1, len(f)):
		if f[i] == len(t):
			ch[idx].append(i - len(t) - len(t))
(n, m) = map(int, input().split())
s = input()
t = []
dp = {}
dp1 = [-1 for i in range(1 << 15)]

def func(idx, mask):
	if time.time() - current_time > 5:
		global var
		var = 1
		return 0
	if mask == (1 << m) - 1:
		return 1
	if idx >= n:
		return 0
	patanahi = (idx, mask)
	if patanahi not in dp:
		ans = 0
		for i in range(m):
			if mask & 1 << i == 0:
				lol = bisect.bisect_left(ch[i], idx)
				if lol != len(ch[i]):
					newidx = ch[i][lol] + len(t[i])
					ans += func(newidx, mask | 1 << i)
		dp[patanahi] = ans
	return dp[patanahi]

def func1(idx, mask):
	if mask == (1 << m) - 1:
		return 1
	if idx >= n:
		return 0
	if dp1[mask] == -1:
		ans = 0
		for i in range(m):
			if mask & 1 << i == 0:
				lol = bisect.bisect_left(ch[i], idx)
				if lol != len(ch[i]):
					newidx = ch[i][lol] + len(t[i])
					ans += func1(newidx, mask | 1 << i)
		dp1[mask] = ans
	return dp1[mask]
for i in range(m):
	tt = input()
	t.append(tt)
	KMP(s, tt, i)
ans = func(0, 0)
if var == 1:
	ans = func1(0, 0)
print(ans)