Let us first consider the case \(s\) is, for example, a repetition of abcde. It turns out it is easy to solve. Let \(f_i\) denote the position of the \(i\)-th character of \(t\) in \(s\). The character \(t_i\) uniquely determines the value \(f_i \bmod 5\), so let \(g_i=floor((f_i+4)/5)\) and let us only consider \(g_i\).

Depending on the characters \(t_i\) and \(t_{i+1}\), we have a contraint of the form \(g_i \leq g_{i+1}\) or \(g_i < g_{i+1}\). Also, \(1\leq g_i \leq N\) must naturally hold. Then, the number of sequences \(g_i\) satisfying those constraints equals the number of ways to extract \(t\) from \(s\). We can find this count as a simple formula with a binomial coefficient.

Let us go back to the case where \(s\) is a repetition of keyence. We cannot directly apply the above method because the positions of es \(\bmod 7\) are not uniquely determined. (Note that, on the other hand, the positions of other characters \(\bmod 7\) are uniquely determined.)

Here, for each e in \(t\), let us fix its position \(\bmod 7\). Then, we have constraints of the form \(g_i \leq g_{i+1}\) or \(g_i < g_{i+1}\), and we have to count the sequences \(g_i\) satisfying them. We said we could find this count by “a simple formula,” which can be written in a form that depends only on the number of indices \(i\) such that we have the constraint \(g_i < g_{i+1}\). (The other variables in the formula, such as \(N\) and \(|t|\), are determined from the input.)

For parts involving e, we can have either of the constraints \(g_i \leq g_{i+1}\) and \(g_i < g_{i+1}\). For each maximal substring of \(t\) consisting of e, we want to solve the following problem:

• For each e, we have three options for its position \(\bmod 7\). How many ways to make these choices result in \(k\) constraints of the form \(g_i <g_{i+1}\)?

Let \(L\) be the length of the substring consisting of e we are now looking at. We can solve this problem in \(O(L\log L)\) time with FFT and binary lifting. However, we have the coefficient of \(27\) in the computation time since we have to classify the substrings according to the positions \(\bmod 7\) of the first and last es. (Quiz: this algorithm takes \(O(k^3 L \log L)\) time, where \(k\) is the number of options for the positions in the cycle, but we can also solve this problem in \(O(kL+L\log L)\) time.)

Finally, we should regard the answer to the above problem for each maximal substring as a polynomial and multiply all of them, which can be done in \(O(|T| \log^2 |T|)\) time.

Therefore, we can solve the problem in a total of \(O(|T| \log^2 |T|)\) time.