Your country has $N$ cities and $N-1$ roads connecting pairs of cities in such a way that there is a path between any pair of cities. For each road, you are given its toll that is the amount of money one has to pay in order to traverse it. The cost of traveling from city $A$ to city $B$ is the sum of the tolls of the roads in the path from $A$ to $B$.

You are given $Q$ queries to process. There are two types of queries:

• $0\ c$: Due to inflation, the toll of all roads adjacent to city $c$ (all roads that have $c$ as one of its endpoints) is multiplied by 2.
• $1\ x\ y$: You are required to find the cost of traveling from $x$ to $y$.

Since the answers can be very large, print them modulo $1,000,000,007$.