一排有$N$个座位。 $N$人按照以下规则依次填补席位：

1. 如果有相邻座位未被占用的座位，请就座。
2. 如果没有该座位，且有任何座位仅占用一个相邻座位，则乘坐该座位。
3. 否则请选择剩余的可用座位之一。

令$T(N)$为在给定规则下$N$个座位被$N$个人占据的可能性数量。
下图显示$T(4)=8$。

我们可以验证 $T(10)=61632$ 和 $T(1000)mod100000007=47255094$。

求 $T(1000000)mod100000007$。