Military Class - 2019 ICPC Malaysia National

#include <bits/stdc++.h>

#define F first
#define S second
#define EB emplace_back
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define all(x) x.begin(),x.end()
#define endl '\n'
#define W(x) cerr << "\033[31m"<<  #x << " = " << x << "\033[0m" << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const int MAXN = 2010;

int dp[MAXN][1<<10];
bool mat[MAXN][MAXN];

int n, e;
int solve(int i, int mask){
    if(i == n)
        return 1;
    if(dp[i][mask] != -1)
        return dp[i][mask];
    int ans=0;
    for(int k=-e; k<=e; k++){
        if(i+k>=0 and i+k<n and ((mask&(1<<(e+k))) == 0) and !mat[i][i+k]){
            ans = (ans + solve(i+1, (mask|(1<<(e+k)))>>1))%MOD;
        }
    }
    return dp[i][mask] = ans;
}

int main() {
    memset(dp, -1, sizeof(dp));
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int k;
    cin >> n >> e >> k;

    for(int i=0; i<k; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        mat[a][b] = true;
    }

    cout << solve(0, 0) << endl;
    return 0;
}