#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005, MOD = 1000000007;
int n,m;
vector<int> g[N];
int dist[N];
ll cnt[N];
void bfs(){
memset(dist,0x3f,sizeof dist);
queue<int> q;
q.push(1);
dist[1] = 0;
cnt[1] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
for(auto v : g[u]){
if(dist[u]+1<dist[v]){
dist[v] = dist[u]+1;
cnt[v] = cnt[u];
q.push(v);
}else if(dist[u]+1==dist[v]){
cnt[v] += cnt[u];
cnt[v] %= MOD;
}
}
}
}
int main(){
cin >> n >> m;
for(int i=1,u,v; i<=m; i++){
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bfs();
cout << cnt[n];
return 0;
}
