You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place  (The pointer should not be placed outside the array at any time).
Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:
Input: steps = 4, arrLen = 2
Output: 8

 
Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

Difficulty: interview

Starter code:

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        

Solutions:
# https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/569521/7-python-approaches-with-Time-and-Space-analysis
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        r = min(arrLen, steps // 2 + 1)
        dp = [0, 1]
        for t in range(steps):
            dp[1:] = [sum(dp[i-1:i+2]) for i in range(1, min(r+1, t+3))]
        return dp[1] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        waysDict = {}
        return self.numWaysRec(steps, arrLen, 0, waysDict)%(10**9 + 7)
    
    def numWaysRec(self, steps: int, arrLen: int, currentPos: int, waysDict: dict) -> int:
        if (steps == currentPos) or (steps == 1 and currentPos == 0):
            return 1
        totalWays = 0
        for nextMove in self.validMoves(steps,currentPos,arrLen):
            if (nextMove,steps-1) in waysDict:
                totalWays += waysDict[(nextMove, steps-1)]
            else:
                result = self.numWaysRec(steps-1,arrLen,nextMove, waysDict)
                waysDict[(nextMove,steps-1)] = result
                totalWays += result
        return totalWays
            
    #def checkTerminal(self, steps, currentPos)
    
    '''def validPath(self, steps: int, currentPos: int) -> bool:
        return currentPos <= steps'''
    
    def updateDict(self, steps: int, currentPos: int) -> None:
        pass
    
    def validMoves(self, steps: int, currentPos: int, arrLen: int) -> list:
        validList = []
        #Check left move
        if (currentPos - 1 <= steps-1) and currentPos - 1 >= 0:
            validList.append(currentPos-1)
        #Check stay move
        if (currentPos <= steps-1):
            validList.append(currentPos)
        #Check right move
        if (currentPos+1 <= steps-1) and currentPos +1 < arrLen:
            validList.append(currentPos+1)
        
        return validList
    
    
    
    
    def numWaysTree(self, steps: int, arrLen: int) -> int:
        pass
    
    def numWaysTreeRec(self, steps: int, arrLen: int, counter: list, currentPos: int) -> None:
        if (steps == 1 and currentPos  == 0) or (steps == currentPos):
            counter[0] += 1

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if steps is None or steps < 0 or not arrLen: return 0
        arrLen = min(arrLen, steps + 1)
        memo = [[0] * arrLen for _ in range(steps + 1)]
        memo[0][0] = 1
        for i in range(1, steps + 1):
            for j in range(arrLen):
                memo[i][j] += memo[i - 1][j]
                if j > 0: memo[i][j] += memo[i - 1][j - 1]
                if j < arrLen - 1: memo[i][j] += memo[i - 1][j + 1]
        return memo[steps][0] % (10 ** 9 + 7)


from functools import lru_cache

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        moves = [-1, 0, 1]
        
        @lru_cache(maxsize=2048)
        def count(s, position=0):
            if position < 0 or position >= arrLen:
                return 0
            if s == 0:
                return 1 if position == 0 else 0
            number_of_moves = 0
            for delta in moves:
                new_position = position + delta
                number_of_moves += count(s-1, new_position)
            return number_of_moves
        
        return count(steps) % (10**9 + 7)

class Solution:
    
    def count_paths(self, i, s, n, memo):
        
        if i < 0 or i > min(n -1, s):
            
            return 0
        
        if s == 0 and i == 0:
            
            return 1
        
        if (s, i) in memo:
            
            return memo[(s, i)]
        
        else:
            
            memo[(s, i)] = self.count_paths(i - 1, s - 1, n, memo) + self.count_paths(i, s - 1, n, memo) + self.count_paths(i + 1, s - 1, n, memo)
        
        return memo[(s, i)]
    
    def numWays(self, steps: int, arrLen: int) -> int:
        
        memo = {}
        
        return self.count_paths(0, steps, arrLen, memo) % (10 ** 9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        n=min(arrLen,steps)
        m= (10**9) + 7
        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(n):
                if(j-1<0):
                    dp[i][j]=(dp[i-1][j]+dp[i-1][j+1] ) % m
                elif(j+1>=n):
                    dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%m
                else:
                    dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1]) % m
        return dp[steps][0]
                    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(arrLen, steps)
        r = [[0] * arrLen for _ in range(steps)]

        r[0][0] = 1
        r[0][1] = 1
        mod = 10**9 + 7
        for t in range(steps):
            for i in range(arrLen):
                r[t][i] += r[t-1][i] + (r[t-1][i-1] if i > 0 else 0) + (r[t-1][i+1] if i < arrLen -1 else 0)
#                 if i > 0:
#                     r[t][i] += r[t-1][i-1]
                    
#                 if i < arrLen - 1:
#                     r[t][i] += r[t-1][i+1]
                    
                r[t][i] = r[t][i] % mod
        # print(r)
        return r[t][0] 

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        kmod = pow(10, 9) + 7
        arrLen = min(steps, arrLen)
        dp = [[0] * arrLen for _ in range(steps + 1)]
        dp[0][0] = 1
        dirs = [0, -1, 1]
        
        for s in range(steps):
            for i in range(arrLen):
                if dp[s][i]:
                    for d in dirs:
                        j = i + d
                        if j < 0 or j >= arrLen:
                            continue
                        dp[s + 1][j] += dp[s][i]
            for i in range(arrLen):
                dp[s + 1][i] %= kmod
                
        return dp[steps][0]

                        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = {}
        for i in range(steps+1):
            dp[i] = defaultdict(int) 
        
        # dp[i][j] stores the number of ways to reach index j using i steps
        dp[1][1] += 1 # move right
        dp[1][0] += 1 # stay
        # cannot move left at this moment, as index j must satisfy 0 <= sums < arrLen 
        
        for i in range(2, steps+1):
            # index is where we are after the first i-1 steps
            for index in dp[i-1].keys():
                if index + 1 < arrLen: # move right  
                    dp[i][index + 1] += dp[i-1][index]
                
                if index - 1 >= 0: # move left
                    dp[i][index - 1] += dp[i-1][index]
                
                dp[i][index] += dp[i-1][index] # stay
                
        return dp[steps][0]   % (10 ** 9 + 7) 

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        right_most=min(steps+1//2,arrLen)
        dp=[[0 for __ in range(right_most)] for _ in range(steps)]
        for i in range(steps):
            if i==0:
                dp[0][0]=1
                dp[0][1]=1
            else:
                for j in range(right_most):
                    dp[i][j]=dp[i-1][j]
                    if j>0:
                        dp[i][j]+=dp[i-1][j-1]
                    if j<right_most-1:
                        dp[i][j]+=dp[i-1][j+1]
        return dp[-1][0]%(10**9+7)

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


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if steps is None or steps < 0 or not arrLen: return 0
        arrLen = min(arrLen, steps + 1)
        f = [[0] * arrLen for _ in range(steps + 1)]
        f[0][0] = 1
        for i in range(1, steps + 1):
            for j in range(arrLen):
                f[i][j] += f[i - 1][j]
                if j > 0:
                    f[i][j] += f[i - 1][j - 1]
                if j < arrLen - 1:
                    f[i][j] += f[i - 1][j + 1]
        return f[steps][0] % (10 ** 9 + 7)


from functools import lru_cache

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7
        # num_ways(0, 0, 0) = 1
        @lru_cache(maxsize=steps*arrLen) 
        def num_ways(current, target, steps):
            if not 0 <= target < arrLen:
                return 0
            if steps == 0:
                return 1 if current == target else 0
            elif steps == 1:
                return 1 if abs(current - target) <= 1 else 0 
            return (num_ways(current, target, steps - 1) + num_ways(current, target - 1, steps - 1) + num_ways(current, target +1, steps - 1)) % MOD 
        
        return num_ways(0, 0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        n = min(steps, arrLen)
        dp = [0] * n
        dp[0] = 1
        for step in range(1, steps+1):
            tmp_dp = [0] * n
            for idx in range(n):
                tmp_dp[idx] = sum(dp[max(0, idx-1):min(idx+1, n)+1])
            dp = tmp_dp
        
        return dp[0] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        self.memo = {}
        def dfs(steps, pos):
            if pos < 0 or pos >= arrLen or pos>steps:
                return 0
            
            if steps == 0:
                if pos == 0:
                    return 1
                return 0
            
            if self.memo.get((steps, pos), None) is not None:
                return self.memo.get((steps, pos))
            
            ret = dfs(steps-1, pos-1)
            ret = ret % (10**9+7)
            ret += dfs(steps-1, pos)
            ret = ret % (10**9+7)
            ret += dfs(steps-1, pos+1)
            ret = ret % (10**9+7)
            
            self.memo.update({(steps, pos): ret})
            
            return ret
        
        return dfs(steps, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        dp = [[0] * min(steps+1, arrLen) for _ in range(steps+1)]
        dp[0][0] = 1
        m, n = len(dp), len(dp[0])
        
        for step in range(1, steps+1):
            for pos in range(n):
                dp[step][pos] += dp[step-1][pos]
                if pos - 1 >=0:
                    dp[step][pos] += dp[step-1][pos-1]
                if pos + 1 < n:
                    dp[step][pos] += dp[step-1][pos+1]
                # for j in range(1, step+1):
                #     if pos - j >= 0:
                #         dp[step][pos] += dp[step-j][pos-j]
                #     if pos + j < n:
                #         dp[step][pos] += dp[step-j][pos+j]
            # print(\"step\", step)
            # print(dp[step])
        return dp[-1][0] %(10**9+7)


class Solution:
    # 2D DP, where ways[k][i] indicates the number of ways to stay at i after k steps.
    def numWays(self, steps: int, arrLen: int) -> int:
        ways = [[0] * min(251, arrLen) for _ in range(steps + 1)]
        ways[0][0] = 1  # start at index 0
        for k in range(1, steps + 1):
            for i in range(len(ways[k])):
                for offset in [-1, 0, 1]:
                    # move into pos i from left or right
                    if 0 <= i + offset < len(ways[k]):  
                        ways[k][i] += ways[k - 1][i + offset]
                ways[k][i] %= 10**9 + 7
        return ways[-1][0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        M = (10**9) + 7
        @lru_cache(None)
        def help(s,i):
            if s==1: return 1 if i<=min(1,arrLen-1) else 0
            out = help(s-1,i)
            if i > 0: out += help(s-1,i-1) 
            if i < arrLen-1: out += help(s-1,i+1) 
            return out % M
        return help(steps,0)

import math

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        self.cache = {}
        self.array_length = arrLen-1
        
        return self._numWays(0, steps) % (10**9 + 7)
        
    def _numWays(self, position, steps):
        
        # print(position, steps)
        
        if position > steps:
            return 0
        
        if (position, steps) in self.cache:
            return self.cache[(position, steps)]
        
        if steps == 1:
            if position in (-1, 0, 1):
                return 1
            else:
                return 0
        options = 0
        if position > 0:
            options += self._numWays(position-1, steps-1)
        if position < self.array_length:
            options += self._numWays(position+1, steps-1)
        options += self._numWays(position, steps-1)
        
        self.cache[(position, steps)] = options
        
        return options
        
        
#         max_possible = max(steps // 2, arrLen)
        
#         total = 0
#         for i in range(max_possible):
#             # i moves to the right, i moves to the left
#             # 


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


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(arrLen, steps + 1)
        dp = [[0] * (arrLen) for _ in range(steps)]
        dp[0][0] = 1
        dp[0][1] = 1
        m = 10**9+7
        for i in range(1, len(dp)):
            for j in range(len(dp[0])):
                #print([i,j])
                if j == 0:
                    dp[i][j] = (dp[i-1][j] + dp[i-1][j+1])% (m)
                    #print(dp[i][j])
                elif j == len(dp[0]) - 1:
                    dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])% (m)
                else:
                    dp[i][j] = (dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1])% (m)
        #print(dp)
        return dp[-1][0]


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        maxPos = min(steps, arrLen)
        mod = 10**9+7
        f = [[0]*maxPos for _ in range(steps+1)]
        f[1][0] = 1
        f[1][1] = 1
        for i in range(2,steps+1):
            for j in range(maxPos):
                f[i][j] = f[i-1][j]
                if j > 0:
                    f[i][j] = (f[i][j] + f[i-1][j-1])%mod
                if j < maxPos-1:
                    f[i][j] = (f[i][j] + f[i-1][j+1])%mod
        return f[steps][0]

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

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        self.steps = steps
        self.arrLen = arrLen
        self.memo = {}
        return self.dfs(steps, 0)
        
        
    def dfs(self, n, pos):
        if n == pos:
            return 1
        if n < pos or pos > self.arrLen - 1:
            return 0
        
        if (n, pos) in self.memo:
            return self.memo[(n, pos)]
        
        ans = 0
        
        if pos > 0:
            ans += self.dfs(n-1, pos-1)
        ans += self.dfs(n-1, pos)
        
        if pos != self.arrLen - 1:
            ans += self.dfs(n-1, pos+1)
            
        ans %= 10**9 + 7
        self.memo[(n, pos)] = ans
        
        return ans

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        @lru_cache(None)
        def dp(index, steps):
            if index < 0 or index == arrLen: # index outside arraySize
                return 0
            
            if steps == 0:
                return 1 if index == 0 else 0
            
            ans = 0
            for i in range(-1, 2, 1): # try [left, stay, right]
                ans += dp(index+i, steps - 1)
                ans %= (10**9 + 7)
            return ans
        
        return dp(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        @lru_cache(None)
        def dp(index, steps):
            if index < 0 or index == arrLen: # index outside arraySize
                return 0
            
            if steps == 0:
                return index == 0
            
            ans = 0
            for i in range(-1, 2, 1):
                ans += dp(index+i, steps - 1)
                ans %= (10**9 + 7)
            return ans
        
        return dp(0, steps)

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

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.dp = collections.defaultdict(int)
        return self.helper(0, steps, arrLen)
        
    def helper(self, cur, steps, n):
        x = (pow(10,9)+7)
        if(cur==0 and steps==0):
            return 1
        if(abs(cur)>steps or cur<0 or cur>=n):
            return 0
        if((cur,steps) in self.dp):
            return self.dp[(cur,steps)]
        
        res = self.helper(cur, steps-1,n) + self.helper(cur-1, steps-1,n) + self.helper(cur+1, steps-1,n)
        self.dp[(cur,steps)] = res %x
        return res%x
            


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        ans = 0
        
        mem = [dict() for _ in range(501)]
        
        def dfs(s, arrLen, pos):
            nonlocal ans
            if pos < 0 or pos >= arrLen:
                return 0
            
            if s == 0 and pos == 0:
                return 1
            
            if s < 0:
                return 0
            
            if pos in mem[s]:
                return mem[s][pos]
            
            s1 = dfs(s - 1, arrLen, pos)
            s2 = dfs(s - 1, arrLen, pos + 1)
            s3 = dfs(s - 1, arrLen, pos - 1)
            
            total = (s1 + s2 + s3) 
            
            if not pos in mem[s]:
                mem[s][pos] = total
            
            
            #print(s, pos, total)
            
            return total
        
        ans = dfs(steps, arrLen, 0)
        
        return ans % (10**9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        def ncr(n, r, p): 
            # initialize numerator 
            # and denominator 
            num = den = 1 
            for i in range(r): 
                num = (num * (n - i)) % p 
                den = (den * (i + 1)) % p 
            return (num * pow(den,  
                    p - 2, p)) % p
        
        ans = 0
        dp = [[0 for i in range(min(steps, arrLen))] for j in range(steps+1)]
        
        dp[1][1] = 1
        
        for k in range(2,steps+1):
            for l in range(len(dp[k])):
                f,b = l-1,l+1
                if f>=0 and f<len(dp[k]): dp[k][f]+=dp[k-1][l]
                if b>=0 and b<len(dp[k]): dp[k][b]+=dp[k-1][l]
        
        for numstay in range(0,steps+1):
            numMoves = steps - numstay
            if numMoves%2!=0: continue
            ans += (ncr(numstay+numMoves, numstay, 1000000007) * dp[numMoves][0])%1000000007
            #print(numstay,numMoves,ans) 
            ans = ans%1000000007
        #print(dp)
        return ans+1

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        # nw(s, idx): number of ways to end up at idx after s steps
        # nw(s, idx) = s * (nw(s - 1, idx) + nw(s - 1, idx - 1) + nw(s - 1, idx + 1))
        
        nw = [[0 for _ in range(min(arrLen, steps + 1))] for _ in range(steps + 1)]
        nw[0][0] = 1
        
        # arr  0 1
        #    0 1 0
        #  s 1 1 1 
        #    2 2 2
        #    3 4 4
        
        for s in range(1, steps + 1):
            for idx in range(min(arrLen, steps + 1)):
                ways = nw[s - 1][idx]
                if idx > 0:
                    ways += nw[s - 1][idx - 1]
                if idx < min(arrLen, steps + 1) - 1:
                    ways += nw[s - 1][idx + 1]
                nw[s][idx] = ways
                
        return nw[steps][0] % (10**9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
#         def numWays(self, steps: int, arrLen: int) -> int:
#             if steps == 0 or arrLen == 1:
#                 return 1

#             visited = {}
#             return self.helper(0, steps, arrLen, visited) % (10 ** 9 + 7)

#         def helper(self, pos, steps, n, visited):
#             if (pos, steps) in visited:
#                 return visited[(pos, steps)]
#             if steps == 0:
#                 if pos == 0:
#                     return 1
#                 else:
#                     return 0
#             if pos > steps:
#                 return 0
#             res = self.helper(pos, steps-1, n, visited)
#             if 0<=pos+1<n:
#                 res += self.helper(pos+1, steps-1, n, visited)
#             if 0<=pos-1<n:
#                 res += self.helper(pos-1, steps-1, n, visited) 
#             visited[(pos, steps)] = res
#             return visited[(pos, steps)]


        #
        # Solution 1: DFS + dict for recording ----- 680 ms (28.33%) / 113.1 MB (7.87%)
        # ------------------------------------------------------------------------------------------
        cases = {}
        def dfs(steps, pos):
            if (steps, pos) in cases: return cases[(steps, pos)]
            if steps == 0: return 1 if pos == 0 else 0
            if pos >= arrLen or pos < 0: return 0
            subcount = dfs(steps-1, pos+1) + dfs(steps-1, pos) + dfs(steps-1, pos-1)
            cases[(steps, pos)] = subcount
            return subcount % (10**9 + 7)
        
        return dfs(steps, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        @lru_cache(None)
        def simulate(currIdx, stepsTaken):
            nonlocal arrLen
            nonlocal steps
            if stepsTaken == steps:
                if currIdx == 0:
                    return 1
                return 0
            
            ret = 0
            
            moves = [currIdx, currIdx - 1, currIdx + 1]
            for nextIdx in moves:
                if nextIdx >= 0 and nextIdx < arrLen:
                    ret += simulate(nextIdx, stepsTaken + 1)
                    
            return ret
        
        return simulate(0, 0) % (10 ** 9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = collections.defaultdict(int)
        def dfs(index, curr):
            if curr == steps:
                if index == 0:
                    return 1
                else:
                    return 0
            key = (index, curr)
            if key in memo:
                return memo[key]
            res = 0
            if index > 0:
                res += dfs(index - 1, curr + 1)
            if index < arrLen - 1:
                res += dfs(index + 1, curr + 1)
            res += dfs(index, curr + 1)
            memo[key] = res
            return res
        
        return dfs(0, 0) % (10 ** 9 + 7)


class Solution:
    def __init__(self):
        self.mnem = {}
    def numWays(self, steps: int, arrLen: int) -> int:
        def dp(pos, steps):
            if (pos, steps) in self.mnem:
                return self.mnem[(pos, steps)]
            if steps == 0:
                return 1 if pos == 0 else 0
            if (pos < 0):
                return 0
            if (pos >= arrLen):
                return 0
            result = dp(pos + 1, steps - 1) + dp(pos - 1, steps - 1) + dp(pos, steps - 1)
            self.mnem[(pos, steps)] = result
            return result
        
        return dp(0, steps)  % (10**9 + 7)

class Solution:
    
    def __init__(self):
        self.dp = {}
        
    def numWays(self, steps: int, arrLen: int, ptr: int = 0) -> int:
        
        return self.numWays_dp(steps, min(arrLen, steps+1), ptr) % (10**9+7)
    
    def numWays_dp(self, steps: int, arrLen: int, ptr: int = 0) -> int:
        if ptr >= arrLen:
            return 0
        if ptr < 0:
            return 0
        if steps == 0:
            if ptr == 0:
                return 1
            else:
                return 0
            
        if (ptr, steps) in self.dp:
            return self.dp[(ptr, steps)]
        
        left_ways = self.numWays(steps-1, arrLen, ptr-1)
        middle_ways = self.numWays(steps-1, arrLen, ptr)
        right_ways = self.numWays(steps-1, arrLen, ptr+1)
        
        total_ways = left_ways + middle_ways + right_ways
        self.dp[(ptr, steps)] = total_ways
        
        return total_ways

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen == 1:
            return 1
        memo = {}
        return self.dfs(steps, arrLen, 0, memo)
        
        
    def dfs(self, steps, arrLen, currpos, memo):
        if (steps, currpos) in memo:
            return memo[(steps, currpos)]
        
        if currpos < 0 or currpos >= arrLen:
            return 0
        
        if steps == 0:
            if currpos == 0:
                return 1
            else:
                return 0
        
        memo[(steps, currpos)] = self.dfs(steps - 1, arrLen, currpos, memo) + self.dfs(steps - 1, arrLen, currpos + 1, memo) + self.dfs(steps - 1, arrLen, currpos - 1, memo)
        
        return memo[(steps, currpos)] %(10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        visited = dict()
        
        def move(cur_index, cur_step):
            if (cur_index, cur_step) in visited:
                return visited[(cur_index, cur_step)]
            if cur_index < 0 or cur_index >= arrLen:
                visited[(cur_index, cur_step)] = 0
                return 0
            
            if cur_step == steps:
                if cur_index == 0:
                    return 1
                return 0
            
            visited[(cur_index, cur_step)] = move(cur_index+1, cur_step+1) + move(cur_index-1, cur_step+1) + move(cur_index, cur_step+1)
            
            return visited[(cur_index, cur_step)]
        
        move(0, 0)
        
        return move(0, 0) % ((10**9)+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(arrLen, steps + 1)
        f = [[0] * arrLen for _ in range(steps + 1)]
        f[0][0] = 1
        for i in range(1, steps + 1):
            for j in range(arrLen):
                for k in [-1, 0, 1]:
                    if 0 <= j - k < arrLen:
                        f[i][j] += f[i - 1][j - k]
        return f[steps][0] % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10 ** 9 + 7
        def dp(x, s, memo):
            if s == 0:
                if x == 0:
                    return 1
                else:
                    return 0
            if (x, s) not in memo:
                if x == 0:
                    memo[(x, s)] = (dp(x + 1, s - 1, memo) + dp(x, s - 1, memo)) % MOD
                elif x == arrLen - 1:
                    memo[(x, s)] = (dp(x - 1, s - 1, memo) + dp(x, s - 1, memo)) % MOD
                else:
                    memo[(x, s)] = (dp(x + 1, s - 1, memo) + dp(x - 1, s - 1, memo) + dp(x, s - 1, memo)) % MOD
            return memo[(x, s)]
        
        return dp(0, steps, {})

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen == 1: 
            return 1    
        memo = {}
        
        return self.dfs(steps, arrLen, 0, memo)   
        

    def dfs(self, steps, arrLen, cur_pos, memo):
        if (steps, cur_pos) in memo:
            return memo[(steps, cur_pos)]
        
        if cur_pos < 0 or cur_pos >= arrLen:
            return 0 
            
        if steps == 0:
            if cur_pos == 0:
                return 1
            else:
                return 0
                
        memo[(steps, cur_pos)] = self.dfs(steps-1, arrLen, cur_pos, memo) + self.dfs(steps-1, arrLen, cur_pos-1, memo) + self.dfs(steps-1, arrLen, cur_pos+1, memo)         
        
            
        return  memo[(steps, cur_pos)]%(10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = {}
        def dfs(steps, ind):
            if (steps, ind) in dp:
                return dp[(steps, ind)]
            if steps == ind:
                return 1
            elif steps == 0:
                return 0
            res = 0
            res += dfs(steps-1, ind)
            if ind > 0:
                res += dfs(steps-1, ind-1)
            if ind < arrLen-1:
                res += dfs(steps-1, ind+1)
            dp[(steps, ind)] = res
            return res%(10**9+7)
        return dfs(steps, 0)

def memoize(f):
    d = {}
    def memoized_f(*args):
        if args not in d:
            d[args] = f(*args)
        return d[args]
    return memoized_f

@memoize
def numWaysHelper(steps, arrLen, position):
    if position<0 or position >= arrLen:
        return 0
    if steps == 0:
        if position == 0:
            return 1
        return 0
    big_num = 10 ** 9 + 7
    return (numWaysHelper(steps-1, arrLen, position-1) + 
           numWaysHelper(steps-1, arrLen, position) +
           numWaysHelper(steps-1, arrLen, position+1)) % big_num

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        return numWaysHelper(steps, arrLen, 0)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10 ** 9 + 7
        memo = {}
        def dfs(steps, i):
            if not steps:
                return int(i == 0)
            
            if (steps, i) in memo:
                return memo[(steps, i)]
            
            res = dfs(steps - 1, i)
            if i - 1 >= 0:
                res += dfs(steps - 1, i - 1)
            
            if i + 1 <= arrLen - 1:
                res += dfs(steps - 1, i + 1)
            
            memo[(steps, i)] = res % mod
            return memo[(steps, i)]
        
        return dfs(steps, 0)


class Solution:
    def numWays(self, s: int, a: int) -> int:
        MOD = 1000000007
        mem = {}
        def f(s, a, i):
            if (s, i) in mem:
                return mem[(s,i)]
            if not s:
                if i:
                    return 0
                return 1
            if i < 0 or i == a:
                return 0
            #if i > s:
            #    return 0
            ans = 0
            #stay
            ans += f(s-1, a, i)
            #left
            ans += f(s-1, a, i-1)
            #right
            ans += f(s-1, a, i+1)
            
            mem[(s,i)] = ans
            return ans%MOD
            
        return f(s, a, 0)
            
            
        
            
    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = {}
        
        return self.dfs(steps, arrLen, 0, memo)

    def dfs(self, steps, arrLen, pos, memo):
        if (steps, pos) in memo:
            return memo[(steps, pos)]
        
        if pos < 0 or pos >= arrLen:
            return 0
        
        if steps == 0:
            return 1 if pos == 0 else 0
        
        memo[(steps, pos)] = self.dfs(steps - 1, arrLen, pos - 1, memo) + self.dfs(steps - 1, arrLen, pos, memo) + self.dfs(steps - 1, arrLen, pos + 1, memo)
        
        return memo[(steps, pos)] % (10 ** 9 + 7)


MOD = int(1e9 + 7)

class Solution:
    def get_count(self, counts, i):
        if i < 0 or i >= len(counts):
            return 0
        else:
            return counts[i]
        
    def numWays(self, steps: int, arrLen: int) -> int:
        counts = [1]
        for si in range(1, steps + 1):
            new_len = min(si + 1, arrLen)
            new_counts = [0] * new_len
            for i in range(new_len):
                new_counts[i] = sum(self.get_count(counts, j) for j in range(i - 1, i + 1 + 1)) % MOD
            counts = new_counts
        return counts[0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if steps is None or steps < 0 or not arrLen: return 0
        arrLen = min(arrLen, steps)
        memo = [[0] * arrLen for _ in range(steps + 1)]
        memo[0][0] = 1
        for i in range(1, steps + 1):
            for j in range(arrLen):
                memo[i][j] += memo[i - 1][j]
                if j > 0: memo[i][j] += memo[i - 1][j - 1]
                if j < arrLen - 1: memo[i][j] += memo[i - 1][j + 1]
        return memo[steps][0] % (10 ** 9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        return self.getWays(0, steps, 0, arrLen, {})
        
        
    def getWays(self, step, steps, position, arrLen, cache):
        if step == steps: return position == 0
        if (step, position) in cache: return cache[(step, position)]
        numWays = 0
        if position > 0:
            numWays += self.getWays(step + 1, steps, position - 1, arrLen, cache)
        if position < arrLen - 1:
            numWays += self.getWays(step + 1, steps, position + 1, arrLen, cache)
        numWays += self.getWays(step + 1, steps, position, arrLen, cache)
        cache[(step, position)] = numWays
        return numWays % (10**9 + 7)
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int: 
        memo = {}
        
        def helper(position, num_steps, idx):
            nonlocal steps, arrLen, memo
            if (position, num_steps, idx) in memo:
                return memo[(position, num_steps, idx)]
            if idx < 0 or idx > arrLen-1:
                return 0
            if num_steps == steps:
                if position == 0:
                    return 1
                return 0
            stay = helper(position, num_steps+1, idx) 
            right = helper(position+1, num_steps+1, idx+1)
            left = helper(position-1, num_steps+1, idx-1)
            memo[(position, num_steps, idx)] = stay + left + right
            return memo[(position, num_steps, idx)]
        
        return helper(0, 0, 0) % (10**9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        states = [{0: 1}, {}]
        base = 0
        mod = 1000000007
        shift = [1, 0, -1]
        for k in range(0, steps):
            nxt = (base+1)%2
            states[nxt].clear()
            for p in states[base].keys():
                for j in range(0, 3):
                    np = p+shift[j]
                    if 0 <= np < arrLen:
                        if np not in states[nxt].keys():
                            states[nxt][np] = 0
                        states[nxt][np] = (states[nxt][np] + states[base][p]) % mod
            base = nxt
        return states[base][0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if not steps or steps < 0 or arrLen == 0:
            return 0
        memo = {}
        return self.dfs(steps, arrLen, 0, memo)
    
    def dfs(self, steps, arrLen, pos, memo):
        if (steps, pos) in memo:
            return memo[(steps, pos)]
        if pos < 0 or pos > arrLen - 1:
            memo[(steps, pos)] = 0
            return 0
        if steps == 0:
            return 1 if pos == 0 else 0
        memo[(steps, pos)] = self.dfs(steps - 1, arrLen, pos - 1, memo) + self.dfs(steps - 1, arrLen, pos + 1, memo) + self.dfs(steps - 1, arrLen, pos, memo) 
        return memo[(steps, pos)] % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
#         max_position = max(steps, arrLen)
#         dp = [[0] * (max_position + 1) for step in range(steps+1)]
        
#         dp[1][0] = 1
#         dp[1][1] = 1
        
#         for i in range(2, steps + 1):
#             for j in range(0, max_position):
#                 if j > 0:
#                     dp[i][j] = (dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1]) % (10 ** 9 + 7)
#                 else:
#                     dp[i][j] = (dp[i-1][j] + dp[i-1][j+1]) % (10 ** 9 + 7)
        
#         return dp[steps][0]

        mod = 10 ** 9 + 7
        n = arrLen
        
        A = [0, 1]
        for t in range(steps):
            A[1:] = [sum(A[i - 1:i + 2]) % mod for i in range(1, min(n + 1, t + 3))]
        
        return A[1] % mod
#         ways = [-1, 0, 1]
        
#         def visit(cur_total_steps, cur_index):
#             if cur_total_steps == steps and cur_index == 0:
#                 self.total_ways += 1
#                 return
            
#             if cur_total_steps > steps or cur_index >= arrLen:
#                 return

#             for way in ways:
#                 if cur_index == 0 and way == -1:
#                     continue
                
#                 if cur_index == arrLen - 1 and way == 1:
#                     continue
                
#                 visit(cur_total_steps + 1, cur_index + way)
        
#         self.total_ways = 0
#         visit(0, 0)
        
#         return self.total_ways % (10^9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if steps is None or steps < 0 or not arrLen:
            return 0
        memo = {}
        return self.dfs(steps, arrLen, 0, memo)

    def dfs(self, steps, arrLen, pos, memo):
        if (steps, pos) in memo:
            return memo[(steps, pos)]
        if pos < 0 or pos > arrLen - 1:
            memo[(steps, pos)] = 0
            return 0
        if steps == 0:
            return 1 if pos == 0 else 0
        memo[(steps, pos)] = self.dfs(steps - 1, arrLen, pos - 1, memo) + self.dfs(steps - 1, arrLen, pos, memo) + self.dfs(steps - 1, arrLen, pos + 1, memo) 
        return memo[(steps, pos)] % (10 ** 9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10 ** 9 + 7
        real_len = min(steps, arrLen) + 2
        f1 = [0 for _ in range(real_len)]
        f1[0] = 1
        for _ in range(steps):
            f2 = [0 for _ in range(real_len)]
            for i in range(real_len - 1):
                for d in [ -1, 0, 1 ]:
                    ii = i + d
                    if ii >= 0  and ii <= arrLen - 1:
                        f2[i] += f1[ii] % mod
            f1 = f2.copy()
        
        return f1[0] % mod
                        
                
            


from functools import lru_cache
class Solution:
    @lru_cache(None)
    def helper(self, index, n, arrlen):
        if not 0<=index<arrlen or n<0 or index>n:
            return 0
        if index==n:
            return 1
        return (self.helper(index+1, n-1, arrlen) + self.helper(index-1, n-1, arrlen) + self.helper(index, n-1, arrlen)) % self.MOD
    
    def numWays(self, steps: int, arrLen: int) -> int:
        self.MOD = 10**9 + 7
        return self.helper(0, steps, arrLen)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        def count(pos, i):
            if i == steps: 
                return pos == 0
            
            if (pos, i) in memo:
                return memo[(pos, i)]
            res = 0
            if pos > 0:
                res += count(pos-1, i+1)
                res %= mod
            if pos < arrLen-1:
                res += count(pos+1, i+1)
                res %= mod
            res%= mod
            res += count(pos, i+1)
            res %= mod
                
            memo[(pos, i)] = res
            return res
        
        mod = 10**9 + 7
        memo = {}
        return count(0, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10 ** 9 + 7
        memo = {}
        
        def nw(i: int, k: int) -> int:
            if k == 0:
                return i == 0
            if k < 0 or i < 0 or i >= arrLen:
                return 0
            if (i, k) not in memo:
                memo[(i, k)] = (nw(i - 1, k - 1) + nw(i + 1, k - 1) + nw(i, k - 1)) % MOD
            return memo[(i, k)]
        
        return nw(0, steps)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(steps//2+1, arrLen)
        ans = [0]*arrLen
        ans[0] = 1
        for i in range(steps):
            new_ans = []
            for j in range(arrLen):
                tmp = ans[j]
                if j > 0: tmp += ans[j-1]
                if j < arrLen-1: tmp += ans[j+1]
                new_ans.append(tmp)
            ans = new_ans
        return ans[0]%(10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = dict()
        def calculateWays(steps, arrLen, index):
            if index < 0 or index >= arrLen:
                return 0
            elif steps == 0 and index == 0:
                return 1
            elif steps == 0 and index != 0:
                return 0
            elif (steps, index) in memo:
                return memo[(steps, index)]
            else:
                goLeft = calculateWays(steps - 1, arrLen, index - 1)
                stay = calculateWays(steps - 1, arrLen, index)
                goRight = calculateWays(steps - 1, arrLen, index + 1)
                memo[(steps, index)] = goLeft + stay + goRight
                return memo[(steps, index)]
        
            
        return calculateWays(steps, arrLen, 0) % (10**9 + 7)


MODULO = 10**9 + 7 

class DP:
    def __init__(self, arrLen: int):
        self._len = arrLen
        self._cache = {}
        
    def get(self, index, steps):
        if (index, steps) in self._cache:
            return self._cache[(index, steps)]
        result = self._get_uncached(index, steps)
        # print(f\"index={index} steps={steps}  =>  ways={result}\")
        self._cache[(index, steps)] = result
        return result
        
    def _get_uncached(self, index, steps):
        if index < 0 or index >= self._len:
            return 0
        if steps == 0 and index == 0:
            return 1
        elif steps == 0:
            return 0
        return (self.get(index - 1, steps - 1) + self.get(index, steps - 1) + self.get(index + 1, steps - 1)) % MODULO
        

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = DP(arrLen)
        return dp.get(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.arrLen = arrLen
        self.memo = {}
        return self.helper(steps, 0)
    
    def helper(self, steps, pos):
        if (steps, pos) in self.memo:
            return self.memo[(steps, pos)]
        if pos < 0 or pos >= self.arrLen or steps < 0:
            return 0
        if steps == 0:
            if pos == 0:
                return 1
            else:
                return 0
        res = 0
        for x in [-1, 0, 1]:
            ans = self.helper(steps-1, pos+x)
            res += ans
            
        self.memo[(steps, pos)] = res % (10**9 + 7)
        return res % (10**9 + 7)
        


class Solution:
    # 了解和对比TC
    # dfs to find all possible way - dfs + dp: cutting rope
    # state: remaining steps + distance 
        # - break to two parts which sum of remain steps == total steps
        # - sum of dist <= arrLen
        # - takes 1 extra steps to connect
    def numWays(self, steps: int, arrLen: int) -> int:
        # if dist == 1, combos always 1 regardless of steps
        if arrLen == 0 or (arrLen == 1 and steps > 0):
            return arrLen
        combos = {} # (dist, steps): # of combos
        
        def _dfs_ways(steps, arrLen, loc = 0, tar = 0):
            if steps == 0:
                return 1 if loc == tar else 0
            if (steps, loc) in combos: return combos[(steps, loc)]
            steps -= 1
            stay, right, left = 0, 0, 0
            stay = _dfs_ways(steps, arrLen, loc)
            if loc + 1 < arrLen: right = _dfs_ways(steps, arrLen, loc + 1)
            if loc - 1 >= 0: left = _dfs_ways(steps, arrLen, loc - 1)
            steps += 1
            res = (stay + left + right) % (math.pow(10, 9) + 7)
            combos[(steps, loc)] = res
            return res
        
        # for i in range(1, min(arrLen, steps // 2) + 1):
        #     # for combo two parts
        #     res = 0
        #     for div in range(1, i + 1): # divide len for dfs
        #         for left_steps in range(1, steps):
        #             left_ways = _dfs(left_steps, div)
        #             right_ways = _dfs(steps - left_steps - 1, i - div)
        #             res += left_ways * right_ways
        #     # for whole
        #     res += _dfs(steps, i)
        #     combos[(steps, i)] = res
        _dfs_ways(steps, arrLen)
        # print(combos)
        ans = combos[(steps, 0)]
        return int(ans % (math.pow(10, 9) + 7))

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.arrLen = arrLen
        self.memo = {}
        return self.helper(steps, 0)
    
    def helper(self, steps, pos):
        if (steps, pos) in self.memo:
            return self.memo[(steps, pos)]
        if pos < 0 or pos >= self.arrLen or steps < 0:
            self.memo[(steps, pos)] = 0
            return 0
        if steps == 0:
            if pos == 0:
                self.memo[(steps, pos)] = 1
                return 1
            else:
                self.memo[(steps, pos)] = 0
        res = 0
        for x in [-1, 0, 1]:
            res += self.helper(steps-1, pos+x)
        self.memo[(steps, pos)] = res
        return res % (10**9 + 7)
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.arrLen = arrLen
        
        @lru_cache(None)
        def dp(curr, steps):
            # print(curr, steps)
            if steps:
                temp = 0
                for i in [curr-1, curr, curr+1]:
                    if 0 <= i < self.arrLen:
                        temp += dp(i, steps-1)
                return temp
            else:
                return 1 if curr == 0 else 0
        
        return dp(0, steps) % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        # time O(n); space O(n)
        n = min(steps, arrLen)
        dp = [0] * n
        dp[0] = 1
        for step in range(1, steps+1):
            tmp_dp = [0] * n
            for idx in range(n):
                tmp_dp[idx] = sum(dp[max(0, idx-1):min(idx+1, n)+1])
            dp = tmp_dp
        
        return dp[0] % (10**9+7)

class Solution:
    # 了解和对比TC
    # dfs to find all possible way - dfs + dp: cutting rope
    # state: remaining steps + distance 
        # - break to two parts which sum of remain steps == total steps
        # - sum of dist <= arrLen
        # - takes 1 extra steps to connect
    def numWays(self, steps: int, arrLen: int) -> int:
        # if dist == 1, combos always 1 regardless of steps
        if arrLen == 0 or (arrLen == 1 and steps > 0):
            return arrLen
        combos = {} # (dist, steps): # of combos
        def _dfs_ways(steps, arrLen, loc = 0, tar = 0):
            if steps == 0:
                return 1 if loc == tar else 0
            if (steps, loc) in combos: return combos[(steps, loc)]
            steps -= 1
            stay = _dfs_ways(steps, arrLen, loc)
            left = _dfs_ways(steps, arrLen, loc - 1) if loc - 1 >= 0 else 0
            right = _dfs_ways(steps, arrLen, loc + 1) if loc + 1 < arrLen else 0
            res = int((left + right + stay) % (math.pow(10, 9) + 7))
            steps += 1
            combos[(steps, loc)] = res
            return res
        
        # for i in range(1, min(arrLen, steps // 2) + 1):
        #     # for combo two parts
        #     res = 0
        #     for div in range(1, i + 1): # divide len for dfs
        #         for left_steps in range(1, steps):
        #             left_ways = _dfs(left_steps, div)
        #             right_ways = _dfs(steps - left_steps - 1, i - div)
        #             res += left_ways * right_ways
        #     # for whole
        #     res += _dfs(steps, i)
        #     combos[(steps, i)] = res
        _dfs_ways(steps, arrLen)
        ans = combos[(steps, 0)]
        return int(ans % (math.pow(10, 9) + 7))

from functools import lru_cache

class Solution:
  @lru_cache(None)
  def recursive(self, x, i):
    # x: steps remain, i: current position.
    if x == i:
      return 1
    count = 0
    if x > 0:
      # stay
      count += self.recursive(x - 1, i)
      # left
      if i - 1 >= 0:
        count += self.recursive(x - 1, i - 1)
      # right
      if i + 1 < self.L:
        count += self.recursive(x - 1, i + 1)
    return count % (10 ** 9 + 7)
  def numWays(self, steps: int, arrLen: int) -> int:
    self.L = arrLen
    return self.recursive(steps, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.mod = 10 ** 9 + 7
        
        return self.dp(arrLen, steps, 0)
    
    @lru_cache(None)
    def dp(self, n, steps, i):        
        if i >= n or i < 0:
            return 0
        
        if steps == 0:
            return 1 if i == 0 else 0
        
        stay_in_place = self.dp(n, steps - 1, i)
        move_left = self.dp(n, steps - 1, i - 1)
        move_right = self.dp(n, steps - 1, i + 1)

        
        return (stay_in_place + move_left + move_right) % self.mod

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        f_old = [0] * min(steps + 1, arrLen)
        f_new = [0] * min(steps + 1, arrLen)
        if arrLen == 1:
            return 1
        elif arrLen == 0:
            return 0
        f_old[0] = 1
        for i in range(steps):
            f_new[0] = f_old[0] + f_old[1]
            if i + 1 <= arrLen - 1:
                f_new[i + 1] = 1
            else:
                f_new[-1] = f_old[-1] + f_old[-2]
            for j in range(1, min(i + 1, arrLen - 1)):
                f_new[j] = f_old[j - 1] + f_old[j] + f_old[j + 1]
            f_old = f_new.copy()
            f_old = [_ % (10 ** 9 + 7) for _ in f_old]
        return f_old[0] 



def count(curr, maxpos, steps, mod, obj):
    if curr < 0: return 0
    if curr == maxpos: return 0
    if steps == 1 and curr == 1: return 1
    if steps == 1 and curr == 0: return 1
    if steps == 0: return 0
    if (curr,steps) in obj: return obj[(curr,steps)]
    obj[(curr,steps)] = (count(curr, maxpos, steps-1, mod, obj)%mod + count(curr+1, maxpos, steps-1, mod, obj)%mod + count(curr-1, maxpos, steps-1, mod, obj)%mod)%mod
    return obj[(curr,steps)]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        curr = 0
        mod = 10**9+7
        obj = {}
        return count(curr, arrLen, steps, mod, obj)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.mod = 10 ** 9 + 7
        
        return self.dp(arrLen, steps, 0)
    
    @lru_cache(None)
    def dp(self, n, steps, i):
        if steps == 0 and i == 0:
            return 1
        
        if i >= n or i < 0 or steps == 0:
            return 0
        
        stay_in_place = self.dp(n, steps - 1, i)
        move_left = self.dp(n, steps - 1, i - 1)
        move_right = self.dp(n, steps - 1, i + 1)
        
        return (stay_in_place + move_left + move_right) % self.mod

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mem = {}
        
        def helper(i, k, arrLen):
            # print(i, k)
            if i == 0 and k == 0:
                return 1
            if (i, k) in mem:
                return mem[(i, k)]
            count = 0
            for x in [-1, 0, 1]:
                if i+x < 0 or i+x >= arrLen or k < 0:
                    continue
                count += helper(i+x, k-1, arrLen)
            mem[(i,k)] = count
            return count
        return helper(0, steps, arrLen)%(10**9 + 7)

from functools import lru_cache
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        @lru_cache(None)
        def dfs(s, l):
            if s == steps:
                if l == 0:
                    return 1
                return 0
            
            return (dfs(s + 1, l) + (dfs(s + 1, l + 1) if l < arrLen-1 else 0 )+ (dfs(s + 1, l - 1) if l else 0)) % mod
        return dfs(0, 0)

class Solution:
    
    
    def helper(self, pos, steps):
        if (pos, steps) in self.cache:
            return self.cache[(pos,steps)]
        
        if steps == 0:
            return 1 if pos == 0 else 0
        
        stay = self.helper(pos, steps - 1)
        
        self.cache[(pos, steps - 1)] = stay
        
        left = self.helper(pos + 1, steps - 1) if pos < self.arrLen - 1 else 0
        
        self.cache[(pos + 1, steps - 1)] = left

        
        right =  self.helper(pos - 1, steps - 1) if pos > 0 else 0
        
        self.cache[(pos -1 , steps - 1)] = right

        
        return stay + left + right
        
        
    def numWays(self, steps: int, arrLen: int) -> int:
        self.cache = {}
        self.steps = steps
        self.arrLen = arrLen
        return self.helper(0, steps) % (10**9 + 7)

import functools
@functools.lru_cache(maxsize=10**7+1)
def count(curr, maxpos, steps, mod):
    if curr < 0: return 0
    if curr == maxpos: return 0
    if steps == 1 and curr == 1: return 1
    if steps == 1 and curr == 0: return 1
    if steps == 0: return 0
    return (count(curr, maxpos, steps-1, mod)%mod + count(curr+1, maxpos, steps-1, mod)%mod + count(curr-1, maxpos, steps-1, mod)%mod)%mod

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        curr = 0
        mod = 10**9+7
        return count(curr, arrLen, steps, mod)

class Solution:
    def numWays(self, steps: int, n: int) -> int:
        A = [0, 1]
        mod=10 ** 9 + 7
        for t in range(steps):
            A[1:] = [sum(A[i - 1:i + 2]) % mod for i in range(1, min(n + 1, t + 3))]
        return A[1] % mod        

class Solution:
    
    def __init__(self):
        self.dp = {}
        
    def numWays(self, steps: int, arrLen: int, ptr: int = 0) -> int:
        
        return self.numWays_dp(steps, arrLen, ptr) % (10**9+7)
    
    def numWays_dp(self, steps: int, arrLen: int, ptr: int = 0) -> int:
        if ptr >= arrLen:
            return 0
        if ptr < 0:
            return 0
        if steps == 0:
            if ptr == 0:
                return 1
            else:
                return 0
            
        if (ptr, steps) in self.dp:
            return self.dp[(ptr, steps)]
        
        left_ways = self.numWays(steps-1, arrLen, ptr-1)
        middle_ways = self.numWays(steps-1, arrLen, ptr)
        right_ways = self.numWays(steps-1, arrLen, ptr+1)
        
        total_ways = left_ways + middle_ways + right_ways
        self.dp[(ptr, steps)] = total_ways
        
        return total_ways

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        return self.dfs(steps, arrLen, {}, 0)%(10**9+7)
    
    def dfs(self, step, arrLen, mem, index):
        if (step, index) in mem:
            return mem[(step, index)]
        if index < 0 or index >= arrLen:
            return 0
        if step == 0:
            if index == 0:
                return 1
            return 0
        mem[(step, index)] = 0
        for i in range(-1, 2):
             mem[(step, index)] += self.dfs(step-1, arrLen, mem, index+i)
        return mem[(step, index)]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = [0 for _ in range(arrLen)]
        dp[0],dp[1]=1,1
        for s in range(2,steps+1):
            dp2 = [0 for _ in range(min(steps-s+2,arrLen))]
            dp2[0]= dp[0]+dp[1]
            if arrLen !=1:
                dp2[-1]= dp[-2]+dp[-1]
            for num in range(1,min(steps-s+1,arrLen-1)):
                dp2[num] = dp[num-1]+dp[num]+dp[num+1]
            dp = dp2
            
        return(dp[0])%(10**9+7)
    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        r, memo = min(arrLen, steps // 2 + 1), [0, 1]
        for t in range(steps):
            memo[1:] = [sum(memo[i-1:i+2]) for i in range(1, min(r+1, t+3))]
        return memo[1] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        c_ori=[0]*min(steps+2,(2+arrLen))
        c_ori[1]=1
        c_new=[0]*min(steps+2,(2+arrLen))
        
        for i in range(0,steps):
            for j in range(1,len(c_ori)-1):
                c_new[j]=c_ori[j]+c_ori[j-1]+c_ori[j+1]
            #print(c_new)
            c_ori=c_new.copy()
        return c_ori[1]%1000000007


LIMIT = 10**9 + 7

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        max_pos = min(steps // 2 + 1, arrLen) + 1
        dp = [[0] * max_pos for _ in range(steps)]
        dp[0][0] = dp[0][1] = 1
        
        for i in range(1, steps):
            for j in range(max_pos-1):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]) % LIMIT
            
        return dp[-1][0]
    
# time: O(min(arrLen, steps) * steps)
# space: O(min(arrLen, steps) * steps)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        counts = [0] * min(arrLen, steps // 2 + 1)
        counts[0], counts[1] = 1, 1
        
        mod = (10**9 + 7) 
        while steps - 1:
            prev_counts = counts[:]
            for i in range(len(counts)):
                if i == 0:
                    counts[i] = sum(prev_counts[i:i+2]) % mod
                elif i == arrLen - 1:
                    counts[i] = sum(prev_counts[i-1:i+1]) % mod
                else:
                    counts[i] = sum(prev_counts[i-1:i+2]) % mod
            steps -= 1
        
        return counts[0]
            
        
        
    
        
        
           
            
            
            


class Solution:
    def numWays(self, steps: int, n: int) -> int:
        mod = 10**9 + 7
        A = [0, 1]
        for t in range(steps):
            A[1:] = [sum(A[i - 1:i + 2]) % mod for i in range(1, min(n + 1, t + 3))]
        return A[1] % mod

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen < 2:
            return 1
        MAX = 10**9 + 7
        
        dp = [0]*arrLen
        dp[0] = 1
        dp[1] = 1
        
        ndp = [0]*arrLen
        for step in range(2, steps+1):
            ndp[0] = dp[0] + dp[1]
            ndp[arrLen - 1] = dp[arrLen - 1] + dp[arrLen - 2]
            
            for i in range(1, min(steps, arrLen-1)):
                ndp[i] = (dp[i-1] + dp[i] + dp[i+1])%MAX
                
            
            dp[:min(steps, arrLen)] = ndp[:min(steps, arrLen)]
        return dp[0] % MAX
    
        
        
        
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        A = [0] * (arrLen + 2)
        A[1] = 1
        mod = 10**9 + 7
        for n in range(1,steps+1):
            prev = 0
            for m in range(1,min(arrLen+1,n+2)): 
                old = A[m]
                A[m] = (prev + A[m] + A[m+1]) % mod
                prev = old
                
        return A[1]


# dp[k][i] = # of ways at step k in i position

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        dp = [[0]*(steps//2+2) for _ in range(steps+1)] #如果k=500, i可以去到250 length 有251个
        dp[0][0] = 1
        M = 10**9 + 7
        
        for k in range(1, steps+1):
            for i in range(steps//2+1):
                if i == 0:
                    dp[k][i] = (dp[k-1][i] + dp[k-1][i+1])%M
                    
                elif i == arrLen-1:
                    dp[k][i] = (dp[k-1][i] + dp[k-1][i-1])%M
                    
                else:
                    dp[k][i] = (dp[k-1][i] + dp[k-1][i-1] + dp[k-1][i+1])%M
                    
        return dp[steps][0]%M

from functools import lru_cache
mod = 10**9+7

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:    

        @lru_cache(None)
        def calculation(pos: int, steps: int):
            if pos < 0 or pos >= arrLen:
                return 0
            if pos > steps:
                return 0            
            if pos == steps:
                return 1            
            
            return (calculation(pos+1, steps-1) + calculation(pos-1, steps-1) + calculation(pos, steps-1) ) % mod
        
        return calculation(0, steps)
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if steps == 0:
            return 0
        if arrLen == 1:
            return 1
        
        start = [1, 1] + ([0] * (min(steps, arrLen)-2))
        return self.numWaysHelper(steps-1, start)
        
    # Assumes len(start) > 1
    def numWaysHelper(self, steps, start):
        if steps == 0:
            return start[0] % (10**9 + 7)

        n = [0] * len(start)
        n[0] = start[0] + start[1]
        n[len(start) - 1] = start[len(start)-1] + start[len(start)-2]
        
        for i in range(1, len(start) - 1):
            n[i] = (start[i-1] + start[i] + start[i+1])
        
        return self.numWaysHelper(steps-1, n)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        max_len = min(steps //2 + 1, arrLen) #steps //2 + 1
        mod = 10**9 + 7
        dp = [[0] * (max_len+1) for _ in range(steps+1)]
        dp[1][0] = 1
        dp[1][1] = 1
        for i in range(2, steps+1):
            for j in range(max_len):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1] + (dp[i-1][j-1] if j > 0 else 0)) % mod
        
        for r in dp:
            print(r)
        return dp[steps][0]

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

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen < 2:
            return 1
        MAX = 10**9 + 7
        
        # dp[i] is num of ways to reach position i, starting from position 0
        # if steps < i, is impossible to reach i
        dp = [0] * arrLen 
        dp[0] = 1 # one step: stay
        dp[1] = 1 # one step: move right
        
        ndp = [0] * arrLen # new dp array
        # dp is status for previous step
        # ndp is updated from last dp
        for step in range(2, steps+1):
            # two boundary case at poistion 0 and arrLen-1
            ndp[0] = dp[0] + dp[1] #stay or move from right 
            ndp[arrLen-1] = dp[arrLen-1] + dp[arrLen-2] #stay or move from left
            
            # any other non-boundary positions
            # stay, move from left, move from right
            for i in range(1, min(steps, arrLen-1)):
                ndp[i] = (dp[i] + dp[i-1] + dp[i+1]) % MAX
            
            # save status
            for i in range(0, min(steps, arrLen)):
                dp[i] = ndp[i]
            
        return dp[0] % MAX
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        needed = min(steps+1,arrLen)
        
        dp = [0 for i in range(needed+1)]
        new_dp = dp.copy()
        dp[0] = 1
        for step in range(1,steps+1):
            for pos in range(min(step+1,arrLen)):
                new_dp[pos] = dp[pos] + dp[pos-1] +dp[pos+1]
            
            dp,new_dp = new_dp,dp
        return dp[0]%(10**9+7)
       
     
        
        needed = min(arrLen, steps + 1)
        dp = [0 for i in range(needed + 1)]
        dp[0] = 1
        # used to avoid unnecessary allocation of lists
        next_dp = dp.copy()
        for step in range(1, steps+1):
            # anything after index=step+1 will be 0, so we don't need to access them.
            #for pos in range(min(step+1, needed)):
            for pos in range(min(step+1,arrLen )):
            #for pos in range(arrLen):
                next_dp[pos]=dp[pos-1]+dp[pos]+dp[pos+1]
            print((step, next_dp, dp))
            dp, next_dp = next_dp, dp
        return dp[0]%(10**9+7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen < 2:
            return 1
        MAX = 10**9 + 7
        
        dp = [0]*arrLen
        dp[0] = 1
        dp[1] = 1
        
        ndp = [0]*arrLen
        for step in range(2, steps+1):
            ndp[0] = dp[0] + dp[1]
            ndp[arrLen - 1] = dp[arrLen - 1] + dp[arrLen - 2]
            
            for i in range(1, min(steps, arrLen-1)):
                ndp[i] = (dp[i-1] + dp[i] + dp[i+1])%MAX
                
            for i in range(min(steps, arrLen)):
                dp[i] = ndp[i]
        return dp[0] % MAX
    
        
        
        
        


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

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        v = min(steps, arrLen)
        dp = [0] * v
        dp[0] = 1
        temp = [0] * v
        for _ in range(steps):
            left = 0
            for idx, val in enumerate(dp):
                temp = val
                right = 0 if idx == len(dp) - 1 else dp[idx + 1]
                dp[idx] += left + right
                left = temp
            
        return dp[0] % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        @lru_cache(None)
        def helper(i, steps):
            if steps == 0:
                return i == 0
            elif steps < i or steps + i < 0:
                return 0
            else:
                result = helper(i, steps - 1)
                if i < arrLen - 1:
                    result += helper(i + 1, steps - 1)
                if i > 0:
                    result += helper(i - 1, steps - 1)
                return result % 1_000_000_007
        mod = 1_000_000_007
        return helper(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        ### dp[steps][pos]
        modulo = 10 ** 9 + 7
        
        maxPos = min(steps//2 + 1, arrLen)
        
        dp = [ [0 for _ in range(maxPos+1)] for _ in range(steps + 1) ]
        
        dp[1][0], dp[1][1] = 1, 1
        
        ### dp[s][p] = dp[s-1][p] + dp[s-1][p-1] + dp[s-1][p+1]
        
        for i in range(2, steps+1):
            for j in range(maxPos):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1]) % modulo
                    
                if j - 1 >= 0:
                    dp[i][j] += dp[i-1][j-1] % modulo
        
        return dp[steps][0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        # write your code here
        arrLen = min(arrLen, steps + 1) 
        f = [1]+[0]*(arrLen-1) # f[0] = 1

        for i in range(1, steps+1):
            old = 0 
            for j in range(arrLen):
                old_left = old
                old = f[j]
                if j > 0:
                    f[j] += old_left      
                if j < arrLen - 1:
                    f[j] += f[j+1]   
        return f[0] % (10 ** 9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(arrLen,steps + 1)
        f = [1] + [0] * (arrLen - 1)
        
        for i in range(1, steps + 1):
            old = 0
            for j in range(arrLen):
                old_left = old
                old = f[j]
                
                if j > 0:
                    f[j] += old_left
                    
                if j < arrLen - 1:
                    f[j] += f[j + 1]
        return f[0] % (10 ** 9 + 7)

from functools import lru_cache

class Solution:
    def numWays(self, steps, arrLen):
        # write your code here
        arrLen = min(arrLen, steps + 1) 
        f = [1]+[0]*(arrLen-1) # f[0] = 1

        for i in range(1, steps+1):
            old = 0 
            for j in range(arrLen):
                old_left = old
                old = f[j]
                if j > 0:
                    f[j] += old_left      
                if j < arrLen - 1:
                    f[j] += f[j+1]   
        return f[0] % (10 ** 9 + 7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        n = min(steps//2 + 1, arrLen)
        f = [None] * (steps + 1)
        f[0] = [0] * n
        f[0][0] = 1
        for t in range(1, steps + 1):
            f[t] = [0] * n
            for i in range(n):
                f[t][i] = f[t-1][i]
                if i + 1 < n:
                    f[t][i] += f[t-1][i+1]
                if i - 1 >= 0:
                    f[t][i] += f[t-1][i-1]
        return f[steps][0] % (10**9 + 7)

        memo = {}
        def f(i, c):
            if c == 0:
                return 1 if i == 0 else 0
            if (i, c) in memo:
                return memo[(i, c)]
            cnt = f(i, c - 1)
            if i + 1 < arrLen:
                cnt += f(i + 1, c - 1)
            if i - 1 >= 0:
                cnt += f(i - 1, c - 1)
            memo[(i, c)] = cnt
            return cnt
        
        return f(0, steps) % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        # From index 0, we can venture out at most steps//2 additional steps and still
        # gurantee we can come back. The length of the array that we can cover is
        # therefore the 0-th cell, plus the steps//2 additional cells = steps//2 + 1
        # (we ideally always need steps to be even because, from index 0, we can hit at most
        # step//2 cells, and to come back we need again step//2 moves. But if it is odd,
        # the extra step modulo 2 does us no good, we can make use of at most step//2 moves
        # to the right and step//2 moves back, unable to make use of the extra step)
        n = min(steps//2 + 1, arrLen)
        f = [None] * (steps + 1)
        f[0] = [0] * n
        f[0][0] = 1
        for t in range(1, steps + 1):
            f[t] = [0] * n
            for i in range(n):
                f[t][i] = f[t-1][i]
                if i + 1 < n:
                    f[t][i] += f[t-1][i+1]
                if i - 1 >= 0:
                    f[t][i] += f[t-1][i-1]
        return f[steps][0] % (10**9 + 7)

        memo = {}
        def f(i, c):
            if c == 0:
                return 1 if i == 0 else 0
            if (i, c) in memo:
                return memo[(i, c)]
            cnt = f(i, c - 1)
            if i + 1 < arrLen:
                cnt += f(i + 1, c - 1)
            if i - 1 >= 0:
                cnt += f(i - 1, c - 1)
            memo[(i, c)] = cnt
            return cnt
        
        return f(0, steps) % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        # time O(n^2); space O(n)
        n = min(steps//2 + 1, arrLen)
        dp = [0] * n
        dp[0] = 1
        for _ in range(steps):
            tmp_dp = [0] * n
            for idx in range(n):
                tmp_dp[idx] = sum(dp[max(0, idx-1):min(n, idx+1)+1])
            dp = tmp_dp
        
        return dp[0] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        modulo = 10**9 + 7
        @lru_cache(None)
        def make_step(pos, steps_left):
            if steps_left == 0 or pos > steps_left:
                if pos == 0:
                    return 1
                return 0
            else:
                #Left
                ways = 0
                if pos > 0:
                    ways += make_step(pos-1, steps_left-1) % modulo
                #Right
                if pos < arrLen-1:
                    ways += make_step(pos+1, steps_left-1) % modulo
                #Stay
                ways += make_step(pos, steps_left-1) % modulo
                return ways % modulo
        
        return make_step(0, steps) 

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(steps+1, arrLen)
        ans = [0]*arrLen
        ans[0] = 1
        for i in range(steps):
            new_ans = []
            for j in range(arrLen):
                tmp = ans[j]
                if j > 0: tmp += ans[j-1]
                if j < arrLen-1: tmp += ans[j+1]
                new_ans.append(tmp)
            ans = new_ans
        return ans[0]%(10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen>steps//2+1:
            arrLen=steps//2+1
        num_ways=[0 for i in range(arrLen)]
        num_ways[0]=1
        k=10**9+7
        for _ in range(steps):
            cur_num_ways=num_ways[:]
            for i in range(arrLen):
                if i-1>=0:
                    cur_num_ways[i]+=num_ways[i-1]
                if i+1<arrLen:
                    cur_num_ways[i]+=num_ways[i+1]
                cur_num_ways[i]=cur_num_ways[i]%k
            num_ways=cur_num_ways
        return num_ways[0]
                    
                    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        max_dist = min(steps // 2 + 1, arrLen)
        dp = [[0] * (max_dist + 1) for _ in range(steps)]
        
        dp[0][0] = dp[0][1] = 1
        
        for i in range(1, steps):
            for j in range(max_dist):
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]) % (10**9 + 7)
                
        return dp[-1][0]

from collections import defaultdict

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.counter = 0
        cache = defaultdict(defaultdict)
       
        def rec(pos, steps):
            if pos in cache:
                if steps in cache[pos]:
                    return cache[pos][steps]
                
            if steps == 0:
                if pos == 0:
                    return 1
                return
            if pos < 0 or pos >= arrLen:
                return
           
            if steps < pos:
                return
            
            left = rec(pos-1, steps-1)
            right = rec(pos+1, steps-1)
            stay = rec(pos, steps-1)
            if left is None and right is None and stay is None:
                val = None
            else:
                val = (left or 0) + (right or 0) + (stay or 0)
                
            cache[pos][steps] = val
            return val
        
        res = rec(0, steps) 
        
        return res % (10**9 + 7)


from functools import lru_cache

class Solution:
    def numWays(self, steps: int, n: int) -> int:
        
        MOD = 10**9 + 7
        
        # @lru_cache(None)
        def calculate(pos, steps):
            nonlocal dp

            if pos < 0 or pos >= n: return 0
            if pos > steps: return 0
            if steps == pos: return 1
            steps -= 1
            
            if (pos+1,steps) in dp:
                step1 = dp[(pos+1,steps)]
            else:
                step1 = calculate(pos+1, steps) 
                dp[(pos+1,steps)] = step1
            
            if (pos-1, steps) in dp:
                step2 = dp[(pos-1,steps)]
            else:
                step2 = calculate(pos-1, steps)
                dp[(pos-1,steps)] = step2
            
            if (pos,steps) in dp:
                step3 = dp[(pos,steps)]
            else:
                step3 = calculate(pos, steps)   
                dp[(pos,steps)] = step3
                
            return (step1+step2+step3) % MOD
        
        dp = {}
        return calculate(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        '''
        Two-row DP solution. dp[i][j] = # of ways to get to position j in i steps.
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1] (need to take care of boundary conditions on first/last)
        This is guarantee to be unique # of ways because we just look at what's the last step taken (stay, left, or right).
        The final answer is dp[steps][0]
        '''
        arrLen = min(steps // 2 + 1, arrLen)
        dp = [0] * arrLen
        dp[0], dp[1] = 1, 1
        for i in range(2, steps):
            dp_new = [0] * arrLen
            for j in range(min(i + 1,arrLen)):
                dp_new[j] = (dp[j - 1] if (j - 1) >= 0 else 0) + dp[j] + (dp[j + 1] if (j + 1) < arrLen else 0)
            dp = dp_new
        return (dp[0] + dp[1]) % (10**9 + 7)


class Solution:
    def numWays(self, steps: int, n: int) -> int:
        
        MOD = 10**9 + 7
        
        @lru_cache(None)
        def calculate(pos, steps):
            if pos < 0 or pos >= n: return 0
            if pos > steps: return 0
            if steps == pos: return 1
            steps -= 1
            return (calculate(pos+1, steps) + calculate(pos-1, steps) + calculate(pos, steps)) % MOD
        
        return calculate(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        rec = [1]
        mod = 10**9+7
        
        for i in range(1, steps+1):
            temp = []
            for j in range(min(i+1, arrLen)):
                temp.append(sum(rec[max(0,j-1) : min(j+2, arrLen)])%mod)
            rec = temp
#            print(rec)
        return rec[0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        counts = [0] * min(arrLen, steps + 1)
        counts[0], counts[1] = 1, 1
        
        mod = (10**9 + 7) 
        while steps - 1:
            prev_counts = counts[:]
            for i in range(len(counts)):

                if i == 0:
                    counts[i] = sum(prev_counts[i:i+2]) % mod
                elif i == arrLen - 1:
                    counts[i] = sum(prev_counts[i-1:i+1]) % mod
                else:
                    counts[i] = sum(prev_counts[i-1:i+2]) % mod
            steps -= 1
        
        return counts[0]
            
        
        
    
        
        
           
            
            
            


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if arrLen == 0 or arrLen == 1: return 1
        
        MODULO = 10 ** 9 + 7
        ans = [0] * arrLen
        # step 1:
        ans[0] = 1
        ans[1] = 1
        
        arrLen = min(steps+1, arrLen)
        for _ in range(1, steps):
            next_ans = [0] * arrLen
            for j in range(arrLen):
                if j == 0:
                    next_ans[j] = (ans[j] + ans[j+1]) % MODULO
                elif j == arrLen - 1:
                    next_ans[j] = (ans[j-1] + ans[j]) % MODULO
                else:
                    next_ans[j] = (ans[j-1] + ans[j] + ans[j+1]) % MODULO
            ans = next_ans
        return ans[0]


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7
        def count_steps(steps_left, current_pos, memo):
            if (steps_left, current_pos) in memo:
                return memo[(steps_left, current_pos)]
            
            if current_pos < 0 or current_pos > arrLen - 1 or current_pos > steps_left:
                return 0
            
            if not steps_left:
                if current_pos == 0:
                    return 1
                else:
                    return 0
            
            ans = count_steps(steps_left - 1, current_pos, memo) + count_steps(steps_left - 1, current_pos - 1, memo) + count_steps(steps_left - 1, current_pos + 1, memo)
            memo[(steps_left, current_pos)] = ans % MOD
            return memo[(steps_left, current_pos)]
        
        return count_steps(steps, 0, {})

class Solution:
    dp = {}
    
    def traverse(self, pos, steps, arrLen):
        key = (pos, steps)
        dp = self.dp
        
        if key not in dp:
            if pos<0 or pos>=arrLen:
                r = 0
            elif pos > steps:
                r = 0
            elif steps == 0:
                if pos == 0:
                    r = 1
                else:
                    r = 0
            else:
                r = (self.traverse(pos-1, steps-1,arrLen)+self.traverse(pos,steps-1,arrLen)+self.traverse(pos+1, steps-1, arrLen))%1000000007
            
            dp[key] = r
        
        return dp[key]
        
    def numWays(self, steps: int, arrLen: int) -> int:
        self.dp={}
        return self.traverse(0, steps, arrLen)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        kmod = pow(10, 9) + 7
        arrLen = min(steps, arrLen)
        dp = [0] * arrLen
        dp[0] = 1
        
        for s in range(steps):
            tmp = [0] * arrLen
            for i in range(arrLen):
                tmp[i] = dp[i]
                if i > 0:
                    tmp[i] += dp[i - 1]
                if i < arrLen - 1:
                    tmp[i] += dp[i + 1]
                tmp[i] %= kmod
            dp = list(tmp)
        return dp[0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = {(0, 0):1}
        N = 10 ** 9 + 7
        def dfs(x, t):
            if (x, t) not in memo:
                if x < 0 or x >= arrLen:
                    res = 0
                elif x > t or x > steps - t:
                    res = 0
                else:
                    res = dfs(x+1, t-1) + dfs(x, t-1) + dfs(x-1, t-1)
                memo[(x, t)] = res % N
            return memo[(x, t)]
        
        return dfs(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = {}
        def dfs(steps, ind):
            if (steps, ind) in dp:
                return dp[(steps, ind)]
            if steps == ind:
                return 1
            elif steps < ind:
                return 0
            res = 0
            res += dfs(steps-1, ind)
            if ind > 0:
                res += dfs(steps-1, ind-1)
            if ind < arrLen-1:
                res += dfs(steps-1, ind+1)
            dp[(steps, ind)] = res
            return res%(10**9+7)
        return dfs(steps, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        r, dp = min(arrLen, steps // 2 + 1), [0, 1]
        for t in range(steps):
            dp[1:] = [sum(dp[i-1:i+2]) for i in range(1, min(r+1, t+3))]
        return dp[1] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrlen: int) -> int:
        mod = 10 ** 9 + 7
        if arrlen == 1: return 1
        dp = [[0]*min(arrlen, steps+1) for _ in range(steps+1)]  # dp[a][b]: stays at position b after a steps
        dp[1][0] = 1
        dp[1][1] = 1
        for a in range(2, steps + 1):
            dp[a][0] = (dp[a-1][0] + dp[a-1][1]) % mod
            for b in range(1,min(arrlen, a+1)):
                if b == arrlen-1 or b == a :
                    dp[a][b] = (dp[a-1][b] + dp[a-1][b-1]) % mod
                else:
                    dp[a][b] = (dp[a-1][b] + dp[a-1][b+1] + dp[a-1][b-1]) % mod
        return dp[-1][0] 

from functools import lru_cache
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        @lru_cache(maxsize=None)
        def cc(step, pos):
            if step == steps:
                return 1 if pos == 1 else 0
            else:
                if pos == 1:
                    return cc(step+1, pos+1) + cc(step+1, pos)
                elif pos == arrLen:
                    return cc(step+1, pos-1) + cc(step+1, pos)
                else:
                    return cc(step+1, pos+1) + cc(step+1, pos-1) + cc(step+1, pos)
        mod = int(10 **9 + 7)
        return cc(0, 1) % mod
                    
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        max_len = min(steps, arrLen) #steps //2 + 1
        mod = 10**9 + 7
        dp = [[0] * (max_len+1) for _ in range(steps+1)]
        dp[1][0] = 1
        dp[1][1] = 1
        for i in range(2, steps+1):
            for j in range(max_len):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1] + (dp[i-1][j-1] if j > 0 else 0)) % mod
        
        for r in dp:
            print(r)
        return dp[steps][0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = collections.defaultdict(int)
        def dfs(index, curr):
            if curr == steps:
                if index == 0:
                    return 1
                else:
                    return 0
            if index > steps - curr:
                return 0
            key = (index, curr)
            if key in memo:
                return memo[key]
            res = 0
            if index > 0:
                res += dfs(index - 1, curr + 1)
            if index < arrLen - 1:
                res += dfs(index + 1, curr + 1)
            res += dfs(index, curr + 1)
            memo[key] = res
            return res
        
        return dfs(0, 0) % (10 ** 9 + 7)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if not arrLen or not steps:return 1
        if arrLen == 1: return 1 #stay all the time 
        
        shorter = min(steps, arrLen)
        dp = [[0 for _ in range(shorter)] for _ in range(steps+1)]
        dp[0][0] = 1
        dp[1][0] = 1
        
        for i in range(1, steps+1):
            for j in range(shorter):
                if j == 0:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
                elif j == shorter - 1:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1]
        return dp[-1][0] % (10**9 + 7)
    
        
                    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        
        dp = {}
        MOD = 10**9 + 7
        
        def moveOnce(i0, steps0):
            if steps0 == 0:
                if i0 == 0:
                    return 1
                return 0
            
            if (i0, steps0) in dp:
                return dp[(i0, steps0)]
            if i0 > steps0:
                ans = 0
            else:
                if i0 == 0:
                    ans = moveOnce(i0+1, steps0-1) + moveOnce(i0, steps0-1)
                elif i0 == arrLen-1:
                    ans = moveOnce(i0-1, steps0-1) + moveOnce(i0, steps0-1)
                else:
                    ans = moveOnce(i0+1, steps0-1) + moveOnce(i0-1, steps0-1) + moveOnce(i0, steps0-1)
            dp[(i0, steps0)] = ans % MOD
            return dp[(i0, steps0)]
        
        return moveOnce(0, steps)

class Solution:
    def numWays(self, s: int, a: int) -> int:
        MOD = 1000000007
        mem = {}
        def f(s, a, i):
            if (s, i) in mem:
                return mem[(s,i)]
            if not s:
                if i:
                    return 0
                return 1
            if i < 0 or i == a:
                return 0
            if i > s:
                return 0
            ans = 0
            #stay
            ans += f(s-1, a, i)
            #left
            ans += f(s-1, a, i-1)
            #right
            ans += f(s-1, a, i+1)
            
            mem[(s,i)] = ans
            return ans%MOD
            
        return f(s, a, 0)
            
            
        
            
    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        if not arrLen or not steps:return 1
        if arrLen == 1: return 1 #stay all the time 
        
        shorter = min(steps, arrLen)#the position cannot be larger than the min(steps, arrLen)
        dp = [[0 for _ in range(shorter)] for _ in range(steps+1)]
        dp[0][0] = 1
        dp[1][0] = 1
        
        for i in range(1, steps+1):
            for j in range(shorter):
                if j == 0:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
                elif j == shorter - 1:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1]
        return dp[-1][0] % (10**9 + 7)
    
        
                    


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        self.dic = dict()
        self.search(steps,arrLen,0) 
        return self.search(steps,arrLen,0)%(10**9+7)
        
        
    def search(self,steps,arrLen,start):
        if (steps,start) in self.dic:
            return self.dic[(steps,start)]
        if start>steps:
            return 0
        if start == 0 and steps == 0:
            return 1
        
        output = 0
        output += self.search(steps-1,arrLen,start)
        if start>0:
            output += self.search(steps-1,arrLen,start-1)
        if start<arrLen-1:
            output += self.search(steps-1,arrLen,start+1)
        self.dic[(steps,start)] = output
        
        return output
        


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        arrLen = min(steps+1, arrLen)
        num = [0 for i in range(arrLen)]
        num[0] = 1
        modulo = 10**9+7
        for i in range(steps):
            newnum = [num[i] for i in range(arrLen)]
            for i in range(arrLen):
                if i > 0:
                    newnum[i] += num[i-1]
                if i < arrLen-1:
                    newnum[i] += num[i+1]
                if newnum[i] > modulo:
                    newnum[i] %= modulo
            num = newnum
        return num[0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9+7
        memory = {}
        
        def helper(i, steps):
            if i < 0 or i == arrLen:
                return 0
            if i > steps:
                return 0
            if i == steps:
                return 1
            prev = memory.get((i, steps))
            if prev is not None:
                return prev

            stay = helper(i, steps-1)
            left = helper(i-1, steps-1)
            right = helper(i+1, steps-1)
            
            result = (stay + left + right) % MOD
            memory[(i, steps)] = result
            
            return result
        
        return helper(0, steps) 

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9+7
        @lru_cache(None)
        def dp(index,steps):
            if index < 0 or index >= arrLen:
                return 0
            if steps == 0:
                if index == 0:
                    return 1
                return 0
            return (dp(index-1,steps-1) + dp(index+1,steps-1) + dp(index,steps-1))%mod
        
        return dp(0,steps)%mod

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
  
        @lru_cache(None)
        def nw(pos, left):
            
            if pos < 0:
                return 0
            
            if pos >= arrLen:
                return 0
            
            if left == 0 and pos == 0:
                return 1
            
            if left == 0 and pos != 0:
                return 0
            
            res = nw(pos+1,left-1)
            res += nw(pos-1,left-1)
            res += nw(pos,left-1)
            
            return res
            
        res = nw(0,steps)
            
        return res % 1000000007

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9+7
        memory = {}
        
        def helper(i, steps):
            if i < 0 or i == arrLen:
                return 0
            if i > steps:
                return 0
            if i == steps:
                return 1
            prev = memory.get((i, steps))
            if prev is not None:
                return prev
            
            steps -= 1
            stay = helper(i, steps)
            left = helper(i-1, steps)
            right = helper(i+1, steps)
            
            memory[(i, steps+1)] = (stay + left + right)
            
            return memory[(i, steps+1)]
        
        return helper(0, steps) % MOD

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        maxPos = min(steps, arrLen)
        mod = 10 ** 9 + 7
        dp = [[0] * (maxPos + 1) for _ in range(steps + 1)]
        dp[1][0] = 1
        dp[1][1] = 1
        
        for s in range(2, steps + 1):
            for p in range(maxPos):
                dp[s][p] = dp[s-1][p] + dp[s-1][p+1]
                dp[s][p] += dp[s-1][p-1] if p > 0 else 0
                dp[s][p] %= mod
        
        return dp[steps][0]
    
# initial state is critical
# 0 step is meaningless
# 1 step could be set manually


from collections import defaultdict
def numWays(steps: int, arrLen: int) -> int:
    if steps is None or steps < 0 or not arrLen:
        return 0
    arrLen = min(arrLen, steps + 1)
    f = [[0] * arrLen for _ in range(steps + 1)]
    f[0][0] = 1
    for i in range(1, steps + 1):
        for j in range(min(arrLen, i+1)):
            f[i][j] += f[i - 1][j]
            if j > 0:
                f[i][j] += f[i - 1][j - 1]
            if j < arrLen - 1:
                f[i][j] += f[i - 1][j + 1]
    return f[steps][0] % (10 ** 9 + 7)
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        return numWays(steps,arrLen)


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = {}
        const = 10**9+7
        def num(step, idx) -> int:
            if (step, idx) in memo:
                return memo[(step, idx)]
            if idx < 0 or idx >= arrLen:
                return 0
            if step <= 0:
                return idx == step
            if idx > step:
                return 0
            elif idx == step:
                return 1
            else:
                memo[(step, idx)] = num(step-1, idx) + num(step-1, idx-1) + num(step-1, idx+1)  
                if memo[(step, idx)] > const:
                    memo[(step, idx)] = memo[(step, idx)]%const
                return memo[(step, idx)]
        return num(steps, 0)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        memo = {}
        mod = 10**9 + 7
        
        return self.dfs(steps, arrLen, 0, memo, mod)
    
    def dfs(self, steps, arrLen, pos, memo, mod):
        if (steps, pos) in memo:
            return memo[(steps, pos)]
        
        if steps == 0:
            if pos == 0:
                memo[(steps, pos)] = 1
                return 1
            return 0
        
        tmp = 0
        for d in (-1, 0, 1):
            nxt = pos + d
            if not (0 <= nxt < arrLen) or (nxt > steps): continue
            tmp += self.dfs(steps-1, arrLen, nxt, memo, mod)%mod
            
        tmp %= mod
            
        memo[(steps, pos)] = tmp
        
        return tmp
            
            
            


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        l = min(steps, arrLen)
        
        dp = [0] * l
        dp[0] = 1
        
        for i in range(steps):
            nextdp = [0] * l
            for j in range(l):
                if j - 1 >= 0: # LEFT
                    nextdp[j] += dp[j-1]
                nextdp[j] += dp[j]
                if j + 1 < l:
                    nextdp[j] += dp[j+1]
                nextdp[j] %= (10**9+7)
            dp = nextdp
            
        return dp[0] % (10**9+7)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        ### dp[steps][pos]
        modulo = 10 ** 9 + 7
        
        maxPos = min(steps + 1, arrLen)
        
        dp = [ [0 for _ in range(maxPos+1)] for _ in range(steps + 1) ]
        
        dp[1][0], dp[1][1] = 1, 1
        
        ### dp[s][p] = dp[s-1][p] + dp[s-1][p-1] + dp[s-1][p+1]
        
        for i in range(2, steps+1):
            for j in range(maxPos):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1]) % modulo
                    
                if j - 1 >= 0:
                    dp[i][j] += dp[i-1][j-1] % modulo
        
        return dp[steps][0]

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        waysDict = {}
        return self.numWaysRec(steps, arrLen, 0, waysDict)%(10**9 + 7)
    
    def numWaysRec(self, steps: int, arrLen: int, currentPos: int, waysDict: dict) -> int:
        if (steps == currentPos) or (steps == 1 and currentPos == 0):
            return 1
        totalWays = 0
        for nextMove in self.validMoves(steps,currentPos,arrLen):
            if (nextMove,steps-1) in waysDict:
                totalWays += waysDict[(nextMove, steps-1)]
            else:
                result = self.numWaysRec(steps-1,arrLen,nextMove, waysDict)
                waysDict[(nextMove,steps-1)] = result
                totalWays += result
        return totalWays
    
    def validMoves(self, steps: int, currentPos: int, arrLen: int) -> list:
        validList = []
        #Check left move
        if (currentPos - 1 <= steps-1) and currentPos - 1 >= 0:
            validList.append(currentPos-1)
        #Check stay move
        if (currentPos <= steps-1):
            validList.append(currentPos)
        #Check right move
        if (currentPos+1 <= steps-1) and currentPos +1 < arrLen:
            validList.append(currentPos+1)
        
        return validList


class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        #dp = [steps][10^6]
        dp = [defaultdict(int) for _ in range(steps+1)]
        
        dp[0][0] += 1
        dp[1][1] += 1
        dp[1][0] += 1
        
        modulo = pow(10, 9) + 7
        
        for i in range(2, steps+1):
            for j in dp[i-1].keys():
                remain = j - (steps - i)
                if j < 0:
                    break
                if j + 1 < arrLen:
                    dp[i][j + 1] += dp[i-1][j]
                if j - 1 >= 0:
                    dp[i][j - 1] += dp[i-1][j]
                dp[i][j] += dp[i-1][j]
        
        return dp[steps][0] % modulo

from collections import defaultdict
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int: 
        dp = {}
        for i in range(steps+1):
            dp[i] = defaultdict(int) 
        
        # dp[i][j] stores the number of ways to reach index j using i steps
        dp[1][1] += 1 # move right
        dp[1][0] += 1 # stay
        # cannot move left at this moment, as index j must satisfy 0 <= sums < arrLen 
        
        for i in range(2, steps+1):
            # index is where we are after the first i-1 steps
            for index in dp[i-1].keys():
                if index + 1 < arrLen: # move right  
                    dp[i][index + 1] += dp[i-1][index]
                
                if index - 1 >= 0: # move left
                    dp[i][index - 1] += dp[i-1][index]
                
                dp[i][index] += dp[i-1][index] # stay
                
        return dp[steps][0]   % (10 ** 9 + 7) 

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        dp = {}
        for i in range(steps+1):
            dp[i] = collections.defaultdict(int) 
        
        # dp[i][j] stores the number of ways to reach index j using i steps
        dp[1][1] += 1 # move right
        dp[1][0] += 1 # stay
        # cannot move left at this moment, as index j must satisfy 0 <= sums < arrLen 
        
        for i in range(2, steps+1):
            # index is where we are after the first i-1 steps
            for index in dp[i-1].keys():
                if index + 1 < arrLen: # move right  
                    dp[i][index + 1] += dp[i-1][index]
                
                if index - 1 >= 0: # move left
                    dp[i][index - 1] += dp[i-1][index]
                
                dp[i][index] += dp[i-1][index] # stay
                
        return dp[steps][0]   % (10 ** 9 + 7)