## DSUBSEQ - Distinct Subsequences

Given a string, count the number of distinct subsequences of it (including empty 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.

### Input

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

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.

### Example

```Input:
3
AAA
ABCDEFG
CODECRAFT

Output:
4
128
496
```

### Constraints and Limits

T ≤ 100, length(S) ≤ 100000
All input strings shall contain only uppercase letters.

hide comments
 kabramanan: 2017-05-31 16:30:49 Just add mod wherever you think the answer could be negative. Ex: ( (2*x - y) +m)%m Few testcases:- ABCABCABC=326 AABBAABBAA=139 MANANM=47 MISSISSIPPI=478 kush_code: 2017-05-17 18:20:38 input contains lowercase characters also. cost me 3 WA sfialok98: 2017-04-03 21:33:39 Very nice Problem..... Just 8 lines of code... Accepted in 1 Go...!! nilabja16180: 2017-03-24 15:50:27 GOOD problem! vunnamtej: 2017-03-09 14:51:24 good dp. string to maths ipg_2015054: 2017-02-21 19:27:27 @Avik Sarkar how can the value be negative..please explain prasoonbatham: 2017-01-14 15:17:38 Always check output before submitting. Cost me 1 wa. :( Great question though!! Just observe the pattern :) kira28: 2017-01-07 19:53:04 FINALLY AC :) 4 WAs due to MOD :/ madhavgaba: 2016-12-30 12:31:23 @VINAYAK if ur answer is negative.....just add MOD to ur answer vinayak_1997: 2016-12-29 14:05:45 Why will modulo here give negative answer? Last edit: 2016-12-29 14:31:38

 Added by: Ajay Somani Date: 2008-02-05 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: CPP Resource: CodeCraft 08, Problem Setter: Jin Bin