A sorted string

You are given a string $S$ of length $N$. The string contains only '$a$', '$b$', and '$c$'.

Your task is to find the count of substrings in string $S$ that have $F{(}^{\prime }{a}^{\prime })>F{(}^{\prime }{c}^{\prime })$. Print $ans\mathrm{\%}({10}^9+7)$.

Here, $F(x)$ denotes the frequency of occurrence of character $x$ in the string.

Input format

• The first line contains an integer $N$ that denotes the length of the string.
• The next line contains string $S$.

Output format

Print the count of substrings in string $S$ that have $F{(}^{\prime }{a}^{\prime })>F{(}^{\prime }{c}^{\prime })$ modulus ${10}^9+7$. 

Constraints
$1\le N\le {10}^5$

 

SAMPLE INPUT

 

7
abccaab

SAMPLE OUTPUT

 

11

Explanation

There are total 11 substrings in which $f{(}^{\prime }{a}^{\prime })>f{(}^{\prime }{c}^{\prime })$. These are:
['a','ab', 'abccaa', 'abccaab', 'a', 'a', 'aa', 'ab', 'aab', 'caa', 'caab']

Note:- Partially Solved TIME EXTENDED