You are given a string s. A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters. Count the number of distinct non-empty subsequences of s (subsequences that are equal as strings are counted only once, even if they can be formed by deleting different sets of positions). Print the count modulo 1000000007.
Input format
Line 1: the string s (may be empty, producing a blank line).
s contains only lowercase English letters.
Output format
A single integer: the number of distinct non-empty subsequences of s, modulo 1000000007.
Constraints
- 0 <= |s| <= 16