Palindromic Subsequences

G: Palindromic Subsequences

problem

Given a string S consisting only of lowercase letters, find out how many subsequences of this string S are not necessarily continuous and are palindromes.

Here, a subsequence that is not necessarily continuous with S is an arbitrary selection of one or more characters | S | characters or less from the original character string S (the position of each character to be selected may be discontinuous), and they are used. Refers to a character string created by concatenating the characters in the original order. Note that an empty string is not allowed as a subsequence in this issue.

Also, if the string X is a palindrome, it means that the original string X and the inverted X string X'are equal.

Also note that even if the same palindrome is generated as a result of different subsequence arrangements, it will not be counted twice. For example, if S = acpc, both the subsequence consisting of only the second character and the subsequence consisting of only the fourth character are palindromes c, but this cannot be repeated multiple times, only once in total. I will count it.

The answer can be very large, so print the remainder divided by 1,000,000,007.

Input format

S

Constraint

• 1 \ leq | S | \ leq 2,000
• S contains only lowercase letters

Output format

• Output the remainder of the answer divided by 1,000,000,007 on one line.

Input example 1

acpc

Output example 1

Five

There are five types of subsequences of the string acpc that are not necessarily continuous and are palindromes: a, c, cc, cpc, and p. Note that we count the number of substring types.

Input example 2

z

Output example 2

1

The only subsequence that meets the condition is z. Note that an empty string is not allowed as a subsequence.

Input example 3

madokamagica

Output example 3

28

Example

Input

acpc

Output

5

inputFormat

Input format

S

Constraint

• 1 \ leq | S | \ leq 2,000
• S contains only lowercase letters

outputFormat

Output format

• Output the remainder of the answer divided by 1,000,000,007 on one line.

Input example 1

acpc

Output example 1

Five

There are five types of subsequences of the string acpc that are not necessarily continuous and are palindromes: a, c, cc, cpc, and p. Note that we count the number of substring types.

Input example 2

z

Output example 2

1

The only subsequence that meets the condition is z. Note that an empty string is not allowed as a subsequence.

Input example 3

madokamagica

Output example 3

28

Example

Input

acpc

Output

5

样例

acpc

5