Конфігурації

У цій задачі вам дано сітку розміру R \!\times\! C (1 \leq R \leq 10^9 і 1 \leq C \leq 10). У сітці розміщено $B$ блоків (0 \leq B \leq 100). Кожен блок займає одну клітинку, причому в одній клітинці може бути кілька блоків.

Вам також дано $M$ однакових фішок. Ви можете розмістити ці фішки у першому рядку довільним чином. Жодна клітинка не може містити більше однієї фішки, і ви не можете розмістити фішку в клітинці, яка вже зайнята блоками. Після розміщення фішок ви можете їх переміщувати згідно з такими правилами:

1. Якщо фішка знаходиться у клітинці $(r,c)$, її можна перемістити до (r{+}1, c{-}1) або (r{+}1, c{+}1).

2. Фішку не можна перемістити в клітинку, зайняту блоком.

3. Фішку не можна перемістити за межі сітки.

4. Дві або більше фішок не можуть бути переміщені в одну і ту ж клітинку.

5. Всі фішки мають бути переміщені в $i$-й рядок перед тим, як хоча б одна фішка зможе перейти у $(i+1)$-й рядок.

Нехай S = \{(1, c_1), (1, c_2), \ldots, (1, c_M)\} — це множина клітинок, у які ви розмістили $M$ фішок. Позначимо через $W(S)$ кількість способів перемістити ці фішки до останнього рядка, дотримуючись наведених вище правил. Знайдіть суму $W(S)$ для всіх можливих $S$.

Для R = 2, C = 2, M = 1 та B = 0 відповідь — 2.