/// *** --- ||| In the name of ALLAH ||| --- *** /// #include <bits/stdc++.h> using namespace std; #define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long #define MOD 1000000009 int main() { fastio(); int n; ll d; cin >> n >> d; vector<ll> h(n); for (int i = 0; i < n; i++) { cin >> h[i]; } int mx = 1 << n; // safe because n <= 20 vector<vector<ll>> dp(mx, vector<ll>(n, 0)); // Base case: one block as bottom for (int i = 0; i < n; i++) { dp[1 << i][i] = 1; } // Bitmask DP for (int mask = 0; mask < mx; mask++) { for (int last = 0; last < n; last++) { // last must be used if ((mask & (1 << last)) == 0) continue; if (dp[mask][last] == 0) continue; for (int nxt = 0; nxt < n; nxt++) { // nxt must be unused if ((mask & (1 << nxt)) != 0) continue; // size constraint if (h[nxt] <= h[last] + d) { int newMask = mask | (1 << nxt); dp[newMask][nxt] = (dp[newMask][nxt] + dp[mask][last]) % MOD; } } } } // Collect answer ll ans = 0; int fullMask = mx - 1; for (int i = 0; i < n; i++) { ans = (ans + dp[fullMask][i]) % MOD; } cout << ans << "\n"; return 0; }