d13seed

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
int Next[(1 << 17) + 1][2];
long long dp[200][(1 << 17) + 1];
int n;
string s, t;
bitset<(1 << 17) + 1> Ans;
struct Trie
{
    struct node
    {
        int child[2];
    };
    vector<node> Tree;
    void new_node()
    {
        node tmp;
        for (int i = 0; i < 2; ++ i)
        {
            tmp.child[i] = -1;
        }
        Tree.push_back(tmp);
    }
    void add_num(string & num)
    {
        int id = 0;
        for (char c : num)
        {
            int w = c - '0';
            if (Tree[id].child[w] == -1)
            {
                new_node();
                Tree[id].child[w] = Tree.size() - 1;
            }
            id = Tree[id].child[w];
        }
        Ans.set(id, 1);
    }
    int get(string & num)
    {
        int id = 0;
        for (char c : num)
        {
            int w = c - '0';
            if (Tree[id].child[w] == -1)
            {
                return -1;
            }
            id = Tree[id].child[w];
        }
        return id;
    }
    void BuildNext(int id, string num)
    {
        if (num.length() == t.length())
        {
            Next[id][0] = id;
            Next[id][1] = id;
            return ;
        }
        for (char c = '0'; c < '2'; ++ c)
        {
            if (Tree[id].child[c - '0'] != -1)
            {
                Next[id][c - '0'] = Tree[id].child[c - '0'];
                BuildNext(Tree[id].child[c -'0'], num + c);
            }
            else
            {
                string tmp = num + c;
                while(get(tmp) == -1)
                {
                    tmp.erase(0, 1);
                }
                Next[id][c - '0'] = get(tmp);
            }
        }
    }
    int CountNode()
    {
        return Tree.size() - 1;
    }
};
Trie Tree;
void Gen(int i)
{
    if (i == t.length())
    {
        Tree.add_num(t);
        return ;
    }
    if (s[i] == '1')
    {
        t[i] = '1';
        Gen(i + 1);
    }
    else
    {
        for (char c = '0'; c <= '1'; ++ c)
        {
            t[i] = c;
            Gen(i + 1);
        }
    }
}
void read()
{
    cin >> n >> s;
    Tree.new_node();
    while(s.back() == '*')
    {
        s.pop_back();
    }
    t.resize(s.length());
    dp[0][0] = 1;
}
void solve()
{
    Gen(0);
    Tree.BuildNext(0, "");
    long long res = 0;
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j <= Tree.CountNode(); ++ j)
        {
            dp[i + 1][Next[j][0]] += dp[i][j];
            dp[i + 1][Next[j][1]] += dp[i][j];
        }
    }
    for (int i = 0; i <= Tree.CountNode(); ++ i)
    {
        if(Ans.test(i))
        {
            res += dp[n][i];
        }
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}