• Tên file bài làm: TOPOCOUNT.cpp
• File dữ liệu vào: TOPOCOUNT.INP
• File kết quả: TOPOCOUNT.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Cho một cây có gốc gồm ~N~ đỉnh được đánh số từ ~1~ đến ~N~, trong đó đỉnh ~R~ là gốc của cây. Các cạnh của cây được định hướng từ đỉnh cha xuống các đỉnh con trực tiếp của nó, tạo thành một đồ thị có hướng không chu trình (DAG).

Một hoán vị ~p = (p_1, p_2, \dots, p_N)~ của tập hợp ~\{1, 2, \dots, N\}~ được gọi là một thứ tự tô-pô hợp lệ của cây nếu với mọi cặp đỉnh ~u~ và ~v~, nếu có đường đi có hướng từ ~u~ đến ~v~ (tức ~u~ là tổ tiên của ~v~) thì đỉnh ~u~ phải xuất hiện trước đỉnh ~v~ trong hoán vị.

Nói cách khác, nếu ta gán nhãn cho mỗi đỉnh ~u~ một số nguyên ~b_u \in \{1, 2, \dots, N\}~ đôi một khác nhau (chính là vị trí của đỉnh ~u~ trong dãy hoán vị), thì với mọi cạnh có hướng từ cha ~u~ đến con ~v~, ta luôn có: ~b_u < b_v~

Yêu cầu: Hãy đếm số lượng thứ tự tô-pô hợp lệ của cây có gốc đã cho. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~R~ (~1 \le N \le 10^5, 1 \le R \le N~) lần lượt là số lượng đỉnh của cây và chỉ số đỉnh gốc.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le N, u \ne v~) mô tả một cạnh vô hướng của cây.

Kết quả

• In ra một số nguyên duy nhất là số lượng thứ tự tô-pô hợp lệ của cây chia lấy dư cho ~10^9 + 7~.

Subtask

• Subtask 1 (30% số điểm): ~N \le 10~.
• Subtask 2 (30% số điểm): ~N \le 1000~.
• Subtask 3 (40% số điểm): ~N \le 10^5~.

Ví dụ

Giải thích ví dụ 1

• Cây có gốc ~R = 1~ và 2 con là 2 và 3.
• Gốc 1 bắt buộc phải đứng đầu (~b_1 = 1~). Hai đỉnh 2 và 3 có thể xuất hiện theo bất kỳ thứ tự nào:
  1. Hoán vị ~(1, 2, 3)~ ứng với ~b_1 = 1, b_2 = 2, b_3 = 3~.
  2. Hoán vị ~(1, 3, 2)~ ứng với ~b_1 = 1, b_2 = 3, b_3 = 2~.
• Vậy có 2 thứ tự tô-pô hợp lệ.