制約から，DPで計算するときに 状態 \( O(NM^3) \), 遷移 \( O(M) \) でも間に合う． LIS の求め方を考えると， LIS の 3つの項が \(x,y,z\) のときを状態に持てばよい．
一旦，LIS を無視して考える． 長さ \(N\) の vector \(v\) であって，各元 \(c \in M\) となるものの個数を DP で数える．
for i in N
for c in M
v[i] を c とする
という形で求まる．
再び LIS を思い出す． LIS が \([x,y,z]\) で与えられているとして， 次に \(v_{i}\) を定めようとしている．それを \(c \in M\) とする． LIS の作り方を真似すると，
if \(c \leq x\) : \([x,y,z] \rightarrow [c,y,z]\)
else if \(c \leq y\) : \([x,y,z] \rightarrow [x,c,z]\)
else if \(c \leq z\) : \([x,y,z] \rightarrow [x,y,c]\)
else : LIS の長さが 4以上となるので不適
という遷移で，LIS を構成できる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
mint dp[15][15][15];
mint old[15][15][15];
int main() {
ll n,m;
cin >> n >> m;
dp[m][m][m] = 1;
rep(i,n) {
rep(x,m+1) rep(y,m+1) rep(z,m+1) old[x][y][z] = 0;
swap(dp, old);
rep(x,m+1) rep(y,m+1) rep(z,m+1) {
mint now = old[x][y][z];
rep(c,m){
if (c <= x) dp[c][y][z] += now;
else if(c <= y) dp[x][c][z] += now;
else if(c <= z) dp[x][y][c] += now;
}
}
}
mint ans = 0;
rep(x,m) rep(y,m) rep(z,m) if(x < y && y < z)
ans += dp[x][y][z];
cout << ans.val() << endl;
return 0;
}
