Distinct Palindromic Subsequences

Difficulty: 2200 6000 ms 128 MB

strings dp

Count the DISTINCT non-empty palindromic subsequences of S, modulo 10⁹+7.

Input: one line with the string S.

Output: the number of distinct palindromic subsequences mod 10⁹+7.

Constraints:

• 1 ≤ |S| ≤ 2000
• lowercase letters

Sample Tests

aba

4

abc

3

Read the Editorial