包除原理を用いる。 寄与を計算すると、同じ色が \(S\) 個連続するかたまりの寄与を \((-1)^S\) とすればよいことがわかる。 よって、色 1 を除いた列について、valid なものの数は

\[ \sum_{t=0}^\infty \left( \sum_{i=2}^N \sum_{j=1}^\infty (A_i x)^j (-1)^{j-1} \right)^t =\sum_{t=0}^\infty \left( \sum_{i=2}^N \frac{A_i x}{1+A_ix}\right)^t \]

となることがわかる。 右辺の括弧の中身は分数の形を保ったまま分割統治すれば \(O(N\log^2 N)\) で求まる。求まったものを \(\dfrac{p}{q}\) とする。

すると、色 2 ~ N のみを用いた列について、valid なものの数は

\[ \dfrac{\frac{p}{q}}{1 - \frac{p}{q}} = \dfrac{p}{q-p} =: f \]

となる。

これに、色 1 の地域を追加することを考えると、求める答えは

\[ [x^{T-1}] f + xA_1 f^2 + \left(xA_1\right)^2 f^3 + \ldots = [x^{T-1}]\dfrac{f}{1-A_1fx} \\ = [x^{T-1}]\dfrac{p}{q-p-apx} \]

とわかるので、Bostan-Mori 法で求めることができる。