There's a board with n squares in a horizontal row.
You start in the leftmost square, and roll a 3-faced dice.
3 possible outcomes for a single roll of the die:
- Left: you move 1 step to the left, if possible.
- None: you stay where you are
- Right: you move 1 step to the right, if possible.
You want to roll the dice exactly t times, and end up at the rightmost square on the last roll.
If you arrive at the rightmost square before t rolls, your only valid move is None.
You need to determine the number of valid (meaning, for instance, that you don't count sequences that try to move left or right from the rightmost square), unique sequences of dice rolls, for given (t,n) pairs. As the answer may be large, give it modulo 1000000007 (ie. 10^9+7).
- t is a positive integer s.t. t <= 1000
- n is a positive integer s.t. 2 <= n <= 1000
Sample testcases:
- t=1, n=2, answer=1
- t=3, n=2, answer=3
- t=4, n=3, answer=7
The shortest code in bytes wins.
t=3, n=2
, with the sequencesRSS, SRS, SSR, RLR
. Am I missing a rule? \$\endgroup\$