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