记录编号	608926	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4190.Binaria	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	1.337 s
提交时间	2025-10-30 17:48:27	内存使用	15.33 MiB

#include<bits/stdc++.h>
#define N 1000005
#define mod 1000003
using namespace std;
int n, k, s[N], a[N], fa[N], ans = 0, fac[N], inv[N], p = 0, q = 0;
int qpow(int x, int y) {
    int ret = 1;
    while (y) {
        if (y & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return ret;
}
int find(int x) {
    return (x == fa[x]) ? x : (fa[x] = find(fa[x]));
}
int C(int x, int y) {
    if (x < 0 || y < 0 || x > y) return 0;
    return 1LL * fac[y] * inv[x] % mod * inv[y - x] % mod;
}
int read() {
    int r = 0, f = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        r = r * 10 + (c - '0');
        c = getchar();
    }
    return f ? -r : r;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
signed main() {
    freopen("Binaria.in","r",stdin);
    freopen("Binaria.out","w",stdout);
    n = read();
    k = read();
    fac[0] = 1;
    inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        a[i] = -1;        
        fa[i] = i; 
        fac[i] = 1LL * fac[i - 1] * i % mod;
    }
    inv[n] = qpow(fac[n], mod - 2);
    for (int i = n - 1; i >= 1; i--) {
        inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
    }
    
    int sms_len = n - k + 1;
    for (int i = 1; i <= sms_len; i++) {
        s[i] = read();
    }
    for (int i = 2; i <= sms_len; i++) {
        int x = i - 1;
        int y = i + k - 1;
        if (s[i] == s[i - 1]) {
            fa[find(y)] = find(x);
        } else if (s[i] == s[i - 1] + 1) {
            a[x] = 0;
            a[y] = 1;
        } else if (s[i] + 1 == s[i - 1]) {
            a[x] = 1;
            a[y] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] != -1) {
            int root = find(i);
            a[root] = a[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        int root = find(i);
        if (a[root] != -1) {
            a[i] = a[root];
        }
    }
    bool vis[N] = {false};
    for (int i = 1; i <= k; i++) {
        int root = find(i);
        if (a[i] == -1) {
            if (!vis[root]) {
                p++;
                vis[root] = true;
            }
        } else if (a[i] == 1) {
            q++;
        }
    }
    ans = C(s[1] - q, p);
    for (int i = 1; i <= n; i++) {
        int root = find(i);
        if (i == root && a[root] == -1 && !vis[root]) {
            ans = 1LL * ans * 2 % mod;
            vis[root] = true;
        }
    }
    write(ans);
    putchar('\n');
    
    return 0;
}