翻转卡片
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

多多喜欢翻转卡片。他一共有张卡片，初始时卡片被排成一行，并且全部背面朝上。
多多每次随机选择一张背面朝上的卡片进行翻转，如果翻转该卡片后存在两张相邻的卡片都是正面朝上，那么该卡片不可被翻转，多多会重新随机选择卡片。
当不存在任何一张卡片可以被翻转时，多多会停下来数一数正面朝上的卡片数量。
他想问问你：最后正面朝上的卡片数量的期望值是多少？

输入描述:

第一行输入一个整数，代表询问的次数。
接下来行，每行输入一个正整数，代表卡片的总数。

输出描述:

输出行，对于每次询问输出正面朝上的卡片数量的期望值，并对结果取模。
设答案为，如果满足，那么取模后的答案为
示例1

输入

复制 
5
1
2
3
4
5

输出

复制 
1
1
666666673
2
500000006

说明

假设代表背面朝上，代表正面朝上，代表第张被翻转的卡片。

当时，翻转卡片后会有种情况：
所以期望值为

当时，翻转卡片后会有种情况：，
所以期望值为

当时，翻转卡片后会有种情况：，，
所以期望值为2\times\frac{1}{3}+2\times\frac{1}{3}+1\times\frac{1}{3}(mod\ 1000000007) = \frac{5}{3}(mod\ 1000000007)=666666673