좌석 N 개가 한 줄로 있습니다. N 명의 사람이 한 명씩 아래 규칙에 따라 좌석을 채웁니다:

1. 어떤 좌석에 인접한 좌석이 (하나든 둘이든) 모두 비었다면 그 좌석에 앉습니다.
2. 만일 그런 좌석이 없고 인접한 좌석중 하나가 차 있는 좌석이 있다면 그 좌석에 앉습니다.
3. 그것도 아니라면 남은 좌석 중 하나에 앉습니다.

T(10) = 61632 이고 T(1 000) mod 100 000 007 = 47255094 입니다.

T(1 000 000) mod 100 000 007 값을 구하세요.