Given a string s, return *the number of different non-empty palindromic subsequences in* `s`

. Since the answer may be very large, return it **modulo** `10`

.^{9} + 7

A subsequence of a string is obtained by deleting zero or more characters from the string.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences `a`

and _{1}, a_{2}, ...`b`

are different if there is some _{1}, b_{2}, ...`i`

for which `a`

._{i} != b_{i}

**Example 1:**

Input:s = "bccb"Output:6Explanation:The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'. Note that 'bcb' is counted only once, even though it occurs twice.

**Example 2:**

Input:s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"Output:104860361Explanation:There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^{9}+ 7.

**Constraints:**

`1 <= s.length <= 1000`

`s[i]`

is either`'a'`

,`'b'`

,`'c'`

, or`'d'`

.

class Solution {
public int countPalindromicSubsequences(String s) {
}
}