472. Comfortable Distance II
http://projecteuler.net/problem=472
现有一排N个座位，并有N人遵循下述规则依序就座：
1. 所有人皆不相邻。
2. 第一个人可以选择任意座位。
3. 接下来每个人都在不违反规则1的前提下，选择最远离所有人的座位。如果有大于一个
座位符合条件，则选择所有符合条件的座位中最左边的那一个。
注意到因为规则1的关系，必然会有一些座位是自始至终没人坐的，故有座位能坐的人必
然小于N（在N>1时）。
下图是当N=15时所有可能的座位组合（数字代表就座顺序）：
http://projecteuler.net/project/images/p472_n15.png
我们可以发现如果第一个人选的座位恰当，则有7个人能就座。
此时，第一个人有9个选择使就座人数达到最大。
令f(N)为有N个座位时，第一个人有多少选择使得就座人数最大。所以有f(1) = 1、
f(15) = 9、f(20) = 6以及f(500) = 16。
同时Σf(N) = 83为1≦N≦20时的和，Σf(N) = 13343为1≦N≦500时的和。
请求出Σf(N)在1≦N≦10^12时的和，并给出最后8位数作为答案。