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(NN)
Expected Auxiliary Space: O(NN)
Constraints:
1<=length of string str <=1000

见题面

见题面