After Professor TOI has done his initial planning to promote tourism, in order to ensure the completeness of the work, he sent a research assistant Mr. K to explore the tourist attractions seriously. However!!! There is a problem once again. While Mr. K was travelling to explore the new attractions, Mr. K got stuck in a maze. Fortunately, Mr. K has a heritage, which is the cryptic writing, that has been passed from generations to generations for 19 generations. Therefore, he knows that the maze consists of $$$N$$$ rooms. Each of the rooms has a number labeled between $$$1$$$ to $$$N$$$, none of which are repeated. There is a total of $$$N-1$$$ pathways between the rooms such that it is always possible to walk between one room to any other rooms using these pathways.

Since the heritage is an old piece of data, and has been written using ancient ways, to prevent errors, Mr. K then chose to investigate the maze once again to update the data. This means, if the entrance of the maze is at room $$$x$$$, Mr. K will use the exploration algorithm learned from his first and second training camp, which is exactly the following.

1. Mr. K has an "exploration list" at the start. This list will be an empty list and when Mr. K go into any room of the maze, he might take note the number of that room, "appending" into the list. The number will be written if and only if the room hasn't been in the list before. Mr. K starts exploring by walking into the room $$$x$$$ and write $$$x$$$ into the "list".
2. Once Mr. K gets into any room, he will choose one of the pathways to exit that room by the following procedure.
   1. If there exists a pathway leading into a room that he hasn't been there before, Mr. K will choose the pathway and walk into that room (and he will simultaneously write down the number of the new room according to the first step of the algorithm). If there are multiple ways of choosing the next room, he may choose any of the options.
   2. However, if all pathways lead into rooms that he has already been in before, Mr. K will check whether the current room is $$$x$$$ or not. If not, Mr. K will walk into the pathway leading to the room appearing on the topmost of the "list" and walk inside that room. But if the current room is $$$x$$$, Mr. K will know that he has explored the entire maze already, so he will end his exploration, which leads him outside of the maze.
3. Once he exits the maze, Mr. K will submit "the list" as a result of his exploration to Professor TOI.

For example, if the maze consists of three rooms, with pathways connecting room 1 to room 2, and room 2 to room 3, as shown in Fig 1.

Fig 1. A maze consisting of pathways connecting room 1 to room 2 and room 2 to room 3.

For the case that the entrance $$$x$$$ is room 1, Mr. K will walk and record his exploration list as the following. He starts walking into room 1 and the "list" of Mr. K is [1], or as shown in the following table.

From room 1, there is a pathway to room 2, which is the room that Mr. K has never been to. Hence, Mr. K then walks into room 2 and the "list" of Mr. K is now [1, 2] or as shown in the following table.

From room 2, there are two pathways leading into room 1 and room 3, where Mr. K will only choose room 3 because it's the only room he hasn't been to before. Now, his list will be [1 2 3] or as shown in the following table.

From room 3, there is only one pathway leading to room 2, where he has already gone there, so he must go there because it is the topmost number appearing in his list. And his list will be the same, that is [1 2 3].

From room 2, there are two pathways leading to room 1 and room 3. Mr. K must go to room 1 because it's the room appearing in the topmost position on his list.

Now Mr. K is inside room $$$x = 1$$$, so Mr. K ends his journey and immediately quits the maze. Observe that for the case of the entrance $$$x$$$ equals 1, there is only one possibility of the "list", that is, [1 2 3].

Observe that if two people explore the same maze, they might come back with two different "list"s. For example, in the same case as in Fig 1., if the entrance $$$x$$$ is room 2, there will be two possibilities of the "list": [2 1 3] and [2 3 1].

However, we don't know the explicit structure of the maze. We only have a "list" from the result of a historical explorer, which has been passed from generations to generations. And the explorers in the past used a different method of writing down the data. The difference is at step 1 of the algorithm where the old ways of doing this is that no matter whether one has been to the room or not, the explorer will always write down the number of that room, appending into the end of the list. The exploration is still the same, i.e., only explore the unexplored rooms (both the step 2 and step 3 of the algorithm are the same between the old way and the current way). For example, if the old explorer explores the maze from Fig 1., starting from the entrance $$$x$$$ being room 2, the explorer might write down either [2 1 2 3 2] or [2 3 2 1 2] (both ways are possible).

Your Task

Write an efficient program to compute the number of ways to write the exploration list using Mr. K's algorithm (the current one), answering the remainder of the answer with 1,000,000,007.

Notices regarding the test sets are as follows:

Define "distance from the entrance $$$x$$$" to be the minimum number of pathways required to walk between the entrance $$$x$$$ to that room. For example, the entrance room (room $$$x$$$) has distance from the entrance $$$x$$$ as 0. Whereas the rooms connected to $$$x$$$ has distance from the entrance $$$x$$$ as 1.