Harmonic Operations timer 1s memory 1024MB

In this problem we consider three types of operations that can be applied to any 0-based string t of length |t| ≥ 2.

I(t): Reverses t.

R(t, D): Rotates t to the right D positions, for some positive integer D < |t|. That is, for each 0 ≤ i < |t|, the character at position (i+D) \bmod |t| in R(t, D) is the character at position i in t.

L(t, D): Analogous to R(t, D), but rotates t to the left instead of to the right.

For example, I(“pda”) = “adp”, R(“pda”, 2) = “dap”, and L(“pda”, 2) = “apd”. Note that for any t and any D it holds that |I(t)| = |R(t, D)| = |L(t, D)| = |t|.

When a list of the above operations is applied to a string, it is done sequentially in list order. That is, the first operation of the list is applied to the original string, the second operation is applied to the result after having applied the first operation, the third operation is applied to the result after having applied the first two operations, and so on.

You are given a string S consisting of lowercase letters, and a list of K operations F_1, F_2, \dots , F_K. Your task is to find out how many pairs of indices (i, j) there are such that 1 ≤ i ≤ j ≤ K, and applying the sublist of operations F_i , F_{i+1}, \dots , F_j to S yields S as the final result.

Consider for instance S = “pda”, K = 2, F_1 = R(t, 2) and F_2 = L(t, 2). The result of applying the sublist

F_1 to S is R(“pda”, 2) = “dap”, which is different from S. The result of applying the sublist F_1, F_2 to S is

L(R(“pda”, 2), 2) = L(“dap”, 2) = “pda” = S. Finally, the result of applying the sublist F_2 to S is L(“pda”

, 2) = “apd”, which is different from S. Thus, in this example the answer is 1.