Distinct Palindromic Subsequences

Given a string S, your task is to count the number of distinct palindromic subsequences in S. A subsequence is a sequence that can be derived from S by deleting some or no characters without changing the order of the remaining characters. Two subsequences are considered different if they occur at different positions in S or have a different set of characters.

The answer can be very large, so output it modulo \(10^9+7\).

Note: A single character is considered a palindrome, and subsequences with repeated characters are counted only once if they are identical.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer T, the number of test cases.
• Each of the next T lines contains a string S.

outputFormat

For each test case, output a single line containing one integer: the number of distinct palindromic subsequences in the given string modulo \(10^9+7\).

## sample

2
abc
aaa

3
3

</p>