狂汗!有什么trick?

#include <cstdio>
#include <cstring>
const int MaxN = 100000 + 10, MaxM = 100;
const int MOD = 1000000;
int Sum[MaxN], F[MaxN], G[MaxN];
int Total[MaxM];

int Sumup(int i, int j) {
	if (i <= 0) return Sum[j];
	else return (Sum[j] - Sum[i - 1] + MOD) % MOD;
}
int main() {
	int N, M, Left, Right, x, i, j;
	scanf("%d%d%d%d", &N, &M, &Left, &Right);
	for (i = 0; i < M; i ++) {
		scanf("%d", &x);
		Total[x - 1] ++;
	}
	F[0] = 1;
	for (j = 0; j <= M; j ++) Sum[j] = 1;
	for (i = 0; i < N; i ++) {
		for (j = 0; j <= M; j ++)
			G[j] = Sumup(j - Total[i], j);
		for (j = 1; j <= M; j ++)
			Sum[j] = (G[j] + Sum[j - 1]) % MOD;
		memcpy(F, G, sizeof(G));
	}
	printf("%d\n", Sumup(Left, Right));
	return 0;
}