Subtask 1:

• Vì ~n, m~ bé nên chúng ta có thể duyệt qua toàn bộ các tập đường đi có độ lớn ~k~ và kiểm tra xem các đường đi có giao nhau hay không

Subtask 2:

• Vì cây trong subtask này là một đường thẳng, ta sẽ coi một đường đi là một đoạn ~[l, r]~ trên mảng ~[1, 2, 3, \cdots, n]~.
• Phần giao nhau của các đoạn luôn luôn là một đoạn khác, vì vậy để đếm phân biệt với nhau cần phải đếm các tập độ lớn ~k~ giao nhau tại vị trí ~i~ ~\textbf{và}~ tồn tại một đoạn thẳng bắt đầu tại ~i~
• Với mỗi vị trí ~i~ bất kì ta có thể đếm được số đoạn đi qua nó và số đoạn có điểm bắt đầu xuất phát tại ~i~
• Gọi ~A~ là tập đoạn đi qua ~i~ và ~B~ là tập đoạn bắt đầu tại ~i~
• Bằng phép loại trừ cơ bản, số tập ~k~ giao nhau tại ~i~ và có một đoạn xuất phát tại ~i~ sẽ là số tập ~k~ thuộc A trừ đi số tập ~k~ thuốc ~A - B~ (các đoạn đi qua ~i~ nhưng không có điểm bắt đầu là ~i~)

Subtask 3:

• Như đã nói ở subtask 2, tương tự với cây nói chung, phần giao nhau của tất cả đường đi trên cây chính một đường đi trên cây
• Nhận xét: trên một đường đi, số đỉnh trừ số cạnh 1
• Vậy chúng ta có thuật toán như sau: Đếm tất cả tập ~k~ đường đi qua một nút ~u~ và tổng lại tất cả ~n~ nút, khi đó các đường đi giao nhau ~a~ nút sẽ bị đếm lặp lại ~a~ lần
• Tuy nhiên nhờ nhận xét ở trên, bằng việc trừ đi số tập ~k~ đi qua tất cả các cạnh ~(u, v)~ trên cây, các đường đi giao nhau ~a~ nút sẽ bị trừ đi ~a - 1~ lần
• Vậy nên mọi tập ~k~ đều phân biệt

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define FF first
#define SS second
#define eps 1e-9
#define PI aocs(-1.0)
// VECTOR (6)
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
#define uniq(x) sort(all((x))), (x).resize(unique(all((x))) - (x).begin());
// BIT (6)
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define SUBSET(big, small) (((big)&(small))==(small))
#define FIRSTBIT(x) __builtin_ctzll(x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;

/* */
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 1e5 + 7, M = 1e9 + 7;
const int MOD = 1e9 + 7;
const int oo = 1e9 + 7;

const int LOGN = 16;

int n, m, k;

struct Edge {
    int u, v;
    int other(int p) const {
        return u ^ v ^ p;
    }
} edge[N];

vector<int> adj[N];

int in[N], out[N], cnt = 0;
int par[N][LOGN+1];
int parEdge[N];

int comb[N];
int cntNode[N];
int cntEdge[N];

/* */

void gcd(int a, int b, int &x, int &y) {
    if(!b) {x = 1, y = 0; return;}
    int tx, ty; gcd(b, a%b, tx, ty);
    x = ty, y = tx - (a/b) * ty;
}

int inv(int v) {
    int x, y; gcd(v, MOD, x, y);
    return (x % MOD + MOD) % MOD;
}

int add(int a, int b) {
    a+= b; if(a>=MOD) a-=MOD;
    return a;
}

void upd(int &a, int b) {
    a+= b; if(a>=MOD) a-=MOD;
}

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

/* */

void dfs(int u = 1) {
    in[u] = ++cnt;
    for(int i : adj[u]) {
        int v = edge[i].other(u);
        if(v == par[u][0]) continue;
        parEdge[v] = i;
        par[v][0] = u;
        dfs(v);
    }
    out[u] = cnt;
}

void dfs2(int u = 1) {
    for(int i : adj[u]) {
        int v = edge[i].other(u);
        if(v == par[u][0]) continue;
        dfs2(v);
        cntNode[u]+= cntNode[v];
        cntEdge[parEdge[u]]+= cntEdge[i];
    }
}

bool isAnc(int u, int v) {
    if(u == -1) return 1; if(v == -1) return 0;
    return (in[u] <= in[v] && out[v] <= out[u]);
}

int lca(int u, int v) {
    if(isAnc(u, v)) return u;
    if(isAnc(v, u)) return v;
    for(int i = LOGN;i>=0;i--) {
        if(!isAnc(par[u][i], v)) {
            u = par[u][i];
        }
    }
    return par[u][0];
}

void inc(int u, int v) {
    int l = lca(u, v);

    cntNode[u]++;
    cntNode[v]++;
    cntNode[l]--;
    if(par[l][0] != -1) {
        cntNode[par[l][0]]--;
    }

    cntEdge[parEdge[u]]++;
    cntEdge[parEdge[v]]++;
    cntEdge[parEdge[l]]-= 2;
}

signed main() {
    fastIO;
    cin >> n >> m >> k;
    for(int i=1;i<n;i++) {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        adj[u].pb(i);
        adj[v].pb(i);
    }
    memset(par, -1, sizeof par);

    dfs();
    for(int j=1;MASK(j)<=n;j++) {
        for(int i=1;i<=n;i++) {
            if(par[i][j-1] == -1) continue;
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=m;i++) {
        int u, v;
        cin >> u >> v;
        inc(u, v);
    }
    dfs2();

    comb[k] = 1;
    for(int i=k+1;i<=m;i++) {
        comb[i] = mul(comb[i-1], mul(i, inv(i - k)));
    }

    int ans = 0;
    for(int i=1;i<=n;i++) {
        upd(ans, comb[cntNode[i]]);
        upd(ans, MOD - comb[cntEdge[i]]);
    }
    cout << ans;

    return 0;
}