Alice is going to host a competition in running, called the Candy Cup.
Candy Cup will take place in a city that consists of N intersections.
The intersections are numbered 0 through N-1.
There are M roads in the city.
The roads are numbered 0 through M-1.
Each road is bidirectional and connects two intersections.
There are no self-loops.
Each pair of intersections is directly connected by at most one road.
Note that the road network is not guaranteed to be connected.
(That is, it may be impossible to travel between some pairs of intersections.)
You are given the description of the city: the int N and two ints A and B, each with M elements.
For each valid i, the road number i connects the intersections A[i] and B[i].
As a preparation for the Candy Cup, Alice has placed some candies into the middle of each road.
For each i, she placed exactly 3^i (three to the power of i) candies into the middle of road i.
The rules of Candy Cup are really simple.
Each participant starts at the intersection 0 and must reach intersection N-1 by following some roads.
Additionally, each time a participant takes a road, they must pick up a candy from that road.
(Once there are no candies left on a road, participants in the race are not allowed to take that road.)
Note that different participants may use a different number of roads to reach the finish.
Let F be the largest possible number of participants that can finish Candy Cup by reaching the finish in a valid way.
Return the value (F modulo 1,000,000,007).