Tô màu cây 2

Cho một cây gồm \(n\) đỉnh. Hãy đếm số cách tô màu tất cả các đỉnh của cây bằng \(3\) màu sao cho không có hai đỉnh kề nhau nào được tô cùng một màu.

Input

• Dòng đầu tiên gồm một số nguyên \(n\) (\(1 \le n \le 10^5\)).

• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện có một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Dữ liệu vào luôn tạo thành một cây.

Output

In ra một số nguyên duy nhất là số cách tô màu thỏa mãn yêu cầu, lấy phần dư khi chia cho \(10^9 + 7\).

Example

Input:

5
1 2
1 3
2 4
2 5

Output:

48

Note

Cây gồm \(5\) đỉnh với các cạnh \((1,2), (1,3), (2,4), (2,5)\). Đỉnh \(1\) có \(3\) cách chọn màu; với mỗi cách chọn màu cho đỉnh \(1\), đỉnh \(3\) có \(2\) cách chọn màu khác đỉnh \(1\). Đỉnh \(2\) có \(2\) cách chọn màu khác đỉnh \(1\); với mỗi cách chọn màu cho đỉnh \(2\), mỗi đỉnh trong \(\{4, 5\}\) có \(2\) cách chọn màu khác đỉnh \(2\). Tổng số cách tô màu là \(3 \times 2 \times 2 \times 2 \times 2 = 48\).