Counting Subsequences

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

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.

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

May someone check my code please?

Can someone check my code

Use a long data type, you have data type overflow


what does it mean by that

that means you output your answer mod 10007. In other words, if your answer was 10007, you output 0. By modding a number, you get the remainder. As such, if you do 10 mod 5, you get 0, or 10 mod 7, you get 3.

EDIT: nvm, i solved it :P

in this problem don't count empty Subsequences I was getting all WAs because of that just print your answer - 1 .

note : even in the example they didn't count the empty Subsequence because here are the Subsequences of "aba"
{
"" , "a" , "b" , "ab" , "ba" , "aba" , "aa"
}

I wish if the admins would put a note tn the problem statments it will lower the number of WAs alot

What is the reason for this error in my code?

MemoryError