Square Subsequences

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how many (non-empty) subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.

Input Format

The first line contains the number of test cases, $T$. 

$T$ test cases follow. Each case contains a string, $S$.

Output Format

Output $T$ lines, one for each test case, containing the required answer modulo 1000000007.

Constraints: 

$1\leq T\leq20$ 

$S$ will have at most $200$ lowercase characters ('a' - 'z').

Sample Input

3 

aaa 

abab 

baaba

Sample Output

3 

3 

6

Explanation

For the first case, there are 3 subsequences of length 2, all of which are square strings. 

For the second case, the subsequences "abab", "aa", "bb" are square strings. 

Similarly, for the third case, "bb", "baba" (twice), and "aa" (3 of them) are the square subsequences.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def count_square_subsequences(s, t):
	m = len(s)
	n = len(t)
	T = [[0 for _ in range(n)] for _ in range(m)]
	T[0][0] = 1 if s[0] == t[0] else 0
	for i in range(1, n):
		T[0][i] = T[0][i - 1] + (1 if s[0] == t[i] else 0)
		T[0][i] %= 1000000007
	for i in range(1, m):
		T[i][0] = T[i - 1][0]
		T[i][0] %= 1000000007
	for i in range(1, m):
		for j in range(1, n):
			T[i][j] = T[i - 1][j] + T[i][j - 1] + (0 if s[i] == t[j] else -T[i - 1][j - 1])
			T[i][j] %= 1000000007
	return T[m - 1][n - 1]

def square_subsequences(string):
	m = len(string)
	R = 0
	for i in range(1, m):
		R += count_square_subsequences(string[i:], string[:i])
		R %= 1000000007
	return R

def main():
	T = int(input())
	for _ in range(T):
		print(square_subsequences(input()))
main()


from sys import stderr

def dp(a, b):
	c = [[0 for j in range(len(b))] for i in range(len(a))]
	for i in range(len(b)):
		if a[0] == b[i]:
			c[0][i] = 1
		if i:
			c[0][i] += c[0][i - 1]
			c[0][i] %= mod
	for i in range(1, len(a)):
		c[i][0] = c[i - 1][0]
		for j in range(1, len(b)):
			c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1]
			if a[i] == b[j]:
				c[i][j] += c[i - 1][j - 1]
				c[i][j] %= mod
	return c[len(a) - 1][len(b) - 1]

def backtrack(c, a, b, i, j):
	if i == 0 or j == 0:
		return ''
	elif a[i - 1] == b[j - 1]:
		return backtrack(c, a, b, i - 1, j - 1) + a[i - 1]
	elif c[i][j - 1] > c[i - 1][j]:
		return backtrack(c, a, b, i, j - 1)
	else:
		return backtrack(c, a, b, i - 1, j)
mod = 1000000007
t = int(input().strip())
for _ in ' ' * t:
	s = list(input().strip())
	s = ''.join((x for x in s if s.count(x) > 1))
	c = 0
	for k in range(1, len(s)):
		d = dp(s[k:], s[:k])
		print(s[:k], s[k:], file=stderr)
		print(d, file=stderr)
		c += d
		c %= mod
	print(c)


NUMBER = 1000000007

class SquareSubstring:

	def __init__(self):
		self.T = int(input())
		for i in range(self.T):
			string = input()
			print(self.solve(string))

	def solve_sub(self, string, size):
		s1 = string[:size]
		size1 = len(s1) + 1
		s2 = string[size:]
		size2 = len(s2) + 1
		f = [[0 for i in range(size2)] for j in range(size1)]
		for i in range(1, size1):
			for j in range(1, size2):
				if s1[i - 1] != s2[j - 1]:
					f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1]
				else:
					f[i][j] = f[i - 1][j] + f[i][j - 1] + 1
		return f[len(s1)][len(s2)] - f[len(s1) - 1][len(s2)]

	def solve(self, string):
		length = len(string)
		count = 0
		for i in range(length):
			count = (count + self.solve_sub(string, i)) % NUMBER
		return count
SquareSubstring()


tr = int(input().strip())
for t in range(tr):
	s = input().strip()
	n = len(s)
	T = [[0 for i in range(n)] for i in range(n)]
	sum = 0
	for p in range(1, n):
		for i in range(p):
			for j in range(p, n):
				left = T[i][j - 1] if j > p else 0
				above = T[i - 1][j] if i > 0 else 0
				diag = T[i - 1][j - 1] if j > p and i > 0 else 0
				if s[i] == s[j]:
					T[i][j] = left + above + 1
				else:
					T[i][j] = left + above - diag
		sum += T[p - 1][n - 1]
		if p > 1:
			sum -= T[p - 2][n - 1]
	print(sum % 1000000007)


mod = 1000000007

def squareSubSeq(a, b):
	m = len(a)
	n = len(b)
	DP = [[0 for x in range(n)] for x in range(m)]
	DP[0][0] = 1 if a[0] == b[0] else 0
	for i in range(1, n):
		DP[0][i] = DP[0][i - 1] + (1 if a[0] == b[i] else 0)
		DP[0][i] = DP[0][i] % mod
	for i in range(1, m):
		DP[i][0] = DP[i - 1][0]
		DP[i][0] = DP[i][0] % mod
	for i in range(1, m):
		for j in range(1, n):
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1] + (0 if a[i] == b[j] else -DP[i - 1][j - 1])
			DP[i][j] = DP[i][j] % mod
	return DP[m - 1][n - 1]

def subStrings(s):
	l = len(s)
	A = 0
	for i in range(1, l):
		A = A + squareSubSeq(s[i:], s[:i])
		A = A % mod
	return A
T = int(input())
for k in range(T):
	print(subStrings(input()))


case_count = int(input())
MOD = 1000000007

def solve(A, B):
	solutions = [[0] * len(A) for j in range(len(B))]
	for j in range(len(A)):
		solutions[0][j] = solutions[0][j - 1] + int(B[0] == A[j])
		solutions[0][j] %= MOD
	for i in range(1, len(B)):
		solutions[i][0] = solutions[i - 1][0]
		for j in range(1, len(A)):
			solutions[i][j] = solutions[i - 1][j] + solutions[i][j - 1]
			if A[j] != B[i]:
				solutions[i][j] -= solutions[i - 1][j - 1]
			solutions[i][j] %= MOD
	return solutions[-1][-1]

def task(source):
	result = 0
	for i in range(len(source) - 1):
		res = solve(source[:i + 1], source[i + 1:])
		result += res
		result %= MOD
	return result
for i in range(case_count):
	print(task(input()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


t = int(input().strip())

def comSub(str1, str2):
	n = len(str1)
	m = len(str2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if str1[i] == str2[j]:
				dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + 1
			else:
				dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
	return dp[n][m]
for _ in range(t):
	s = input().strip()
	n = len(s)
	comSubs = 0
	for i in range(1, n):
		comSubs = (comSubs + comSub(s[0:i], s[i:n]) - comSub(s[0:i], s[i + 1:n])) % 1000000007
	print(comSubs)


def subsequences(s, k):
	s1 = s[:k]
	s2 = s[k:]
	subs = [[0 for j in range(len(s) - k + 1)] for i in range(k + 1)]
	for i in range(k):
		for j in range(len(s) - k):
			if s1[i] == s2[j]:
				subs[i + 1][j + 1] = subs[i][j + 1] + subs[i + 1][j] + 1
			else:
				subs[i + 1][j + 1] = subs[i][j + 1] + subs[i + 1][j] - subs[i][j]
	return (subs[-1][-1] - subs[-2][-1]) % 1000000007
t = int(input())
for _ in range(t):
	s = input()
	print(sum((subsequences(s, k) for k in range(1, len(s)))) % 1000000007)


def count_common_subs(s1, s2):
	dp = [[0 for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s1)):
		for j in range(len(s2)):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] + 1
			else:
				dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j]
	return dp[-1][-1] - dp[-2][-1]

def find_sq_subs(s):
	result = 0
	for i in range(1, len(s)):
		s1 = s[:i]
		s2 = s[i:]
		result += count_common_subs(s1, s2)
	return result
import sys
_ = sys.stdin.readline()
modulo = 1000000007
for line in sys.stdin:
	print(find_sq_subs(line.strip()) % modulo)


def sub(s, size):
	s1 = s[:size]
	s2 = s[size:]
	N = [[0 for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(1, len(s1) + 1):
		for j in range(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]
num = int(input())
for n in range(num):
	inp = input()
	print(sum((sub(inp, i) for i in range(1, len(inp)))) % 1000000007)


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import array

class Solution:

	def __init__(self, A):
		self.A = A
		self.n = len(A)
		self.B = array.array('L')
		for i in range(self.n):
			self.B.append(0)

	def solve(self):
		result = 0
		for i in range(1, self.n):
			result = (result + self.solve_helper(i)) % 1000000007
		return result

	def solve_helper(self, k):
		self.init_left_side(k, 0, k)
		q = k + 1
		while q < self.n:
			self.go_one_step_right_side(q, 0, k)
			q = q + 1
		return self.B[k - 1]

	def init_left_side(self, fixed, start, end):
		self.B[fixed] = 0
		count = 0
		for i in range(start, end):
			if self.A[i] == self.A[fixed]:
				count = (count + 1) % 1000000007
			self.B[i] = count
		self.B[fixed] = count

	def go_one_step_right_side(self, to_update, start, end):
		t = to_update
		inc = 0
		temp = 0
		for i in range(start, end):
			if self.A[t] == self.A[i]:
				inc = (inc + temp) % 1000000007
			temp = self.B[i]
			self.B[i] = (self.B[i] + inc) % 1000000007
		self.B[t] = (temp + inc) % 1000000007
import sys
data = sys.stdin.readlines()
N = int(data[0])
for i in range(N):
	print(Solution(data[i + 1]).solve())


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


t = int(input().strip())

def comSub(str1, str2):
	n = len(str1)
	m = len(str2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if str1[i] == str2[j]:
				dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + 1
			else:
				dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
	return dp[n][m]
for _ in range(t):
	s = input().strip()
	n = len(s)
	comSubs = 0
	for i in range(1, n):
		comSubs = (comSubs + comSub(s[0:i], s[i:n]) - comSub(s[0:i], s[i + 1:n])) % 1000000007
	print(comSubs)


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


def f(a, b):
	row = len(a) + 1
	col = len(b) + 1
	dp = [[0] * col for _ in range(row)]
	r = 0
	for i in range(1, row):
		for j in range(1, col):
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
			if a[i - 1] == b[j - 1]:
				if i == row - 1:
					r += dp[i - 1][j - 1] + 1
					r %= 10 ** 9 + 7
				dp[i][j] += dp[i - 1][j - 1] + 1
	return r

def solve(string):
	ans = 0
	n = len(string)
	for i in range(1, n):
		ans += f(string[:i], string[i:])
		ans %= 10 ** 9 + 7
	return ans
t = int(input())
for t_itr in range(t):
	s = input()
	print(solve(s))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
from collections import defaultdict

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	NUMBER = 1000000007
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
from collections import Counter, defaultdict
from itertools import combinations

def check_square(intuple):
	mid = len(intuple) // 2
	for i in range(mid):
		if intuple[i] != intuple[i + mid]:
			return False
	return True
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


import os
import sys
from collections import Counter
from itertools import combinations
import re
NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))


NUMBER = 1000000007

def solve_sub(string, size):
	s1 = string[:size]
	size1 = len(s1) + 1
	s2 = string[size:]
	size2 = len(s2) + 1
	N = [[0 for j in range(size2)] for i in range(size1)]
	for i in range(1, size1):
		for j in range(1, size2):
			if s1[i - 1] == s2[j - 1]:
				N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
			else:
				N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]
	return N[-1][-1] - N[-2][-1]

def solve(string):
	count = sum((solve_sub(string, i) for i in range(1, len(string))))
	return count % NUMBER
import sys
_ = sys.stdin.readline()
for line in sys.stdin:
	print(solve(line.strip()))