问题 G: 飞行棋

今晚飞行棋大师Legend_dy 不是很想学习于是邀请 Jeneveuxpas 和 LZVSDY 一起来玩把 飞行棋，赛前放下豪言势必要血虐他们。没想到成了小丑，四连胜就此终结。

Jeneveuxpas 三辆飞机抵达终点，剩下的一辆飞机也已率先进入直道，本以为自己已经胜券 在握了，没想到连摇了十来次骰子都没能摇进终点，让LZVSDY 后来居上夺走了胜利的果 实，他非常难过百思不得其解提出了这样一个问题： 有n+1个的格子编号0到n，0号格子为起点，n号格子为终点。 花费1的代价等概率随机[1,n] 中的一个整数x，向终点走x步，若达到终点还有剩余步数 则反向行走。如果随机到了数字n并且未抵达终点则赠送一次等概率随机[1,n−1]中整数 y 的机会，并向终点走y步。问期望花费多少代价能恰好抵达终点？

第一行输入一个正整数T ,表示一共有T 组测试用例，1≤T ≤100.
接下来T 行，每行输入一个整数n，即题目描述的n，6≤n≤10^9.

一行一个整数，表示期望花费多少代价对109+7取模的结果.