My approach was for each i=0,1,…,N-1, we can get the distribution of values on the next turn if we start the current turn at i. Then we can put this all in a matrix M, and our answer is M^k * [0 1 0 0 0 0 0 0 … 0]^T.
This is too slow tho… can someone help hint / give the solution?