This problem contains three sub-problems and a meta-problem. Enter the answer to the meta-problem as final answer.

---

Sub-problem: Max And

The numbers $1$ to $n$ are to be divided into two groups $A$ and $B$. Let $I(n)$ be the maximum possible value of $$\sum _{a\in A}\sum _{b\in B}a\wedge b$$ where $\wedge$ is the bitwise AND operator.

It can be verified that $I(10)=50$, if for example $A=\{1,4,7,10\}$ and $B=\{2,3,5,6,8,9\}$, although there are a number of other solutions as well.

Find $I(1000)$.

---

Sub-problem: Max Xor Sum

For two integers $x,y$, write $[x,y]$ for the bitwise XOR of $x^2$ and $y^2$.

A finite sequence of integers $a_0,a_1,\dots ,a_r$ satisfies the following properties:

• $1\le a_i\le N$ for all $0\le i\le r$;
• $[a_{i-1},a_i]<[a_i,a_{i+1}]$ for all $0<i<r$.

Let $X(N)$ be the maximal possible value of the sum $\sum _{i=1}^r[a_{i-1},a_i]$.

For example, $X(4)=71$ can be achieved with the sequence $2,1,3,2,4,3$. Also $X(10)=702$.

Find $X(1000)$.

---

Sub-problem: Unreachable Nim

Two players are playing a three-pile Nim game. The game status is an ordered triple $(a,b,c)$, representing the number of stones in each pile.

A player will always make a winning move, if there is at least one; otherwise, any valid move can be made, unless there is no valid move left, at which point the game ends.

A game status is called unreachable if it never appears during the game, unless when it is the initial position. For example, the game status $(1,1,1)$ is unreachable.

Let $C(N)$ be the number of unreachable statuses with $0\le a,b,c<N$. You are given $C(10)=123$.

Find $C(1000)$.

---

Meta-problem:

A sequence $M$ is defined by

• $M(0)=I(1000)$;
• $M(1)=X(1000)$;
• $M(2)=C(1000)$;
• $M(k)=M(k-1)M(k-2)M(k-3)$ for $k\ge 3$.

You are given $M(4)\equiv 457587170(\mathrm{mod}{10}^9+7)$.

Find $M(1000)mod({10}^9+7)$.

Hint: one may assume that the given value of $M(4)$ is correct.