You are given a String **S** of length **N**. Now, a special subsequence is one that can be represented in the form **a^i b^j c^k**, where i≥1, j≥1 and k≥1. In short, a special subsequence is a subsequence that first consist of i ′a′ characters, followed by j ′b′ characters, followed by k ′c′ characters, where i≥1, j≥1 and k≥1

Now, you need to find the number of special subsequences of String S. Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different. For example :

Sample Input : abcabc

Output : 7

Subsequences are abc, abc, abbc, aabc

abcc, abc and abc

For the purpose of the answer let’s define:

- abc-good : String is a string in the form aibjck, for i,j,k≥1
- ab-good : String is a string in the form aibj, for i,j≥1
- a-good : String is a string in the form ai, for i≥1

We are interested in the number of abc-good subsequences of the input string S[1…N].

Let **fabc[x] **be the number of **abc-good** subsequences of S[1…x]. Any **abc-good **subsequence of S[1…x] is either any **abc-good** subsequence of S[1…x−1], or if S[x]=c it is any **abc-good** subsequence of S[1…x−1] extended with S[x], or if S[x]=c it is any **ab-good** subsequence of S[x−1]. Similar reasoning holds for **fab[x] **and **fa[x]**.

So to find the count of special subsequence, traverse given string. For every character S[i] do following

- If current character is ‘a’, then there are following possibilities :
**‘a’**begins a new subsequence.- It is part of
**aCount**subsequences, where**aCount**is number of**a**encountered till index**i**. - It is not part of
**aCount**subsequences.

Therefore

**aCount**= (1 + 2 * aCount) - Similary if current character is ‘b’, then there are following possibilities :
- It begins a new subsequence of b’s with
**aCount**subsequences. - It is part of bCount subsequences.
- It is not part of bCount subsequences.

- It begins a new subsequence of b’s with

Therefore

**bCount**= (aCount + 2 * bCount) - Similary if current character is ‘c’, then
**cCount**is given by

**cCount**= (bCount + 2 * cCount);

Finally **cCount** gives the number special subsequence.