\(1\) の場所、\(2\) の場所、\(\ldots\) と決めていきます。

今 1 ～ 3 の数と位置関係が \(N\) 個決まっているとします。 (1331131 のように)

この時に、\(4\) を \(S\) 個挿入するとします。これは \(S+N\) 個の枠の中から \(4\) の位置を決める方法 \(binom(S + N, S)\) を掛ければよいです。

\(0\) の時は、一番前に入ってはいけないのでかわりに \(binom(S + N - 1, S)\) を掛けます。

これは、

\(dp[i][j] = 1, \ldots, i\) の場所 \(j\) 個を確定させたときの場合の数

という \(dp\) で \(O\left(HNW\right)\) で計算することができます。