Putnam 2009 B6

Prove that for every positive integer $n$, there is a sequence of integers $a_0, a_1, \dots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$, or of the form $b\,\mathrm{mod} c$ for some earlier positive terms $b$ and $c$. [Here $b\,\mathrm{mod} c$ denotes the remainder when $b$ is divided by $c$, so $0 \leq (b\,\mathrm{mod} c) < c$.]