Элис и Боб наслаждаются игрой в Ним каждый день. Однако, им уже поднадоел обычный Ним с тремя кучками.
Поэтому они добавили еще одно правило:

- Нельзя создавать две кучки одинакового размера.

Тройка (a,b,c) описывает размеры трех кучек в текущем положении.
При игре с дополнительным правилом (2,4,5) является одним из проигрышных положений для следующего игрока.

Это видно на следующем примере:
- Элис ходит на (2,4,3)
- Боб ходит на (0,4,3)
- Элис ходит на (0,2,3)
- Боб ходит на (0,2,1)

В отличие от обычного Нима с тремя кучками, в новом варианте игры положение (0,1,2) и его перестановки являются проигрышными для следующего игрока.

Для целого N определим F(N) как сумму a+b+c для всех проигрышных положений для следующего игрока, где 0 < a < b < c < N.

Например, F(8) = 42, потому что существует 4 проигрышных положения для следующего игрока: (1,3,5), (1,4,6), (2,3,6) и (2,4,5).
Также можно показать, что F(128) = 496062.

Найдите последние 9 цифр F(10¹⁸).