#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       p(i)=ゾンビiが1回以上感電する確率
       K回ともiの約数以外のCが選ばれる事象の余事象
       1-(1-(iの約数であるものの数)/M)^K
    */
    int N, M, K, L=1000000, A;
    cin >> N >> M >> K;
    vector<int> cnt(L+1);
    for (int i=1; i<=M; i++){
        cin >> A;
        cnt[A]++;
    }
    vector<int> cnt2(L+1);
    for (int i=1; i<=L; i++){
        for (int j=i; j<=L; j+=i){
            cnt2[j] += cnt[i];
        }
    }
    mint ans=0, iv=mint(M).inv();
    for (int i=1; i<=N; i++){
        ans += mint(1) - mint(mint(1)-iv*cnt2[i]).pow(K);
    }
    cout << ans.val() << endl;

    return 0;
}