8.1 How many ACs?

Score: 30pts

Time Limit: 1.00 sec

You are given a string \(s\) of length \(L\) containing alphabets \(A\) and \(C\). You need to print the count of unique subsequences of \(AC\) in string \(s\). Two subsequences are said to be unique if the indices of either character \(A\) or character \(C\) or both differ.<br>

A subsequence is a sequence that can be derived from the given sequence of string by deleting zero or more characters without changing the order of the remaining elements.

A subsequence is a sequence that can be derived from the given sequence of string by deleting zero or more characters without changing the order of the remaining elements.

Constraints

\(2 \leq L \leq 100000\)

String \(s\) contains only characters ‘A’ and ‘C’.

String \(s\) contains only characters ‘A’ and ‘C’.

Input Format

\(L\)

\(s\)

\(s\)

Output Format

An integer, x, denoting the total number of subsequences of \(AC\) in string \(s\).

Example 1

Input:

7

CACCAAC

Output:

5

Explanation:

Explanation -

If we consider the indexing to be done using 0-based indexing, then the index pairs for ‘A’ and ‘C’ are - (1,2), (1,3), (1,6), (4,6), (5,6).

7

CACCAAC

Output:

5

Explanation:

Explanation -

If we consider the indexing to be done using 0-based indexing, then the index pairs for ‘A’ and ‘C’ are - (1,2), (1,3), (1,6), (4,6), (5,6).

Example 2

Input:

7

ACACACC

Output:

9

Explanation:

The index pairs for ‘A’ and ‘C’ are - (1,2), (1,4), (1,6), (1,7), (3,4), (3,6), (3,7), (5,6), (5,7)

7

ACACACC

Output:

9

Explanation:

The index pairs for ‘A’ and ‘C’ are - (1,2), (1,4), (1,6), (1,7), (3,4), (3,6), (3,7), (5,6), (5,7)