Counting Subsequences

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type

Given a string, count all distinct subsequences (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 Specification

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 Specification

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


There are no comments at the moment.