A border of a string is a proper prefix of it that is also a suffix. For example:

a and abra are borders of abracadabra,
kan and kankan are borders of kankankan. 
de is a border of decode. 

Note that decode is not a border of decode because it's not proper.

A palindromic border is a border that is palindromic. For example,

a and ana are palindromic borders of anabanana, 
l, lol and lolol are palindromic borders of lololol.

Let's define $P(s)$ as the number of palindromic borders of string $\boldsymbol{\mathrm{~s~}}$. For example, if $\boldsymbol{s}=$ lololol, then $P(s)=3$. 

Now, a string of length $N$ has exactly $N(N+1)/2$ non-empty substrings (we count substrings as distinct if they are of different lengths or are in different positions, even if they are the same string). Given a string $\boldsymbol{\mathrm{~s~}}$, consisting only of the first 8 lowercase letters of the English alphabet, your task is to find the sum of $P(s^{\prime})$ for all the non-empty substrings ${s'}$ of $\boldsymbol{\mathrm{~s~}}$. In other words, you need to find:
$\sum\limits_{1\leq i\leq j\leq N}P\left(s_{i\ldots j}\right)$
where $s_{i\ldots j}$ is the substring of $\boldsymbol{\mathrm{~s~}}$ starting at position $\boldsymbol{i}$ and ending at position $j$.

Since the answer can be very large, output the answer modulo $10^9+7$.

Input Format  

The first line contains a string consisting of $N$ characters.

Output Format  

Print a single integer: the remainder of the division of the resulting number by $10^9+7$.

Constraints  

$1\leq N\leq10^5$ 

All characters in the string can be any of the first 8 lowercase letters of the English alphabet (abcdefgh).  

Sample Input 1  

ababa

Sample Output 1  

5

Sample Input 2  

aaaa

Sample Output 2  

10

Sample Input 3  

abcacb

Sample Output 3  

3

Explanation  

$\boldsymbol{s}=$ ababa has 15 substrings but only 4 substrings have palindromic borders.  

$s_{1\ldots3}=$ aba    $\longrightarrow P(s_{1\ldots3})=1$ 

$s_{1\ldots5}=$ ababa  $\longrightarrow P(s_{1...5})=2$ 

$s_{2\ldots4}=$ bab    $\longrightarrow P(s_{2\ldots4})=1$ 

$s_{3\ldots5}=$ aba    $\rightarrow P(s_{3\ldots5})=1$

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


import math
import os
import random
import re
import sys

def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


import math
import os
import random
import re
import sys

def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


import math
import os
import random
import re
import sys

def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	outpt = 0
	for (paln, tmes) in palin_dict.items():
		outpt += tmes * (tmes - 1) // 2
	return outpt

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	outpt = 0
	for i in range(2, len(s) + 1):
		outpt += i * (i - 1) // 2
		outpt %= 1000000007
	return outpt

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	outpt = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	outpt += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	outpt += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		outpt += calc_palin_borders(new_tuple[1])
		outpt %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return outpt
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


import math
import os
import random
import re
import sys

def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def mod(x):
	return x % 1000000007

class trie(object):

	def __init__(self, depth=0, parent=None, data=None):
		self.count = 0
		self.depth = depth
		self.parent = parent
		self.data = data
		self.next = {}

	def get(self, char):
		if char in self.next:
			return self.next[char]
		ans = trie(self.depth + 2, self, char)
		self.next[char] = ans
		return ans

	def children(self):
		return self.next.values()

def dfs(node):
	ans = 0
	stack = []
	stack.append((node, True))
	while len(stack) > 0:
		(node, extend) = stack.pop()
		if extend:
			stack.append((node, False))
			for child in node.children():
				stack.append((child, True))
		else:
			for child in node.children():
				node.count += child.count
			if node.depth > 0:
				ans = mod(ans + mod(node.count * (node.count - 1) // 2))
	return ans

def pr(node):
	print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
	for child in node.children():
		pr(child)

def score(string):
	string = list(map(ord, string))
	N = len(string) * 2 + 1
	c = [0] * N
	c[1::2] = string
	odd = trie(depth=-1)
	even = trie()
	(center, radius) = (0, 0)
	(left, right) = (0, 0)
	node = [even]
	span = [0]
	for i in range(1, N):
		if i > radius:
			node.append(odd.get(c[i]) if i & 1 else even)
			span.append(0)
			left = i - 1
			right = i + 1
		else:
			mirror = center * 2 - i
			if span[mirror] < radius - i:
				span.append(span[mirror])
				node.append(node[mirror])
				left = -1
			else:
				span.append(radius - i)
				node.append(node[mirror])
				while node[i].depth > radius - i:
					node[i] = node[i].parent
				right = radius + 1
				left = i * 2 - right
		while left >= 0 and right < N and (c[left] == c[right]):
			if c[right]:
				node[i] = node[i].get(c[right])
			span[i] += 1
			left -= 1
			right += 1
		node[i].count += 1
		if i + span[i] > radius:
			center = i
			radius = i + span[i]
	return mod(dfs(odd) + dfs(even))
print(score(str(input())))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))


def is_palin(s):
	(head, tail) = (0, len(s) - 1)
	while head < tail:
		if s[head] != s[tail]:
			return False
		head += 1
		tail -= 1
	return True

def calc_palin_borders(palin_dict):
	output = 0
	for (palin, times) in palin_dict.items():
		output += times * (times - 1) // 2
	return output

def mono_str(s):
	cc = s[0]
	for c in s:
		if c != cc:
			return False
	return True

def mono_str_result(s):
	output = 0
	for i in range(2, len(s) + 1):
		output += i * (i - 1) // 2
		output %= 1000000007
	return output

def pb(s):
	if mono_str(s):
		return mono_str_result(s)
	output = 0
	odd = [[], {}, 1]
	for c in s:
		if c not in odd[1]:
			odd[1][c] = 0
		odd[1][c] += 1
	for i in range(len(s)):
		odd[0].append(i)
	output += calc_palin_borders(odd[1])
	even = [[], {}, 1]
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			even[0].append(i)
			ss = s[i:i + 2]
			if ss not in even[1]:
				even[1][ss] = 0
			even[1][ss] += 1
	output += calc_palin_borders(even[1])
	for l in range(3, len(s)):
		if l % 2 == 0:
			wt = even
		else:
			wt = odd
		new_tuple = [[], {}, l]
		for idx in wt[0]:
			if idx - 1 >= 0 and idx + l - 2 < len(s) and (s[idx - 1] == s[idx + l - 2]):
				new_tuple[0].append(idx - 1)
				ss = s[idx - 1:idx - 1 + l]
				if ss not in new_tuple[1]:
					new_tuple[1][ss] = 0
				new_tuple[1][ss] += 1
		output += calc_palin_borders(new_tuple[1])
		output %= 1000000007
		if l % 2 == 0:
			even = new_tuple
		else:
			odd = new_tuple
	return output
print(pb(input()))