For the sequence \(A\), let us define a sequence \(B=(b_1,\ldots,b_N)\) as follows:

• \(b_1 = a_1\),
• \(b_i = a_i - a_{i-1} ( i \geq 2)\).

Here, the conditions of \(A\) correspond to those of \(B\) as:

• \(0 \leq b_i\)
• each of \(b_2,b_3,\ldots\), and \(b_N\) is congruent to \(1\) or \(2\) modulo \(3\)
• \(\sum b_i \leq M\)

Since \(A\) and \(B\) corresponds one-to-one, it is sufficient to count the number of \(B\) satisfying the conditions.

Let \(x_i\) be the remainder of \(b_i\) by \(3\), and \(y_i\) be \(\lfloor \frac {b_i}{3} \rfloor\). When we fix \(x_1,x_2,\ldots\), and \(x_N\), the number of corresponding \(y_1,\ldots,y_N\) is equal to the number of sequences of non-negative integers \(y_1,\ldots,y_N\) such that \(\sum y_i \leq \lfloor \frac{M-\sum x_i} {3} \rfloor\). We can find the count in an \(\mathrm {O} (1)\) time as follows:

• The number of sequences of non-negative sequences \(y_1,\ldots,y_N\) such that \(\sum y_i = t\) is equal to \(_{N+t-1} C _{N-1}\). We precalculate them for \(t=0,1,\ldots\) and their cumulative sums so that we can find the count for \(\sum y_i \leq t\) fast enough.
• By the way, the count is equal to \(_{N+t} C _{N}\).
  • Consider Snuke with \(t\) indistinguishable balls. The sought count is equal to the number of ways to receive between \(0\) and \(t\) balls from Snuke and put them in \(N\) distinguishable boxes. Regarding Snuke as a box, we can see that it is equal to \(_{N+t}C_{N}\).
  • Alternatively, we can consider it as a number of paths. (See also https://atcoder.jp/contests/abc154/tasks/abc154_f)

Regarding \(x_1,\ldots,x_N\), since each of \(x_2,x_3,\ldots,x_N\) is either \(1\) or \(2\), and since the number of ways to determine \(y_1,\ldots,y_N\) is only dependent on \(\sum x_i\), it is sufficient to consider the value of \(x_1\) and the number of \(1\)’s in \(x_2,\ldots,x_N\), so the problem can be solved in a total of \(\mathrm{O}(N)\) time.