制約は緩めに設定してありますが、\(O(N \log N)\) で解くことも出来ます。

条件を満たす数列の形は、以下の \(3\) 種類のものを組み合わせたものになります。

• \(a\)：\(a\) のみからなる長さ \(1\) の数列
• \(S_a\)：\(a\) 以外が全て現れる任意長の数列
• \(T_{a,b}\)：\(a,b\) が現れない任意長の数列

例えば、\(x = {1,2,2,3}\) の場合、\(S_1, 2, T_{1,2}, 1, S_2, 2, S_2, 3, T_{2,3}, 2, S_3\) という形になります。

\(a,S_a,T_{a,b}\) の個数をそれぞれ \(p,q,r\) 個とします。

\(c_i\) を「\(S_a\) のうち長さ \(i\) のものの個数」とし、\(F = \sum_{i=0}^{\infty} c_i x^i\) とします。（明らかに \(F\) は \(a\) の値に依りません。）

同様に、\(T_{a,b}\) に対して \(G\) も定義します。

すると答えは、\([x^N](x^p F^q G^r)\) となり、これは FPS の pow を使うと \(O(N \log N)\) で計算できます。

解説

\(M=1\) の場合は \(S_{x_1}\) です。以降は \(M \ge 2\) とします。

最後に現れる \(x_M\) に注目し、それより前を \(P\)、後ろを \(Q\) とします。

\(P\) は、長さ \(M-1\) の数列のうち \(x_1 \dots x_{M-1}\) 以外すべてを部分列として含むような数列である必要があります。 つまり、長さが \(1\) 減った問題になっています。

\(Q\) は、「\(x_1 \dots x_M\) と末尾のみが異なる数列すべて」を含められるようにするためのパーツである必要があります。

• \(x_{M-1} = x_{M}\) の場合：\(Q = S_{x_M}\)
• \(x_{M-1} \ne x_{M}\) の場合：\(Q\) は \(T_{x_M, x_{M-1}}, x_{M-1}, S_{x_M}\) をこの順で並べたもの

最終形

上記の議論をまとめると、条件を満たす数列の形は具体的には以下の通りです。

• \(S_{x_1} \dots S_{x_M}\) の \(S_{x_{i-1}}\) と \(S_{x_i}\) の間に以下を挿入したもの
  • \(x_{i-1} = x_i\) の場合：\(x_i\)
  • \(x_{i-1} \ne x_i\) の場合：\(x_i, T_{x_i,x_{i-1}}, x_{i-1}\)