Sum of Distinct Subsequences over All Subsequences

Given a string \(S\) consisting of lowercase letters, we define the value of a string \(T\) as the number of its essentially different nonempty subsequences (a subsequence can be the entire string). For example, if \(T = \mathtt{aba}\), then its distinct nonempty subsequences are \(\{a, b, ab, aa, ba, aba\}\) (note that although the letter a appears twice, it is counted only once).

Your task is to compute the sum of the values of all subsequences of \(S\). Since the answer can be very large, output it modulo \(10^9+7\).

Note: The subsequence used to compute the value may be empty; in that case its value is \(0\).

More formally:

Let \(f(T)\) be the number of distinct nonempty subsequences of string \(T\). You need to compute \[ \sum_{T \text{ is a subsequence of } S} f(T) \mod (10^9+7). \]

The number of distinct nonempty subsequences of a string \(T\) can be computed by dynamic programming with the recurrence

\[ dp[i] = 2\,dp[i-1] - dp[last(T_i)] \quad \text{(if }T_i\text{ has occurred before),} \] \[ dp[i] = 2\,dp[i-1] \quad \text{(otherwise),} \]

with \(dp[0]=1\) (which counts the empty subsequence) and the final answer for \(T\) being \(dp[|T|]-1\) (to exclude the empty subsequence).

inputFormat

The input consists of a single line containing the string \(S\). \(S\) consists only of lowercase English letters.

outputFormat

Output a single integer, the sum of the values for every subsequence of \(S\) modulo \(10^9+7\).

sample

a

1