Given a string str of length N, you have to find number of palindromic subsequence (need not necessarily be distinct) present in the string str.
Note: You have to return the answer module 10^{9}+7;
 
Example 1:
Input: 
Str = "abcd"
Output: 
4
Explanation:
palindromic subsequence are : "a" ,"b", "c" ,"d"
 
Example 2:
Input: 
Str = "aab"
Output: 
4
Explanation:
palindromic subsequence are :"a", "a", "b", "aa"
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPs() which takes a string str as input parameter and returns the number of palindromic subsequence.
 
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N*N)
Constraints:
1<=length of string str <=1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: class Solution:

    # Your task is to complete this function

    # Function should return an integer

    def countPS(self,string):

        # Code here



Solutions:
class Solution:

	def countPS(self, s):
		n = len(s)
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for length in range(2, n + 1):
			for i in range(n - length, -1, -1):
				j = i + length - 1
				if s[i] == s[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
		return dp[0][n - 1] % (10 ** 9 + 7)


import numpy as np

class Solution:

	def rec_sol(self, start, end, string):
		if start == end:
			return 1
		if start > end:
			return 0
		if string[start] == string[end]:
			return 1 + self.rec_sol(start, end - 1, string) + self.rec_sol(start + 1, end, string)
		else:
			return self.rec_sol(start, end - 1, string) + self.rec_sol(start + 1, end, string) - self.rec_sol(start + 1, end - 1, string)

	def dp_sol(self, string):
		len_s = len(string)
		dp = np.array([[0] * len_s] * len_s)
		for i in range(len_s):
			for j in range(i, -1, -1):
				if i == j:
					dp[j][i] = 1
				elif string[i] == string[j]:
					dp[j][i] = (1 + dp[j][i - 1] + dp[j + 1][i]) % 1000000007
				else:
					dp[j][i] = (dp[j][i - 1] + dp[j + 1][i] - dp[j + 1][i - 1]) % 1000000007
		return dp[0][len_s - 1]

	def countPS(self, string):
		return self.dp_sol(string)


class Solution:

	def solve(self, i, j, s, dp):
		if i > j:
			return 0
		if i == j:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i] == s[j]:
			ans = self.solve(i + 1, j, s, dp) + self.solve(i, j - 1, s, dp) + 1
		else:
			ans = self.solve(i + 1, j, s, dp) + self.solve(i, j - 1, s, dp) - self.solve(i + 1, j - 1, s, dp)
		dp[i][j] = ans
		return ans

	def countPS(self, string):
		n = len(string)
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		ans = self.solve(0, n - 1, string, dp)
		ans = ans % (10 ** 9 + 7)
		return ans


class Solution:

	def countPS(self, s):
		m = 1000000007
		n = len(s)
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for cl in range(2, n + 1):
			for i in range(n - cl + 1):
				j = i + cl - 1
				if s[i] == s[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
		return dp[0][n - 1] % m


class Solution:

	def countPS(self, string):
		N = len(string)
		dp = [[0 for j in range(N)] for i in range(N)]
		for g in range(0, N):
			i = 0
			j = g
			while j < N:
				if g == 0:
					dp[i][j] = 1
				elif g == 1:
					if string[i] == string[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif string[i] == string[j]:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
				i += 1
				j += 1
		return dp[0][N - 1] % (10 ** 9 + 7)


class Solution:

	def countPS1(self, st, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		elif st[i] == st[j]:
			dp[i][j] = self.countPS1(st, i + 1, j, dp) + self.countPS1(st, i, j - 1, dp) + 1
		else:
			dp[i][j] = self.countPS1(st, i + 1, j, dp) + self.countPS1(st, i, j - 1, dp) - self.countPS1(st, i + 1, j - 1, dp)
		return dp[i][j]

	def countPS(self, string):
		n = len(string)
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		a = self.countPS1(string, 0, n - 1, dp)
		return a % 1000000007


class Solution:

	def countPS(self, string):
		MOD = int(1000000000.0) + 7
		n = len(string)
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if string[i] == string[j]:
					dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % MOD
				else:
					dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % MOD
		return dp[0][n - 1]


class Solution:

	def countPS(self, string):

		def subs(i, j, strg):
			if i > j:
				return 0
			if i == j:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			if strg[i] == strg[j]:
				dp[i][j] = subs(i + 1, j, strg) + subs(i, j - 1, strg) + 1
			else:
				dp[i][j] = subs(i + 1, j, strg) + subs(i, j - 1, strg) - subs(i + 1, j - 1, strg)
			return dp[i][j]
		n = len(string)
		MOD = 10 ** 9 + 7
		dp = [[-1] * n for i in range(n)]
		ans = subs(0, n - 1, string)
		return ans % MOD


class Solution:

	def countPS(self, str):
		N = len(str)
		cps = [[0 for i in range(N + 2)] for j in range(N + 2)]
		for i in range(N):
			cps[i][i] = 1
		for L in range(2, N + 1):
			for i in range(N):
				k = L + i - 1
				if k < N:
					if str[i] == str[k]:
						cps[i][k] = cps[i][k - 1] + cps[i + 1][k] + 1
					else:
						cps[i][k] = cps[i][k - 1] + cps[i + 1][k] - cps[i + 1][k - 1]
		return cps[0][N - 1] % (pow(10, 9) + 7)


class Solution:

	def countPS(self, string):
		if len(string) == 0:
			return 0
		big = 10 ** 9 + 7
		dp = [[-1 for _ in range(len(string))] for __ in range(len(string))]
		return self.num_pal(string, dp, 0, len(string) - 1, big)

	def num_pal(self, s, arr, start, end, mod):
		if start == end:
			return 1
		if start > end:
			return 0
		if arr[start][end] != -1:
			return arr[start][end]
		if s[start] == s[end]:
			arr[start][end] = 1 + self.num_pal(s, arr, start + 1, end, mod) % mod + self.num_pal(s, arr, start, end - 1, mod) % mod
			arr[start][end] %= mod
		else:
			arr[start][end] = self.num_pal(s, arr, start + 1, end, mod) % mod + self.num_pal(s, arr, start, end - 1, mod) % mod - self.num_pal(s, arr, start + 1, end - 1, mod) % mod
			arr[start][end] %= mod
		return arr[start][end]


class Solution:

	def countPS(self, s):
		dp = [[-1] * len(s) for _ in range(len(s))]

		def rec(i, j):
			nonlocal dp, s
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = 1
				return dp[i][j]
			if i > j:
				return 0
			if s[i] == s[j]:
				a = rec(i + 1, j) + rec(i, j - 1) + 1
				dp[i][j] = a
				return a
			else:
				a = rec(i + 1, j) + rec(i, j - 1) - rec(i + 1, j - 1)
				dp[i][j] = a
				return a
		return rec(0, len(s) - 1) % (10 ** 9 + 7)


class Solution:

	def countPS(self, s):
		n = len(s)
		dp = {}
		mod = 10 ** 9 + 7

		def backtracking(start, end):
			if (start, end) in dp:
				return dp[start, end]
			if start == end:
				dp[start, end] = 1
				return 1
			if start > end:
				dp[start, end] = 0
				return 0
			if s[start] == s[end]:
				dp[start, end] = 1 + backtracking(start + 1, end) + backtracking(start, end - 1)
				return dp[start, end] % mod
			else:
				dp[start, end] = backtracking(start + 1, end) + backtracking(start, end - 1) - backtracking(start + 1, end - 1)
				return dp[start, end] % mod
		return backtracking(0, n - 1)


class Solution:

	def countPS(self, s):
		cnt = 0
		dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
		for g in range(len(s)):
			i = 0
			for j in range(g, len(s)):
				if g == 0:
					dp[i][j] = 1
				elif g == 1:
					if s[i] == s[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif s[i] == s[j]:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1
				else:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
				i += 1
		return dp[0][len(s) - 1] % (10 ** 9 + 7)


class Solution:

	def countPS(self, string1):
		self.string1 = string1
		self.n = len(string1)
		self.t = [[-1 for _ in range(self.n + 1)] for _ in range(self.n + 1)]
		return self.count_palindromic_subsequence(i=0, j=self.n - 1) % (10 ** 9 + 7)

	def count_palindromic_subsequence(self, i, j):
		if i > j:
			return 0
		if self.t[i][j] != -1:
			return self.t[i][j]
		if i == j:
			self.t[i][j] = 1
			return self.t[i][j]
		elif self.string1[i] == self.string1[j]:
			self.t[i][j] = 1 + self.count_palindromic_subsequence(i + 1, j) + self.count_palindromic_subsequence(i, j - 1)
			return self.t[i][j]
		else:
			self.t[i][j] = self.count_palindromic_subsequence(i + 1, j) + self.count_palindromic_subsequence(i, j - 1) - self.count_palindromic_subsequence(i + 1, j - 1)
			return self.t[i][j]


class Solution:

	def countPS(self, string):
		n = len(string)
		dp = [[False for i in range(n)] for j in range(n)]
		mod = 1000000007
		for gap in range(n):
			(i, j) = (0, gap)
			while j < n:
				if gap == 0:
					dp[i][j] = 1
				elif gap == 1:
					if string[i] == string[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif string[i] == string[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
				dp[i][j] = dp[i][j] % mod
				i += 1
				j += 1
		return dp[0][n - 1]


class Solution:

	def recur(self, i, j, string, dp):
		if i > j:
			return 0
		if i == j:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		if string[i] == string[j]:
			dp[i][j] = self.recur(i + 1, j, string, dp) + self.recur(i, j - 1, string, dp) + 1
		else:
			dp[i][j] = self.recur(i + 1, j, string, dp) + self.recur(i, j - 1, string, dp) - self.recur(i + 1, j - 1, string, dp)
		return dp[i][j]

	def countPS(self, string):
		dp = [[-1 for i in range(len(string))] for j in range(len(string))]
		return self.recur(0, len(string) - 1, string, dp) % (10 ** 9 + 7)


class Solution:

	def countPSUtil(self, i, j, dp, s):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if i == j:
			dp[i][j] = 1
		elif s[i] == s[j]:
			dp[i][j] = self.countPSUtil(i + 1, j, dp, s) + self.countPSUtil(i, j - 1, dp, s) + 1
		else:
			dp[i][j] = self.countPSUtil(i + 1, j, dp, s) + self.countPSUtil(i, j - 1, dp, s) - self.countPSUtil(i + 1, j - 1, dp, s)
		return dp[i][j] % self.mod

	def countPS(self, s):
		self.mod = 10 ** 9 + 7
		n = len(s)
		dp = [[-1 for x in range(n + 1)] for y in range(n + 1)]
		self.countPSUtil(0, n - 1, dp, s)
		return dp[0][n - 1] % self.mod


class Solution:

	def countPS(self, arr):

		def count(i, j, arr, dp):
			if i > j:
				return 0
			if i == j:
				dp[i][j] = 1
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			if arr[i] == arr[j]:
				dp[i][j] = 1 + count(i + 1, j, arr, dp) + count(i, j - 1, arr, dp)
				return dp[i][j]
			dp[i][j] = count(i + 1, j, arr, dp) + count(i, j - 1, arr, dp) - count(i + 1, j - 1, arr, dp)
			return dp[i][j]
		dp = [[-1] * len(arr) for x in range(len(arr))]
		return count(0, len(arr) - 1, arr, dp) % (10 ** 9 + 7)


class Solution:

	def countPS(self, s):

		def manu(i, j):
			if i > j:
				return 0
			if i == j:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j]:
				k = 1 + manu(i + 1, j) + manu(i, j - 1)
			else:
				k = manu(i + 1, j) + manu(i, j - 1) - manu(i + 1, j - 1)
			k = k % (10 ** 9 + 7)
			dp[i][j] = k
			return k
		dp = [[-1 for i in range(len(s))] for i in range(len(s))]
		return manu(0, len(s) - 1)


class Solution:

	def countPS(self, string):
		n = len(string)
		count = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			count[i][i] = 1
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if string[i] == string[j]:
					count[i][j] = 1 + count[i][j - 1] + count[i + 1][j]
				else:
					count[i][j] = count[i][j - 1] + count[i + 1][j] - count[i + 1][j - 1]
		return count[0][n - 1] % (10 ** 9 + 7)


from itertools import combinations

class Solution:

	def countPS(self, string):

		def subs(i, j, strng):
			if i > j:
				return 0
			if i == j:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			if strng[i] == strng[j]:
				dp[i][j] = subs(i + 1, j, strng) + subs(i, j - 1, strng) + 1
			else:
				dp[i][j] = subs(i + 1, j, strng) + subs(i, j - 1, strng) - subs(i + 1, j - 1, strng)
			return dp[i][j]
		dp = [[-1] * len(string) for i in range(len(string))]
		return subs(0, len(string) - 1, string) % (10 ** 9 + 7)


class Solution:

	def countPS(self, string):

		def count(i, j, st, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				return 1
			elif st[i] == st[j]:
				dp[i][j] = 1 + count(i + 1, j, st, dp) + count(i, j - 1, st, dp)
				return dp[i][j] % 1000000007
			else:
				dp[i][j] = count(i + 1, j, st, dp) + count(i, j - 1, st, dp) - count(i + 1, j - 1, st, dp)
				return dp[i][j] % 1000000007
		dp = [[-1 for j in range(len(string))] for i in range(len(string))]
		return count(0, len(string) - 1, string, dp)


class Solution:

	def countPS(self, s):
		n = len(s)
		dp = {}
		mod = 1000000007

		def fun(i, j):
			if i > j:
				return 0
			if i == j:
				return 1
			if (i, j) in dp:
				return dp[i, j]
			if s[i] == s[j]:
				dp[i, j] = 1 + fun(i + 1, j) + fun(i, j - 1)
				return dp[i, j]
			dp[i, j] = fun(i + 1, j) + fun(i, j - 1) - fun(i + 1, j - 1)
			return dp[i, j]
		return fun(0, len(s) - 1) % mod


class Solution:

	def countPS(self, string):

		def func(i, j, stri, dp):
			if i > j:
				return 0
			if i == j:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			if stri[i] == stri[j]:
				dp[i][j] = 1 + func(i + 1, j, stri, dp) + func(i, j - 1, stri, dp)
				return dp[i][j]
			else:
				dp[i][j] = func(i + 1, j, stri, dp) + func(i, j - 1, stri, dp) - func(i + 1, j - 1, stri, dp)
				return dp[i][j]
		dp = [[-1 for i in range(len(string))] for j in range(len(string))]
		kk = func(0, len(string) - 1, string, dp)
		return kk % (10 ** 9 + 7)


class Solution:

	def countPS(self, s):
		N = len(s)
		mod = 10 ** 9 + 7
		dp = [[0] * N for _ in range(N)]
		for i in range(N):
			dp[i][i] = 1
		for L in range(2, N + 1):
			for i in range(N - L + 1):
				j = i + L - 1
				if s[i] == s[j]:
					dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % mod
				else:
					dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % mod
				dp[i][j] %= mod
		return dp[0][N - 1] % mod


class Solution:

	def countPS(self, string):
		n = len(string)
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]

		def sol(i, j, string, dp):
			mod = 1000000000.0 + 7
			if i == j:
				return 1
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if string[i] == string[j]:
				dp[i][j] = (1 + sol(i + 1, j, string, dp) + sol(i, j - 1, string, dp)) % mod
			else:
				dp[i][j] = ((sol(i + 1, j, string, dp) + sol(i, j - 1, string, dp) - sol(i + 1, j - 1, string, dp)) % mod + mod) % mod
			return dp[i][j]
		return int(sol(0, len(string) - 1, string, dp))


class Solution:

	def countPS(self, string):
		dp = [[None] * len(string) for _ in range(len(string))]

		def fun(i, j):
			if i == j:
				return 1
			if i > j:
				return 0
			if dp[i][j] != None:
				return dp[i][j]
			if string[i] == string[j]:
				dp[i][j] = 1 + fun(i + 1, j) + fun(i, j - 1)
				return dp[i][j] % (pow(10, 9) + 7)
			else:
				dp[i][j] = fun(i + 1, j) + fun(i, j - 1) - fun(i + 1, j - 1)
				return dp[i][j] % (pow(10, 9) + 7)
		return fun(0, len(string) - 1)


class Solution:

	def countPS(self, s):
		dp = [[0] * len(s) for i in range(len(s))]
		for gap in range(len(s)):
			for i in range(len(s) - gap):
				j = i + gap
				if i == j:
					dp[i][j] = 1
				else:
					if s[i] == s[j]:
						dp[i][j] = 1 + dp[i + 1][j] + dp[i][j - 1]
					else:
						dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
					dp[i][j] = dp[i][j] % 1000000007
		return dp[0][len(s) - 1]


class Solution:

	def countPS(self, string):
		n = len(string)
		mod = 10 ** 9 + 7
		dp = [[0] * n for i in range(n)]
		for g in range(0, n):
			for (i, j) in zip(range(0, n), range(g, n)):
				if g == 0:
					dp[i][j] = 1
				elif g == 1:
					if string[i] == string[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif string[i] == string[j]:
					dp[i][j] = (dp[i][j - 1] + dp[i + 1][j] + 1) % mod
				else:
					dp[i][j] = (dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]) % mod
		return dp[0][n - 1] % mod


import sys
sys.setrecursionlimit(10000)

class Solution:

	def countPS(self, stringe):
		hmap = {}
		n = len(stringe)

		def count_palindrome_sub(S, i, j):
			mod = 1000000000.0 + 7
			if i > j:
				return 0
			if i == j:
				return 1
			if (i, j) not in hmap:
				hmap[i, j] = count_palindrome_sub(S, i + 1, j) % mod + count_palindrome_sub(S, i, j - 1) % mod
				if S[i] == S[j]:
					hmap[i, j] += 1
				else:
					hmap[i, j] -= count_palindrome_sub(S, i + 1, j - 1) % mod
			return hmap[i, j]
		ans = count_palindrome_sub(stringe, 0, n - 1)
		return int(ans % (1000000000.0 + 7))


class Solution:

	def countPS(self, string):
		s = string
		N = len(s)
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N, -1, -1):
			for j in range(i, N, 1):
				if i == j:
					dp[i][j] = 1
				elif s[i] == s[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
		return dp[0][N - 1] % (pow(10, 9) + 7)


class Solution:

	def countPS(self, string):
		arr = [[-1 for i in range(len(string))] for j in range(len(string))]
		(i, j) = (0, len(string) - 1)
		res = self.cpsHelper(string, i, j, arr)
		return res % (10 ** 9 + 7)

	def cpsHelper(self, string, i, j, arr):
		if i > j:
			return 0
		if arr[i][j] != -1:
			return arr[i][j]
		if string[i] == string[j]:
			res = self.cpsHelper(string, i + 1, j, arr) + self.cpsHelper(string, i, j - 1, arr) + 1
		else:
			res = self.cpsHelper(string, i + 1, j, arr) + self.cpsHelper(string, i, j - 1, arr) - self.cpsHelper(string, i + 1, j - 1, arr)
		arr[i][j] = res
		return res


class Solution:

	def countPS(self, s):
		dp = [[0] * len(s) for i in range(len(s))]
		for gap in range(len(s)):
			i = 0
			j = gap
			while j < len(s):
				if gap == 0:
					dp[i][j] = 1
				elif gap == 1:
					if s[i] == s[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif s[i] == s[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
				i = i + 1
				j = j + 1
		return dp[0][-1] % 1000000007


class Solution:

	def countPS(self, s):
		n = len(s)
		dp = [[0 for i in range(n)] for j in range(n)]
		fp = sp = 0
		for i in range(n):
			dp[i][i] = 1
		for i in range(1, n):
			for j in range(n - i):
				fp = j
				sp = j + i
				if s[fp] == s[sp]:
					dp[fp][sp] = (dp[fp + 1][sp] + dp[fp][sp - 1] + 1) % (10 ** 9 + 7)
				else:
					dp[fp][sp] = (dp[fp + 1][sp] + dp[fp][sp - 1] - dp[fp + 1][sp - 1]) % (10 ** 9 + 7)
		return dp[fp][sp]


class Solution:

	def countPS(self, s):
		dp = []
		ans = 0
		for i in range(len(s)):
			dp.append([0] * len(s))
		for i in range(len(s)):
			dp[i][i] = 1
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				dp[i][i + 1] = 3
			else:
				dp[i][i + 1] = 2
		for lent in range(2, len(s)):
			i = 0
			while i + lent < len(s):
				if s[i] != s[i + lent]:
					dp[i][i + lent] = dp[i + 1][i + lent] + dp[i][i + lent - 1] - dp[i + 1][i + lent - 1]
				else:
					dp[i][i + lent] = dp[i + 1][i + lent] + dp[i][i + lent - 1] + 1
				i += 1
		return dp[0][len(s) - 1] % (10 ** 9 + 7)


class Solution:

	def countPS(self, s):
		t = [[-1 for i in range(1001)] for i in range(1001)]
		mod = 10 ** 9 + 7

		def solve(s, i, j, t):
			if i == j:
				return 1
			if i > j:
				return 0
			if t[i][j] != -1:
				return t[i][j]
			elif s[i] == s[j]:
				t[i][j] = 1 + solve(s, i + 1, j, t) % mod + solve(s, i, j - 1, t) % mod
				t[i][j] %= mod
				return t[i][j]
			else:
				t[i][j] = solve(s, i + 1, j, t) % mod + solve(s, i, j - 1, t) % mod - solve(s, i + 1, j - 1, t) % mod
				t[i][j] %= mod
				return t[i][j]
		return solve(s, 0, len(s) - 1, t)


class Solution:

	def countPS(self, string):
		S = string
		n = len(S)
		dp = [[0] * n for i in range(n)]
		M = 10 ** 9 + 7
		for i in range(n):
			for j in range(i, -1, -1):
				if i == j:
					dp[j][i] = 1
				elif S[i] == S[j]:
					dp[j][i] = dp[j + 1][i] + dp[j][i - 1] + 1
				else:
					dp[j][i] = dp[j + 1][i] + dp[j][i - 1] - dp[j + 1][i - 1]
		return dp[0][n - 1] % M


class Solution:

	def countPS(self, string):
		dic = {}
		n = len(string)

		def recursive(string, n, left, right):
			if left > right:
				return 0
			if (left, right) in dic:
				return dic[left, right]
			if left == right:
				dic[left, right] = 1
			elif string[left] == string[right]:
				dic[left, right] = (1 + recursive(string, n, left + 1, right) + recursive(string, n, left, right - 1)) % 1000000007
			else:
				dic[left, right] = (recursive(string, n, left + 1, right) + recursive(string, n, left, right - 1) - recursive(string, n, left + 1, right - 1)) % 1000000007
			return dic[left, right]
		return recursive(string, n, 0, n - 1)


class Solution:

	def countPS(self, string):
		n = len(string)
		MOD = 10 ** 9 + 7
		dp = [[0] * n for i in range(n)]
		for l in range(1, n + 1):
			i = 0
			while i + l <= n:
				j = i + l - 1
				if i > j:
					break
				if l == 1:
					dp[i][j] = 1
				elif l == 2:
					if string[i] == string[j]:
						dp[i][j] = 3
					else:
						dp[i][j] = 2
				elif string[i] == string[j]:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
				else:
					dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
				dp[i][j] %= MOD
				i += 1
		return dp[0][n - 1]


class Solution:

	def countPS(self, s):

		def count(i, j, s):
			if i > j:
				return 0
			if i == j:
				return 1
			if t[i][j] != -1:
				return t[i][j]
			if s[i] == s[j]:
				t[i][j] = 1 + count(i + 1, j, s) + count(i, j - 1, s)
				return t[i][j] % 1000000007
			else:
				t[i][j] = count(i + 1, j, s) + count(i, j - 1, s) - count(i + 1, j - 1, s)
				return t[i][j] % 1000000007
		n = len(s)
		t = [[-1] * (n + 1) for x in range(n + 1)]
		return count(0, n - 1, s)


def solver(str, i, j, dct):
	if i > j:
		return 0
	if (i, j) in dct:
		return dct[i, j]
	res = 0
	if str[i] == str[j]:
		res = solver(str, i + 1, j, dct) + solver(str, i, j - 1, dct) + 1
	else:
		res = solver(str, i + 1, j, dct) + solver(str, i, j - 1, dct) - solver(str, i + 1, j - 1, dct)
	res %= 1000000007
	dct[i, j] = res
	return res

class Solution:

	def countPS(self, string):
		dct = dict()
		return solver(string, 0, len(string) - 1, dct)


class Solution:

	def countPS(self, string):
		n = len(string)
		dp = []
		for _ in range(n):
			dp.append([0] * n)
		for i in range(n):
			dp[i][i] = 1
		for i in range(n - 1):
			k = 0
			for j in range(i + 1, n):
				if string[k] == string[j]:
					dp[k][j] = 1 + dp[k][j - 1] + dp[k + 1][j]
				else:
					dp[k][j] = dp[k][j - 1] + dp[k + 1][j] - dp[k + 1][j - 1]
				k += 1
		return dp[0][n - 1] % (10 ** 9 + 7)


class Solution:

	def countPS(self, string):
		dp = [[0 for j in range(len(string))] for i in range(2)]
		mod = 1000000007
		dp[1][-1] = 1
		for i in range(len(string) - 2, -1, -1):
			dp[0][i] = 1
			for j in range(i + 1, len(string)):
				dp[0][j] = 0
				dp[0][j] += dp[0][j - 1] + dp[1][j]
				if string[i] == string[j]:
					dp[0][j] += 1
				else:
					dp[0][j] -= dp[1][j - 1]
				dp[0][j] %= mod
			(dp[0], dp[1]) = (dp[1], dp[0])
		return dp[1][len(string) - 1]


import sys
sys.setrecursionlimit(10000)

class Solution:

	def __count_palin_subseq_helper(self, i, j, string):
		if i > j:
			return 0
		if i == j:
			return 1
		if self.dp[i][j] == None:
			self.dp[i][j] = 0
			self.dp[i][j] += self.__count_palin_subseq_helper(i, j - 1, string) + self.__count_palin_subseq_helper(i + 1, j, string)
			if string[i] == string[j]:
				self.dp[i][j] += 1
			else:
				self.dp[i][j] -= self.__count_palin_subseq_helper(i + 1, j - 1, string)
			self.dp[i][j] %= self.mod
		return self.dp[i][j]

	def countPS(self, string):
		self.dp = [[None for j in range(len(string))] for i in range(len(string))]
		self.mod = 1000000007
		return self.__count_palin_subseq_helper(0, len(string) - 1, string)


class Solution:

	def countPS(self, s):
		n = len(s)
		dp = [[-1 for k in range(n + 1)] for t in range(n + 1)]
		m = 10 ** 9 + 7

		def memo(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = 1
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = memo(i + 1, j) + memo(i, j - 1) + 1
			else:
				dp[i][j] = memo(i + 1, j) + memo(i, j - 1) - memo(i + 1, j - 1)
			return dp[i][j]
		return memo(0, n - 1) % m


class Solution:

	def countPS(self, string):
		n = len(string)
		dp = [[-1 for x in range(n)] for y in range(n)]

		def countPA(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = 1
				return dp[i][j]
			if string[i] == string[j]:
				dp[i][j] = countPA(i + 1, j) + countPA(i, j - 1) + 1
				return dp[i][j]
			else:
				dp[i][j] = countPA(i + 1, j) + countPA(i, j - 1) - countPA(i + 1, j - 1)
				return dp[i][j]
		return countPA(0, n - 1) % (10 ** 9 + 7)


class Solution:

	def solve(self, s, i, j, dp):
		if i > j:
			return 0
		if i == j:
			return 1
		if dp[i][j]:
			return dp[i][j]
		if s[i] == s[j]:
			dp[i][j] = 1 + self.solve(s, i + 1, j, dp) + self.solve(s, i, j - 1, dp)
		else:
			dp[i][j] = self.solve(s, i + 1, j, dp) + self.solve(s, i, j - 1, dp) - self.solve(s, i + 1, j - 1, dp)
		return dp[i][j]

	def countPS(self, s):
		mod = 10 ** 9 + 7
		dp = [[0 for i in range(len(s))] for j in range(len(s))]
		return self.solve(s, 0, len(s) - 1, dp) % mod


class Solution:

	def countPS(self, string):
		n = len(string)
		ans = [[0] * n for i in range(n)]
		for d in range(n):
			i = 0
			for j in range(d, n):
				if d == 0:
					ans[i][j] = 1
				elif string[i] == string[j]:
					ans[i][j] = ans[i][j - 1] + ans[i + 1][j] + 1
				else:
					ans[i][j] = ans[i][j - 1] + ans[i + 1][j] - ans[i + 1][j - 1]
				i += 1
		return ans[0][n - 1] % (10 ** 9 + 7)


class Solution:

	def countPS(self, string):
		n = len(string)
		dp = [[0] * n for _ in range(n)]
		mod = 1000000007
		for i in range(n):
			dp[i][i] = 1
		for i in range(0, n - 2 + 1):
			j = i + 2 - 1
			if string[i] == string[j]:
				dp[i][j] = 3
			elif string[i] != string[j]:
				dp[i][j] = 2
		for l in range(3, n + 1):
			for i in range(0, n - l + 1):
				j = i + l - 1
				if string[i] == string[j]:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1
				elif string[i] != string[j]:
					dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
		if dp[0][n - 1] > mod:
			return dp[0][n - 1] % mod
		else:
			return dp[0][n - 1]