409 : 極端なNim

n を正の整数とする。以下のような nim (訳注:いくつかの山に分かれた石を交互にとっていくゲーム, Problem 301を参照のこと) の配置について考えよう :

• n 個の空でない山がある.

• それぞれの山の大きさは 2&sup{n}; 未満である.

• 同じサイズの山は存在しない.

上記の条件を満たす必勝nim配置(最初のプレイヤーが必勝法を持つ配置)の数を W(n) としよう. 例として, W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360, W(100) mod 1 000 000 007 = 384777056 となる.

W(10 000 000) mod 1 000 000 007 を求めよ。