MathDB

Let

W = \ldots x_{-1}x_0x_1x_2 \ldots

be an infinite periodic word consisting of only the letters

a

and

b

. The minimal period of

W

2^{2016}

. Say that a word

U

appears in

W

if there are indices

k \le \ell

such that

U = x_kx_{k+1} \ldots x_{\ell}

. A word

U

is called special if

Ua, Ub, aU, bU

all appear in

W

. (The empty word is considered special) You are given that there are no special words of length greater than 2015.
Let

N

be the minimum possible number of special words. Find the remainder when

N

is divided by

1000

. Proposed by Yang Liu

Problem Statement