分析
设答案的 OGF 为 $F(x)$，则有
$$
F(x) = x + \sum_{i \in D} F(x) ^i
$$
即
$$
x = F(x) - \sum_{i \in D} F(x)^i
$$
令 $G(x) = F^{-1}(x)$，可知
$$
G(x) = x - \sum_{i \in D} x^i
$$
由拉格朗日反演可得
$$
[x^n]F(x) = \frac{1}{n} [x^{n - 1}] \left(\frac{x}{G(x)}\right) ^ n
$$
注意到 $[x^0] G(x) = 0$，所以我们把上下同时除以 $x$，上式变为
$$
[x^n]F(x) = \frac{1}{n} [x^{n - 1}] \left(\frac{1}{\frac{G(x)}{x}}\right) ^ n
$$
多项式求逆 + 多项式快速幂计算即可。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X = 0, w = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 262144 + 10;
const int mod = 950009857;
int qpow(int a, int b) {
int c = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod)
if (b & 1) c = 1ll * c * a % mod;
return c;
}
int r[N];
void NTT(int *A, int n, int op) {
for (int i = 0; i < n; ++i)
if (i < r[i]) swap(A[i], A[r[i]]);
for (int i = 1; i < n; i <<= 1) {
int rot = qpow(op == 1 ? 7 : 135715694, (mod - 1) / (i << 1));
for (int j = 0; j < n; j += i << 1)
for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) {
int x = A[j + k], y = 1ll * w * A[j + k + i] % mod;
A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod;
}
}
if (op == -1) {
int inv = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod;
}
}
int NTT_init(int n) {
int lim = 1, l = 0;
for (; lim < n; lim <<= 1, ++l);
for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
return lim;
}
void PolyInv(int *F, int *G, int n) {
static int A[N], B[N];
if (n == 1) { G[0] = qpow(F[0], mod - 2); return; }
PolyInv(F, G, n >> 1);
for (int i = 0; i < n; ++i) A[i] = F[i], B[i] = G[i];
int lim = NTT_init(n << 1);
NTT(A, lim, 1), NTT(B, lim, 1);
for (int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod * B[i] % mod;
NTT(A, lim, -1);
for (int i = 0; i < n; ++i) G[i] = (2ll * G[i] - A[i] + mod) % mod;
for (int i = 0; i < lim; ++i) A[i] = B[i] = 0;
}
void PolyDeri(int *F, int *G, int n) {
for (int i = 1; i < n; ++i) G[i - 1] = 1ll * F[i] * i % mod;
G[n - 1] = 0;
}
void PolyInte(int *F, int *G, int n) {
for (int i = 1; i < n; ++i) G[i] = 1ll * F[i - 1] * qpow(i, mod - 2) % mod;
G[0] = 0;
}
void PolyLn(int *F, int *G, int n) {
static int A[N], B[N];
PolyDeri(F, A, n), PolyInv(F, B, n);
int lim = NTT_init(n << 1);
NTT(A, lim, 1), NTT(B, lim, 1);
for (int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod;
NTT(A, lim, -1);
PolyInte(A, G, n);
for (int i = 0; i < lim; ++i) A[i] = B[i] = 0;
}
void PolyExp(int *F, int *G, int n) {
static int A[N], B[N];
if (n == 1) { G[0] = 1; return; }
PolyExp(F, G, n >> 1);
for (int i = 0; i < n; ++i) A[i] = G[i];
PolyLn(G, B, n);
for (int i = 0; i < n; ++i) B[i] = (mod - B[i] + F[i]) % mod;
B[0] = (B[0] + 1) % mod;
int lim = NTT_init(n << 1);
NTT(A, lim, 1), NTT(B, lim, 1);
for (int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod;
NTT(A, lim, -1);
for (int i = 0; i < n; ++i) G[i] = A[i];
for (int i = 0; i < lim; ++i) A[i] = B[i] = 0;
}
void PolyPow(int *F, int *G, int n, int k) {
static int A[N];
PolyLn(F, A, n);
for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * k % mod;
PolyExp(A, G, n);
for (int i = 0; i < n; ++i) A[i] = 0;
}
int n, m, G[N], A[N], B[N];
int main() {
n = read(), m = read();
G[1] = 1;
for (int i = 1; i <= m; ++i) G[read()] = mod - 1;
for (int i = 0; i <= n; ++i) G[i] = G[i + 1];
int lim = 1;
for (; lim < n; lim <<= 1);
PolyInv(G, A, lim);
PolyPow(A, B, lim, n);
printf("%d\n", 1ll * B[n - 1] * qpow(n, mod - 2) % mod);
return 0;
}