#include using namespace std; bool st; namespace _wrk{; ostream& operator<<(ostream &w,__int128 p){ static char buf[45]; auto *c=buf; if(p<0){ w<<'-'; p=-p; } if(p==0){ w<<'0'; }else{ while(p){ (*c++)=(p%10+'0'); p/=10; } c--; while(1){ w<<(*c); if(c==buf)break; c--; } } return w; } istream& operator>>(istream &w,__int128 &p){ static bool mask; mask=0; while(isspace(w.peek())){ w.get(); } if(w.peek()=='-'){ mask=1; w.get(); if(!isdigit(w.peek())){ w.putback('-'); return w; } } p=0; while(isdigit(w.peek())){ char c=w.get(); p=p*10+(c-'0'); } if(mask)p=-p; return w; } template struct modint{ int num; const static __uint128_t brt=((__uint128_t)(1)<<(64))/mod; modint(){ num=0; } modint(int x){ num=x%mod; } modint(long long x){ num=x%mod; } modintoperator=(int x){ num=x%mod; return (*this); } modintoperator=(long long x){ num=x%mod; return (*this); } modintoperator=(modintx){ num=x.num; return (*this); } modint operator+(modint c)const{ long long x=num+c.num; return x>=mod?x-mod:x; } modint operator-(modint c)const{ long long x=num-c.num; return x<0?x+mod:x; } modintoperator*(modintc)const{ long long x=(long long)num*c.num; x=x-mod*(brt*x>>64); while(x>=mod)x-=mod; return x; } modintfpof(long long x)const{ if(x<0)return inv().fpof(-x); if(x==0)return 1; auto c=((*this)*(*this)).fpof(x/2); if(x&1)return c*(*this); else return c; } modintinv()const{ return fpof(mod-2); } modintoperator/(modintc){ return (*this)*c.inv(); } operator int(){ return num; } modintoperator+=(modint c){ return (*this)=(*this)+c; } modintoperator-=(modint c){ return (*this)=(*this)-c; } modintoperator*=(modint c){ return (*this)=(*this)*c; } modintoperator/=(modint c){ return (*this)=(*this)/c; } modintoperator-(){ return mod-num; } friend ostream& operator<<(ostream &w,modint&&x){ w<>(istream &w,modint&x){ w>>x.num; x.num%=mod; return w; } bool operator==(modintx){ return num==x.num; } }; #define int long long template struct matrix{ type a[N+2][N+2]; int n; type* operator[](int pos){ return a[pos]; } matrix operator*(matrixb){ matrixans; ans.n=n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ ans[i][j]+=a[i][k]*b[k][j]; } } } return ans; } }; template type fp(type a,int b){ if(b==0)return type(); if(b==1)return a; type w=fp(a*a,b/2); if(b%2)return w*a; return w; } template struct yw_int_array{ struct three21bit{ int a:21; int b:21; int c:21; }a[N/3+2]; struct ref{ three21bit& s; char type; operator int(){ if(type==0)return s.a; if(type==1)return s.b; return s.c; } ref& operator=(int x){ if(type==0)s.a=x; else if(type==1)s.b=x; else s.c=x; return (*this); } }; ref operator[](int pos){ char w=pos%3; return {a[pos/3],(char)w}; } }; template struct backup_array{ type name[N+5]; vector>>cc; void new_array(){ cc.push_back(vector>()); } backup_array(){ cc.resize(1); } struct x{ int id; type* name; vector>> &cc; operator type(){ return name[id]; } type operator=(type w){ cc.back().push_back({id,name[id]}); name[id]=w; return w; } }; x operator[](int pos){ return {pos,name,cc}; } void backup(){ reverse(cc.back().begin(),cc.back().end()); for(auto &x:cc.back()){ name[x.first]=x.second; } cc.pop_back(); } }; template struct Math{ type jc[N+5],inv[N+5],invjc[N+5]; Math(){ jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1; for(int i=2;i<=N;i++){ jc[i]=jc[i-1]*type(i); } invjc[N]=type(1)/jc[N]; for(int i=N-1;i>=2;i--){ invjc[i]=invjc[i+1]*type(i+1); } for(int i=1;i<=N;i++){ inv[i]=invjc[i]*jc[i-1]; } } type binom(int a,int b){ return jc[a]*invjc[b]*invjc[a-b]; } type catalan(int n){ return binom(2*n,n)/type(n+1); } }; template struct pows{ type w[maxnum+5]; pows(){ w[0]=type(1); for(int i=1;i<=maxnum;i++)w[i]=w[i-1]*type(num); } type operator[](int pos){ return w[pos]; } }; #ifdef hash namespace hashing{ constexpr static int N=5000006;//5e6 constexpr static int count=1; constexpr static int mods[count]={1000000007}; constexpr static int bases[count]={37}; constexpr static char start='a'; int hash_base[count][N+5]; void init(){ for(int i=0;ipos){ return substr(pos.first,pos.second); } }; }; #endif #ifdef use_seg_tree template struct segment_tree{ type a[len<<2]; laz_type laz[len<<2]; void pushup(int now){ PUSHUP_VALUE } void pushdown(int now,int l,int r){ PUSHDOWN_VALUE } void build(int now,int l,int r){ if(l+1==r){ FIRST_VALUE return; } LAZ_CLEAR int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid,r); pushup(now); } void do1(int now,int l,int r,int L,int R,...){ if(l+1!=r)pushdown(now,l,r); if(R<=l||r<=L)return; if(L<=l&&r<=R){ FULL_BLOCK_VALUE return; } int mid=(l+r)>>1; do1(now<<1,l,mid,L,R,...); do1(now<<1|1,mid,r,L,R,...); pushup(now); } void do1_one(int now,int l,int r,int p,...){ if(l+1!=r)pushdown(now,l,r); if(l+1==r){ DO1_VALUE return; } int mid=(l+r)>>1; if(p>1; return RETURN_VALVE qu1(now<<1,l,mid,L,R)+qu1(now<<1|1,mid,r,L,R); } type qu1_one(int now,int l,int r,int p){ if(l+1!=r)pushdown(now,l,r); if(l+1==r)return a[now]; int mid=(l+r)>>1; if(p //powstp;note the size //Mathmath; //vectorg[1000006] mint dp[403][403][403]; int a[403],count[403]; mint cdp[403][403]; mint dc[403]; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; count[a[i]]++; } sort(a+1,a+1+n); int m=*max_element(a+1,a+1+n)+10; dp[m][0][0]=1; mint res=1; for(int i=m;i>=0;i--){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ if(dp[i][j][k].num){ // cout<=0;i--){ for(int j=0;j<=count[i];j++){ for(int k=0;k<=n;k++){ cdp[i][k+j]+=cdp[i+1][k]; } if(j==count[i]-1){ for(int d=0;d<=n;d++){ dc[d]=cdp[i][d]; } if(i==*min_element(a+1,a+1+n))dc[0]-=mint(1); for(int d=n-1;d>=0;d--){ dc[d]+=dc[d+1]; } vectorp(m+1); p[i]=1; int c=1; int f=-1; for(int w=i;w>=0;w--){ if(w!=i){ int z=min(count[w],p[w]); p[w]-=z; c+=count[w]-z; } if(w==0){ f=p[w]; }else{ for(int j=w-1;j>=0;j--){ p[j]+=p[w]; p[j]=min(p[j],2*n+1); } p[w]=0; } } assert(~f); int h=max(0ll,f-c); // cout<