Starting from the empty slot, consider blocks numbered \(0\) through \(N\). Block \(i\) contains \(S_i\) S-chips and \(C_i\) C-chips, and these chips can be connected to chips in blocks \(i-1\), \(i\), and \(i+1\).

We define \(d[i][s]\) as [the number of ways to connect all chips in blocks numbered \(i\) or lower using chips from blocks numbered \(i\) or lower, while leaving \(s\) S-chips in block \(i\)]. If we know the number of remaining S-chips, we can easily determine the number of remaining C-chips.

The transition from \(d[i-1][s']\) to \(d[i][s]\) can be defined as the number of ways to connect all the chips remaining in block \(i-1\) to the chips in block \(i\), and then continue connecting the chips in block \(i\) to each other until there are \(s\) S-chips remaining. If we precompute factorials and their inverses, this value can be computed in \({\cal O}(1)\).

Valid values for \(s\) in \(d[i][s]\) are those less than or equal to \(S_i+1\) in block \(i\). Therefore, the total number of states is \({\cal O}(N+M)\). Since each state can only transition to states in the next block, calculating all transitions from a single state takes \({\cal O}(M)\) operations. The problem can be solved in total time complexity of \({\cal O}(M(N+M))\).

Using atcoder/convolution, we can also process the propagation from all states in block \(i-1\) to all states in block \(i\) in \({\cal O}((S_{i-1}+S_i) \lg (N+M))\). Therefore, the problem can also be solved in \({\cal O}((N+M) \lg (N+M)),\) but this is not required.