Let \(M\) be the length of \(T\).

\(S_N\) can be a very long string, but performing any sequence of operations on \(T\) yields a rotation of \(T\), or its reverse. Let us formally describe this idea:

• For a string consisting of a and b, define \(U_a \in \Z / M\Z, U_b \in \Z / 2\Z\) as follows. These \(U_a\) and \(U_b\) uniquely determines the action on the string. Here, “replacing with the \(k\)-th rotation” refers to moving the first character to the end \(k\) times.

• • If \(U\) replaces the string with its \(k\)-th rotation, let \(U_a = k\) and \(U_b = 0\).
• • If \(U\) replaces the string with the inverse of its \(k\)-th rotation, let \(U_a = k\) and \(U_b = 1\).

Then, the behavior when concatenating strings can be encoded as follows. In mathematical terms, this forms a dihedral group \(D_M\) (sometimes denoted as \(D_{2M}\) depending on convention).

• Suppose that concatenating strings \(X\) and \(Y\) in this order yields \(U\).

• • If \(X_b = 0\), then \(U_a = X_a + Y_a\) and \(U_b = Y_b\).
• • If \(X_b = 1\), then \(U_a = X_a - Y_a\) and \(U_b = 1 + Y_b\).

Let \(a_i \coloneqq {S_i}_a\) and \(b_i \coloneqq {S_i}_b\). Our goal is to compute \(a_N\) and \(b_N\).

The periodicity of \(b_i\)

For all integers \(i > K\), we have \(b_i = b_{i - 1} + b_{i - 2} + \ldots + b_{i - K}\) and \(b_{i + 1} = b_i + b_{i - 1} + \ldots + b_{i - K + 1}\), yielding \(b_{i + 1} = b_{i - K}\). Therefore, \(b_i\) has a period \((K + 1)\), and \(b_N\) can be computed fast.

Computing \(a_i\)

Considering the behavior when concatenating strings, we see that for \(i > K\) we can write \(a_i = c_{i, i - 1}a_{i - 1} + c_{i, i - 2}a_{i - 2}+ \ldots +c_{i, i - K}a_{i - K}\) for some \(c_{i, j} \in \{ \pm 1 \}\). Here, since the coefficients \(c_{i, j}\) are determined by \(b_{i - 1}, b_{i - 2}, \ldots, b_{j + 1}\) (specifically, \(c_{i, j} = (-1)^{b_{i - 1} + b_{i - 2} + \ldots, b_{j + 1}}\)) and \(b_i\) has the period \((K + 1)\), we notice that \(c_{i, j} = c_{i + K + 1, j + K + 1}\). Hence, there exists a matrix \(A\) with integer coefficients, such that \(\begin{pmatrix} a_{(K + 1)(i + 1) + 1} \\ a_{(K + 1)(i + 1) + 2} \\ \vdots \\ a_{(K + 1)(i + 2)} \end{pmatrix} = A \begin{pmatrix} a_{(K + 1)i + 1} \\ a_{(K + 1)i + 2} \\ \vdots \\ a_{(K + 1)(i + 1)} \end{pmatrix}\) for all non-negative integers \(i\).

Moreover, \(A\) can be filled from the top rows to bottom according to the equation corresponding to string concatenation. Once \(A\) is found, we can apply the fast exponentiation algorithm to compute \(A^{\lfloor\frac{N - 1}{K + 1} \rfloor}\), thus obtaining \(a_N\).

For \(i \leq K+1\), we can obtain \(a_i\) and \(b_i\) in \(O(\sum|S_i|)\) time, compute \(A\) in \(O(K^3)\) time, perform the matrix exponentiation in \(O(K^3)\) time, and construct the final string in \(O(M)\) time, so the total time complexity is \(O(\sum |S_i| + K^3 \log N + M)\).