#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int P=1000000009;const int N=310;int n,m,i,j,k,f[N][N][N];inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}int main(){  scanf("%d%d",&n,&m);  f[0][0][0]=1;  for(i=1;i<=n;i++)for(j=0;j<=i;j++)for(k=j;k<=m;k++){    if(f[i-1][j][k]){      up(f[i][j][k],f[i-1][j][k]);      up(f[i][j+1][max(j+1,k)],f[i-1][j][k]);      if(j)up(f[i][j-1][k],f[i-1][j][k]);    }  }  printf("%d",f[n][0][m]);}

#include<cstdio>#include<algorithm>#include<vector>using namespace std;typedef pair<int,int>P;typedef pair<int,P>PI;const int N=100010,M=3000000;int n,m,i,x,y,z,op;int g[N],nxt[N<<1],v[N<<1],w[N<<1],ok[N<<1],ed;int son[N],f[N],all,now,cnt,value[N];int G[N],NXT[M],V[M],W[M],ED;vector<PI>q[N];int top[N];int Time;//top dis is low but time is newinline void add(int x,int y,int z){  v[++ed]=y;  w[ed]=z;  nxt[ed]=g[x];  ok[ed]=1;  g[x]=ed;}inline void ADD(int x,int y,int w){  V[++ED]=y;  W[ED]=w;  NXT[ED]=G[x];  G[x]=ED;}void findroot(int x,int y){  son[x]=1,f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(all-son[x]>f[x])f[x]=all-son[x];  if(f[x]<f[now])now=x;}void dfs(int x,int y,int dis){  ADD(x,now,dis);  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,dis+w[i]);}void solve(int x){  int i;  dfs(x,0,0);  for(i=g[x];i;i=nxt[i])if(ok[i]){    ok[i^1]=0;    f[0]=all=son[v[i]];    findroot(v[i],now=0);    solve(now);  }}inline void paint(int x,int y,int z){  Time++;  for(int i=G[x];i;i=NXT[i]){    int w=y-W[i];    if(w<0)continue;    int u=V[i];    while(top[u]){      if(w>=q[u][top[u]-1].first)top[u]--;      else break;    }    PI t(w,P(Time,z));    if(top[u]==q[u].size())q[u].push_back(t);else q[u][top[u]]=t;    top[u]++;  }}inline int query(int x){  P ret(0,0);  for(int i=G[x];i;i=NXT[i]){    int w=W[i];    int u=V[i];    if(!top[u])continue;    if(q[u][0].first<w)continue;    int l=0,r=top[u]-1,mid,fin;    while(l<=r){      mid=(l+r)>>1;      if(q[u][mid].first>=w)l=(fin=mid)+1;else r=mid-1;    }    ret=max(ret,q[u][fin].second);  }  return ret.second;}int main(){  scanf("%d",&n);  for(ed=i=1;i<n;i++){    scanf("%d%d%d",&x,&y,&z);    add(x,y,z);    add(y,x,z);  }  f[0]=all=n;  findroot(1,now=0);  solve(now);  scanf("%d",&m);  while(m--){    scanf("%d%d",&op,&x);    if(op==1)scanf("%d%d",&y,&z),paint(x,y,z);    else printf("%d\n",query(x));  }}

#include<cstdio>#include<cmath>#include<algorithm>#include<vector>using namespace std;typedef double DB;const int N=88888;const DB eps=1e-8,pi=acos(-1);DB ans;int n;struct PT{  DB x,y;  PT(DB x=0,DB y=0):x(x),y(y){}  void input(){scanf("%lf%lf",&x,&y);}  bool operator<(const PT&p)const{    if(fabs(x-p.x))return x<p.x;    return y<p.y;  }  void output(){printf("%.10f %.10f\n",x,y);}}p[N],q[N];vector<PT>ret;DB vect(PT p,PT p1,PT p2){  return (p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x);}int convex_hull(PT*p,int n,PT*q){  int i,k,m;  sort(p,p+n);  m=0;  for(i=0;i<n;q[m++]=p[i++])while(m>1&&vect(q[m-2],q[m-1],p[i])<eps)m--;  k=m;  for(i=n-2;i>=0;q[m++]=p[i--])while(m>k&&vect(q[m-2],q[m-1],p[i])<eps)m--;  return --m;}PT get(PT p,DB x){  return PT(p.x*cos(x)-p.y*sin(x),p.x*sin(x)+p.y*cos(x));}bool is_ext(int id,PT pp){  if(vect(p[id],PT(p[id].x+pp.x,p[id].y+pp.y),p[id+1])<-eps)return 0;  if(vect(p[id],PT(p[id].x+pp.x,p[id].y+pp.y),p[(id-1+n)%n])<-eps)return 0;  return 1;}PT inter(PT p1,PT p2,PT p3,PT p4){  p2.x+=p1.x;  p2.y+=p1.y;  p4.x+=p3.x;  p4.y+=p3.y;  DB s=vect(p1,p2,p3),s1=vect(p1,p2,p4);  DB t=s/(s-s1);  return PT(p3.x+(p4.x-p3.x)*t,p3.y+(p4.y-p3.y)*t);}void solve(){  int f[4];  f[1]=f[2]=f[3]=0;  for(int i=0;i<n;i++){    f[0]=i;    PT v[4];    v[0]=PT(p[i+1].x-p[i].x,p[i+1].y-p[i].y);    for(int j=1;j<4;j++)for(v[j]=get(v[0],pi/2*j);!is_ext(f[j],v[j]);f[j]=(f[j]+1)%n);    vector<PT>tmp;    for(int j=0;j<4;j++)tmp.push_back(inter(p[f[j]],v[j],p[f[(j+1)%4]],v[(j+1)%4]));    DB tmps=0;    for(int j=0;j<4;j++)tmps+=vect(tmp[0],tmp[j],tmp[(j+1)%4]);    tmps=fabs(tmps);    if(ans>tmps)ans=tmps,ret=tmp;  }}int main(){  scanf("%d",&n);  for(int i=0;i<n;i++)p[i].input();  n=convex_hull(p,n,q);  for(int i=0;i<n;i++)p[i]=q[i];  p[n]=p[0];  ans=1e100;  solve();  for(int i=0;i<4;i++)ret[i].output();  return 0;}

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int Maxn=100020;typedef vector<LL>vi;const double Inf=1e80;const int mod=1e9+9;double dp[17][Maxn];int pre[17][Maxn],pe[17][Maxn];int n;vector<int>ys;vector<int>pri;bool isp[100];int powmod(int x,int y){	int ret=1;	while(y){		if(y&1)ret=1LL*ret*x%mod;		y>>=1;		x=1LL*x*x%mod;	}	return ret;}int main(){	for(int i=2;i<100;i++){		if(!isp[i])pri.push_back(i);		for(int j=i+i;j<100;j+=i)isp[j]=1;	}	while(scanf("%d",&n)!=EOF){		if(n==1){puts("1");continue;}		for(int i=1;i<=n;i++){			if(n%i==0)ys.push_back(i);		}		for(int i=0;i<=16;i++){			for(int j=1;j<=n;j++)dp[i][j]=Inf;		}		dp[0][1]=0;		for(int i=1;i<=16;i++){			for(int j=0;j<ys.size();j++){				int x=ys[j];				dp[i][x]=Inf;				for(int k=0;k<=j;k++){					int y=ys[k];					if(x%y)continue;					if(dp[i-1][x/y]+(y-1)*log(pri[i]+.0)<dp[i][x]){						dp[i][x]=dp[i-1][x/y]+(y-1)*log(pri[i]+.0);						pre[i][x]=x/y;						pe[i][x]=y-1;					}				}			}		}		vector<int>res;		int cur=n;		for(int i=16;i>=1;i--){			//printf("cur=%d\n",cur);			if(pe[i][cur]>=1)res.push_back(pe[i][cur]);			cur=pre[i][cur];		}		sort(res.begin(),res.end(),greater<int>());		int ans=1;		for(int i=0;i<res.size();i++){			//printf("res=%d\n",res[i]);			ans=1LL*ans*powmod(pri[i+1],res[i])%mod;		}		printf("%d\n",ans);	}}

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int Maxn=100020;const LL t0=1000000000000LL,t1=1000000;int n;LL x[Maxn];int main(){	while(scanf("%d",&n)!=EOF){		LL ans=5e18;		LL totsum=0;		for(int i=1;i<=n;i++){			LL a,b,c;scanf("%lld%lld%lld",&a,&b,&c);			x[i]=a*t0+b*t1+c;			totsum+=x[i];		}		sort(x+1,x+n+1);		LL cur=0;		LL All=12*t0;		for(int i=1;i<=n;i++){			cur+=x[i];			LL bef=i*x[i]-cur;			LL aft=(x[i]+All)*(n-i)-(totsum-cur);			ans=min(ans,bef+aft);		}		printf("%lld %lld %lld\n",ans/t0,(ans/t1)%t1,ans%t1);	}}

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef vector<LL>vi;const int Maxn=2020;LL dp[Maxn][Maxn],sum[Maxn][Maxn];LL n,m;int ans[Maxn];void calsum(int idx){	for(int i=0;i<=n;i++){		sum[idx][i]=dp[idx][i];		if(i)sum[idx][i]+=sum[idx][i-1];	}}LL cal(LL x){	if(x<m)return 0;	LL tmp=1;//C(1000,1000)	if(m+m<=x){		for(LL i=0;i<m;i++){			//if(tmp/(i+1)>ned/(x-i)+1)return 0;			//if((long double)ned*(i+1.)+10<(long double)tmp*(x-i))return 0;			tmp=tmp*(x-i)/(i+1);		}	}	else{		for(LL i=x;i>m;i--){			//printf("tmp%lld\n",tmp);			//if((long double)ned*(x-i+1)+10<(long double)tmp*(i))return 0;			tmp=tmp*i/(x-i+1);		}	}	return tmp;}bool check(LL x,LL ned){	if(x<m)return 1;	LL tmp=1;//C(1000,1000)	if(m+m<=x){		for(LL i=0;i<m;i++){			//if(tmp/(i+1)>ned/(x-i)+1)return 0;			if((long double)ned*(i+1.)+10<(long double)tmp*(x-i))return 0;			tmp=tmp*(x-i)/(i+1);		}	}	else{		for(LL i=x;i>m;i--){			//printf("tmp%lld\n",tmp);			if((long double)ned*(x-i+1)+10<(long double)tmp*(i))return 0;			tmp=tmp*i/(x-i+1);		}	}	//printf("tmp=%lld\n",tmp);	if(tmp>ned)return 0;	return 1;}LL solve(LL ned){	LL l=0,r=1e9;	while(l+1<r){		LL mid=(l+r)>>1;		if(check(mid,ned))l=mid;		else r=mid;	//	printf("l=%lld r=%lld\n",l,r);	}	return l;}int main(){	//n=10000000000000LL;	//m=2;	//printf("%lld",cal(4472136LL));	//solve(7937589951629LL);	//printf("%d\n",check(n/2,7937589951629LL));	//m=10;	///printf("%d\n",check(10,1));	while(scanf("%lld%lld",&n,&m)!=EOF){		//solve(n);		//printf("%d\n",check(7,n));				int tot=m;		LL pre=1e9;		for(int i=1;i<=tot;i++){			LL tmp=solve(n);			//printf("tmp=%lld\n",tmp);			tmp=min(tmp,pre-1);			pre=tmp;			n-=cal(tmp);			printf("%lld%c",tmp,i==tot?‘\n‘:‘ ‘);			//printf("tmp=%lld n=%lld\n",tmp,n);			m--;		}		//printf("n=%lld\n",n);			}		}

#include<cstdio>typedef long long ll;ll n,m,x,y,P,B,s[1111111];ll exgcd(ll a,ll b){  if(!b)return x=1,y=0,a;  ll d=exgcd(b,a%b),t=x;  return x=y,y=t-a/b*y,d;}ll rev(ll a,ll P){exgcd(a,P);while(x<0)x+=P;return x%P;}ll pow(ll a,ll b,ll P){  ll t=1;  for(;b;b>>=1LL,a=a*a%P)if(b&1LL)t=t*a%P;  return t;}struct Num{  ll a,b;  Num(){a=1,b=0;}  Num(ll _a,ll _b){a=_a,b=_b;}  Num operator*(Num x){return Num(a*x.a%P,b+x.b);}  Num operator/(Num x){return Num(a*rev(x.a,P)%P,b-x.b);}};Num cal(ll n){return n?Num(s[n%P]*pow(s[P],n/P,P)%P,n/B)*cal(n/B):Num(1,0);}void pre(){  ll i;  for(i=s[0]=1;i<P;i++)if(i%B)s[i]=s[i-1]*i%P;else s[i]=s[i-1];  s[P]=s[P-1];}ll solve(int _B,int _P){  B=_B,P=_P;  pre();  Num t=cal(n)/cal(m)/cal(n-m);  return 1LL*t.a*pow(B,t.b,P)%P;}ll a[11111],b[11111];int cnt;void divide(int P){  for(int i=2;;i++)if(P%i==0){    int x=1;    while(P%i==0)P/=i,x*=i;    a[cnt]=x;    b[cnt]=solve(i,x);    cnt++;    if(P==1)return;  }}ll CRT(int n){  ll ans=0,P=1;  for(int i=0;i<n;i++)P*=a[i];  for(int i=0;i<n;i++)ans=(ans+(P/a[i])*rev(P/a[i],a[i])%P*b[i]%P)%P;  return (ans%P+P)%P;}int main(){  int P;  scanf("%lld%lld%d",&n,&m,&P);  divide(P);  printf("%lld",CRT(cnt));}

#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;int n,i,a[200000],v[1000000];ll ans=1LL<<60;void change(int x,int a,int b,int c,int p){  v[x]+=p;  if(a==b)return;  int mid=(a+b)>>1;  if(c<=mid)change(x<<1,a,mid,c,p);  else change(x<<1|1,mid+1,b,c,p);}inline void upd(){  int a=0,b=100010,mid,x=1;  while(a<b){    mid=(a+b)>>1;    if(v[x<<1|1])a=mid+1,x=x<<1|1;else b=mid,x<<=1;  }  ans=min(ans,1LL*a*v[x]);}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  for(i=1;i<=n;i++)change(1,0,100010,a[i],1);  upd();  for(i=1;i<n;i++){    if(a[i]){      change(1,0,100010,a[i],-1);      change(1,0,100010,a[i]-1,1);      change(1,0,100010,a[i+1],-1);      change(1,0,100010,a[i+1]+1,1);      upd();      change(1,0,100010,a[i],1);      change(1,0,100010,a[i]-1,-1);      change(1,0,100010,a[i+1],1);      change(1,0,100010,a[i+1]+1,-1);    }  }  for(i=2;i<=n;i++){    if(a[i]){      change(1,0,100010,a[i],-1);      change(1,0,100010,a[i]-1,1);      change(1,0,100010,a[i-1],-1);      change(1,0,100010,a[i-1]+1,1);      upd();      change(1,0,100010,a[i],1);      change(1,0,100010,a[i]-1,-1);      change(1,0,100010,a[i-1],1);      change(1,0,100010,a[i-1]+1,-1);    }  }  printf("%lld",ans);}