Стол в форме правильного шестиугольника с длиной стороны $N$ разделен на равносторонние треугольники с длиной стороны $1$. На изображении ниже показан случай с $N = 3$.

Блоха пренебрежительно малого размера прыгает по столу. Блоха начинает путь в центре стола. Далее, с каждым шагом она выбирает один из шести углов стола и перепрыгивает на среднюю точку между своим текущим расположением и выбранным углом.

Для каждого треугольника $T$ обозначим минимальное количество прыжков, необходимое блохе, чтобы попасть внутрь треугольника $T$, как $J(T)$. Приземление на сторону или вершину треугольник $T$ не засчитывается.

Например, для обозначенного звездочкой на изображении треугольника $J(T) = 3$: прыжок на половину пути от центра до F, затем к C, затем к E.

Пусть $S(N)$ будет суммой $J(T)$ для всех треугольников $T$, расположенных на верхней половине стола и направленных вершиной вверх. Такие треугольники для случая $N = 3$ закрашены черным на изображении выше.

Известно, что $S(3) = 42$, $S(5) = 126$, $S(123) = 167178$ и $S(12345) = 3185041956$.

Найдите $S(123456789)$.