You are given a String S of length N.
Now, a good subsequence is one that can be represented in the form , where , and . For example ,if ,,, it represents the string . In short, a good subsequence is a subsequence that first consist of i a characters, followed by j b characters, followed by k c characters, where , and
Now, you need to find the number of good subsequences of String S. As the number of such subsequences could be rather large, print the answer Modulo .
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:
Valid sub sequences are(1-based indexing):
{1,2,3}
{1,2,6}
{1,5,6}
{4,5,6}
{1,2,5,6}
{1,4,5,6}
{1,2,3,6}