# CF285E Positions in Permutations

What is different from others here is modulo addition and multiplication (I think this thing is very good, maybe a little faster?

### Solution

First, it allows us to calculate the number of schemes, so we set an array \ (F(x) \) to represent the number of permutations whose perfect number is exactly \ (x \). From this familiar coincidence, we can set another array \ (G(x) \) to represent the number of permutations whose perfect number is at least \ (x \), so it is obvious that: \ (g (m) = \ sum \ limits can be obtained_ {I = m} ^ n \ binom IMF (I) \), a normal binomial inversion can get \ (F(m)=\sum\limits_{i=m}^n(-1)^{i-m}\binom imG(i) \), now consider how to find \ (G(x) \).

Because the perfection of each bit is only related to the front and back, we can set \ (f_{i,j,0/1,0/1} \) to indicate that the current bit is \ (i \), there are \ (j \) perfect numbers, \ (i \) yes / no and \ (i+1 \) yes / No.

Now consider the state transition equation:

Select bit \ (I \) as the perfect bit and put \ (i-1 \) in bit \ (I \), just make sure that \ (i-1 \) is not selected.

$f_{i,j,0,0}+=f_{i-1,j-1,0,0},f_{i,j,1,0}+=f_{i-1,j-1,0,1}$

Select bit \ (i \) as the perfect bit and put \ (i+1 \) in bit \ (i \), just make sure that \ (i+1 \) is not selected.

$f_{i,j,0,1}+=f_{i-1,j-1,0,0}+f_{i-1,j-1,1,0},f_{i,j,1,1}+=f_{i-1,j-1,0,1}+f_{i-1,j-1,1,1}$

Do not select bit \ (i \) as the perfect bit

$f_{i,j,0,0}+=f_{i-1,j,0,0}+f_{i-1,j,1,0},f_{i,j,1,0}+=f_{i-1,j,0,1}+f_{i-1,j,1,1}$

Initial state: \ (f_{1,0,0,0}=1,f_{1,1,0,1}=1 \)

Because the \ (n \) bit can only select \ (n-1 \) as the perfect number, it is necessary to transfer or subtract the part of \ (n+1 \). I chose to relocate.

Now you can get \ (g (m) = (f {n, m, 0,0} + F {n, m, 1,0}) \ times (n-m)! \), Where \ ((n-m)! \) It is the full arrangement of the remaining \ (n-m \) positions.

Finally, inversion is enough.

### code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;
const int N=2050,mod=1e9+7;
int n,m;
ll f[N][N][2][2],G[N],fac[N],inv[N];

int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}

ll mul(ll a,ll b){return a*b%mod;}

inline void init(){
fac[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=mul(inv[mod%i],mod-mod/i);
for(int i=1;i<=n;i++){
fac[i]=mul(fac[i-1],i);
inv[i]=mul(inv[i],inv[i-1]);
}
}

ll C(int n,int m){
if(n<m) return 0;
return mul(fac[n],mul(inv[n-m],inv[m]));
}

int main(){
init();
f[1][0][0][0]=f[1][1][0][1]=1;
for(int i=2;i<=n;i++){
f[i][0][0][0]=1;
for(int j=1;j<=i;j++){
}
}
f[n][0][0][0]=1;
for(int i=1;i<=n;i++){
}
//Above is the retransfer n
for(int i=0;i<=n;i++)