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 đỉnh và đánh số các đỉnh từ đến .
Nhắc lại, cây là đồ thị vô hướng phi chu trình. Một cây gồm đỉnh chắc chắn có cạnh.
Sau khi vẽ xong, GS. PVH chọn ra đỉ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 đỉnh trong số đỉ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ố và yêu cầu bạn phải tính ra kết quả theo modulo . Các bạn hãy chiều GS nhé.
Dữ liệu ra:
Dòng đầu tiên chứa ba số nguyên , và , 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ố được nhắc đến trong đề bài;
Trong dòng còn lại, mỗi dòng chứa hai số nguyên và cho biết trên cây có một cạnh nối hai đỉnh và .
Dữ liệu ra:
In ra tổng số đỉnh màu vàng trong bức tranh của GS. PVH.
Ví dụ:
Dữ liệu vào:
6 3 1019972207
1 2
2 3
3 4
3 5
3 6
Dữ liệu ra:
16
Giải thích:
Dưới đây là bức tranh siêu to khổng lồ to nhất Việt Nam do GS. PVH vẽ trong ví dụ ở trên. Có tất cả cách chọn ra đỉnh trong một cây gồm đỉnh. Tổng số đỉnh được tô màu vàng trong các cách này là:
Giới hạn:
Bộ test của bài được chia làm các subtask như sau:
