272. Count Different Palindromic Subsequences (Modulo 10^9+7)

HardString String

Given a string s, return the number of distinct non-empty palindromic subsequences of s, modulo 10^9+7. Two subsequences are different if there is some index at which they differ in character.

Input: A quoted string s.

Output: Integer — count mod 10^9+7.

Examples

Example 1

Input: "bccb"
Output: 6
Explanation: b,c,cc,bb,bcb,bccb.

Example 2

Input: "aaa"
Output: 3
Explanation: a,aa,aaa.

Example 3

Input: "abc"
Output: 3
Explanation: a,b,c.

Constraints

1<=s.length<=1000
s contains a-d

Asked by

Google

Solve this problem in the editor →