题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒每一步只能向下或向右走。

棋盘上还有一匹对方的马。马所在的位置以及它按中国象棋规则一步能跳到的位置，称为马的控制点。卒不能经过任何马的控制点。

用坐标表示棋盘，$A$ 点为 $(0,0)$，$B$ 点为 $(n,m)$，马的位置为 $(x,y)$。已知马不在起点和终点。请计算卒从 $A$ 点走到 $B$ 点的不同路径条数。

输入格式

输入一行四个整数 $n,m,x,y$，分别表示终点 $B(n,m)$ 和马的位置 $(x,y)$。

输出格式

输出一个整数，表示卒从 $A$ 点到达 $B$ 点的路径条数。

8 6 0 4

1617

数据范围与提示

• $0 \le n,m \le 20$
• $0 \le x \le n$，$0 \le y \le m$
• 马的位置不等于 $A$ 点或 $B$ 点

可以用动态规划。设 $f_{i,j}$ 为到达 $(i,j)$ 的路径数，若 $(i,j)$ 不是控制点，则 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。样例中共有 $1617$ 条合法路径。