边长为$N$的正六边形表被分成边长为$1$的等边三角形。下图是 $N=3$ 情况的说明。

一只大小可以忽略不计的跳蚤正在这张桌子上跳跃。跳蚤从桌子中央开始。此后，在每一步中，它都会选择桌子的六个角之一，并跳转到当前位置和所选角之间的中点。

对于每个三角形 $T$，我们用 $J(T)$ 表示跳蚤到达 $T$ 内部所需的最小跳跃次数。落在 $T$ 的边或顶点上是不够的。

例如，对于图中标有星号的三角形，$J(T)=3$：从中心向 F 跳一半，然后向 C 跳，然后向 E 跳。

令 $S(N)$ 为表格上半部分中所有指向上方的三角形 $T$ 的 $J(T)$ 之和。对于 $N=3$ 的情况，这些是上图中涂成黑色的三角形。

已知 $S(3)=42$、$S(5)=126$、$S(123)=167178$ 和 $S(12345)=3185041956$。

查找$S(123456789)$。