# T1

$x=\sum p_i^{a_i}$（$p_i$为质数）
$B=\sum p_i^{b_i}$

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int pri[505],is[505];
LL n,m,mod=1000000009;int tot;
void init(){
for(int i=2;i<=500;i++){
if(!is[i])pri[++tot]=i;
for(int j=1;j<=tot&&pri[j]*i<=500;j++){
is[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
}
LL work(LL x,LL y){
LL re=1;
for(LL i=1;pri[i]<=x;i++){
LL kl=x,js=0;
while(kl){kl/=pri[i],js+=kl;}//求质因子个数
if(!(js/y))break;
re=(re*(js/y+1))%mod;
}
return re;
}
int main()
{
freopen("supernum.in","r",stdin);
freopen("supernum.out","w",stdout);
init();scanf("%lld%lld",&n,&m);
printf("%lld\n",(work(n,m)-work(n,m+1)+mod)%mod);
return 0;
}


# T2

$ans=C_{n+m+1}^{m}-2*C_{n+m}^{m-1}$

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define N 1000000
LL mod=1000000007;
LL jie[N+5],ni[N+5],n,m,ans;
LL ksm(LL x,LL y){
LL re=1;
while(y){
if(y&1)re=(re*x)%mod;
x=(x*x)%mod,y>>=1;
}
return re;
}
int main()
{
jie[0]=ni[0]=1;
for(LL i=1;i<=N;i++)jie[i]=(jie[i-1]*i)%mod;
ni[N]=ksm(jie[N],mod-2);
for(LL i=N-1;i>=1;i--)ni[i]=(ni[i+1]*(i+1))%mod;
while(scanf("%lld%lld",&n,&m)==2){
n=n-m;if(m<n){printf("0\n");continue;}
ans=jie[n+m]*ni[n]%mod*ni[m]%mod;
ans=(ans+mod-jie[n+m]*ni[m+1]%mod*ni[n-1]%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}


# T3

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL n,m;
LL f[1000005];
int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
scanf("%lld%lld",&n,&m);
n=(n-1)%m+1;
f[1]=0,f[2]=1;
for(LL i=3;i<=n;i++)f[i]=((i-1)%m)*((f[i-1]+f[i-2])%m)%m;
printf("%lld",(f[n]*f[n])%m);
return 0;
}


# T4

f(i,1) 表示点 i 把火，与第一把火颜色相同的方案数。f(i,0) 则是不同的方案数。那么非常容易得到转移方程：$f(i,1)=f(i-1,0)$.$f(i,0)=f(i-1,1) * (m-2)+f(i-1,0) * (m-1)$

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define MOD 10000
struct bign{
int len,s[100];
bign(){memset(s,0,sizeof(s)),len=1;}
bign operator * (int a){
bign c;c.len=len+1;
for(int i=1;i<=len;i++){
c.s[i+1]=(c.s[i]+s[i]*a)/MOD;
c.s[i]=(c.s[i]+s[i]*a)%MOD;
}
while(!c.s[c.len]&&c.len>1)--c.len;//注意不要把 c. 什么什么写漏了！
return c;
}
bign operator + (bign a){
bign c;c.len=max(len,a.len);
for(int i=1;i<=len;i++){
c.s[i+1]=(c.s[i]+a.s[i]+s[i])/MOD;
c.s[i]=(c.s[i]+a.s[i]+s[i])%MOD;
}
while(c.s[c.len+1])++c.len,c.s[c.len+1]=c.s[c.len]/MOD,c.s[c.len]%=MOD;
return c;
}
void print(){
for(int i=len;i>=1;i--){
if(i!=len)printf("%04d",s[i]);
else printf("%d",s[i]);
}
}
}f[105][2];
int n,m;
int main()
{
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);
scanf("%d%d",&n,&m);
if(n==1){printf("%d",m);return 0;}
f[1][1].s[1]=m;
for(int i=2;i<=n;i++){
f[i][1]=f[i-1][0];
f[i][0]=f[i-1][0]*(m-2)+f[i-1][1]*(m-1);
}
f[n][0].print();
return 0;
}