Alice and Bob have enjoyed playing Nim every day. However, they finally got bored of playing ordinary three-heap Nim.
So, they added an extra rule:
- Must not make two heaps of the same size.
The triple (a,b,c) indicates the size of three heaps.
Under this extra rule, (2,4,5) is one of the losing positions for the next player.
- Alice moves to (2,4,3)
- Bob moves to (0,4,3)
- Alice moves to (0,2,3)
- Bob moves to (0,2,1)
Unlike ordinary three-heap Nim, (0,1,2) and its permutations are the end states of this game.
For an integer N, we define F(N) as the sum of a+b+c for all the losing positions for the next player, with 0 < a < b < c < N.
For example, F(8) = 42, because there are 4 losing positions for the next player, (1,3,5), (1,4,6), (2,3,6) and (2,4,5).
We can also verify that F(128) = 496062.
Find the last 9 digits of F(1018).
对于一个整数N和所有满足0 < a < b < c < N的必败局面(a,b,c)，记所有a+b+c的和为F(N)。
例如 F(8) = 42，因为满足上述条件的必败局面共有4组，分别是(1,3,5)，(1,4,6)，(2,3,6)和(2,4,5)。
我们同样也可以验证 F(128) = 496062。