AtCoder Beginner Contest 211 [ D - Number of Shortest paths ] https://atcoder.jp/contests/abc211/tasks/abc211_d

abc211_d.py

'''
[問題]
https://atcoder.jp/contests/abc211/tasks/abc211_d

[解説]
公式
https://atcoder.jp/contests/abc211/editorial/2003

'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N, M = map(int, input().split())

route = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    route[A].append(B)
    route[B].append(A)

# 幅優先探索
que = [0]
dist = [None] * N   # 距離
cnt = [0] * N
dist[0] = 0
cnt[0] = 1

for v in que:
    for vv in route[v]:
        if dist[vv] is None:
            dist[vv] = dist[v] + 1
            que.append(vv)  # 次の探索キューに追加
            cnt[vv] = cnt[v]    # cnt初期化
        elif dist[vv] == dist[v] + 1:
            cnt[vv] += cnt[v]
            cnt[vv] %= (10**9+7)

print(cnt[N-1])