#include <bits/stdc++.h>

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;
    std::vector<int> input(n - k + 1);
    for (int& i : input) {
        std::cin >> i;
    }

    std::vector<char> cum(n);
    int ans = 0;
    int cnt = -1;
    for (int mask = 0; mask < (1 << k - 1); mask++) {
        for (int j = 0; j < k - 1; j++) {
            cum[j] = (mask >> j) & 1;
        }
        bool fuck = false;
        for (int i = 0; i < n - k + 1; i++) {
            int val = input[i] - std::accumulate(cum.begin() + i, cum.begin() + i + k - 1, 0);
            if (0 <= val && val <= 1) {
                cum[i + k - 1] = val;
            } else {
                fuck = true;
                break;
            }
        }
        if (!fuck) {
            assert(cnt == -1 || cnt == cum[k - 1] + __builtin_popcount(mask));
            cnt = __builtin_popcount(mask) + cum[k - 1];
        }
        ans += !fuck;
    }

    ans %= int(1e6 + 3);
    std::cout << ans << "\n";

    return 0;
}