You are given a String S of length N.
Now, a good subsequence is one that can be represented in the form aibjci, where
i≥1,
j≥1
and
k≥1.
For example ,if
i=2, j=1,k=3, it represents the string aabccc. In short, a good sub-sequence is a sub-sequence that first consist of i ′a′ characters, followed by j ′b′ characters, followed by k ′c′ characters.
Now, you need to find the number of good sub-sequences of S. As the number of such sub-sequences could be rather large, print the answer Modulo 109+7.
Note1: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.
Input Format:
The first and only line of input contains the
S
Output Format :
Print the required answer on a single line.
Constraints:
1≤|S|≤105
Sample Input
abcabc
Sample Output
7