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位數作為答案。