#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*t;
}
const int mod=1004535809;
int ksm(int x,int y){
    int ret=1;x=(x%mod+mod)%mod;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
unordered_map<int,int> mp;
int inv(int x){
    if(mp.find(x)!=mp.end())return mp[x];
    else return mp[x]=ksm(x,mod-2);
}
int lglr(int *y,int c,int t){
    if(t<0)return 0;
    if(t<=c)return y[t];
    t%=mod;
    int bas=(c&1)?-1:1,tmp=1,ret=0;
    fo(i,1,c)tmp=tmp*(t-i)%mod;
    fo(i,1,c)tmp=tmp*inv(i)%mod;
    fo(i,0,c){
        ret=(ret+bas*y[i]*tmp+mod)%mod;
        tmp=tmp*(t-i)%mod*inv(t-i-1)%mod;
        tmp=tmp*(c-i)%mod*inv(i+1)%mod;
        bas=-bas;
    }
    return (ret%mod+mod)%mod;
}
int nn,m,a,b,c,p[25];
int get(int x){
    int tmp=1,ret=0;
    fo(i,0,m)ret=(ret+tmp*p[i])%mod,tmp=tmp*x%mod;
    return ret;
}
int f[105][2005],sf[105][2005];
int P(int x){return (x+b)/c;}
int Q(int x){if((nn+b)/c<x)return nn+1;return x*c-b;}
int sol(int d,int n,int c){
    if(!n)return 0;
    int ret=a*lglr(sf[d],c+1,n)%mod,nc=c+1+m;
    fo(i,0,nc+1){
        if(n<Q(i))break;
        f[d+1][i]=get(i)*(lglr(sf[d],c+1,n)-lglr(sf[d],c+1,Q(i)-1)+mod)%mod;
    }
    // sf[d+1][0]=f[d+1][0];
    fo(i,1,nc+1)sf[d+1][i]=(sf[d+1][i-1]+f[d+1][i])%mod;
    ret=(ret+sol(d+1,P(n),nc))%mod;
    // cout<<ret<<endl;
    return ret;
}
signed main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    nn=read();a=read();b=read();c=read();m=read();
    fo(i,0,m)p[i]=read()%mod;
    fo(i,0,m+1)f[1][i]=get(i);
    // sf[1][0]=f[1][0];
    fo(i,1,m+1)sf[1][i]=(sf[1][i-1]+f[1][i])%mod;
    printf("%lld",(a+sol(1,nn,m))%mod);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*t;
}
const int inf=0x3f3f3f3f;
const int N=1e5+5;
struct E{int to,nxt,val;}e[N*8];
int hea[N*2],head[N*2],s=2e5+1,t=2e5+2,rp;
void add_edg(int x,int y,int z){
    e[++rp].to=y;e[rp].nxt=head[x];
    head[x]=rp;e[rp].val=z;
}
int dis[N*2];
bool bfs(){
    memcpy(head,hea,sizeof(hea));
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;while(!q.empty())q.pop();
    dis[s]=0;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        // cout<<x<<endl;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;//cout<<y<<" "<<e[i].val<<endl;
            if(!e[i].val||dis[y]<=dis[x]+1)continue;
            dis[y]=dis[x]+1;q.push(y);
            
            if(y==t)return true;
        }
    }
    return false;
}
int dfs(int x,int in){
    // cout<<x<<" "<<in<<endl;
    if(x==t)return in;
    int rest=in,go=0;
    for(int i=head[x];i;head[x]=i=e[i].nxt){
        int y=e[i].to;
        if(!e[i].val||dis[y]!=dis[x]+1)continue;
        go=dfs(y,min(e[i].val,rest));
        if(go)rest-=go,e[i].val-=go,e[i^1].val+=go;
        else dis[y]=0;
        if(!rest)break;
    }
    return in-rest;
}
int dinic(){
    memcpy(hea,head,sizeof(head));
    int ret=0;
    while(bfs())ret+=dfs(s,inf);
    return ret;
}
int fa1[N],vi1[N];
int find1(int x){return fa1[x]==x?x:fa1[x]=find1(fa1[x]);}
int fa2[N],vi2[N],vis[N*2];
int find2(int x){return fa2[x]==x?x:fa2[x]=find2(fa2[x]);}
int n,m,bl[N],ans;
struct D{int x,y;}d[N*2];
int id[N];
signed main(){
    freopen("restriction.in","r",stdin);
    freopen("restriction.out","w",stdout);
    n=read();m=read();
    fo(i,1,n)bl[i]=read();
    fo(i,1,m)d[i].x=read(),d[i].y=read();
    fo(i,1,n)fa1[i]=i,fa2[i]=i,vi1[i]=0,vi2[i]=0;
    fo(i,1,2*n)vis[i]=0;
    fo(i,1,m){
        if(bl[d[i].x]!=2&&bl[d[i].y]!=2){
            fa1[find1(d[i].x)]=find1(d[i].y);
        }
        if(bl[d[i].x]!=3&&bl[d[i].y]!=3){
            fa2[find2(d[i].x)]=find2(d[i].y);
        }
    }
    memset(head,0,sizeof(head));rp=1;
    fo(i,1,n){
        if(bl[i]!=1)continue;
        vi1[find1(i)]=true;
        vi2[find2(i)]=true;
        // cout<<find1(i)<<" "<<find2(i)<<endl;
        add_edg(find1(i),find2(i)+n,inf);
        add_edg(find2(i)+n,find1(i),0);
        id[i]=rp;
    }ans=0;
    // cout<<rp<<endl;
    fo(i,1,n){
        if(vi1[i]){ans++;
            // cout<<i<<endl;
            add_edg(s,i,1);
            add_edg(i,s,0);
        }
        if(vi2[i]){ans++;
            // cout<<i+n<<endl;
            add_edg(i+n,t,1);
            add_edg(t,i+n,0);
        }
    }
    // cout<<ans<<endl;
    // cout<<rp<<endl;
    ans-=dinic();
    printf("%d ",ans);
    fo(i,1,n){
        if(bl[i]!=1)continue;
        if(e[id[i]].val){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    fo(i,1,n){
        if(bl[i]!=1)continue;
        if(!vis[find1(i)]||!vis[find2(i)+n]){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    printf("\n");

    fo(i,1,n)fa1[i]=i,fa2[i]=i,vi1[i]=0,vi2[i]=0;
    fo(i,1,2*n)vis[i]=0;
    fo(i,1,m){
        if(bl[d[i].x]!=1&&bl[d[i].y]!=1){
            fa1[find1(d[i].x)]=find1(d[i].y);
        }
        if(bl[d[i].x]!=3&&bl[d[i].y]!=3){
            fa2[find2(d[i].x)]=find2(d[i].y);
        }
    }
    memset(head,0,sizeof(head));rp=1;
    fo(i,1,n){
        if(bl[i]!=2)continue;
        vi1[find1(i)]=true;
        vi2[find2(i)]=true;
        // cout<<find1(i)<<" "<<find2(i)<<endl;
        add_edg(find1(i),find2(i)+n,inf);
        add_edg(find2(i)+n,find1(i),0);
        id[i]=rp;
    }ans=0;
    // cout<<rp<<endl;
    fo(i,1,n){
        if(vi1[i]){ans++;
            // cout<<i<<endl;
            add_edg(s,i,1);
            add_edg(i,s,0);
        }
        if(vi2[i]){ans++;
            // cout<<i+n<<endl;
            add_edg(i+n,t,1);
            add_edg(t,i+n,0);
        }
    }
    // cout<<ans<<endl;
    // cout<<rp<<endl;
    ans-=dinic();
    printf("%d ",ans);
    fo(i,1,n){
        if(bl[i]!=2)continue;
        if(e[id[i]].val){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    fo(i,1,n){
        if(bl[i]!=2)continue;
        if(!vis[find1(i)]||!vis[find2(i)+n]){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    printf("\n");

    fo(i,1,n)fa1[i]=i,fa2[i]=i,vi1[i]=0,vi2[i]=0;
    fo(i,1,2*n)vis[i]=0;
    fo(i,1,m){
        if(bl[d[i].x]!=2&&bl[d[i].y]!=2){
            fa1[find1(d[i].x)]=find1(d[i].y);
        }
        if(bl[d[i].x]!=1&&bl[d[i].y]!=1){
            fa2[find2(d[i].x)]=find2(d[i].y);
        }
    }
    memset(head,0,sizeof(head));rp=1;
    fo(i,1,n){
        if(bl[i]!=3)continue;
        vi1[find1(i)]=true;
        vi2[find2(i)]=true;
        // cout<<find1(i)<<" "<<find2(i)<<endl;
        add_edg(find1(i),find2(i)+n,inf);
        add_edg(find2(i)+n,find1(i),0);
        id[i]=rp;
    }ans=0;
    // cout<<rp<<endl;
    fo(i,1,n){
        if(vi1[i]){ans++;
            // cout<<i<<endl;
            add_edg(s,i,1);
            add_edg(i,s,0);
        }
        if(vi2[i]){ans++;
            // cout<<i+n<<endl;
            add_edg(i+n,t,1);
            add_edg(t,i+n,0);
        }
    }
    // cout<<ans<<endl;
    // cout<<rp<<endl;
    ans-=dinic();
    printf("%d ",ans);
    fo(i,1,n){
        if(bl[i]!=3)continue;
        if(e[id[i]].val){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    fo(i,1,n){
        if(bl[i]!=3)continue;
        if(!vis[find1(i)]||!vis[find2(i)+n]){
            printf("%d ",i);
            vis[find1(i)]=vis[find2(i)+n]=true;
        }
    }
    return 0;
}

#include<bits/stdc++.h>
#include "green.h"
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int visit(int x,int y);
const int N=1e5+5;
int dep[N],fa[N],mxd;
vector<int> vec[N];
int dis[N];
bool com(int x,int y){return dis[x]<dis[y];}
void sol(int d,int l1,int r1,int l2,int r2){
    // printf("%d %d %d %d %d\n",d,l1,r1,l2,r2);
    if(l1>r1||l2>r2)return ;
    if(l1==r1){
        // printf("%d %d\n",l2,r2);
        fo(i,l2,r2){
            int x=vec[d+1][i];
            // printf("s%d %d\n",i,x);
            fa[x]=vec[d][l1];
        }
        return ;
    }
    dis[vec[d][l1]]=0;
    fo(i,l1+1,r1)dis[vec[d][i]]=visit(vec[d][l1],vec[d][i]);//printf("%d\n",i);
    fo(i,l2,r2)dis[vec[d+1][i]]=visit(vec[d][l1],vec[d+1][i]);
    sort(vec[d].begin()+l1,vec[d].begin()+r1+1,com);
    sort(vec[d+1].begin()+l2,vec[d+1].begin()+r2+1,com);
    // printf("%d\n",vec[d][1]);
    int s1=l1,s2=l2;
    while(dis[vec[d+1][s2]]==1)fa[vec[d+1][s2]]=vec[d][l1],s2++;
    int t2=s2;s1++;
    // printf("%d %d %d\n",s1,s2,t2);
    fo(i,l1+1,r1){
        // printf("%d %d %d\n",i,dis[vec[d][i]],dis[vec[d][i+1]]);
        if(i==r1||dis[vec[d][i]]!=dis[vec[d][i+1]]){
            while(t2<r2){
                if(dis[vec[d+1][t2]]!=dis[vec[d+1][t2+1]])break;
                t2++;
            }
            // printf("%d %d %d %d\n",i,s1,s2,t2);
            if(dis[vec[d][s1]]+1==dis[vec[d+1][s2]]){
                // printf("%d %d %d %d %d\n",d,s1,i,s2,t2);
                sol(d,s1,i,s2,t2);
                s2=t2+1;t2=s2;
            }s1=i+1;
            if(s2>r2||s1>r1)break;
        }
    }
}
void findtree(int n,int m,int *p){
    fo(i,2,n){
        dep[i]=visit(1,i);
        mxd=max(mxd,dep[i]);
        vec[dep[i]].push_back(i);
    }
    for(int i:vec[1])p[i]=1;
    fo(i,1,mxd-1){
        sol(i,0,(int)vec[i].size()-1,0,(int)vec[i+1].size()-1);
        for(int j:vec[i+1])p[j]=fa[j];//printf("%d %d\n",j,fa[j]);
    }
}