D - Poor Sense of Direction

解説

$\mathrm{dp}[i][j]$ を、 $i$ 分時点で街 $j$ にいる確率と定義した動的計画法で解くことが出来ます。

遷移時に $k$ の逆元 $(1 \leq k \leq N)$ を求める必要がありますが、 低速な言語だと毎回計算していると間に合わないため、前計算をしておく必要があります。

前計算を行った場合、動的計画法の状態数が $O(NT)$、遷移回数の合計は $O(MT)$ ですので、計算量は $O((N+M)T + N\log \mathrm{mod})$ や $O((N+M)T)$ で求めることができます。
(ここで $\mathrm{mod} = 998244353$ とします。)

想定解