We do DP (Dynamic Programming) for \(\mathrm{DP}[i]=\) the expected value of the number of times the die is rolled to reach from Sqaure \(i\) to Square \(N\).

First, \(\mathrm{DP}[N]=0\).

Now we find \(\mathrm{DP}[i]\) for each \(i=N-1,N-2,\dots,1\).

If the die shows only a number between \(1\) and \(A_i\) with equal probability, then \(\mathrm{DP}[i]=\frac{\sum_{j=1}^{A_i} \mathrm{DP}[j]}{A_i} + 1\).

Considering this fact, we can see that \(\mathrm{DP}[i]=\frac{\sum_{j=1}^{A_i} \mathrm{DP}[j]}{A_i} + X + 1\), where \(X\) is the expected value of having \(0\) on a die when you are on Square \(i\).

Now we consider \(X\). It holds that \(X=\sum_{j=0}^{\infty} j \times \frac{A_i}{(A_i+1)^{j+1}}\).

Since \(\sum_{i=0}^{\infty} \frac{i}{x^i}=\frac{x}{(1-x)^2}\), it holds that \(\sum_{j=0}^{\infty} \frac{j}{(A_i+1)^j} = \frac{A_i+1}{A_i^2}\).

\(X=\left(\sum_{j=0}^{\infty} \frac{j}{(A_i+1)^j}\right) \times \frac{A_i}{A_i+1}\), so we have \(X=\frac{A_i+1}{A_i^2} \times \frac{A_i}{A_i+1} = \frac{1}{A_i}\).

Therefore, the problem can be solved in a total of about \(\mathrm{O}(N\log \bmod)\) time with cumulative sums or a Segment Tree.