466D - Increase Sequence - CodeForces Solution

//#pragma GCC optimize("Ofast,unroll-loops") 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 2005;
const int mod = 1e9+7;
int n, h, a[maxn];
int f[maxn][maxn]; 
// f(i, j) number of ways to
// cover [1, i] with j open

void solve(){
    cin >> n >> h;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= i; ++j){
            if(a[i] + j == h){ 
                if(j > 0) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod; // add an open 
                f[i][j] = (f[i][j] + f[i - 1][j]) % mod; // do nothing
            }
            if(a[i] + j + 1 == h){
                f[i][j] = (f[i][j] + f[i - 1][j + 1] * (j + 1)) % mod; // add a close
                f[i][j] = (f[i][j] + f[i - 1][j]) % mod; // add len-1 interval
                if(j > 0) f[i][j] = (f[i][j] + f[i - 1][j] * j) % mod; // add ][ idk why
            }
            debug(i, j, f[i][j]);
        }
    }
    cout << f[n][0];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    return 0;
}