First, let’s observe the characteristics of the generated graph.

By conducting experiments, we find that the connected components correspond to intervals in the sequence. Specifically, if vertices \(i\) and \(i + k\) are connected, then vertices \(i\) and \(i + 1, \ldots, i + k - 1\) are also connected.

Furthermore, vertices \(i\) and \(i + 1\) will not be connected if and only if \(\min(A_1, \ldots, A_i) > \max(A_{i+1}, \ldots, A_N)\).

This can be proved by mathematical induction on \(N\).

From this fact, the number of connected components can be determined as \(1 +\) (the number of vertices \(i\) such that vertices \(i\) and \(i+1\) are not connected \((1\leq i \leq N-1)\)).

Thus, we can solve the problem if, for each \(i\), we can find the number of sequences where vertices \(i\) and \(i + 1\) are not connected.

This can be found by exhaustively searching over the possible values of \(\min(A_1, \ldots, A_i)\), the LHS of the above condition, in \(\mathrm{O}(M)\) time.

Therefore, we can solve this problem in \(\mathrm{O}(N M)\) time.

Bonus: Solve it with \(N \leq 2000\) and \(M < 998244353\).