This problem can be solved in a total of \(O(NM)\) time with a Dynamic Programming (DP) where \(dp[i][j] =\) number of paths to \((i,j)\) with the following initial values and transitions:

• \(dp[1][j] =(\)the number of integers \(j\) with \(A_k = j)(1 \le j \le M)\)
• \(dp[i][j] = dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1](2 \le i \le N,1 \le j \le M)\)

Here, \(dp[i][0] = dp[i][M+1] = 0\). However, this solution does not finish in the execution time limit. So we use a technique called “method of mirror images.” Extend the range of \(j\) in the DP from \(1 \le j \le M\) to \(0 \le j \le 2M+1\), with the following transitions:

• \(dp[1][j] =(\)the number of integers \(j\) with \(A_k = j)(1 \le j \le M)\)
• \(dp[1][2M+2-j] =(-1) \times (\)the number of integers \(j\) with \(A_k = j)(1 \le j \le M)\)
• \(dp[1][0] = dp[1][N+1] = 0\)
• \(dp[i][j] = dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1](2 \le i \le N,0 \le j \le 2M+1)\)

For example, in Sample 2, we have the following transitions:

   0   2   0   1   1   0   0   0   0   0   0   0   0   0  -1  -1   0  -2
   0   2   3   2   2   1   0   0   0   0   0   0   0  -1  -2  -2  -3  -2
   0   5   7   7   5   3   1   0   0   0   0   0  -1  -3  -5  -7  -7  -5
   0  12  19  19  15   9   4   1   0   0   0  -1  -4  -9 -15 -19 -19 -12
   0  31  50  53  43  28  14   5   1   0  -1  -5 -14 -28 -43 -53 -50 -31

Intuitively, moves to \(dp[i][0]\) and \(dp[i][M+1]\), which are prohibited, are canceled out thanks to \(+\) and \(-\).

By extending the indices like this, the transitions can be represented with polynomials; that is, the polynomials \(f_i(x) = \sum_{j=0}^{2M+1} dp[i][j] x^j\) have the relations \(f_i(x) = f_{i-1}(x) \times (x^{-1} + 1 + x)\), where the exponent of \(x\) is considered modulo \((2M+2)\). (Since this is equivalent to regarding \(x^{2M+2} = 1\), we can say that we consider modulo \((x^{2M+2} - 1)\).) The former DP is hard to represent as polynomials, since \(dp[i][0]\) and \(dp[i][M+1]\) are undefined.

Therefore, it is sufficient to find \(f_N(x) = f_1(x) \times (x^{-1} + 1 + x)^{N-1} \bmod (x^{2M+2}-1)\). With the fast exponentiation, we can find the coefficients of \(f_N(x)\) in an \(\mathrm{O}(M\log M \log N)\) time. The answer to this problem is obtained as the sum of coefficients of \(x^{B_i}\) in \(f_N(x)\) over \(1 \le i \le L\). The complexity is \(\mathrm{O}(M\log M \log N)\).