// [Irelia]
#include<bits/stdc++.h>

namespace Irelia // [Irelia Library] Irelia
{
    #define Irelia__ 201307
    #define fcc(i, j, k) for(num (i)=(j); (i)<=(k); ++(i))
    #define ccf(i, j, k) for(num (i)=(j); (i)>=(k); --(i))
    #define I (*this)
    #define same_type(T1, T2) (std::is_same<T1, T2>::value)
    #define num_type(T) (same_type(T, num) || same_type(T, Num))
    #define fra_type(T) (same_type(T, fra) || same_type(T, Fra))
    #define num_or_fra_type(T) (num_type(T) || fra_type(T))

    using num = int;
    using Num = long long;
    using unum = unsigned int;
    using uNum = unsigned long long;
    using fra = double;
    using Fra = long double;
    using pnum = std::pair<num, num>;
    using pNum = std::pair<Num, Num>;
    template<typename T>
    using heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

    const char newl = '\n', *snewl = " \n";

    constexpr Num read()
    {
        Num ret = 0, s = 1, c = getchar();
        for(; !isdigit(c); c = getchar()) if(c == '-') s = -1;
        for(; isdigit(c); c = getchar()) ret = (ret << 1) + (ret << 3) + (c ^ 48);
        return s * ret;
    }
    constexpr std::string readstr()
    {
        std::string ret; char c;
        for(; (c = getchar()) <= ' ';);
        for(; c > ' '; c = getchar()) ret += c;
        return ret;
    }
    template<typename T>
    constexpr void min_(T &a, auto &&b) { if(b < a) a = b; }
    template<typename T>
    constexpr void max_(T &a, auto &&b) { if(a < b) a = b; }
    template<typename Tnf> requires num_or_fra_type(Tnf)
    constexpr Tnf inf() { return (std::numeric_limits<Tnf>::max() - Irelia__) / 2; }
    template<typename Tn> requires num_type(Tn)
    constexpr Tn lowbit(Tn i) { return i & -i; }

    template<typename T>
    class vector : private std::vector<T>
    {
        public:
        using iterator = std::vector<T>::iterator;
        iterator begin() { return std::vector<T>::begin(); }
        iterator end() { return std::vector<T>::end(); }

        vector() { }
        vector(num siz) : std::vector<T>(siz) { }
        vector(num siz, auto &&t) : std::vector<T>(siz, t) { }
        vector(std::initializer_list<T> il) : std::vector<T>(il) { }
        vector(T *pb, T *pe) : std::vector<T>(pb, pe) { }
        vector(iterator itb, iterator ite) : std::vector<T>(itb, ite) { }

        void clear() { std::vector<T>::clear(); }
        operator bool () { return !I.empty(); }
        num size() { return std::vector<T>::size(); }
        vector &set(num siz) { return I.resize(siz), I; }
        T &front() { return std::vector<T>::front(); }
        T &back() { return std::vector<T>::back(); }
        T &operator [] (num i)
        {
            #ifdef DEBUG__
            assert(0 <= i && i < size());
            #endif
            return std::vector<T>::operator[](i);
        }
        void push(auto &&...t) { I.emplace_back(t...); }
        void insert(num i, auto &&...t) { I.emplace(begin() + i, t...); }
        void pop() { I.pop_back(); }
        void erase(num i) { std::vector<T>::erase(begin() + i); }
        void fill(auto &&t) { std::fill(begin(), end(), t); }
        void reverse() { std::reverse(begin(), end()); }
        template<typename Tcom = std::less<T>>
        void sort() { std::sort(begin(), end(), Tcom()); }
        template<typename Tcom = std::less<T>>
        num lower(auto &&t) { return std::lower_bound(begin(), end(), t, Tcom()) - begin(); }
        template<typename Tcom = std::less<T>>
        num upper(auto &&t) { return std::upper_bound(begin(), end(), t, Tcom()) - begin(); }
        template<typename Tcom = std::less<T>>
        void discretize()
        {
            sort<Tcom>(), set(std::unique(begin(), end(),
                [&](T &a, T &b) { return !Tcom()(a, b) && !Tcom()(b, a); }) - begin());
        }
    };

    #define every(e, G, o) for(num (e)=(G).las[(o)]; (e); (e)=(G).pre[(e)])
    template<typename Tn> requires num_type(Tn)
    class graph
    {
        public:
        num V, E; vector<num> las, pre, to, fro; vector<Tn> wei, cap;

        graph(num V = 0) : V(V), E(0), las(V + 1), pre(2), to(2), fro(2), wei(2), cap(2) { }

        void add(num u, num v, Tn w = 0, Tn c = 0)
        { pre.push(las[u]), las[u] = ++E + 1, to.push(v), fro.push(u), wei.push(w), cap.push(c); }
        void addb(num u, num v, Tn w = 0, Tn c = 0) { add(u, v, w, c), add(v, u, w, c); }
    };
}

namespace Irelia // [Irelia Library] modulus
{
    template<num mod>
    class modnum
    {
        private:
        num i;

        public:
        modnum(num i = 0) : i(i) { }

        num operator () () { return i; }
        modnum &operator ++ () { if(++i == mod) i = 0; return I; }
        modnum operator ++ (num) { modnum ret = I; return ++I, ret; }
        modnum operator + (modnum m) { num ret = i + m.i; if(ret >= mod) ret -= mod; return ret; }
        modnum &operator += (modnum m) { if((i += m.i) >= mod) i -= mod; return I; }
        modnum &operator -- () { if(!i--) i = mod - 1; return I; }
        modnum operator -- (num) { modnum ret = I; return --I, ret; }
        modnum operator - (modnum m) { num ret = i - m.i; if(ret < 0) ret += mod; return ret; }
        modnum &operator -= (modnum m) { if((i -= m.i) < 0) i += mod; return I; }
        modnum operator * (modnum m) { return 1ULL * i * m.i % mod; }
        modnum &operator *= (modnum m) { return i = 1ULL * i * m.i % mod, I; }
        modnum operator / (modnum m) { return I * m.inv(); }
        modnum &operator /= (modnum m) { return I *= m.inv(); }
        modnum power(num e)
        { modnum ret = 1, d = I; for(; e; e >>= 1, d *= d) if(e & 1) ret *= d; return ret; }
        modnum inv() { return power(mod - 2); }
        friend std::ostream &operator << (std::ostream &os, modnum m) { return std::cout << m.i; }
    };
}

using namespace Irelia;

const num mod = 1E9 + 7;
using Mod = modnum<mod>;
void solve()
{
    num N1 = read(), N2 = read(), M = read(), K = read(), mas = (1 << M) - 1;
    vector<num> A(K + 1), B(K + 1), con(M + 1);
    fcc(i, 1, K) A[i] = read(), B[i] = read(), con[A[i]] = con[B[i]] = 1;
    num ncon = 0;
    fcc(i, 1, M) if(!con[i]) ++ncon;
    vector<vector<Mod>> dp(M + 1, vector<Mod>(M + 1));
    fcc(s, 0, mas)
    {
        vector<num> vis(M + 1);
        graph<num> G(M);
        fcc(i, 1, K) if(!(s >> A[i] - 1 & 1) && !(s >> B[i] - 1 & 1)) G.addb(A[i], B[i]);
        std::function<pnum(num, num)> DFS = [&](num o, num c)
        {
            pnum ret; vis[o] = c, ++(c == 2 ? ret.first : ret.second);
            every(e, G, o)
                if(vis[G.to[e]] == c) return pnum(-1, -1);
                else if(!vis[G.to[e]])
                {
                    pnum pa = DFS(G.to[e], c ^ 1);
                    if(pa.first < 0) return pnum(-1, -1);
                    ret.first += pa.first, ret.second += pa.second;
                }
            return ret;
        };
        num N = 0, sum = 0, bc = std::popcount<unum>(s), ok = 1;
        vector<pnum> P(1);
        fcc(i, 1, M) if(con[i] && !vis[i] && !(s >> i - 1 & 1))
            ++N, P.push(DFS(i, 2)), sum += P[N].first + P[N].second;
        fcc(i, 1, N) if(P[i].first < 0) ok = 0;
        if(!ok) continue;
        vector<Mod> dp2(sum + 1); dp2[0] = 1;
        auto get = [&](num i) { return i >= 0 ? dp2[i] : Mod(0); };
        fcc(i, 1, N) ccf(j, sum, 0) dp2[j] = get(j - P[i].first) + get(j - P[i].second);
        fcc(j, 0, sum) if(dp2[j]()) dp[j + bc][sum - j + bc] += dp2[j];
    }
    fcc(i, 1, ncon) ccf(j, M, 0) ccf(k, M, 0)
    {
        if(j) dp[j][k] += dp[j - 1][k];
        if(k) dp[j][k] += dp[j][k - 1];
    }
    auto bin = [&](num i, num j)
    {
        Mod ret = 1;
        fcc(k, 1, j) ret = ret * (i - k + 1) / k;
        return ret;
    };
    Mod ans = 0;
    fcc(i, 1, std::min(N1, M)) fcc(j, 1, std::min(N2, M))
        ans += bin(N1 - 1, i - 1) * bin(N2 - 1, j - 1) * dp[i][j];
    std::cout << ans << newl;
}
num main()
{
    #ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0), std::cin.tie(0);

    for(num T = read(); T --> 0;) solve();
    return 0 ^ 0;
}