{"problem":{"name":"Number of Shortest paths","description":{"content":"The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$. Using Road $i$, you can travel from City $A_i$ to $B_i$ or vice versa in one hour. How many path","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc211_d"},"statements":[{"statement_type":"Markdown","content":"The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$.\nUsing Road $i$, you can travel from City $A_i$ to $B_i$ or vice versa in one hour.\nHow many paths are there in which you can get from City $1$ to City $N$ as early as possible?  \nSince the count can be enormous, print it modulo $(10^9 + 7)$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $0 \\leq M \\leq 2\\times 10^5$\n*   $1 \\leq A_i < B_i \\leq N$\n*   The pairs $(A_i, B_i)$ are distinct.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc211_d","tags":[],"sample_group":[["4 5\n2 4\n1 2\n2 3\n1 3\n3 4","2\n\nThe shortest time needed to get from City $1$ to City $4$ is $2$ hours, which is achieved by two paths: $1 \\to 2 \\to 4$ and $1 \\to 3 \\to 4$."],["4 3\n1 3\n2 3\n2 4","1\n\nThe shortest time needed to get from City $1$ to City $4$ is $3$ hours, which is achieved by one path: $1 \\to 3 \\to 2 \\to 4$."],["2 0","0\n\nIt is impossible to get from City $1$ to City $2$, in which case you should print $0$."],["7 8\n1 3\n1 4\n2 3\n2 4\n2 5\n2 6\n5 7\n6 7","4"]],"created_at":"2026-03-03 11:01:14"}}