rXlvve - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
#define int long long
#define st first
#define nd second
#define pb push_back
#define pob pop_back
#define all(st) st.begin(), st.end()
#define ii pair<int, int>
#define mod 1000003

using namespace std;

const int nmax = 1e6 + 5;
int n, m;
int a[nmax], fr[nmax], z[nmax], f[nmax];

int cal(int n) {
    int m = n / 2;
    return (fr[n] * z[m] % mod * z[m + 1] % mod);
}

int Pow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
    // freopen("inp.inp","r",stdin);
    // freopen("out.out","w",stdout);

    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++) cin >> a[i];
    n = 2 * n;
    fr[0] = 1;
    for (int i = 1; i <= n; i++) fr[i] = (fr[i - 1] * i) % mod;
    z[n] = Pow(fr[n], mod - 2);
    for (int i = n; i >= 1; i--) z[i - 1] = (z[i] * i) % mod;
    if (n <= 4000) {
        f[0] = 1;
        for (int i = 2; i <= n; i += 2)
            for (int j = 0; j < i; j += 2)
                if (a[i] - a[j + 1] <= m) {
                    f[i] = (f[i] + f[j] * cal(i - j - 2) % mod) % mod;
                }
        cout << f[n];
    } else
        cout << cal(n);

    return 0;
}