P = 998244353
p, g, ig = 998244353, 3, 332748118
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(ig, (p - 1) >> i, p) for i in range(24)]
def convolve(a, b):
def fft(f):
for l in range(k, 0, -1):
d = 1 << l - 1
U = [1]
for i in range(d):
U.append(U[-1] * W[l] % p)
for i in range(1 << k - l):
for j in range(d):
s = i * 2 * d + j
t = s + d
f[s], f[t] = (f[s] + f[t]) % p, U[j] * (f[s] - f[t]) % p
def ifft(f):
for l in range(1, k + 1):
d = 1 << l - 1
U = [1]
for i in range(d):
U.append(U[-1] * iW[l] % p)
for i in range(1 << k - l):
for j in range(d):
s = i * 2 * d + j
t = s + d
f[s], f[t] = (f[s] + f[t] * U[j]) % p, (f[s] - f[t] * U[j]) % p
n0 = len(a) + len(b) - 1
if len(a) < 80 or len(b) < 80:
ret = [0] * n0
if len(a) > len(b): a, b = b, a
for i, aa in enumerate(a):
for j, bb in enumerate(b):
ret[i+j] = (ret[i+j] + aa * bb) % p
return ret
k = (n0).bit_length()
n = 1 << k
a = a + [0] * (n - len(a))
b = b + [0] * (n - len(b))
fft(a), fft(b)
for i in range(n):
a[i] = a[i] * b[i] % p
ifft(a)
invn = pow(n, p - 2, p)
for i in range(n0):
a[i] = a[i] * invn % p
del a[n0:]
return a
class RelaxedMultiplication():
# h = f * g
def __init__(self):
self.f = []
self.g = []
self.h = []
self.n = 0
def calc(self, l1, r1, l2, r2):
self.h += [0] * (r1 + r2 - 1 - len(self.h))
for i, a in enumerate(convolve(self.f[l1:r1], self.g[l2:r2]), l1 + l2):
self.h[i] = (self.h[i] + a) % p
def append(self, a, b):
self.f.append(a)
self.g.append(b)
self.n += 1
n = self.n
m = (n + 1) & -(n + 1)
s = 0
if m <= n:
a = 1
while a <= m:
self.calc(n - a, n, s, s + a)
self.calc(s, s + a, n - a, n)
s += a
a <<= 1
else:
a = 1
while a < m >> 1:
self.calc(n - a, n, s, s + a)
self.calc(s, s + a, n - a, n)
s += a
a <<= 1
self.calc(n - a, n, s, s + a)
return self.h[n-1]
P = 998244353
nn = 250025
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
fainv[i] = fainv[i+1] * (i+1) % P
rm = RelaxedMultiplication()
ww, K = map(int, input().split())
www = [int(a) for a in input().split()]
F = [0] * ww
G = [0] * ww
F[0] = 1
for w in www:
for i in range(w - 1, ww, w):
G[i] += w
for i in range(ww - 1):
h = rm.append(F[i], G[i])
F[i+1] = (F[i+1] + h * fainv[i+1] % P * fa[i]) % P
a = F[i+1]
print(a)
for j in range(i + 1, ww, i + 2):
G[j] = (G[j] + (i + 2) * a) % P