Bạn được cho một cây ~n~ đỉnh, số nguyên dương ~k~ và ~m~ đường đi trên cây, đường đi thứ ~i~ nối giữa hai đỉnh ~a_i~ và ~b_i~.

Đếm số cách chọn ra tập ~k~ đường đi ~i_1, i_2, ..., i_k~ (~1 \leq i_1 < i_2 < ... < i_k \leq m~) sao cho với mọi cặp hai đường đi ~i_p~ và ~i_q~ (~1 \leq p < q \leq k~), hai đường đi này giao nhau. Hai đường đi giao nhau nếu tồn tại ít nhất một đỉnh ~w~ (~1 \leq w \leq n~) mà đỉnh ~w~ thuộc cả hai đường đi.

Vì kết quả có thể rất lớn, in ra phần dư sau khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên gồm ~3~ số nguyên dương ~n,m,k~ ~(1\leq n,m,k \leq 10^5)~

• ~n - 1~ dòng tiếp theo gồm ~2~ số nguyên dương ~u, v~ là các cạnh của cây

• ~m~ dòng tiếp theo gồm ~2~ số nguyên ~a, b~ là đường đi từ ~a~ đến ~b~ trên cây

Output

In ra một dòng duy nhất là đáp án của bài toán

Scoring

• Subtask ~1~ (~20~ điểm): ~n,m \leq 20~.

• Subtask ~2~ (~20~ điểm): mỗi đỉnh chỉ có tối đa 2 cạnh kề.

• Subtask ~3~ (~60~ điểm): không có ràng buộc gì thêm.

Sample Input 1

5 3 2
1 4
1 2
2 3
2 5
1 4
5 1
3 5

Sample Output 1

2

Sample Input 2

5 3 2
1 4
1 2
2 3
2 5
3 4
5 1
3 5

Sample Output 2

3

Notes

Trong ví dụ thứ nhất, các tập thỏa mãn là {(~1, 4~), (~1, 5~)}, {(~3, 5~), (~1, 5~)}