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('a') \gt F('c')\). Print \(ans \% (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('a') \gt F('c')\) modulus \(10^9 + 7\). 

Constraints
\(1 \le N \le 10^ 5\)