Initial strings:
\begin{aligned}
S_{0}&: A,\\
S_{1}&: C,\\
S_{2}&: B,\\
S_{3}&: BCA=S_{2}S_{1}S_{0},\\
S_{4}&: BCABC=S_{3}S_{2}S_{1},\\
S_{5}&: BCABCBCAB=S_{4}S_{3}S_{2},\dots
\end{aligned}
Notice that for t≥3
\boxed{S_{t}=S_{t-1}\,S_{t-2}\,S_{t-3}.}
Let T_t=|S_t|. With T_0=T_1=T_2=1,
T_t=T_{t-1}+T_{t-2}+T_{t-3}\quad(t\ge3),
the Tribonacci sequence, computed mod M=10^{9}+7.
Define f(t,k) = symbol at position k in S_t; base cases f(0,1)=A,\;f(1,1)=C,\;f(2,1)=B. Depending on which part of the string the letter is located in, we have the following recursive step for t\ge3:
f(t,k) =
\begin{cases}
f(t-1,k), & k\le T_{t-1} \ \text{the letter is in the part $S_{t-1}$} \\
f(t-2,k-T_{t-1}), & T_{t-1}<k\le T_{t-1}+T_{t-2} \ \text{the letter is in the part $S_{t-2}$} \\
f(t-3,k-T_{t-1}-T_{t-2}), & \text{otherwise, the letter is in the part $S_{t-3}$}
\end{cases}
Compute T_n and f(n,k) that would be the answer. Complexity O(n).
