#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

const int maxn=;

const LL mod=1e9+;

int h[maxn],tot;

struct X { int u,v,nx; }e[*maxn];

int pre[maxn],dfs_clock,low[maxn],bcc_cnt,bccno[maxn];

struct Edge

{

    int u,v;

    Edge(int from,int to) { u=from; v=to; }

};

stack<Edge> S;

vector<int>bcc[maxn];

int T,n,m,be[*maxn],block,sz,cnt[maxn];

bool f[maxn];

LL w[*maxn],ans[maxn],val[maxn],SUM,pru[*maxn];

int head[*maxn];

struct Tree{ int u,v,nx; }tree[*maxn];

int id;

LL extend_gcd(LL a,LL b,LL &x,LL &y)

{

    if(a==&&b==) return -;

    if(b==){x=;y=;return a;}

    LL d=extend_gcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

LL mod_reverse(LL a)

{

    LL x,y;

    LL d=extend_gcd(a,mod,x,y);

    if(d==) return (x%mod+mod)%mod;

    else return -;

}

void ADD(int a,int b)

{

    tree[tot].u=a, tree[tot].v=b, tree[tot].nx=head[a], head[a]=tot++;

}

void AddEdge(int a,int b)

{

    e[tot].u=a, e[tot].v=b, e[tot].nx=h[a], h[a]=tot++;

}

int Tarjan(int u,int fa)

{

    int lowu=pre[u]=++dfs_clock;

    for(int i=h[u];i!=-;i=e[i].nx)

    {

        int v=e[i].v;

        Edge e = Edge(u,v);

        if(!pre[v])

        {

            S.push(e);

            int lowv=Tarjan(v,u); lowu=min(lowv,lowu);

            if(lowv>=pre[u])

            {

                bcc_cnt++; id++; w[id]=;

                for(;;)

                {

                    Edge x = S.top();S.pop();

                    if(bccno[x.u]!=bcc_cnt) {

                        ADD(x.u,id); ADD(id,x.u); be[id]=x.u; bccno[x.u]=bcc_cnt;

                    } if(bccno[x.v]!=bcc_cnt) {

                        ADD(x.v,id); ADD(id,x.v); be[id]=x.v; bccno[x.v]=bcc_cnt;

                    } if(x.u==u&&x.v==v) break;

                }

            }

        }

        else if(pre[v]<pre[u]&&v!=fa) { S.push(e); lowu=min(lowu,pre[v]); }

    }

    return lowu;

}

void find_bcc()

{

    memset(pre,,sizeof(pre));

    memset(bccno,,sizeof(bccno));

    dfs_clock=bcc_cnt=;

    for(int i=;i<=n;i++) if(!pre[i]) Tarjan(i,-);

}

void dfs(int x)

{

    sz++; f[x]=; be[x]=block;

    for(int i=h[x];i!=-;i=e[i].nx) if(!f[e[i].v]) dfs(e[i].v);

}

void dp(int x)

{

    f[x]=; pru[x]=w[x]; LL s=;

    for(int i=head[x];i!=-;i=tree[i].nx)

    {

        if(f[tree[i].v]) continue;

        dp(tree[i].v); pru[x]=(pru[x]*pru[tree[i].v])%mod;

        s=(s+pru[tree[i].v])%mod;

    }

    s=(s+val[be[x]]*mod_reverse(pru[x])%mod)%mod;

    ans[x]=((SUM-val[be[x]]+mod)%mod+s)%mod;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++) w[i]=(LL)read();

        memset(h,-,sizeof h); tot=;

        for(int i=;i<=m;i++) {

            int u=read(),v=read(); AddEdge(u,v); AddEdge(v,u);

        }

        memset(f,block=sz=,sizeof f);

        for(int i=;i<=n;i++)

        {

            if(f[i]) continue;

            block++; sz=; dfs(i); cnt[block]=sz;

        }

        SUM=;

        for(int i=;i<=block;i++) val[i]=;

        for(int i=;i<=n;i++) val[be[i]]=(val[be[i]]*w[i])%mod;

        for(int i=;i<=block;i++) SUM=(SUM+val[i])%mod;

        memset(head,-,sizeof head); tot=; id=n;

        find_bcc();

        memset(f,,sizeof f);

        for(int i=;i<=n;i++)

            if(cnt[be[i]]==) ans[i]=(SUM-val[be[i]]+mod)%mod;

        for(int i=n+;i<=id;i++) if(!f[i]) dp(i);

        LL S=;

        for(int i=;i<=n;i++) S=(S+((LL)i*ans[i])%mod)%mod;

        printf("%lld\n",S);

    }

    return ;

}