문제
사람은 3가지 유형으로 분류가 가능하다는 연구 결과가 발표되었다. 3가지 유형은 R유형, G유형, B유형으로 나누어진다. R유형의 사람들은 다혈질이며 열정적이고 상냥하며 외향적이다. G유형의 사람들은 자제력이 뛰어나고 다른 사람과 얘기하는 것을 좋아하며 모험을 즐긴다. B유형의 사람들은 세심하고 사려깊은 생각을 하며 호기심이 많다.
각 유형은 서로 구별되는 특성을 가지고 있기 때문에, 서로 짝이 잘 맞는 유형이 있는가 하면 물과 기름처럼 짝이 될 수 없는 유형도 있다. 예를 들어, R유형은 R유형의 사람과 짝이 될 수 없다. 서로 친구가 되면 매일 싸움을 반복하기 떄문이다. 또한, G유형의 사람은 다른 사람과 얘기하는 것을 좋아하기 때문에 어느 유형과도 짝이 될 수 있다. 그러나, B유형의 사람은 G유형의 사람이랑만 짝을 이룰 수 있다. 즉, B유형은 R유형 혹은 B유형과 친구를 맺지 않는다.
이러한 사실을 학교 수업시간에 배운 민규는 어딘가에 적용해보고 싶은 생각이 들었다. 그래서 민규는 자신의 친구들을 이용하여 친구 관계를 나타내는 그래프를 모델링하고, 여기에 위 조건을 지키면서 각 친구들에게 유형을 분배하려고 한다.
여기서 문제를 단순화시키기 위해 이 그래프에는 사이클이 존재하지 않는다고 가정한다. 즉, 명의 친구로 그래프를 모델링했다면 이 그래프에는 친구 관계를 나타내는 간선이
개 존재한다(이러한 특징을 보이는 그래프를 트리라고 한다).
명의 친구와
개의 친구 관계를 가지고 있을 때, 위 조건을 만족시키도록 각 친구들의 유형을 정하는 경우의 수를 구하여라.
입력
첫째 줄에 민규가 모델링에 사용할 친구의 수
그 이후 줄에 걸쳐 두 개의 서로 다른 정수
가 공백으로 구분되어 주어진다. 이는 A와 B는 서로 친구 관계라는 이다.
출력
문제의 본문에 기술된 조건을 만족하는 각 친구들의 유형을 정하는 경우의 수를 출력한다.
이때, 경우의 수가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
12
23
14
13
12
45
52
63
42
13
21
12
39
57
13
34
25
56
810
38