2024“钉耙编程”中国大学生算法设计超级联赛（5）1013 飞行棋_花费 1 的代价等概率随机 [1,n] 中的一个整数 x ,向终点走 x 步,若达到终点还有剩

今晚飞行棋大师 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≤T≤100.

接下来 T 行，每行输入一个整数 n，即题目描述的 n，6≤n≤109.

Output

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

Sample Input

1

998244353

Sample Output

3168436

思路：

从 0 号格有  直接到终点 n 号格。另外有  的概率到 [ 1 , n-1] 号格，这些点到终点的概率都是 ，另外    的概率继续停留在 [ 1 , n-1 ] 号格内，故在这个问题上，位于 [ 1 , n-1 ] 号格子上的状态都是等价的。所以期望花费的代价是:  。（注意：除n的时候要用逆元）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int ksm(int x,int y){
	int ans=1;
	while(y){
		if(y%2!=0) ans=ans*x%mod,y--;
		else x=x*x%mod,y/=2;
	}
	return ans;
}
signed main()
{
	IOS
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int ans=1+(n-1)*(n-1)%mod*ksm(n,mod-2)%mod;
		cout << ans%mod << endl;
	}
	return 0;
}