First, how can we find the length of the shortest path from Vertex \(1\) to Vertex \(N\)? Since the every edge has weight \(1\), the question can be answered with a BFS (Breadth-First Search) in a total of \(O(N+M)\) time.

The original problem can similarly be solved with BFS in a total of \(O(N+M)\) time, in which we compute not only the shortest distance from the starting vertex but also the number of the paths accomplishing the distance.

When finding the shortest distance with BFS, we compute the array of shortest distance \(\text{dist}\) by

• For each \(v'\) that has an edge from \(v\),
  • if we’ve never visited \(v'\) yet, update \(\text{dist}[v']\) to \(\text{dist}[v]+1\);
  • otherwise, do nothing.

Simultaneously, we can update a new array of number of shortest path \(\text{cnt}\) in the following way:

• For each \(v'\) that has an edge from \(v\),
  • if we’ve never visited \(v'\) yet, update \(\text{dist}[v']\) to \(\text{dist}[v]+1\) and assign \(\text{cnt}[v]\) to \(\text{cnt}[v']\);
  • if we’ve already visited \(v'\) and \(\text{dist}[v']=\text{dist}[v]+1\), add \(\text{cnt}[v]\) to \(\text{cnt}[v']\);
  • otherwise, do nothing.

Sample code (Python)

# read the input
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	A,B=map(int,input().split())
	A-=1
	B-=1
	G[A].append(B)
	G[B].append(A)

# initialize
que=[0]
dist=[None]*N
cnt=[0]*N
dist[0]=0
cnt[0]=1

# BFS
for v in que:
	for vv in G[v]:
		if dist[vv] is None:
			dist[vv]=dist[v]+1
			que.append(vv)
			cnt[vv]=cnt[v]
		elif dist[vv]==dist[v]+1:
			cnt[vv]+=cnt[v]
			cnt[vv]%=10**9+7

print(cnt[N-1])