\(dp[i][a_1][a_2][a_3] :=\) 長さが \(i\) で、長さ \(j\) の部分増加列の最後尾として考えられる最小値が \(a_j\) であるような数列がいくつあるか

とすると、\(dp\) の状態数が \(O(NM^3)\) で、遷移が (愚直にやっても) \(O(M)\) なので、問題全体を \(O(NM^4)\) で解くことができます。

\(dp\) の初期値や遷移が分からなければ下の実装例を参考にしてください。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
using mint=modint998244353;
typedef vector<mint>vi;
typedef vector<vi>vvi;
typedef vector<vvi>vvvi;
typedef vector<vvvi>vvvvi;

signed main(){
    ll n,m;cin>>n>>m;
    vvvvi dp(n+1,vvvi(m+2,vvi(m+2,vi(m+2))));
    dp[0][m+1][m+1][m+1] = 1;
    rep(i,0,n-1)rep(a1,1,m+1)rep(a2,1,m+1)rep(a3,1,m+1){
        rep(x,1,m){
            //数列の i+1 項目の値を x とする
            if(x<=a1)     dp[i+1][x][a2][a3] += dp[i][a1][a2][a3];
            else if(x<=a2)dp[i+1][a1][x][a3] += dp[i][a1][a2][a3];
            else if(x<=a3)dp[i+1][a1][a2][x] += dp[i][a1][a2][a3];
        }
    }
    mint ans=0;
    rep(a1,1,m)rep(a2,a1+1,m)rep(a3,a2+1,m)ans += dp[n][a1][a2][a3];
    cout<<ans.val()<<endl;
    return 0;
}