Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "bobseesanna" can be created by some ways:

* bobseesanna = bob + sees + anna

* bobseesanna = bob + s + ee + s + anna

* bobseesanna = b + o + b + sees + a + n + n + a

...

We want to take the value of function CountPal(s) which is the number of different ways to use the palindromes to create the string s by the above method.

------ Input ------ 

The string s

------ Output ------ 

The value of function CountPal(s), taking the modulo of 1 000 000 007 (10^{9}+7)

------ Limitations ------ 

0 < |s| ≤ 1000

----- Sample Input 1 ------ 
bobseesanna
----- Sample Output 1 ------ 
18

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics


Solutions:
MOD = 10 ** 9 + 7

def count_palindrome(s):
	n = len(s)
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		for j in range(1, i + 1):
			if s[j - 1:i] == s[j - 1:i][::-1]:
				dp[i] += dp[j - 1]
				dp[i] %= MOD
	return dp[n]
s = input().strip()
print(count_palindrome(s))


def soln(s):
	n = len(s)
	dp = [1]
	for i in range(1, n):
		cur = 0
		for j in range(i + 1):
			ss = s[j:i + 1]
			if ss == ss[::-1]:
				cur += dp[j - 1] if j > 0 else 1
		dp.append(cur)
	return dp[-1] % (10 ** 9 + 7)
print(soln(input()))


s = input()
l = len(s)
d = [1]
ans = 0
for i in range(1, l):
	ans = 0
	for j in range(i + 1):
		m = s[j:i + 1]
		if m[::-1] == m:
			x = d[j - 1]
			if j - 1 < 0:
				x = 1
			ans += x
	d.append(ans)
print(d[-1] % (10 ** 9 + 7))


from sys import *

def solve():
	s = stdin.readline().rstrip()
	n = len(s)
	modulo = 1000000000 + 7
	count = [1] * (n + 1)
	is_palindrome = [[True] * n for _ in range(n)]
	for i in range(n - 1):
		count[i + 2] = count[i + 1]
		for j in range(i + 1):
			if s[j] != s[i + 1] or not is_palindrome[j + 1][i]:
				is_palindrome[j][i + 1] = False
			else:
				count[i + 2] = (count[i + 2] + count[j]) % modulo
	print(count[-1])
solve()


for _ in range(1):
	s = input()
	n = len(s)
	MOD = 10 ** 9 + 7
	dp = [1]
	ans = 0
	for i in range(1, n):
		ans = 0
		for j in range(0, i + 1):
			temp1 = s[j:i + 1]
			if temp1[::-1] == temp1:
				x = dp[j - 1]
				if j - 1 < 0:
					x = 1
				ans += x
		dp.append(ans)
	print(dp[-1] % MOD)


T = input()
a = len(T)
b = [1]
for i in range(1, a):
	sum = 0
	for j in range(i + 1):
		M = T[j:i + 1]
		if M[::-1] == M:
			x = b[j - 1]
			if j - 1 < 0:
				x = 1
			sum += x
	b.append(sum)
print(b[-1] % (10 ** 9 + 7))


s = input()
n = len(s)
dp = [1]
ans = 0
for i in range(1, len(s)):
	ans = 0
	for j in range(i + 1):
		tem = s[j:i + 1]
		if tem[::-1] == tem:
			x = dp[j - 1]
			if j - 1 < 0:
				x = 1
			ans += x
	dp.append(ans)
print(dp[-1] % (10 ** 9 + 7))


MD = 1000000007
st = input().strip()
s = chr(7) + st + chr(8)
sz = len(s)
A = [[] for x in range(sz)]
for p in range(1, sz - 1):
	k = 1
	while s[p - k] == s[p + k]:
		A[p - k].append(2 * k + 1)
		k += 1
for p in range(2, sz - 1):
	k = 1
	while s[p - k] == s[p + k - 1]:
		A[p - k].append(2 * k)
		k += 1
Z = [0 for x in range(sz)]
Z[1] = 1
for p in range(1, sz - 1):
	n = Z[p] % MD
	Z[p + 1] += n
	for k in A[p]:
		Z[p + k] += n
	p += 1
r = Z[-1] % MD
print(r)


from sys import stdin, stdout
import math
from collections import Counter
import functools
from functools import reduce
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	s = line()
	n = len(s)
	modulo = 1000000007
	count = [1 for i in range(n + 1)]
	is_palindrome = [[True for _ in range(n)] for _ in range(n)]
	for i in range(n - 1):
		count[i + 2] = count[i + 1]
		for j in range(i + 1):
			if s[j] != s[i + 1] or not is_palindrome[j + 1][i]:
				is_palindrome[j][i + 1] = False
			else:
				count[i + 2] = (count[i + 2] + count[j]) % modulo
	print(count[-1])
main()


s = input()
import sys
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache
n = len(s)

@lru_cache(None)
def is_pal(l, r):
	if l >= r:
		return True
	return s[l] == s[r] and is_pal(l + 1, r - 1)
mod = 10 ** 9 + 7
dp = [1] + [0] * n
for i in range(1, n + 1):
	dp[i] = dp[i - 1]
	for j in range(i - 1):
		if is_pal(j, i - 1):
			dp[i] += dp[j]
			dp[i] %= mod
print(dp[-1])


s = input()
n = len(s)
is_p = [[1 for i in range(n)] for i in range(n)]
for d in range(n - 1, -1, -1):
	for i in range(d):
		j = i + n - d
		is_p[i][j] = 0
		if s[i] == s[j] and is_p[i + 1][j - 1]:
			is_p[i][j] = 1
dp = [1] + [0] * n
for i in range(1, n + 1):
	dp[i] = dp[i - 1]
	for j in range(i - 1):
		if is_p[j][i - 1]:
			dp[i] += dp[j]
print(dp[-1] % 1000000007)


l = list(input())
n = len(l)
ispal = [[1 for i in range(n)] for j in range(n)]
cnt = [1] * (n + 1)
MOD = 10 ** 9 + 7
for i in range(n - 1):
	cnt[i + 2] = cnt[i + 1]
	for j in range(0, i + 1):
		(a, b) = (j, i + 1)
		if l[a] != l[b] or not ispal[a + 1][b - 1]:
			ispal[a][b] = 0
		else:
			cnt[i + 2] = (cnt[i + 2] + cnt[a]) % MOD
print(cnt[n] % MOD)


text = input()
n = len(text)
arr = [[1 for _ in range(n)] for _ in range(n)]
count = [1] + [1] * n
mod = 1000000007
for i in range(n - 1):
	count[i + 2] = count[i + 1]
	for j in range(0, i + 1):
		(a, b) = (j, i + 1)
		if text[a] != text[b] or not arr[a + 1][b - 1]:
			arr[a][b] = 0
		else:
			count[i + 2] = (count[i + 2] + count[a]) % mod
print(count[-1])