$O(N^2)$ DP

动态规划（DP）：

定义 $dp[i][j]$ 表示走了 $i$ 步后到达位置 $j$ 的方法数。

初始状态：$dp[0][M] = 1$（ $0$ 步时位于初始位置 $M$ ）。

状态转移：

如果当前位置 $j$ 是 $1$ （左边界），下一步只能走到 $2$ ： $dp[i+1][2] += dp[i][1]$

如果当前位置 $j$ 是 $N$ （右边界），下一步只能走到 $N-1$ ： $dp[i+1][N-1] += dp[i][N]$

对于中间位置 $j$ ，下一步可以走到 $j-1$ 或 $j+1$ ：$dp[i+1][j-1] += dp[i][j]，dp[i+1][j+1] += dp[i][j]$

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, m, k, p;
long long dp[1010][1010];
int main() {
	cin >> n >> m >> k >> p;
	dp[0][m] = 1;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
		}
	}
	cout << dp[k][p];
	return 0;
}