#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
long long MOD = 1000003; // 10^6 + 3 is prime
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2);
}
long long nCr(int n, int r, const vector<long long>& fact, const vector<long long>& invFact) {
if (r < 0 || r > n) return 0;
return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
void solve() {
int N, K;
if (!(cin >> N >> K)) return;
vector<int> A(N - K + 1);
for (int i = 0; i < N - K + 1; i++) cin >> A[i];
int free_chains = 0;
int required_ones = 0;
// Process K chains
for (int r = 0; r < K; r++) {
// Current logical value relative to start of chain (0)
// We track min_val and max_val relative to start
// If start=0, values are rel_val.
// If start=1, values are rel_val+1.
int current_rel = 0;
int min_rel = 0;
int max_rel = 0;
for (int i = r; i + K < N; i += K) {
// Index in sum array corresponds to window starting at i
// Difference A[j+1] - A[j] corresponds to S[i+K] - S[i]
// where j is the index of the window starting at i.
// Window at i is A[i]. Window at i+1 is A[i+1].
// But A is 0-indexed in code.
// A[x] covers indices x...x+K-1.
// S[i+K] - S[i] = A[i - (K-1) + K]... no wait
// Simpler: A[i+1] - A[i] = S[i+K] - S[i].
// We need to check if A index i exists.
if (i < A.size() - 1) {
int diff = A[i + 1] - A[i];
current_rel += diff;
min_rel = min(min_rel, current_rel);
max_rel = max(max_rel, current_rel);
}
}
// Validity check for the chain starting at S[r]
bool can_be_0 = true;
bool can_be_1 = true;
// If S[r]=0, all values are (0 + relative). Must be in [0,1].
// So min_rel >= 0 AND max_rel <= 1.
if (min_rel < 0 || max_rel > 1) can_be_0 = false;
// If S[r]=1, all values are (1 + relative). Must be in [0,1].
// So min_rel >= -1 AND max_rel <= 0.
if (min_rel < -1 || max_rel > 0) can_be_1 = false;
if (can_be_1 && !can_be_0) {
required_ones++;
} else if (can_be_0 && can_be_1) {
free_chains++;
}
// If neither, output 0 (though problem says input is valid)
}
int target = A[0] - required_ones;
// Prepare Combinatorics
vector<long long> fact(free_chains + 1);
vector<long long> invFact(free_chains + 1);
fact[0] = 1;
invFact[0] = 1;
for (int i = 1; i <= free_chains; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
invFact[i] = modInverse(fact[i]);
}
cout << nCr(free_chains, target, fact, invFact) << endl;
}
int main() {
solve();
return 0;
}
