Ruudukko

input/code.cpp:126:17: error: 'pow' was not declared in this scope
 const int mod = pow(10,9)+7;
                 ^~~

#include <iostream>
#include <unordered_map>

using namespace std;
long n;


long total=0;

char c;

int get(int *ruudukko, int y, int x){
    return ruudukko[y*n+x];
}
void set(int *ruudukko, int y, int x, int value){
    ruudukko[y*n+x]=value;
}

void haku(int *old_ruudukko, bool *old_Arows, bool *old_Brows, bool *old_Acols, bool *old_Bcols, int Ay, int By){
   // cout<<Ay<<" "<<By<<"\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
     //       cout<<old_ruudukko[i*n+j];
        }
    //cout<<"\n";
    }
    bool end=true;
    for(int i=0;i<n;i++){
        //cout<<old_Arows[i]<<old_Brows[i]<<old_Acols[i]<<old_Bcols[i]<<"\n";
        if(old_Arows[i]==0 || old_Brows[i]==0 || old_Acols[i]==0 || old_Bcols[i]==0){
        //    cout<<"not";
            end=false;
        }
    }
    if(end){
        total+=1;
        return;
    }
    for(int i=Ay;i<=n;i++){
        if(old_Arows[Ay]){
      //      cout<<"a added to "<<i<<"\n";
            Ay=i;
        }
        else{
            break;
        }
    }
    for(int i=By;i<=n;i++){
        if(old_Brows[By]){
        //    cout<<"b to "<<i<<"\n";
            By=i;
        }
        else{
            break;
        }
    }
    for(int i=0;i<n;i++){
      //  cout<<old_Arows[i];
    }
    //cout<<"\n";

    for(int i=0;i<n;i++){
        //cout<<old_Brows[i];
    }
    //cout<<"\n";

    //cout<<Ay<<" "<<By<<"\n";
    if(Ay<=By){
      //  cout<<"chose A"<<"\n";
        for(int j=0;j<n;j++){
            if(!old_Acols[j] and get(old_ruudukko,Ay,j)==0){
                bool Arows[n];
                bool Acols[n];
                for(int i=0;i<n;i++){
                    Arows[i]=old_Arows[i];
                    Acols[i]=old_Acols[i];
                }
                int ruudukko[n*n];
                for(int i=0;i<n*n;i++){
                    ruudukko[i]=old_ruudukko[i];
                }

         //       cout<<"found:\n";
                for(int i=0;i<n;i++){
                    //cout<<old_Acols[i];
                }
                //cout<<"\n";
                set(ruudukko,Ay,j,1);
                Arows[Ay]=true;
                Acols[j]=true;
                haku(ruudukko,Arows,old_Brows,Acols,old_Bcols,Ay+1,By);
                //cout<<"fits "<<Ay<<j<<"\n";
            }
        }
        return;

    }
    else{
       // cout<<"chose B"<<"\n";
        for(int j=0;j<n;j++){
            if(!old_Bcols[j] and get(old_ruudukko,By,j)==0){
                bool Brows[n];
                bool Bcols[n];
                for(int i=0;i<n;i++){
                    Brows[i]=old_Brows[i];
                    Bcols[i]=old_Bcols[i];
                }
                int ruudukko[n*n];
                for(int i=0;i<n*n;i++){
                    ruudukko[i]=old_ruudukko[i];
                }



                set(ruudukko,By,j,2);
                Brows[By]=true;
                Bcols[j]=true;
                haku(ruudukko,old_Arows,Brows,old_Acols,Bcols,Ay,By+1);
                //cout<<"b fits"<<By<<j<<"\n";
            }
        }
        return;
    }
}
unordered_map<int,int> dict;
const int mod = pow(10,9)+7;
long D(int n){
    if(n==0){
        return 1;
    }
    if(n==1){
        return 0;
    }

    if(dict[n]!=0){
        return dict[n];
    
    }
    long value=(n-1)%mod*(D(n-1)%mod+D(n-2)%mod)%mod;
    dict[n]=value;
    return value;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    if(n<2){
        cout<<0<<"\n";
        exit(0);
    }

    if(n>5){
        long f=1;
        for(int i=2;i<=n;i++){
            f=(f*i)%mod;
        }
        //cout<<D(n)<<" "<<f<<"\n";
        cout<<(D(n)*f)%mod<<"\n";
        exit(0);
    }


    int ruudukko[n*n];
    for(int i=0;i<n;i++){
        
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c;
            if(c=='.'){
                set(ruudukko,i,j,0);
            }
            else if(c=='A'){
                set(ruudukko,i,j,1);

            }
            else{
                set(ruudukko,i,j,2);
            }
        }
    }

    for(int i=0; i<n;i++){
        for(int j=0; j<n;j++){
            //cout<<get(ruudukko,i,j);
        }
        //cout<<"\n";
    }
    //cout<<"\n";
    bool Arows[n];
    bool Brows[n];
    bool Acols[n];
    bool Bcols[n];

    for(int i=0;i<n;i++){
        Arows[i]=false;
        Brows[i]=false;
        Acols[i]=false;
        Bcols[i]=false;
        for(int j=0;j<n;j++){
            if(get(ruudukko,i,j)==1){
                Arows[i]=true;
            }
            if(get(ruudukko,i,j)==2){
                Brows[i]=true;
            }
            if(get(ruudukko,j,i)==1){
                Acols[i]=true;
            }
            if(get(ruudukko,j,i)==2){
                Bcols[i]=true;
            }
        }
    }
    for(int i=0;i<n;i++){
        ///cout<<Arows[i]<<"\n";
    
    }
    //cout<<"\n";
    for(int i=0;i<n;i++){
        //cout<<Acols[i];
    
    }
    int firstAy=n;
    int firstBy=n;
    for(int i=0;i<n;i++){
        if(!Arows[i]){
            firstAy=i;
            break;
        }
    }
    for(int i=0;i<n;i++){
        if(!Brows[i]){
            firstBy=i;
            break;
        }
    }
    if(firstBy==n and firstAy==n){
        cout<<"0"<<"\n";
        exit(1);
    }
    haku(ruudukko,Arows,Brows,Acols,Bcols,firstAy,firstBy);
    cout<<""<<total<<"\n";
}