#include <iostream>

#include <algorithm>

#include <cstdio>

#include <string.h>

using namespace std;

const int maxn =;

typedef long long ll;

const ll mod=;

ll dp[maxn][maxn];

ll num[maxn][maxn];

char str[maxn];

ll dig[maxn];

void dfs(int loc, int lee , bool e, ll &value, ll &ge)

{

       value = ge = ;

       if(e==false&& num[loc][lee]!=- ){

           value=dp[loc][lee]; ge =num[loc][lee]; return ;

       }

       if(loc==&&lee==){

          value=, ge=; return ;

       }

       int we = e? str[loc-]-'':;

       ll ans=, nu=;

       if(we==){

           if(loc->=lee){

               dfs(loc-,lee,false,ans,nu);

               value=ans, ge=nu;

           }

           if( lee >  ){

               dfs(loc-,lee-,e,ans, nu);

               value=( value + ans + ( dig[loc-] )*nu%mod  )%mod;

               ge = ( nu + ge )%mod;

           }

       }else{

           if(loc->=lee){

            dfs(loc-,lee,e,ans,nu);

            value= ans; ge=nu;

           }

       }

    if(e==false) { dp[loc][lee] = value, num[loc][lee]=ge;  }

}

int main()

{

    int n;

    dig[]=;

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

        dig[i]=(dig[i-]*)%mod;

    while(scanf("%d%s",&n,str)==){

        int len = strlen(str);

        for(int i=; i<len/; ++i){

              char c = str[i];

              str[i]=str[len--i];

              str[len--i]=c;

        }

        memset(dp,,sizeof(dp));

        memset(num,-, sizeof(num));

        memset(num[],,sizeof(num[]));

        num[][]=;

        ll ans=,nu=;

        dfs( len , n , true, ans, nu);

         ll digt=;nu=;

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

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

                 digt++; nu= ( nu + dig[i])%mod;

             }

        }

             if(digt==n) ans=(ans-nu+mod)%mod;

        printf("%I64d\n",ans);

    }

    return ;

}