Those unwilling to return home from a long journey, will be affected by the oddity of the snail and lose their way. Mayoi, the oddity's carrier, wouldn't like this to happen, but there's nothing to do with this before a cure is figured out. For now, she would only like to know the enormous number of possibilities to be faced with if someone gets lost.

There are n towns in the region, numbered from 1 to n. The town numbered 1 is called the capital. The traffic network is formed by bidirectional roads connecting pairs of towns. No two roads connect the same pair of towns, and no road connects a town with itself. The time needed to travel through each of the roads is the same. Lost travelers will not be able to find out how the towns are connected, but the residents can help them by providing the following facts:

• Starting from each town other than the capital, the shortest path (i.e. the path passing through the minimum number of roads) to the capital exists, and is unique;
• Let l_i be the number of roads on the shortest path from town i to the capital, then l_i≥l_i-1 holds for all 2≤i≤n;
• For town i, the number of roads connected to it is denoted by d_i, which equals either 2 or 3.

You are to count the number of different ways in which the towns are connected, and give the answer modulo 10⁹+7. Two ways of connecting towns are considered different if a pair (u,v) (1≤u,v≤n) exists such there is a road between towns u and v in one of them but not in the other.