Convert A,B,C to \(0,1,2\), respectively.

We use the inclusion-exclusion principle. Let us fix the set of positions of forbidden patterns in the string. Then, there will be restrictions of this form: \((i\)-th character \(+1) \equiv ((i+1)\)-th character\() \mod 3\). If we consider the contiguous subsequences “connected” by these restrictions, the string is divided into some intervals.

Let \(L_1,L_2,\cdots,L_k\) be the lengths of the intervals. Consider the counting problem for a fixed \((L_1,L_2,\cdots,L_k)\).

First, for fixed \(L_i\), consider the sets of positions of forbidden patterns in the string achieving that \(L_i\), and compute the sum of their coefficients in the inclusion-exclusion principle. It turns out to be the following:

• \(1\), when \(L_i \equiv 1 \mod P\);
• \(0\), when \(L_i \equiv 2 \mod P\);
• \(-1\), when \(L_i \equiv 0 \mod P\).

This can be verified by induction.

Now, for a given \((L_1,L_2,\cdots,L_k)\), let us count the corresponding strings.

In a part of the string corresponding to \(L_i \equiv 0\), all of \(0,1,2\) must occur the same number of times, and there are three ways to arrange them. In a part corresponding to \(L_i \equiv 1\), one of \(0,1,2\) must occur exactly one more time than the others, and there is a unique way to arrange them after deciding the most frequent.

Now that the counting problem for a fixed \((L_1,L_2,\cdots,L_k)\) is solved, we will unfix \(L_i\) and compute the sum. Let us decompose \(L_i\) into \(3+3+3+\cdots+3(+1)\) to make a sequence \(z\) consisting of \(1\) and \(3\).

We will fix the number of \(3\)s in this \(z\) and try to count the values corresponding to such \(z\).

Consider the case \(z\) ends with a \(1\). It turns out that we can do the counting for all \(L_i\) corresponding to such \(z\) regardless of the order of the remaining \(3\)s and \(1\)s. Specifically, consider choosing for each \(3\) in \(z\) whether to “combine” it with the next term to the right (into the same \(L_i\)). If we choose to combine it, it can be assumed to have a coefficient of \(1\), and \(-3\) if we choose not to, for a total of \(-2\). Therefore, regardless of the order of the \(1\)s and \(3\)s, the number of arrangements should be multiplied by the coefficient \((-2)^{(\text{number of }3 \text{s in } z)}\).

One can similarly handle the case \(z\) ends with a \(3\).

Therefore, the problem can be solved in \(O(A+B+C)\) time.

Sample code (c++)