Number of Ways to Stay in the Same Place After Some Steps

Start at index 0 of an array with arrLen positions. On each of exactly steps turns, move one position left, move one position right, or remain at your current position. Every intermediate position must lie inside the array. Count the distinct sequences of actions that finish at index 0, and return the count modulo 1000000007.

Example 1:

Input: steps = 1
arrLen = 5

Output: 1

Explanation: With only one action, staying at index 0 is the only way to finish there. Moving right would end at index 1, and moving left is outside the array.

Example 2:

Input: steps = 5
arrLen = 1

Output: 1

Explanation: The array has only index 0, so every action must be Stay. The sequence of five Stay actions is the only valid sequence.

Example 3:

Input: steps = 3
arrLen = 3

Output: 4

Explanation: The four sequences are Stay-Stay-Stay, Stay-Right-Left, Right-Stay-Left, and Right-Left-Stay. Reaching index 2 would leave too few actions to return to 0.

Constraints:

• 1 <= steps <= 500
• 1 <= arrLen <= 1000000