Jinnie

显然是一个线性基的问题，那么很显然要用线性基

想要知道所有的方案数，线性基的性质就是用其中的元素$xor$ 出来的元素保证互不相等

这样的话只要知道线性基内元素的数量就可以了

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
string s;
int p[60];
int n,m;
int cnt;
int num;
void add(int x){
    for(int i=n-1;i>=0;--i){
        if(((1ll<<i)&x)==0) continue;
        if(!p[i]){
            cnt++;          
            p[i]^=x;
            break;
        } 
        x^=p[i];
    }
}
signed main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        cin>>s;
        num=0;
        for(int j=n-1;j>=0;--j){
            if(s[j]=='O'){
                num|=(1ll<<j);
            }
        }
        add(num);
    }
    cout<<(1ll<<cnt)%2008;
    return 0;
}