飞行棋

Problem Description

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

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

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

Output

对每个测试用例，输出一行一个整数，表示期望花费代价对 $10^9 + 7$ 取模的结果.

Sample Input

1
998244353

Sample Output

3168436

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）