Let \(m\) be the index \(i\) with the smallest \(A_i\) (if there are multiple such indices, choose the minimum one).

Assume \(m\) is fixed. Here, the possible sequences \(A_i\) are limited to the ones that can be obtained by the following procedure:

• Choose a constant \(C\), initialize \(A=(C,C,\cdots,C)\), then repeat the two operations below.
• Choose \(i < m\), and add \(1,2,3,\cdots\) to \(A_i,A_{i-1},\cdots,A_1\), respectively. (We need to do this operation with \(i=m-1\) at least once.)
• Choose \(i > m\), and add \(1,2,3,\cdots\) to \(A_i,A_{i+1},\cdots,A_N\), respectively.

Then, the problem boils down to the following: having items with weights \(N,1,3,6,\cdots\), how many ways are there to combine them so that the sum will be \(M\)? Since we only need to consider \(O(\sqrt{M})\) kinds of items, we can solve it in \(O(M\sqrt{M})\) time.

Now, let us unfix \(m\) and change it in this way: \(m=1,2,\cdots\). After each change of \(m\), we will do the DP above. It takes too much time to compute from scratch every time. However, by focusing on the differences in the available items, we can redo the DP in \(O(M)\) time.

Since we only need to consider the first \(O(\sqrt{M})\) values for \(m\), the computation will take \(O(M\sqrt{M})\) time in total.