# T1.supernum

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define MX 100002
#define MD 1000000009

using namespace std;

typedef long long ll;

ll prm[MX+1],pnum;
char vis[MX+1];

void init()
{
for(int i=2;i<=MX;)
{
prm[++pnum]=i;
for(int j=1;j*i<=MX;j++)vis[j*i]=1;
while(vis[i])++i;
}
}

ll n,k;
ll num[MX+1];
ll num1[MX+1],num2[MX+1];
ll can[MX+1];
ll but[MX+1];

void work()
{
ll ans1=1,ans2=1;
cin>>n>>k;
for(ll i=1;i<=pnum;i++)
for(ll tmp=prm[i];tmp<=n;tmp*=prm[i])
num[i]+=n/tmp;
for(int i=1;i<=pnum;i++)can[i]=num[i]/k;
for(int i=1;i<=pnum;i++)but[i]=num[i]/(k+1);
for(int i=1;i<=pnum;i++)ans1=ans1*(can[i]+1)%MD,ans2=ans2*(but[i]+1)%MD;
cout<<(ans1-ans2+MD)%MD<<endl;
}

int main()
{
freopen("supernum.in","r",stdin);
freopen("supernum.out","w",stdout);
init();
work();
return 0;
}


$$ans=C_n^{x-1}-C_n^{x+1}$$

#include <iostream>
#include <cstring>
#include <cstdio>

#define MD 1000000007

using namespace std;

typedef long long ll;

ll frc[1000001];

ll ksm(ll x,ll t)
{
ll ans=1;
while(t)
{
if(t&1)ans=ans*x%MD;
x=x*x%MD;
t>>=1;
}
return ans;
}

ll inv(ll x)
{
return ksm(x,MD-2);
}

void init()
{
frc[1]=1;
for(ll i=2;i<=1000000;++i)
frc[i]=frc[i-1]*i%MD;
}

ll C(ll n,ll m)
{
if(n==m)return 1;
else if(m>n)return 0;
else return frc[n]*inv(frc[m]*frc[n-m]%MD)%MD;
}

void work()
{
ll n,x;
while(cin>>n>>x)
{
if(x*2<n||x>n)cout<<0<<endl;
else if(x==n)cout<<1<<endl;
else if(x==n-1)cout<<x<<endl;
else cout<<(C(n-1,x-1)+MD-C(n-1,x+1))%MD<<endl;
}
}

int main()
{
init();
work();
return 0;
}



# T3.Chess

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll f[2000004];
ll n,m;

void work()
{
f[1]=0;
f[2]=1;
for(int i=3;i<=m*2;i++)f[i]=(i-1)*(f[i-1]+f[i-2])%m;
cout<<f[n%m]*f[n%m]%m<<endl;
}

int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
cin>>n>>m;
work();
return 0;
}



# T4.Lights

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 103

using namespace std;

typedef long long ll;

typedef struct lints
{
int x[300];
int len;
}lint;

void out(lint g)
{
if(g.len==0)cout<<0<<endl;
else for(int i=g.len;i>=1;i--)cout<<g.x[i];cout<<endl;
}

{
int len=max(a.len,b.len),x;
lint c;
c.len=len;
for(int i=1;i<=300;i++)c.x[i]=0;
for(int i=1;i<=len+1;i++)
{
c.x[i]=(a.x[i]+b.x[i]+x)%10;
//cout<<c.x[i]<<endl;
if(a.x[i]+b.x[i]+x>=10)x=1;
else x=0;
}
if(c.x[len+1])len++;
c.len=len;
return c;
}

lint f[MX][MX],ans;

int main()
{
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);
int n,m;
cin>>n>>m;
if(n==1){cout<<m<<endl;return 0;}
f[1][1].len=1;
f[1][1].x[1]=1;
for(int i=2;i<=n+1;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
if(k!=j)