Counting a^i b^j c^k subsequences

Time limit2sMemory limit512 MB

Summary

Count subsequences of a string of a, b, c that read as some positive number of a's, then b's, then c's, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, String, Combinatorics
Solved: No attempts yet

Problem

You are given a string $S$ built from the letters a, b, and c only. Count the subsequences of $S$ that have the form $a^i b^j c^k$ , where $i \ge 1$ , $j \ge 1$ , and $k \ge 1$ .

$a^i b^j c^k$ is the string with $i$ copies of a, then $j$ copies of b, then $k$ copies of c. For example, $a^2 b^3 c^1$ is aabbbc and $a^3 b^1 c^6$ is aaabcccccc.

A subsequence is what remains after deleting zero or more characters of $S$ and keeping the rest in their original order. Two subsequences that use different sets of positions count separately, even when the remaining strings are equal.

Input

The first line contains the string $S$ , built from the letters a, b, and c only. The length of $S$ is at most 1,000,000.

Output

On the first line, print the number of subsequences of $S$ of the form $a^i b^j c^k$ , modulo 1,000,000,007.

Examples9

Example 1
Input
```
abc
```
Expected output
```
1
```
Example 2
Input
```
abcc
```
Expected output
```
3
```
Example 3
Input
```
abbcc
```
Expected output
```
9
```
Example 4
Input
```
aabbcc
```
Expected output
```
27
```
Example 5
Input
```
abbccc
```
Expected output
```
21
```
Example 6
Input
```
abbcccabc
```
Expected output
```
51
```
Example 7
Input
```
abcabcabcabc
```
Expected output
```
111
```
Example 8
Input
```
cba
```
Expected output
```
0
```
Example 9
Input
```
aaaaabbbbbccccc
```
Expected output
```
29791
```