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~.