隣接する要素の和も差も \(K\) の倍数にならないようなところで数列を区切ります。 区切ったところをまたぐswapは行われないことがわかるので、数列ごとの総数が求まればそれらをかけ合わせればよいです。 このとき、各数列は以下のいずれかを満たします。

• \(a \times 2\) が \(K\) の倍数となるような整数 \(a\) があって、すべての要素は \(\text{mod } K\) で \(a\) に等しい
• \(a+b\) が \(K\) の倍数であるような相異なる \(2\) 整数 \(a,b\) があって、すべての要素は \(\text{mod } K\) で \(a\) か \(b\) に等しい

一つ目の場合は数列内の要素を自由に並べ替えることができます。 二つ目の場合は \(\text{mod } K\) で \(a\) に等しい要素同士や \(b\) に等しい要素同士を入れ替えることは出来ず、位置関係は変わりません。\(a \pmod K\) の要素をどこに置くかを決めると数列は一意に定まり、置き方が異なるならば数列も異なることから、置き方が何通りあるかを調べればよいです。