ac（动态规划 + 空间压缩）

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static int mod = (int)1e9+7;

    /**
     * 5000 4548 5000 1600
     * 602611261
     * @param args
     */
    public static void main(String[] args) {

        int n = sc.nextInt(); // 1-n位置
        int m = sc.nextInt(); // 初始位置
        int k = sc.nextInt(); // 只能走k步
        int p = sc.nextInt(); // 结束位置

        // 走i步走到j位置 dp[i][j]
        int[] dp = new int[n+1];
        // 走0步走到m位置
        for(int i=1;i<=n;i++){
            dp[i] = 0;
        }
        dp[m] = 1;
        int[] dpTmp = new int[n+1];
        // 机器人只能左右走一步而已
        for(int i=1;i<=k;i++) {
            for(int j=1;j<=n;j++){
                if(j == 1){
                    // 只能右边扩展
                    dpTmp[j] = dp[j+1] % mod;
                }else if(j == n){
                    // 只能左边扩展
                    dpTmp[j] = dp[j-1] % mod;
                }else {
                    // 左右两边扩展
                    dpTmp[j] = (dp[j - 1] + dp[j + 1]) % mod;
                }
            }
            for(int j=1;j<=n;j++){
                dp[j] = dpTmp[j];
            }
        }
        System.out.println(dp[p]);
    }

}

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static int mod = (int)1e9+7;

    public static void main(String[] args) {

        int n = sc.nextInt(); // 1-n位置
        int m = sc.nextInt(); // 初始位置
        int k = sc.nextInt(); // 只能走k步
        int p = sc.nextInt(); // 结束位置

        // 走i步走到j位置 dp[i][j]
        int[][] dp = new int[k+1][n+1];
        // 走0步走到m位置
        dp[0][m] = 1;

        // 机器人只能左右走一步而已
        for(int i=1;i<=k;i++) {
            for(int j=1;j<=n;j++){
                if(j == 1){
                    // 只能右边扩展
                    dp[i][j] = dp[i-1][j+1] % mod;
                }else if(j == n){
                    // 只能左边扩展
                    dp[i][j] = dp[i-1][j-1] % mod;
                }else {
                    // 左右两边扩展
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
                }
           }
        }
        System.out.println(dp[k][p]);
    }

}