// /**
//  * @param {number} steps
//  * @param {number} arrLen
//  * @return {number}
//  */
//  var numWays = function(steps, arrLen) {
//     function fact(x){
//         if(x===0) return 1;
//         let ret=1;
//         for(let i=1;i<=x;i++){
//             ret*=i;
//         }
//         return ret;
//     }
//     let r=1;
//     let temp=1;
//     let mid=1;
//     let edge=Math.min(arrLen,Math.floor(steps/2));
//     for(let j=1;j<=edge;j++){
//         console.log(j,r);
//         if(j*2==steps){
//             r+=1;
//         }
//         else{
//             mid*=j;
//             temp*=(steps-2*j+2);
//             temp*=(steps-2*j+1);
//             r+=temp/(mid*mid*2);
//         }
//         if(r > 1000000007){
//             r=r%1000000007;
//         }
//     }
//     return r;
// };

// console.log(numWays(500,250))

//排列组合解不出来

var numWays = function(steps, arrLen) {
    let edge=Math.min(Math.floor(steps/2)+1,arrLen);
    let dp=new Array(edge).fill(0);
    dp[0]=1;
    dp[1]=1;
    let top=100000007;
    for(let i=1;i<steps;i++){
        let n=new Array(edge).fill(0);
        n[0]=(dp[0]+dp[1])%top;
        n[edge-1]=(dp[edge-1]+dp[edge-2])%top;
        for(let j=1;j<edge-1;j++){
            n[j]=(dp[j]+dp[j-1]+dp[j+1])%top;
            if(dp[j-1]==0) break;
        }
        dp=n;
    }
    return dp[0];
};

console.log(numWays(24,7))

// 执行用时：
// 112 ms
// , 在所有 JavaScript 提交中击败了
// 66.67%
// 的用户
// 内存消耗：
// 41.7 MB
// , 在所有 JavaScript 提交中击败了
// 100.00%
// 的用户