N個の一列に並んだ座席がある. N人の人たちが以下のルールに従って次々に座席を埋めていく. 1.隣接する座席が空いている座席があれば, その座席を取る. 2.そのような座席がなく, 隣接する座席が一つのみ埋まっている座席があれば, その座席を取る. 3.それ以外の場合は, 残っている利用可能な座席を取る. このルールで N 人の人たちが N 個の座席を取るときの可能性の数を T(N) としよう. 以下の図により T(4)=8 であることがわかる.T(10) = 61632, そして T(1000) mod 100000007 = 47255094 となることが確かめられる. T(100万) mod 100000007 を求めよ.