Counting Palindromic Subsequences

Given a string S of length N, count the number of palindromic subsequences in S. Two subsequences are considered different if they occur at different positions in S, even if they are identical strings. Since the number can be huge, return the result modulo (10^9+7).

A palindromic subsequence is a sequence that reads the same backward as forward and can be derived from S by deleting zero or more characters without changing the order of the remaining characters.

You are given T test cases. For each test case, the first integer denotes the length of the string (which can be used for validation) and the following string is the actual sequence. Compute the number of distinct palindromic subsequences for each test case using dynamic programming.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer T, the number of test cases. Each of the following T lines contains a test case with an integer N followed by a string S, separated by a space.

outputFormat

For each test case, output the number of palindromic subsequences modulo (10^9+7) on a new line to standard output (stdout).## sample

2
3 aab
4 aaaa

4
15