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(a)>F(c). Print ans%(109+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)>F(c) modulus 109+7

Constraints
1N105

 

SAMPLE INPUT
 
7
abccaab
SAMPLE OUTPUT
 
11
Explanation

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

Note:- Partially Solved TIME EXTENDED


Comments

Popular posts from this blog

Access and modify all the resources of our Wiki.js using WikiJS API

MySQL Multi Source Master Slave Replication using GTID

How to pass parameters in webhook?