Configurations

In this problem, you are given a grid of size R \!\times\! C (1 \leq R \leq 10^9 and 1 \leq C \leq 10). There are $B$ blocks (0 \leq B \leq 100) placed in the grid. Each block occupies a cell, and a cell may contain more than one block.

You are also given $M$ identical tokens. You can place these tokens in the first row in any way you like. No cell can contain more than one token, and you cannot place a token in a cell already occupied by blocks. After placement, you may move the tokens according to the following rules:

1. If a token is at cell $(r,c)$, it can be moved to (r{+}1, c{-}1) or (r{+}1, c{+}1).

2. A token cannot be moved into a cell occupied by blocks.

3. A token cannot be moved outside the grid.

4. No two or more tokens can be moved into the same cell.

5. All tokens must be moved to the $i$-th row before any token can be moved to the $(i+1)$-th row.

Let S = \{(1, c_1), (1, c_2), \ldots, (1, c_M)\} be the set of cells where you placed the $M$ tokens. Let $W(S)$ be the number of ways to move these tokens to the last row, following the rules above. Find the sum of $W(S)$ over all possible $S$.

For R = 2, C = 2, M = 1 and B = 0, the answer is 2.