## Algorithm

Problem Name: 1269. Number of Ways to Stay in the Same Place After Some Steps

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 is still at index `0` after exactly `steps` steps. Since the answer may be too large, return it modulo `109 + 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 <= 106`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numWays = function (steps, arrLen) {
const MOD = 10 ** 9 + 7
const memo = Array.from({ length: (steps >> 1) + 1 }, () =>
Array(steps + 1).fill(-1)
)
return dp(0, steps)
function dp(i, steps) {
if (steps === 0 && i === 0) return 1
if (i < 0 || i >= arrLen || steps === 0 || i > steps) return 0
if (memo[i][steps] !== -1) return memo[i][steps]
return (memo[i][steps] =
((dp(i + 1, steps - 1) % MOD) +
(dp(i - 1, steps - 1) % MOD) +
(dp(i, steps - 1) % MOD)) %
MOD)
}
}
``````
Copy The Code &

Input

cmd
steps = 3, arrLen = 2

Output

cmd
4