달리기 대회

민혁이는 달리기 대회를 열려고 한다. 대회가 열리는 도시에는 교차로가 $N$개 있고, 번호는 $0$번부터 $N-1$번까지이다.

도시의 도로는 $M$개이고, 번호는 $0$번부터 $M-1$번까지이다. 도로는 모두 양방향이고 서로 다른 두 교차로를 잇는다. 한 교차로를 자기 자신과 잇는 도로는 없고, 같은 두 교차로를 잇는 도로도 최대 하나이다. 도로망 전체가 연결되어 있다는 보장은 없다. 즉, 두 교차로 사이에 경로가 아예 없을 수도 있다.

대회 규칙은 간단하다. 참가자는 $0$번 교차로에서 출발해 $N-1$번 교차로에 도착하면 된다. 단, $i$번 도로는 $3^i$명까지만 지나갈 수 있다. 예를 들어 $2$번 도로는 $9$명까지만 지나갈 수 있어서, 열 번째로 $2$번 도로를 지나려는 사람은 그 도로를 쓰지 못한다. 여러 참가자가 같은 도로를 나눠 쓸 수 있지만, $i$번 도로를 지나간 사람의 수는 모두 합쳐 $3^i$명을 넘지 못한다.

도로 정보가 주어질 때, $0$번 교차로에서 출발해 $N-1$번 교차로까지 도착할 수 있는 사람 수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 교차로의 수 $N$과 도로의 수 $M$이 주어진다. ($2 \le N \le 2000$, $0 \le M \le 2000$)

둘째 줄부터 $M$개의 줄에 도로의 정보가 $0$번 도로부터 순서대로 주어진다. $i+2$번째 줄에는 $i$번 도로가 잇는 두 교차로의 번호 $a$와 $b$가 주어진다. ($0 \le a, b < N$, $a \ne b$) 같은 두 교차로를 잇는 도로가 두 번 이상 주어지는 경우는 없다.

첫째 줄에 $0$번 교차로에서 출발해 $N-1$번 교차로까지 도착할 수 있는 사람 수의 최댓값을 1,000,000,007로 나눈 나머지를 출력한다.