题目描述

给出一串由a,b,c组成的字符串，求该串最多包含多少个abc子串。结果对 $1000000007$ 取模。

输入格式

第一行一个数字 $n$ ，表示字符串的长度；

第二行一个字符串，表示这个字符串。

输出格式

输出一行，一个数表示该字符串最多包含多少个abc子串

样例

5
abbbc

3

3
aab

0

4
abcc

2

Hint

• 第一组样例：abc子串为1,2,5 1,3,5 1,4,5 总共为3
• 第二组样例：没有abc子串 总共为0
  
• 第三组样例：abcc:子串为 1,2,3 1,2,4 总共为2
  

数据范围：

• 对于30%数据：$3 \leq n \leq 200$
• 对于50%数据：$3 \leq n \leq 2000$
• 对于100%数据：$3 \leq n \leq 2*10^5$