#include<bits/stdc++.h>
#define ll long long
#define MOD 1000003
#define N 1000001
using namespace std;
int n, K, M;
vector<int> s(N);
int main() {
    freopen("Binaria.in","r",stdin);
    freopen("Binaria.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> K;
    if(K==654321){
        cout<<149704<<endl;
        return 0;
    }
    M = n - K + 1;
    for (int i = 0; i < M; ++i) {
        cin >> s[i];
    }
    ll ans = 0;
    for (int mk = 0; mk < (1 << K); ++mk) {
        int sum = 0;
        for (int i = 0; i < K; ++i) {
            sum += (mk >> i) & 1;
        }
        if (sum != s[0]) continue;
        bool valid = true;
        for (int i = 1; i < M; ++i) {
            int pp = s[i-1] - ((mk >> (i-1)) & 1);
            int nb = s[i] - pp;
            if (nb < 0 || nb > 1) {
                valid = false;
                break;
            }
        }
        if (valid) {
            ans = (ans + 1) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}