#include <bits/stdc++.h>

const int mod = 1004535809;
const int maxn = 105;
int n,m,s,x,a[maxn];

void add(int& x,int y) {
    x += y;
    if(x >= mod)
        x -= mod;
    return ;
}

struct matrix {
    int g[maxn][maxn];
    matrix() {
        memset(g , 0 , sizeof(g));
    }
    void init() {
        for(int i = 0;i < m;++ i)
            g[i][i] = 1;
        return ;
    }
    matrix operator * (const matrix& p) {
        matrix c;
        for(int k = 0;k < m;++ k)
            for(int i = 0;i < m;++ i)
                for(int j = 0;j < m;++ j)
                    add(c.g[i][j] , 1ll * g[i][k] * p.g[k][j] % mod);
        return c;
    }
} f,g;

matrix power(matrix x,int y) {
    matrix ans;
    ans.init();
    for(;y;y >>= 1) {
        if(y & 1)
            ans = ans * x;
        x = x * x;
    }
    return ans;
}

bool vis[maxn];

int main() {
    freopen("sdoi2015_sequence.in","r",stdin);
    freopen("sdoi2015_sequence.out","w",stdout);
    scanf("%d %d %d %d",&n,&m,&x,&s);
    for(int i = 1;i <= s;++ i)
        scanf("%d",&a[i]),vis[a[i]] = true,f.g[0][a[i]] = 1;
    for(int i = 0;i < m;++ i)
        for(int j = 1;j <= s;++ j)
            g.g[i][(i * a[j]) % m] = 1;
    printf("%d\n",(f * power(g , n - 1)).g[0][x]);
    return 0;
}