We split the sequence at positions where neither the sum nor the difference of adjacent elements is a multiple of \(K\). It can be seen that no swap crosses such a split point, so we only need to find the count for each subsequence and multiply them together. In this case, each subsequence satisfies one of the following:

• There exists an integer \(a\) such that \(a \times 2\) is a multiple of \(K\), and all elements are congruent to \(a\) modulo \(K\).
• There exist two distinct integers \(a\) and \(b\) such that \(a + b\) is a multiple of \(K\), and all elements are congruent to \(a\) or \(b\) modulo \(K\).

In the first case, the elements within the subsequence can be freely rearranged. In the second case, elements congruent to \(a\) cannot be swapped with each other, nor can elements congruent to \(b\), so their relative order does not change. Once we decide where to place the elements congruent to \(a\) modulo \(K\), the sequence is uniquely determined, and different placements yield different sequences, so we just need to count the placements.