N, M, K = map(int, input().split())
A = list(map(int, input().split()))

MOD = 998244353

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

cntA = [0]*(10**6+1)
for i in range(M):
    cntA[A[i]] += 1
C = [0]*(N+1)
for i in range(10**6+1):
    if cntA[i] == 0:
        continue
    idx = i
    while idx <= N:
        C[idx] += cntA[i]
        idx += i

P = [0]
p = inverse(1, M)
for _ in range(M):
    P.append((P[-1]+p)%MOD)

ans = 0
for i in range(1, N+1):
    ans += (1-pow(P[M-C[i]], K, MOD))%MOD
    ans %= MOD

print(ans)