You are given a string \(S\) of length \(N\).

A good subsequence is the one that can be represented in the form \(a^{i}b^{j}c^{k}\), where \( i \ge 1\), \( j \ge 1\) and \(k \ge 1 \). For example, if \(i=2\), \(j=1\), and \(k=3\), it represents the string \(aabccc\). In other words, a good subsequence is a subsequence that first consist of \(i\ a\) characters, followed by \(j\ b\) characters, followed by k c characters, where \( i \ge 1\), \( j \ge 1\) and \( k \ge 1 \).

You are required to determine the number of good subsequences of string \(S\). As the number of such subsequences can be rather large, print the answer Modulo \(10^9+7\).

Note: Two subsequences are considered different if the set of array indexes that are selected for the two subsequences are different.

Input format

The first and only line of the input contains \(S\).

Output format

Print the required answer on a single line.

Constraints

\( 1 \le | S | \le 10^5 \)