\(P_i\)=マス\(i\)に到達する確率 とすると求める答えは\(\sum_{i=1}^{n-1} \frac{A_i+1}{A_i}P_i\)です。\(P_i\)はimos法を用いた配るdpで前から求めることができます。

実装例 を参考にしてください。