For each coin, we can uniquely associate one card (with a positive value written on it). Considering the movement, it takes the form of:

\(0 \to\) negative jumps \(\to\) jump with the card associated with the coin \(\to\) positive jumps \(\to 0\).

The “negative jumps” and “positive jumps” may be empty.

Let’s decide to get a total of \(k\) coins. We also decide on the set of corresponding cards and their order. For each card \(i\), we make a move \(x_i \to x_i+A_i\), and we also decide on this \(x_i\). There are \(A_i+1\) variations for \(x_i\), but it turns out that the answer in the subsequent counting does not change no matter which one is chosen.

Here, first of all, we see that the sequence \(-1,\cdots,-1,A_i,-1,\cdots,-1\) (there are \(|x_i|\) \(-1\)s before \(A_i\) and \((A_i-|x_i|)\) \(-1\)s after) is always necessary as a subsequence. We create a sequence of operations by connecting \(k\) of these sequences as a framework and appropriately inserting the remaining cards.

Let \(T\) be the sum of the values of the \(k\) cards corresponding to the coins, and we can calculate the number of ways to insert the cards not used in the framework from just \(T\) and \(k\). Intuitively, consider inserting appropriate patterns into the framework. A pattern is a sequence of operations that always moves in the non-negative region and has a sum of \(0\). It seems that we also need a sequence of operations that moves in the non-positive region instead of the non-negative, but this corresponds one-to-one with the reverse of the sequence, so we can consider them identical.

If we arrange in a circle the \(S-k\) cards that do not correspond to the coins, they can be uniquely decomposed into \(T\) \(-1\)s and \(T\) patterns. Inserting these patterns directly into the framework yields the final sequence of operations. As it is, we would count cyclic arrangements of patterns, but we can simply multiply the count by \(T\) to turn this into the number of sequences.

If we implement the above algorithm straightforwardly, we can obtain an \(O(N^2)\) solution.

Sample Implementation