Rảnh rỗi vì không có ngiu, GS. PVH lấy giấy ra vẽ cây. GSPVH đã vẽ được một cây gồm \(n\) đỉnh và đánh số các đỉnh từ \(1\) đến \(n\).

Nhắc lại, cây là đồ thị vô hướng phi chu trình. Một cây gồm \(n\) đỉnh chắc chắn có \(n - 1\) cạnh.

Sau khi vẽ xong, GS. PVH chọn ra \(k\) đỉnh phân biệt trên cây và tô các đỉnh này bằng màu xanh lá cây. Tiếp theo đó, GS lại tiếp tục tô màu vàng vào những đỉnh mà GS coi là "xung yếu". Một đỉnh được GS coi là "xung yếu" khi và chỉ khi đỉnh này không được tô màu xanh lá cây; và nếu xóa đỉnh này ra khỏi cây, sẽ có hai đỉnh nào đó vừa được tô màu xanh lá cây không thể đi tới nhau nữa.

Tô màu đủ kiểu rồi, vẫn thấy mình còn dư quá nhiều thời gian, GS. PVH quyết định vẽ một bức tranh "siêu to khổng lồ to nhất Việt Nam" bằng việc liệt kê tất cả các cách chọn ra \(k\) đỉnh trong số \(n\) đỉnh của cây. Sau đó, với mỗi cách chọn, GS lại vẽ ra một cây và tô hai màu xanh lá cây và vàng vào các đỉnh theo quy tắc ở trên.

Thế nhưng, GS sắp hết bút sáp màu vàng. Vì vậy, GS. muốn nhờ bạn tính tổng số đỉnh được tô màu vàng trong bức tranh siêu to khổng lồ của mình.

Để làm khó bạn hơn, GS cho bạn trước một con số \(p\) và yêu cầu bạn phải tính ra kết quả theo modulo \(p\). Các bạn hãy chiều GS nhé.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(p\) \((1 \leq k \leq n \leq 10^6, p \in \{10^9 + 19972207, 10^9 + 22071997\})\), lần lượt là số đỉnh trên cây, số đỉnh được GS. PVH lựa chọn để tô màu xanh lục và số \(p\) được nhắc đến trong đề bài.

• Trong \(n - 1\) dòng còn lại, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\).

Output

• In ra tổng số đỉnh màu vàng trong bức tranh của GS. PVH.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(12.6\) điểm): \(n \leq 20\)
• Subtask \(2\) (\(8.4\) điểm): \(n \leq 5000\)
• Subtask \(3\) (\(7\) điểm): \(k = 1\)
• Subtask \(4\) (\(12.6\) điểm): \(k = 2\)
• Subtask \(5\) (\(11.2\) điểm): \(p = 10^9 + 19972207\)
• Subtask \(6\) (\(18.2\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Example

6 3 1019972207
1 2
2 3
3 4
3 5
3 6

16