OIG XI - lot

// https://szkopul.edu.pl/problemset/problem/qcCvZzMRLiaJB30vbP8gP7Jf/site/?key=statement
// XI OIG — Zawody indywidualne (próbne), etap III

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001, mod = 1e9 + 9;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> v(n);
    for (auto& a : v) {
        std::cin >> a;
    }

    std::map<int, int> mp;

    int ans = 0;

    for (const auto& a : v) {
        if (a > k) {
            continue;
        }

        if (a == k) {
            ans += mp[a - 1];
            ans %= mod;
            continue;
        }

        if (a == 1)
            mp[1]++;
        else {
            mp[a] += mp[a - 1];
            mp[a] %= mod;
        }
    }

    std::cout << ans << '\n';
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}