Kim Chi, Văn Hiệp và Diệp Thảo và 3 người bạn thân. Họ cùng nhau lớn lên, cùng nhau chơi đùa, cùng nhau đọc sách. Để thử tài nhau, hàng tuần, họ sẽ thay phiên nhau ra một bài toán để đố những người còn lại. Tuần này, đến lượt Diệp Thảo ra câu đố.

Lấy cảm hứng từ những chú kiến, Diệp Thảo tạo ra một đồ thị vô hướng G = (N, N − 1) liên thông (nói cách khác, G là một cây có N đỉnh) và M cặp (ai, bi). Đếm xem có bao nhiêu cách thêm hướng vào các cạnh của đồ thị G sao cho với mỗi cặp (ai, bi) trong M, tồn tại đường đi để đi từ ai đến bi hoặc từ bi đến ai.

Dữ liệu

• Dòng đầu gồm hai số nguyên N , M . (1 ≤ N, M ≤ 3 × 105).

• N − 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v (1 ≤ u, v ≤ N ) - cạnh của đồ thị.

• M dòng tiếp theo, mỗi dòng gồm hai số nguyên ai, bi (1 ≤ ai, bi ≤ N ).

Kết quả

• Gồm một số nguyên duy nhất là phần dư khi chia kết quả bài toán với 109 + 7.

Ví dụ

Input	Output
7 2 1 2 1 3 4 2 2 5 6 5 5 7 1 7 2 6	8