class Solution:
    def numWays(self, steps: int, n: int) -> int:
        MOD = 10**9 + 7
        n = min(n, steps+1)
        dp = [[0 for i in range(n)] for i in range(steps+1)]
        dp[0][0] = 1
        for i in range(1,steps+1):
            for j in range(min(i+1,n)):
                dp[i][j] = ((dp[i-1][j-1] if j > 0 else 0) + (dp[i-1][j+1] if (j < i and j < n-1) else 0) + dp[i-1][j])%MOD
        return dp[steps][0]