Shashank loves strings, but he loves palindromic strings the most. He has a list of $n$ strings, $A=[a_0,a_1,...,a_{n-1}]$, where each string, $a_i$, consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty subsequences $s_0,s_1,s_2,\ldots,s_{n-1}$ such that the following conditions are satisfied:

$s_0$ is a subsequence of string $a_0$, $\boldsymbol{s_{1}}$ is a subsequence of string $a_1$, $s_2$ is a subsequence of string $a_2$, $\ldots$, and $\boldsymbol{s_{n-1}}$ is a subsequence of string $a_{n-1}$.
$s_{0}+s_{1}+s_{2}+\ldots+s_{n-1}$ is a palindromic string, where + denotes the string concatenation operator.

You are given $\textit{q}$ queries where each query consists of some list, $\mbox{A}$. For each query, find and print the number of ways Shashank can choose $n$ non-empty subsequences satisfying the criteria above, modulo $10^9+7$, on a new line.

Note: Two subsequences consisting of the same characters are considered to be different if their characters came from different indices in the original string.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains an integer, $n$, denoting the size of the list. 
Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains a non-empty string describing $a_i$.

Constraints

$1\leq q\leq50$  
$1\leq n\leq50$  
$\sum_{i=0}^{n-1}|a_i|\leq1000$ over a test case.

For $40\%$ of the maximum score:

$1\leq n\leq5$  
$\sum_{i=0}^{n-1}|a_i|\leq250$ over a test case.

Output Format

For each query, print the number of ways of choosing non-empty subsequences, modulo $10^9+7$, on a new line.

Sample Input 0
3
3
aa
b
aa
3
a
b
c
2
abc
abc

Sample Output 0
5
0
9

Explanation 0

The first two queries are explained below:

We can choose the following five subsequences:

$s_0="a"$, $s_1="b"$, $s_2="a"$, where $s_0$ is the first character of $a_0$ and $s_2$ is the first character of $a_2$.
$s_0="a"$, $s_1="b"$, $s_2="a"$, where $s_0$ is the second character of $a_0$ and $s_2$ is the second character of $a_2$. 
$s_0="a"$, $s_1="b"$, $s_2="a"$, where $s_0$ is the first character of $a_0$ and $s_2$ is the second character of $a_2$.
$s_0="a"$, $s_1="b"$, $s_2="a"$, where $s_0$ is the second character of $a_0$ and $s_2$ is the first character of $a_2$.   
$s_0=\textsf{“aa}$, $s_1="b"$, $s_2=\textsf{“aa}$     

Thus, we print the result of $5 mod (10^9+7)=5$ on a new line.

There is no way to choose non-empty subsequences such that their concatenation results in a palindrome, as each string contains unique characters. Thus, we print $0$ on a new line.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
def distance(strings, ast, ach, zst, zch):
	if ast > zst:
		return 0 - distance(strings, zst, zch, ast, ach)
	dist = 0
	while ast != zst:
		dist += len(strings[ast]) - ach
		ast += 1
		ach = 0
	return dist + zch - ach

def search_back(strings, ast, ach, zst, zch, sthi, target):
	while zst >= max(ast, sthi - 1):
		s2 = strings[zst]
		while zch >= 0:
			if s2[zch] == target:
				if ast == zst and ach >= zch:
					return (-1, -1)
				return (zst, zch)
			zch -= 1
		zst -= 1
		zch = len(strings[zst]) - 1
	return (-1, -1)

def back(strings, st, ch):
	if ch <= 0:
		return (st - 1, len(strings[st - 1]) - 1)
	else:
		return (st, ch - 1)

def fwd(strings, st, ch):
	if ch + 1 >= len(strings[st]):
		return (st + 1, 0)
	else:
		return (st, ch + 1)

def count_subsequences(strings, counts, ast, ach, zst, zch, stlo, sthi):
	if ast >= zst:
		if ast > zst:
			return 1
		if ach > zch:
			return 1
		if ach == zch:
			if ast == stlo or ast == sthi:
				return 2
			else:
				return 1
	if (ast, ach, zst, zch, stlo, sthi) in counts:
		return counts[ast, ach, zst, zch, stlo, sthi]
	subsequences = 0
	aval = strings[ast][ach]
	(ast2, ach2) = fwd(strings, ast, ach)
	(mst, mch) = search_back(strings, ast, ach, zst, zch, sthi, aval)
	while mst != -1:
		mst2 = mst
		(mst, mch) = back(strings, mst, mch)
		subsequences += count_subsequences(strings, counts, ast2, ach2, mst, mch, ast, mst2)
		(mst, mch) = search_back(strings, ast, ach, mst, mch, sthi, aval)
	if ast2 <= stlo + 1:
		subsequences += count_subsequences(strings, counts, ast2, ach2, zst, zch, stlo, sthi)
	if stlo >= ast - 1 and ast >= sthi - 1:
		subsequences += 1
	counts[ast, ach, zst, zch, stlo, sthi] = subsequences % 1000000007
	return subsequences % 1000000007
for q in range(0, int(input())):
	num_strings = int(input())
	strings = list(map(lambda _: input().strip(), range(0, num_strings)))
	print(count_subsequences(strings, {}, 0, 0, num_strings - 1, len(strings[num_strings - 1]) - 1, -1, num_strings))