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
atomic_lattice:
20231006 13:18:38
Try doing with O(n) time and O(26) space 

ive1010:
20220322 18:24:57
Spoiler : make a 1d dp and try to find the # of subsequence ending at index 'i',


pradeep_7:
20201011 07:22:32
Approach :


manish_thakur:
20200522 19:29:49
good problem , beware of mod of negative values 

mrmajumder:
20200421 13:13:22
Beware of negative values, if you're getting wa for modding 

mrmajumder:
20200421 13:13:06
Beware of negative values, if you're getting wa for modding 

cpp219:
20200129 04:17:21
good problem :) 

hetp111:
20200115 19:08:48
how do you do these kinds of dp problems by top down method ? 

nyawriter:
20191228 12:44:39
Negative value.. 

somz22:
20190531 14:40:40
Try to do it in O(n), not O(26*n) it's possible just make dp relation properly. 
Added by:  Ajay Somani 
Date:  20080205 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  CodeCraft 08, Problem Setter: Jin Bin 