Running Race

Minhyuk is organizing a running race. The city that hosts it has $N$ intersections, numbered $0$ through $N-1$.

The city has $M$ roads, numbered $0$ through $M-1$. Every road is bidirectional and joins two different intersections. No road joins an intersection to itself, and at most one road joins any given pair of intersections. The road network is not guaranteed to be connected, so two intersections may have no route between them at all.

The rule of the race is simple. A runner starts at intersection $0$ and finishes at intersection $N-1$. Road $i$ carries at most $3^i$ people. Road $2$, for example, carries at most $9$ people, so the tenth person who tries to take road $2$ cannot use it. Runners may share a road, but the number of people who pass along road $i$ never exceeds $3^i$ in total.

Given the roads, write a program that finds the largest number of people who can get from intersection $0$ to intersection $N-1$.

The first line contains the number of intersections $N$ and the number of roads $M$. ($2 \le N \le 2000$, $0 \le M \le 2000$)

Each of the next $M$ lines describes one road, in order, starting with road $0$. Line $i+2$ contains the two intersections $a$ and $b$ that road $i$ joins. ($0 \le a, b < N$, $a \ne b$) No pair of intersections appears more than once.

Print the largest number of people who can get from intersection $0$ to intersection $N-1$, modulo 1,000,000,007.