U465958 走格子

> 由于出题人太弱了，所以没有题目背景。

小 W 在走格子。 这是一张 $n$ 行 $m$ 列的网格。可爱的小 W 发现这样一件事情：初始时数字 $S = 0$，当他走偶数步（初始是 $0$ 步）落在格子 $(x, y)$ 上时，会使得 $S \gets S + a_{x, y}$，如果是走奇数步到 $(x, y)$，会使得 $S \gets S - a_{x, y}$。问，从 $(1, 1)$ 走到 $(n, m)$，有多少种方案，使得最后 $S = w$？只能向右或向下走。

无

无

$1 \le n, m \le 20$，$1 \le w \le 10, 1 \le a_{i, j} \le 16000$。