题意：初始有序列 $a_i=i$，你可以进行不超过 $k$ 次交换操作，每次交换操作选择两个位置 $i,j$，交换 $a_i,a_j$，求有多少序列可能被交换出来。

$n\le10^9,k\le3000$

注意到可能被交换的位置很少，最多也就 $2k$ 个。
而且这些被交换过的位置均有 $a_i\ne i$，也就是说我们把序列的置换环拿出来，那么所有大小不为 $1$ 的置换环都是经过交换的。
不难发现拼成一个大小为 $t$ 的置换环需要 $t-1$ 次操作。

我们不妨枚举大小不为 $1$ 的置换环大小总和 $i$ 以及大小不为 $1$ 的置换环大小个数 $j$，那么如果 $i-j\le m$，就是有可能操作出来的。
类似第一类斯特林数，令 $f_{i,j}$ 表示 $i$ 个人坐在 $j$ 个圆桌的方案数，并且每个圆桌的大小均不为 $1$，那么有递推式

\[f_{i,j}=(i-1)(f_{i-1,j}+f_{i-2,j-1})\]

感性理解就是填第 $i$ 个人的时候要么插在之前一个人的左手边，要么和之前 $i-1$ 个人中的一个新开一个桌子。

也可以直接生成函数：

\[\sum_{n\ge0}f_{n,k}\frac{x^n}{n!}=\frac1{k!}\left(\sum_{m=2}^\infty\frac{x^m}m\right)^k=\frac1{k!}\left(-\ln(1-x)-x\right)^k\]

那么答案就是

\[\sum_{i=2}^{2m}\sum_{j=1}^{i/2}[i-j\le m]\binom nif_{i,j}\] 
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=6007,P=1e9+7;
struct mint{
	int d;
	mint()=default;
	mint(int x):d(x){}
	friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
	friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
	friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
	mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
	friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
	mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
	friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
	mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
	static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
	friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
	mint&operator/=(mint z){return (*this)*=qpow(z.d);}
	friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
	mint&operator^=(mint z){return *this=qpow(d,z.d);}
	mint operator()(mint z)const{return qpow(d,z.d);}
	mint&operator[](mint z){return *this=qpow(d,z.d);}
	mint inv()const{return qpow(d);}
	mint pow(mint z)const{return qpow(d,z.d);}
	int operator+()const{return d;}
	mint operator-()const{return d?P-d:0;}
	int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n,m;
mint f[N][N],fac[N],inv[N],fbc[N],ans;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m;
	fac[0]=fbc[0]=inv[0]=1;
	for(int i=1;i<=2*m;i++){
		fac[i]=fac[i-1]*i;
		fbc[i]=fbc[i-1]*(n-i+1);
	}
	inv[2*m]=fac[2*m].inv();
	for(int i=2*m-1;i>=1;i--)
		inv[i]=inv[i+1]*(i+1);
	f[0][0]=1;
	for(int i=2;i<=2*m;i++)for(int j=1;j<=i/2;j++){
		f[i][j]=(i-1)*(f[i-1][j]+f[i-2][j-1]);
		if(i-j<=m)ans+=fbc[i]*inv[i]*f[i][j];
	}
	cout<<ans+1<<'\n';
	return 0;
}