一维dp, 时间：O(n*k), 空间O(n)，根据题意写出dp转移状态即可

一维dp, 时间：O(n*k), 空间O(n)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false);

template <typename T>
inline void read(T &x) {
    char ch = getchar();
    int f = 1; x = 0;
    while (!isdigit(ch)) {if (ch == '-')f *= -1; ch = getchar();}
    while (isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch = getchar();}
    x *= f;
}

ll qpow(ll x, ll y) {
    ll a = 1, b = x;
    while(y) {if(y&0x1) a*=b; b*=b; y>>=1;}
    return a;
}

int main(void)
{
#ifdef LOCAL
    ifstream cin("in.txt");
#endif
    const int MOD = 1e9 + 7;
    int n, m, k, p;
    cin >> n >> m >> k >> p;
    vector<int> dp(n+1, 0), ans(n+1, 0);
    // 首先初始化第一步的状态
    if(m == 1) ans[2] = 1;
    else if(m == n) ans[n-1] = 1;
    else ans[m-1] = ans[m+1] = 1;
    // 从第二步开始计算
    for(int cnt = 2; cnt <= k; cnt++) {
        dp = ans; // 保存上一步的状态，防止数据错乱
        for(int i = 1; i <= n; i++) {
            if(i == 1) {
                if(dp[i+1] == 0) ans[i] = 0; // 表示这一步不能到达
                else ans[i] += dp[i+1];
            } else if(i == n) {
                if(dp[i-1] == 0) ans[i] = 0; // 表示这一步不能到达
                else ans[i] += dp[i-1];
            } else {
                if(dp[i-1] == 0 && dp[i+1] == 0) ans[i] = 0; // 表示这一步不能到达
                else ans[i] += (dp[i-1] + dp[i+1]);
            }
            ans[i] = (ans[i] >= MOD) ? ans[i] - MOD : ans[i]; 
        }
    }
    cout << ans[p] << endl;
    return 0;
}