364 : 気楽な距離

N 個の一列に並んだ座席がある. N 人の人たちが以下のルールに従って次々に座席を埋めていく.

1. 隣接する座席が空いている座席があれば, その座席を取る.

2. そのような座席がなく, 隣接する座席が一つのみ埋まっている座席があれば, その座席を取る.

3. それ以外の場合は, 残っている利用可能な座席を取る.

このルールで N 人の人たちが N 個の座席を取るときの可能性の数を T(N) としよう. 以下の図により T(4)=8 であることがわかる.

p364_comf_dist.gif

T(10) = 61632, そして T(1 000) mod 100 000 007 = 47255094 となることが確かめられる.

T(1 000 000) mod 100 000 007 を求めよ.