class Solution {
public:
    const int m = 1e9+7;
    using vvi = vector<vector<int>>;
    int countWays(int idx, int steps, int arrLen,vvi& dp){
        if(idx < 0 || idx >= arrLen)    return 0;
        if(steps == 0)
            if(idx != 0)  return 0;
            else return 1;
        if(dp[idx][steps] != -1)
            return dp[idx][steps];
        return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m;
    }
    int numWays(int steps, int arrLen) {
        vvi dp;
        arrLen = min(steps/2+1,arrLen);
        dp.resize(arrLen + 1,vector<int>(steps+1, -1));
        return countWays(0, steps, arrLen,dp);
    }
};