Given a string, count all distinct sub

**sequences**(not substrings).

As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous)

For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).

### Input

The string, on one line. It will consist only of lowercase letters.It will be no longer than 100,000 characters long (this is easier than all substrings!)

### Output

The number of distinct subsequences.Note that this number may be ridiculously large, so print it mod 10,007.

D(i) = "i번째에서 끝나고, i번째 문자를 반드시 넣을 때 만들어지는 distinct subsequences의 개수"라고 정의하자.

i번째 문자를 S(i)라고 하자. S[i] = S[j](j<i)인 j중 가장 큰 j에 대해서 D[i] = Sum(D[j] ~ D[i-1])

만약 S[i]가 처음 등장했다면, D[i] = Sum(D[1]~D[i-1])+1이 된다.

Source Code

## No comments:

## Post a Comment