#include<iostream>
using namespace std;

const int MAXN = 1e6 + 5;
const int MOD = 1e6 + 3;
int n, k, m;
int a[MAXN];

int main(){
	freopen("Binaria.in", "r", stdin);
	freopen("Binaria.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	m = n - k + 1;
	for(int i = 0;i < m;i ++){
		cin >> a[i];
	}
    int ans = 0;
    for(int mask = 0;mask < (1 << n);mask ++){
    	bool flag = 1;
    	for(int i = 0;i < m && flag;i ++){
    		int sum = 0;
    		for(int j = 0;j < k;j ++){
    			sum += (mask >> (i + j)) & 1;
    		}
    		if(sum != a[i]) flag = 0;
    	}
    	ans += flag;
    }
    cout << ans % MOD << '\n';
	return 0;
}