A simple solution is to count the number of walks from $0$ to $n-1$ of each length from $0$ to some bound $B$. We can do this with basic dp: Let $dp(u, d)$ be the number of walks from node $0$ to node $u$ of length $d$. With this dp calculated, we can find the sum quickly.

Observation 1: $dp(u, d+2) ≥ 2 \cdot dp(u, d)$ for $u ≠ 0$

Proof: It's enough to show that for some walk of length $d$, we can construct from it $2$ unique walks of length $d + 2$. This can be done by backtracking the first step, and backtracking the last step. The only way for this to generate $2$ equal walks is if $0$ is directly connected only with $u$ and vice versa. However this contradicts the assumptions that $n ≥ 3$ and that the graph is connected.

Observation 2: It's enough to set $B = n + 60$

Proof: Let $d$ be the shortest walk from $0$ to $n-1$. Note that this means $dp(n-1, d) ≥ 1$. Using observation 1, $dp(n-1, d+2) ≥ 2$, $dp(n-1, d+4) ≥ 4$, $dp(n-1, d+6) ≥ 8$, etc. In general $dp(n-1, d + 2 \cdot x) ≥ 2^x$. Since $dp(n-1, d + 60) ≥ 2^{30}$, and $k ≤ 10^9 ≤ 2^{30}$, this means that it's enough to consider walks of length $d + 60$ or less. Of course $d ≤ n$, therefore $d + 60 ≤ n + 60$.

This gives a simple $O(n \cdot m)$ solution. If we observe that it's enough to calculate $dp(u, d)$ for $dist(0, u) ≤ d ≤ dist(0, u) + 60$, we get a $O(60 \cdot m)$ solution.