2044. Distinct Subsequences

单点时限: 2.0 sec

内存限制: 256 MB

Given a string, count the number of distinct subsequences of it ( including e mpty subsequence ). For the uninformed, A subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters.

For example, “agh” is a subsequence of “abcdefgh” while “ahg” is not.

输入格式

First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases. Each of next T lines contains a string s.

输出格式

Output consists of T lines. Ith line in the output corresponds to the number of distinct subsequences of ith input string. Since, this number could be very large, you need to output ans%1000000007 where ans is the number of distinct subsequences.

样例

Input
3
AAA
ABCDEFG
CODECRAFT
Output
4
128
496
Constraints:
Dataset 1: T ≤ 100, length(S) ≤ 15
Dataset 2: T ≤ 100, length(S) ≤ 1000
Dataset 3: T ≤ 20, length(S) ≤ 100000

7 人解决,10 人已尝试。

8 份提交通过,共有 32 份提交。

6.8 EMB 奖励。

创建: 13 年,7 月前.

修改: 4 年前.

最后提交: 3 年,5 月前.

来源: Code 08

题目标签