For each v′ that has an edge from v
• if we’ve never visited v′ yet, update dist[v] to dist[v]+1;
• otherwise, do nothing.

Simultaneously, we can update a new array of number of shortest path cnt in the following way:
• if we’ve never visited v′ yet, update dist[v] to dist[v]+1 and assign cnt[v] to cnt[v];
• if we’ve already visited v′ and dist[v′] = dist[v]+1, add cnt[v] to cnt[v];
• otherwise, do nothing.

const int N = (2 * 1e5) + 2;
const int INF = 1e9;
const int M = 1e9+7;
vector<int> g[N];
int32_t main() {
    int n,m;
    cin >> n >> m;
    for(int i=0; i < m ;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> dist(n+1, INF);
    vector<int> ways(n+1, 0);
    dist[1] = 0;
    ways[1] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : g[u]){
            if(dist[v] > dist[u] + 1){
                dist[v] = dist[u] + 1;
                q.push(v);
                ways[v] = ways[u];
            }
            else if(dist[v] == dist[u] + 1){
                ways[v] = (ways[v] + ways[u]) % M;
            }
        }
    }
 
    cout << ways[n] << endl;
 
    return 0;
}