---

Problem 509

---

Divisor Nim

Anton and Bertrand love to play three pile Nim.
However, after a lot of games of Nim they got bored and changed the rules somewhat.
They may only take a number of stones from a pile that is a proper divisor of the number of stones present in the pile.
E.g. if a pile at a certain moment contains 24 stones they may take only 1,2,3,4,6,8 or 12 stones from that pile.
So if a pile contains one stone they can’t take the last stone from it as 1 isn’t a proper divisor of 1.
The first player that can’t make a valid move loses the game.
Of course both Anton and Bertrand play optimally.

The triple (a,b,c) indicates the number of stones in the three piles.
Let S(n) be the number of winning positions for the next player for 1 ≤ a, b, c ≤ n.
S(10) = 692 and S(100) = 735494.
Find S(123456787654321) modulo 1234567890.

---

约数取石子游戏

安东和伯特兰很喜欢玩三堆取石子游戏。
然而，在玩了许多次之后，他们觉得过于无聊，打算修改一下游戏规则。
他们约定，从一堆中取出的石子数目，必须是这一堆石子数目的真约数。
例如，如果其中一堆目前有24颗石子，他们就只能从中取出1、2、3、4、6、8或12颗石子。
因此，如果一堆中只剩一颗石子，那么他们不能将这颗石子取走，因为1不是1的真约数。
谁先无法再取走石子谁就输了。
当然，安东和伯特兰两个人都会采取最佳策略。

三元组(a,b,c)表示这三堆石子分别的数目。
对于所有1 ≤ a, b, c ≤ n，记S(n)为所有必胜态的数目。
已知S(10) = 692以及S(100) = 735494。
求S(123456787654321) modulo 1234567890。

---