#pragma comment(linker, "/STACK:102400000,102400000")

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn =  << ;

const int mod = 1e9 + ;

const int INF = 1e9;

typedef long long LL;

vector<int> G[maxn];

int arr[];

int n, m;

int inq[maxn], d[maxn];

void spfa() {

    queue<int> Q;

    memset(inq, , sizeof(inq));

    memset(d, 0x7f, sizeof(d));

    d[] = , inq[] = , Q.push();

    while (!Q.empty()) {

        int u = Q.front(); Q.pop();

        inq[u] = ;

        for (int i = ; i < G[u].size(); i++) {

            int v = G[u][i];

            if (d[v] > d[u] + ) {

                d[v] = d[u] + ;

                if (!inq[v]) {

                    inq[v] = ; Q.push(v);

                }

            }

        }

    }

}

void init() {

    for (int i = ; i < maxn; i++) G[i].clear();

}

int main() {

    int tc;

    scanf("%d", &tc);

    while (tc--) {

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

        init();

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

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

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

                G[i].push_back(i^arr[j]);

            }

            for (int j = ; j < ; j++) {

                G[i].push_back(i ^ ( << j));

            }

        }

        spfa();

        LL ans = ;

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

            int u, v;

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

            ans += (LL)i*d[u^v];

            ans%=mod;

        }

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

    }

    return ;

}