Description
Given a string s, return the number of different non-empty palindromic subsequences. Since the answer may be large, return it modulo 10^9 + 7.
Examples
Input:
s = "bccb"Output:
6Explanation:
6 different palindromic subsequences: 'b','c','bb','cc','bcb','bccb'.
Input:
s = "a"Output:
0Explanation:
Edge case with a single character.
Input:
s = "abccba"Output:
19Explanation:
The palindromic subsequences are: 'a' (appears twice but counted once), 'b' (appears twice but counted once), 'c' (appears twice but counted once), 'aa', 'bb', 'cc', 'aba', 'aca', 'bcb', 'cbc', 'abba', 'acca', 'bccb', 'abcba', 'abcca', 'accba', 'bccba', 'abccb', 'abccba'. This example demonstrates a longer string with multiple character types and nested palindromic patterns.
Constraints
- •
1 ≤ s.length ≤ 1000 - •
s contains only 'a','b','c','d'