#include //#include using namespace std; //using namespace atcoder; using ll=long long; #define rng(i,l,r) for(int i=int(l);i=int(l);i--) #define rrep(i,r) rrng(i,0,r) #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define F first #define S second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #define inf INT_MAX/2-100 #define infl LLONG_MAX/3 #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<' '<<#x<<' '<bool chmax(t&a,u b){if(abool chmin(t&a,u b){if(busing vc=vector; templateusing vvc=vector>; using pi=pair; using pl=pair; using vi=vc; using vl=vc; ll readl(void){ ll x; cin>>x; return x; } int readi(void){ int x; cin>>x; return x; } string readstr(){ string s; cin>>s; return s; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=readi(),v[i]+=off; return v; } vl readvl(int n,int off=0){ vl v(n); rep(i,n)v[i]=readl(),v[i]+=off; return v; } template void print(t x,int suc=1){ cout< void print(const vc&v,int suc=1){ rep(i,si(v))print(v[i],i==int(si(v))-1?1:suc); } template bool inc(t a,t b,t c){ return !(c void compress(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } template struct Compress{ vcv; Compress()=default; Compress(const vc&x){ add(x); } Compress(const initializer_list >&x){ for(auto &p:x)add(p); } void add(const t&x){ v.eb(x); } void add(const vc&x){ copy(all(x),back_inserter(v)); } void build(){ compress(v); } int get(const t&x)const{ return lwb(v,x); } vcget(const vc&x)const{ vcres(x); for(auto &p:res)p=get(p); return res; } const t &operator[](int x)const{ return v[x]; } int size(){ return v.size(); } }; void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); } void orYes(bool x,bool ex=true){ if(x)Yes(ex); else No(ex); } void orYES(bool x,bool ex=true){ if(x)YES(ex); else NO(ex); } void Possible(bool ex=true){ cout<<"Possible\n"; if(ex)exit(0); } void POSSIBLE(bool ex=true){ cout<<"POSSIBLE\n"; if(ex)exit(0); } void Impossible(bool ex=true){ cout<<"Impossible\n"; if(ex)exit(0); } void IMPOSSIBLE(bool ex=true){ cout<<"IMPOSSIBLE\n"; if(ex)exit(0); } void orPossible(bool x,bool ex=true){ if(x)Possible(ex); else Impossible(ex); } void orPOSSIBLE(bool x,bool ex=true){ if(x)POSSIBLE(ex); else IMPOSSIBLE(ex); } using uint=unsigned; using ull=unsigned long long; template struct Modular{ static constexpr uint const &mod=MOD; uint v; Modular(long long x=0){c(x%mod+mod);} Modular& c(uint x){ v=x>=1; } return res; } Modular inv()const{return pow(mod-2);} Modular operator-()const{return Modular(mod-v);} Modular& operator+=(const Modular &x){return c(v+x.v);} Modular& operator-=(const Modular &x){return c(v+mod-x.v);} Modular& operator*=(const Modular &x){v=ull(v)*x.v%mod;return *this;} Modular& operator/=(const Modular &x){return *this*=x.inv();} Modular operator+(const Modular &x)const{return Modular(*this)+=x;} Modular operator-(const Modular &x)const{return Modular(*this)-=x;} Modular operator*(const Modular &x)const{return Modular(*this)*=x;} Modular operator/(const Modular &x)const{return Modular(*this)/=x;} friend Modular operator+(long long x,const Modular &y){return Modular(x)+y;} friend Modular operator-(long long x,const Modular &y){return Modular(x)-y;} friend Modular operator*(long long x,const Modular &y){return Modular(x)*y;} friend Modular operator/(long long x,const Modular &y){return Modular(x)/y;} friend ostream& operator<<(ostream&os,const Modular&x){ return os<>(istream&is,Modular&x){ long long p; is>>p; x=Modular(p); return is; } bool operator==(const Modular &x)const{return v==x.v;} bool operator!=(const Modular &x)const{return v!=x.v;} bool operator<(const Modular &x)const{return v; vectorfact,finv,invs; void Initfact(int n=(1<<21)+10){ fact.resize(n+1),finv.resize(n+1),invs.resize(n+1); fact[0]=1; for(int i=1;i<=n;i++){ fact[i]=fact[i-1]*i; } finv[n]=fact[n].inv(); for(int i=n-1;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } invs[0]=1; for(int i=0;i<=n;i++){ invs[i]=finv[i]*fact[i-1]; } } Mint comb(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } ll gcd(ll a,ll b){ if(ap.r[i])return false; } return false; } }; int n,k,a[20],ans; vi p; bool vis[20000]; setcnt; int main(void){ cin.tie(0); ios::sync_with_stdio(0); //cout << fixed << setprecision(15) << y << endl; for(int i=2;i<=1000;i++){ bool isp=true; for(int j=2;j>n>>k; rep(i,n)cin>>a[i]; for(int i=0;i<1<>j&1){ s++; ss+=a[j]; } } if(s>=k)vis[ss]=true; } rep(i,20000){ if(vis[i]){ int x=i; num s; rep(l,168){ while(x%p[l]==0){ x/=p[l]; s.r[l]++; } } if(x>1)ans++; else cnt.insert(s); } } rep(i,1<>j&1){ int x=a[j]; ss++; rep(l,168){ while(x%p[l]==0){ x/=p[l]; s.r[l]++; } } } } if(ss>=k)cnt.insert(s); } print(si(cnt)+ans); }