从 $1$ 到 $n$ 的所有整数的有序列表开始。从左到右，删除第一个数字，然后删除所有其他数字，直到列表末尾。从右到左重复该过程，删除最右边的数字以及左边数字中的所有其他数字。继续从左到右、从右到左交替删除所有其他数字，直到剩下一个数字。

从 $n=9$ 开始，我们有：
$\underset{―}{1}2\underset{―}{3}4\underset{―}{5}6\underset{―}{7}8\underset{―}{9}$
$2\underset{―}{4}6\underset{―}{8}$
$\underset{―}{2}6$
$6$

设 $P(n)$ 为以 $n$ 长度的列表开头的最后一个数字。
设${\displaystyle S(n)=\sum _{k=1}^{n}P(k)}$。
给定 $P(1)=1$、$P(9)=6$、$P(1000)=510$、$S(1000)=268271$。

找到 $S({10}^{18})mod987654321$。