34082번 - Lv2부터 치트였던 전직 아이돌 한별이의 알록달록 트리 라이프

문제

어떻게 살면 트리같이 사이클 없는 인생을 살 수 있을까?

— 오늘은 코딩하고 싶은 날

PRODUCE $\mathbf{{10}^1}$에서 아쉽게 탈락한 한별이는 부족한 실력을 키워서 반드시 아이돌이 되고 싶었다. 그러던 중 Lv2부터 치트였던 전직 용사 후보의 유유자적 이세계 라이프를 본 한별이는 깊은 감명을 받는다.

"나도 이런 치트를 써서 $\infty$의 실력을 가진 아이돌이 되고 싶어!"

그 순간 한별이 눈앞에 우연히 한별이의 꿈을 실현해줄 트리가 나타났다. 트리는 사이클이 없는 연결 그래프이며, 이 트리는 1ドル$번부터 $N$번까지 번호가 붙여진 $N$개의 정점으로 이루어져 있었다.

한별이가 발견한 트리의 치트를 발동하기 위해서는 먼저 두 가지 색을 골라 모든 정점을 각각 두 가지 색 중 하나로 색칠해야 한다. 한별이는 한 치의 고민 없이 자신의 머리카락 색인 코랄색과 개나리색을 선택했다. 다음으로, 이 두 가지 색을 사용하여 트리의 레벨을 2ドル$ 이상으로 만들어야 한다. 트리의 각 정점의 레벨은 인접한 정점 중 자신과 다른 색으로 칠해진 정점의 수이고, 트리의 레벨은 트리에 속한 모든 정점의 레벨 중 최댓값으로 정의된다. 정점의 레벨과 트리의 레벨의 정의가 일반적인 정의와 다름에 유의하라.

한별이는 자신의 꿈을 이루기 위해 트리를 열심히 색칠하다가 문득 이 트리의 치트를 발동할 수 있는 색칠 방법이 매우 많다는 사실을 깨달았다. 한별이는 가능한 색칠 방법이 몇 가지일지 궁금해졌지만, 트리를 색칠하느라 바쁘기 때문에 여러분에게 궁금증 해결을 맡겼다. 한별이가 발견한 트리가 주어질 때, 이 트리의 각 정점을 각각 코랄색과 개나리색 중 하나로 칠하여 트리의 레벨이 2ドル$ 이상이 되는 색칠 방법의 수를 구해보자.

입력

첫 번째 줄에 한별이가 발견한 트리의 정점의 수 $N$과 정수 $M$이 공백으로 구분되어 주어진다. $M$이 소수가 아닐 수 있음에 유의하라. (2ドル\le N\le 300,円 000$; 2ドル\le M\le 10^9$)

두 번째 줄부터 $N-1$개 줄에 걸쳐서 간선으로 연결된 두 정점의 번호 $u_i,ドル $v_i$가 공백으로 구분되어 주어진다. (1ドル \le u_i, v_i \le N,ドル $u_i \neq v_i$)

출력

트리의 레벨이 2ドル$ 이상이 되도록 하는 색칠 방법의 수를 $M$으로 나눈 나머지를 출력한다.

제한

노트