count number of valid, unique sequences for moving on a 1xn board
Python, 74

f=lambda t,n,i=1:i==n or t*i and sum(f(t-1,n,i+d)for d in[-1,0,1])%(1e9+7)


A recusive solution. The current position i is stored 1-indexed as an optional argument. 


If the current position i==n, we've arrived at the final square and are forced to stay still, giving 1 path.
Otherwise,

If the remaining time t==0, we've run out of time, so there's 0 paths.
If the current position i==0, we've run off the left end already, so there's 0 paths.

If neither of those was true, there we recurse. We add up the path counts for each of the directions left, none, and right, corresponding to displacements [-1,0,1], and take the result modulo 1e9+7 as required.


An alternative solution that uses eval with string substitution to do the sum. Same number of chars. Note the use of unary + to start the sum.

f=lambda t,n,i=1:i==n or t*i and eval(3*'+f(t-1,n,i+%d)'%(-1,0,1))%(1e9+7)




Here's another a solution that is surely short for any language with built-in matrices, so anyone who can golf it is welcome to take it.

Let M be the n*n transition matrix for the walk, which is a tridiagonal banded matrix with 1's on the main diagonal and the diagonals above and below it, except for a 0 for movement left from the rightmost cell.

1 1 0 0 0
1 1 1 0 0
0 1 1 1 0
0 0 1 1 1
0 0 0 0 1


Then, the output is (1,n) entry of the matrix power M^t.