ProjectEuler 364 Comfortable distance - 拼圖

364. Comfortable distance

http://projecteuler.net/problem=364


有 N 個座位排成一排，N 個人依序入座並把座位坐滿，但是入座條件如下：

1. 當有某座位的左右兩個相鄰的座位都沒人時，他就坐這裡。

2. 當已經沒有上述條件的座位時，就退而求其次，挑有一邊沒有坐人的座位坐下。

3. 當已經沒有上述條件的座位時，就挑剩下的座位坐。


使 T(N) 表示為有 N 個人要用上述條件去坐滿 N 個座位時的方法數

下列圖示表示出 T(4) = 8

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│●│　│　│　│→│●│　│●│　│→│●│　│●│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│●│　│　│　│→│●│　│　│●│→│●│●│　│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│●│　│　│　│→│●│　│　│●│→│●│　│●│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│　│●│　│　│→│　│●│　│●│→│●│●│　│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│　│　│●│　│→│●│　│●│　│→│●│　│●│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│　│　│　│●│→│●│　│　│●│→│●│●│　│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│　│　│　│●│→│●│　│　│●│→│●│　│●│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘

┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐　┌─┬─┬─┬─┐
│　│　│　│●│→│　│●│　│●│→│●│●│　│●│→│●│●│●│●│
└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘　└─┴─┴─┴─┘


我們可以驗證出 T(10) = 61632 而 T(1000) mod 100000007 = 47255094。


請算出 T(1000000) mod 100000007。

--