Counting a^i b^j c^k subsequences

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.

Medium5Dynamic programmingStringCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Problem

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

aibjcka^i b^j c^k is the string with ii copies of a, then jj copies of b, then kk copies of c. For example, a2b3c1a^2 b^3 c^1 is aabbbc and a3b1c6a^3 b^1 c^6 is aaabcccccc.

A subsequence is what remains after deleting zero or more characters of SS 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 SS, built from the letters a, b, and c only. The length of SS is at most 1,000,000.

Output

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