一排有$N$座位。 $N$人陆续前来，按照以下规则坐满：

1. 没有人坐在另一个人旁边。
2. 第一个人选择任意座位。
3. 随后的每个人都会选择距离已就座的其他人最远的座位，只要不违反规则 1。如果有多个选择满足此条件，则该人选择最左边的选择。

请注意，由于规则1，肯定会有一些座位空着，并且可容纳的最大人数小于$N$（对于$N>1$）。

以下是 $N=15$ 可能的座位安排：

我们看到，如果第一人选择正确，$15$ 座位最多可容纳 $7$ 人。
我们还可以看到，第一人有 $9$ 选择，以最大化可容纳的人数。

令 $f(N)$ 为第一人必须最大化 $N$ 连续座位的乘坐人数的选择数量。因此，$f(1)=1$、$f(15)=9$、$f(20)=6$ 和 $f(500)=16$。

此外，$\sum f(N)=83$ 适用于 $1\le N\le 20$，$\sum f(N)=13343$ 适用于 $1\le N\le 500$。

查找 $1\le N\le {10}^{12}$ 的 $\sum f(N)$。请给出答案的最后一位 $8$ 数字。