N 個の一列に並んだ座席がある. N 人の人たちが以下のルールに従って次々に座席を埋めていく: 1.隣には誰も座っていないこと. 2.最初の人はどの座席を選んでも良い. 3.次の人はそれぞれにすでに座った人の座席からルール1に違反しない限りで最も離れた座席を選ぶ. 条件を満たす選択が一つ以上ある場合は, 最左の座席を選ぶ. ルール1により, 座席のいくつかは確実に空いたままとなり, 座席に座ることのできる最大人員は N 未満となる (N > 1 のとき). N=15 の時に可能な席順は以下の通り:最初の人が正しく選択すれば, 15個の座席なら7人が座れることがわかる. また最初の人は座れる人数を最大にする選択肢を9つ持っていることがわかる. 一列に並んだN個の座席に対し 最初の人が座席に座れる人数を最大にできる選択肢の数をf(N)としよう. f(15) = 9, f(20) = 6, そして f(500) = 16. また, 1 <= N <= 20 に対し シグマ(f(N)) = 83 そして 1 <= N <= 500 に対し シグマ(f(N)) = 13343 1 <= N <= 1兆 における シグマ(f(N)) を求めよ. 回答として末尾8桁を答えよ.