Pogo Stick Competition

Chef is participating in a pogo stick race. In this competition, there are $N$ squares (numbered $1$ through $N$) in a row. Chef must choose a starting square, enter this square and start jumping on his pogo stick. In each jump, if Chef is at a square $s$, then he can only jump to the square $s+K$. If square $s+K$ does not exist, Chef jumps out of the row of squares and the race ends for him. It i