Back to the First Tile

Hard

A robot stands in a narrow corridor of length tiles numbered from 0 to length - 1; right now it is on tile 0. On each move the robot does one of three things: steps to the neighbouring tile on the left, steps to the neighbouring tile on the right, or stays where it is. It must never leave the corridor. In how many ways can the robot make exactly steps moves and end up back on tile 0? Two ways differ if their sequences of moves differ. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

steps=2, length=3 → 2

Either stay put twice, or step right and step back: 2 ways.

Example 2

steps=4, length=1 → 1

There is only one tile, so the only option is to stay put for all 4 moves.

Example 3

steps=3, length=10 → 4

Stay three times, plus three ways to place one stay around a right-then-left pair: 4 in total.

Constraints

1 ≤ steps ≤ 500
1 ≤ length ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

steps=2, length=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.