ISL 2011 C6

Let $n$ be a positive integer and let $W=\ldots x_{-1} x_{0} x_{1} x_{2} \ldots$ be an infinite periodic word consisting of the letters $a$ and $b$. Suppose that the minimal period $N$ of $W$ is greater than $2^{n}$. A finite nonempty word $U$ is said to appear in $W$ if there exist indices $k \leq \ell$ such that $U=x_{k} x_{k+1} \ldots x_{\ell}$. A finite word $U$ is called ubiquitous if the four words $U a, U b, a U$, and $b U$ all appear in $W$. Prove that there are at least $n$ ubiquitous finite nonempty words.