Count Different Palindromic Subsequences

Hard

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

Example 1

Input:  s = "bccb"
Output: 6

Example 2

Input:  s = "abcd"
Output: 4

Example 3

Input:  s = "aaa"
Output: 3

Constraints

• 1 <= s.length <= 12
• s consists of characters 'a', 'b', 'c', or 'd'.