Statement
유담이는 최근 Lemon Tree를 기르기 시작했다!
첫째 날의 Lemon Tree는 개의 정점과 개의 간선으로 이루어진 트리 이다. 정점에는 번부터 번까지 번호가 붙어 있다. 레몬의 종류 역시 번부터 번까지 총 가지이며, 첫째 날에는 번 정점에 번 종류의 레몬이 하나 열려 있다.
Lemon Tree는 매일 밤 매우 빠르게 성장한다. 그날 존재하는 모든 정점에 대해 다음 과정이 동시에 일어난다.
정점 에 번 종류의 레몬이 열려 있다고 하자.
- 첫째 날의 트리 와 동일한 새로운 트리 하나를 만든다.
- 새 트리의 번 정점이 기존 정점 가 되도록 새 트리를 붙인다.
- 새 트리의 번 정점에는 번 종류의 레몬이 열린다. 단, 기존 정점 에는 그대로 번 종류의 레몬이 열린다.
즉, 각 정점에는 그 정점에 열린 레몬의 종류에 해당하는 정점을 연결점으로 하여 첫째 날의 Lemon Tree 한 그루가 새롭게 자라난다.
따라서 일 차의 Lemon Tree에는 정확히 개의 정점이 존재하며, 각 정점에는 레몬이 하나씩 열려 있으므로 레몬 역시 개 존재한다.
Lemon Tree를 기른 지 일째가 된 유담이는 다음 값이 궁금해졌다.
- 일 차 Lemon Tree에 열린 서로 다른 두 레몬을 고르는 모든 경우에 대해, 두 레몬 사이의 거리의 합
두 레몬 사이의 거리는 두 레몬이 열린 정점 사이의 거리이며, 두 정점 사이의 거리는 두 정점을 잇는 단순 경로에 포함된 간선의 개수이다. 위 값을 구하여라. 답이 매우 클 수 있으므로 으로 나눈 나머지를 출력한다. 단, 은 소수이다.
Input
첫 번째 줄에 두 정수 과 가 공백으로 구분되어 주어진다.
다음 개의 줄에는 첫째 날 Lemon Tree의 간선이 주어진다. 각 줄에는 두 정수 와 가 공백으로 구분되어 주어지며, 이는 Lemon Tree의 번 정점과 번 정점 사이에 간선이 있음을 의미한다.
Output
첫 번째 줄에 문제의 답을 으로 나눈 나머지를 출력한다.
Constraints
;