#include // c #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include using namespace std; typedef long long ll;typedef unsigned long long ull;typedef long double ld; #define ALL(c) c.begin(),c.end() #define IN(l,v,r) (l<=v && v < r) template void UNIQUE(T& v){v.erase(unique(ALL(v)),v.end());} //debug #define DUMP(x) cerr << #x <<" = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" struct range{ struct Iter{ int v,step; Iter& operator++(){v+=step;return *this;} bool operator!=(Iter& itr){return vitr.v;} int& operator*(){return v;} }; Iter i, n; rrange(int i, int n,int step):i({i-1,step}), n({n-1,step}){} rrange(int i, int n):rrange(i,n,1){} rrange(int n) :rrange(0,n){} Iter& begin(){return n;} Iter& end(){return i;} }; //input template istream& operator >> (istream& is,pair& p){return is>>p.first>>p.second;} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t) >> get<1>(t);} template istream& operator >> (istream& is,tuple& t){return is >>get<0>(t)>>get<1>(t)>>get<2>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);} template istream& operator >> (istream& is,vector& as){for(int i:range(as.size()))is >>as[i];return is;} //output template ostream& operator << (ostream& os, const set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< ostream& operator << (ostream& os, const pair& p){return os< ostream& operator << (ostream& os, const map& m){bool isF=true;for(auto& p:m){if(!isF)os< ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const vector& as){for(int i:range(as.size())){if(i!=0)os<<" "; os< ostream& operator << (ostream& os, const vector>& as){for(int i:range(as.size())){if(i!=0)os< inline T INF(){assert(false);}; template<> inline int INF(){return 1<<28;}; template<> inline ll INF(){return 1LL<<60;}; template<> inline double INF(){return 1e16;}; template<> inline long double INF(){return 1e16;}; template inline T EPS(){assert(false);}; template<> inline int EPS(){return 1;}; template<> inline ll EPS(){return 1LL;}; template<> inline double EPS(){return 1e-8;}; template<> inline long double EPS(){return 1e-8;}; // min{2^r | n < 2^r} template inline T upper_pow2(T n){ T res=1;while(res inline T msb(T n){ int d=62;while((1LL<n)d--;return d;} template T pmod(T v,U M){return (v%M+M)%M;} ll mod = 1e9+7; struct mint{ ll x; mint(ll x):x((x%mod+mod)%mod){} mint():mint(0){} mint operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;} mint operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;} mint operator*=(const mint& a){ (x*=a.x)%=mod; return *this;} mint operator+(const mint& a)const{ return mint(*this) += a;} mint operator-(const mint& a)const{ return mint(*this) -= a;} mint operator*(const mint& a)const{ return mint(*this) *= a;} bool operator==(const mint& a)const{ return x == a.x;} // O(logN) mint pow(ll N){ mint r(1),x = *this; while(N){ if(N&1) r *= x; N /= 2; x *= x; } return r; } mint minv(){return pow(mod-2);} }; istream& operator >> (istream& is,mint& p){return is>>p.x;} ostream& operator << (ostream& os,mint m){os << m.x;return os;} struct mutil{ //O(N) static vector fact; static void fact_constructor(const int N){ fact = vector(N+1); fact[0] =mint(1); for(int v:range(1,N+1)) fact[v]=mint(v)*fact[v-1]; } inline mint nPr(const int N,const int r){ if(r>N)return 0; return fact[N]*fact[N-r].minv(); } inline mint nCr(const int N,const int r){ if(N<0){ if(0 <= r) return mint(r%2?-1:+1)*nCr(-N +r-1,r); else if(r<=N) return mint(((N-r)%2?-1:+1))*nCr(-r-1,N-r); else return mint(0); } if(0<= r && r<=N) return mint(fact[N]) * fact[r].minv() * fact[N-r].minv(); return mint(0); } // O(N^2) (no mod N<=66) static vector> C; static void C_constructor(const int N){ C = vector>(N,vector(N)); for(int i:range(N)) C[i][0]=1; for(int i :range(1,N))for(int j:range(1,N)) C[i][j] = C[i-1][j-1]+C[i-1][j]; } static vector invs; static void invs_constructor(int K){ invs = vector(K);invs[1] = mint(1); for (int i:range(2,K)) invs[i] = invs[mod % i] * (mod - mod / i); } }; vector mutil::fact,mutil::invs; vector> mutil::C; class Main{ public: void run(){ mutil mu; mu.C_constructor(100); int N,k;cin >> N >> k; vector as(k); cin >> as; for(int i:range(k-1)){ if((as[i]|as[i+1]) > as[i+1]){ cout << 0 << endl;return; } } vector cs(k+1); for(int i:range(k)) cs[i] = __builtin_popcountll(as[i]); cs[k] = N; mint res = 1;int ki = 0; for(int c:range(1,N)){ if(cs[ki] == c){ ki++; }else{ res *= mint(cs[ki] - c + 1); } } cout << res << endl; // vector>> dp(N,vector>(k+1,vector(N+1,0))); // { // dp[0][min(k,1)][cs[0]] = 1; // for(int c:range(cs[0])){ // dp[0][0][c] = mu.C[cs[0]][c]; // } // } // for(int i:range(1,N)){ // for(int j:range(k+1)){ // for(int c:range(cs[j])){ // for(int prec:range(c)){ // dp[i][j][c] += mu.C[cs[j]-prec][c-prec] * dp[i-1][j][prec]; // } // } // if(j >= 1){ // int c = cs[j-1]; // for(int prec:range(c)){ // dp[i][j][c] += dp[i-1][j-1][prec]; // } // } // } // } // // mint res = 0; // for(int c:range(N+1)) res += dp[N-1][k][c]; // cout << res << endl; } }; int main(){ cout <