#include <stdio.h>

#include <string.h>

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

typedef long long ll;

const int N = ;

const ll mod = 1e9+;

int n, m;                   // 同题目描述

int a[N];                   // 记录每个点的权值

struct Edge                 // 前向星存边

{

    int to, next;

} edge[N*];

int cnt_edge;

int head[N];

void add_edge(int u, int v)

{

    edge[cnt_edge].to = v;

    edge[cnt_edge].next = head[u];

    head[u] = cnt_edge++;

}

int dfn[N], low[N], idx;        // tarjan中用到的变量

ll mul;                         // 临时变量，记录每个图的所有点乘积

ll ans[N];                      // 对于每个割点 如果分割了这个点 这棵树的答案

ll smul[N];                     // 对于每个割点 分割它后所有分出来的子树的乘积

bool cut[N];                    // 割点

int graph_cnt;                  // 连通图数量

vector<int> G[N];               // 记录每个连通图

ll graph[N];                    // 每个连通图所有点的乘积

int kind[N];                    // 每个点属于哪个连通图

void init(int n)

{

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

        head[i] = -;

        dfn[i] = ;

        ans[i] = ;

        smul[i] = ;

        cut[i] = false;

        G[i].clear();

    }

    cnt_edge = ;

    idx = ;

    graph_cnt = ;

}

ll pow_mod(ll x, ll n)

{

    ll ans = ;

    while (n) {

        if (n & ) ans = ans * x % mod;

        x = x * x % mod;

        n >>= ;

    }

    return ans;

}

void tarjan(int u, int fa)

{

    dfn[u] = low[u] = ++idx;

    int child = ;

    G[graph_cnt].push_back(u);

    kind[u] = graph_cnt;

    mul = mul * a[u] % mod;

    for (int i = head[u]; i != -; i = edge[i].next) {

        int v = edge[i].to;

        if (v == fa) continue;

        if (!dfn[v]) {

            ll tmp = mul;

            tarjan(v, u);

            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) {     // u是割点

                ++child;

                ll inv = pow_mod(tmp, mod-);

                tmp = mul * inv % mod;  // mul/tmp 就是这个子图的乘积

                ans[u] = (ans[u] + tmp) % mod;

                smul[u] = smul[u] * tmp % mod;

            }

        } else {

            low[u] = min(low[u], dfn[v]);

        }

    }

    if ((fa == - && child > ) || (fa != - && child)) cut[u] = true; // u是割点

}

int main(int argc, char const *argv[])

{

    //freopen("in", "r", stdin);

    int T;

    cin >> T;

    while (T--) {

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

        for (int i = ; i <= n; ++i) scanf("%d", a+i);

        int u, v;

        while (m--) {

            scanf("%d%d", &u, &v);

            add_edge(u, v);

            add_edge(v, u);

        }

        ll res = ;

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

            if (!dfn[i]) {

                mul = ;

                tarjan(i, -);

                graph[graph_cnt] = mul;

                res = (res + mul) % mod;

                for (unsigned j = ; j < G[graph_cnt].size(); ++j) {

                    u = G[graph_cnt][j];

                    if (u != i) {

                        ans[u] = (ans[u] + mul * pow_mod(smul[u]*a[u]%mod, mod - ) % mod) % mod;  //mul/smul[j];

                    }

                }

                ++graph_cnt;

            }

        }

        ll rut = ;

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

            ll tmp;

            if (cut[i]) {               // 如果是割点的话 就是这个点所在图分成多个子图

                tmp = (res - graph[ kind[i] ] + ans[i] + mod) % mod;

            } else {

                if (G[kind[i]].size() == ) {

                    tmp = (res - a[i] + mod) % mod;

                } else {

                    tmp = (res - graph[kind[i]] + graph[kind[i]] * pow_mod(a[i], mod-) % mod + mod) % mod;

                }

            }

            rut = (rut + i * tmp % mod) % mod;

        }

        cout << rut << endl;

     }

    return ;

}