Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define MOD 1000000007
- const int N = 1000005;
- ll int k[N], q[N];
- ll int c(ll int a, ll int b, ll int m)
- {
- ll int ans=1;while(b)
- {if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}
- return ans;
- }
- ll int l(ll int k)
- {return c(k, MOD-2, MOD);}
- void g()
- {
- k[0]=k[1]=1;
- for(int i=2;i<N;i++){k[i]=k[i-1]*i;k[i]%=MOD; }
- q[N-1]=l(k[N-1]);
- for(int i=N-2;i>=0;i--){q[i]=q[i+1]*(i+1);q[i]%=MOD;}
- }
- ll int nCr(ll int x, ll int y)
- {
- if(y>x)return 0ll;ll int v=k[x];v*=q[y];
- v%=MOD;v*=q[x-y];v%=MOD;return v;
- }
- int main()
- {
- int t;
- cin>>t;
- g();
- while(t--)
- {
- int n, m;
- cin>>n>>m;
- vector<string> s(n);
- for (auto &x : s) cin>>x;
- if(n == 1)
- {
- cout<<1<<"\n";
- continue;
- }
- vector<int> a(m), b(m);
- for(int i=0; i<m; i++)
- a[i] = (s[n-1][i] == '1');
- if(accumulate(a.begin(), a.end(), 0) == 1)
- fill(a.begin(), a.end(), 0);
- for(int i=n-2; i>0; i--)
- {
- b = a;
- fill(a.begin(), a.end(), 0);
- for(int j=0; j<m; j++)
- a[j] = (s[i][j] == '1');
- int f = 0;
- for(int j=0; j<m; j++)
- f += (a[j] && b[j]);
- if(f)
- {
- for(int j=0; j<m; j++)
- a[j] |= b[j];
- }
- if(accumulate(a.begin(), a.end(), 0)==1 ||
- count(s[i].begin(), s[i].end(), '1')==1)
- fill(a.begin(), a.end(), 0);
- }
- int cnt1=0, cnt0=0;
- for(int i=0; i<m; i++)
- {
- cnt0 += (s[0][i]=='0' && a[i]);
- cnt1 += (s[0][i]=='1' && a[i]);
- }
- cout<<nCr(cnt0+cnt1, cnt1)<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment