#include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll mod = 1e9+;

 int n;string s;

 int cal(int num){

     int res = ;

     while(num){

         res+=num%;

         num>>=;

     }

     return res;

 }

 int dp[][<<][];

 int main(){

     ios::sync_with_stdio(false);

     cin>>n>>s;s="**"+s;

     for(int i=;i<=n;i++){

         dp[][<<(i-)][i]=;

     }

     for(int i=;i<=n;i++) {

         for (int j=;j<(<<n); j++) {

             if(cal(j)!=i)continue;

             for(int k=;k<=n;k++){

                 if(!((<<k-)&j))continue;

                 for(int l=;l<=n;l++) {

                     if(!((<<l-)&j))continue;

                     if (s[i]=='') {

                         if(!(l==*k||k==*l))

                             dp[i][j][k] += dp[i - ][j ^ ( << k - )][l];

                     } else {

                         if((l==*k||k==*l))

                             dp[i][j][k]+=dp[i-][j^(<<k-)][l];

                     }

                     dp[i][j][k]%=mod;

                 }

             }

         }

     }

     ll ans=;

     for(int k=;k<=n;k++){

         ans=(ans+dp[n][(<<n)-][k])%mod;

     }

     cout<<ans<<endl;

 }