1242. Count Different Palindromic Subsequences

Given a string s, count the distinct non-empty palindromic subsequences of s. Two subsequences are the same if they produce identical strings. Return the count modulo 1000000007. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the number of distinct palindromic subsequences modulo 1e9+7.

Examples

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

Input: {"s":"abcd"}
Output: 4
Explanation: Only the four single characters.

Input: {"s":"a"}
Output: 1
Explanation: Single character.

Constraints

• 1<=|s|<=1000

Asked by