Description：

求每个数在 $[1,n]$ 长为 $n$ 的单调不降或单调不升的数列个数。

$1\leqslant n\leqslant 10^5$

Solution：

单调不降的数列反转就是单调不升，所以只要统计一个就行了。

首先发现最后一定是有若干个连续的，假如说有 $i$ 个，那么这个的方案数有 $n\choose i$ 种，然后就是把 $n$ 个数分为 $i$ 个集合的方案数，好像就是一个整数划分数，但是复杂度不行，发现这个其实就相当于 $n$ 个小球分成 $i$ 组的方案数，由插板法得方案数为 $n-1\choose i-1$ ，所有数都相同的应该只计算一次，所以最后的答案为： $$ ans=\sum_{i=1}^n{n\choose i}\times{n-1\choose i-1} $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int fac[MAXN],inv[MAXN];

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int C(int n,int m)

{

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int main()

{

	scanf("%d",&n);

	fac[0] = inv[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[n] = power(fac[n],MOD - 2);

	for(int i = n - 1;i >= 1;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	int ans = 0;

	for(int i = 2;i <= n;++i)

	{

		ans = (ans + 1ll * C(n,i) * C(n - 1,i - 1) % MOD) % MOD;

	}

	cout << (ans * 2 % MOD + n) % MOD << endl;

	return 0;

}