#include<bits/stdc++.h>

using namespace std;

int Length, mod = 1e9 + 7, N, M, dp[5009], dp2[5009], dp3[309][309];
char sir[5009];

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int substract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}

int Base = 32000, a[16390], b[16390], c[16390], rev[16390], basePower[5];
long double PI = acos (-1.0);
struct comp
{
    long double a, b;
    comp (): a (0.0), b (0.0) {}
    comp (int val): a (val), b (0.0) {}
    comp (long double _a, long double _b): a (_a), b (_b) {};
}a2[3][16390], b2[3][16390], c2[16390];
comp operator + (comp a, comp b) {return comp (a.a + b.a, a.b + b.b);}
comp operator - (comp a, comp b) {return comp (a.a - b.a, a.b - b.b);}
comp operator * (comp a, comp b) {return comp (a.a * b.a - a.b * b.b, a.b * b.a + a.a * b.b);}
comp compU (int n) {return comp (cos (2.0 * PI / n), sin (2.0 * PI / n));}

void DFT (comp a[], bool inv, int N)
{
    for (int i=0; i<N; i++)
        if (i < rev[i]) swap (a[i], a[rev[i]]);
    for (int l=2; l<=N; l <<= 1)
        for (int i=0; i<N; i+=l)
        {
            comp omega = compU (l), put (1.0, 0.0);
            if (inv) omega = compU (-l);
            for (int j=0; j<l / 2; j++)
            {
                comp u = a[i + j], v = a[i + j + l / 2] * put;
                a[i + j] = u + v;
                a[i + j + l / 2] = u - v;
                put = put * omega;
            }
        }
    if (inv)
    {
        for (int i=0; i<N; i++)
            a[i].a = (double) a[i].a / N, a[i].b = (double) a[i].b / N;
    }
}

void Convolution (int a[], int b[], int c[], int N)
{
    for (int i=N / 2; i<=N; i++)
        a[i] = b[i] = 0;
    for (int j=0; j<N; j++)
    {
        int auxA = a[j], auxB = b[j];
        for (int i=0; i<2; i++)
        {
            a2[i][j] = comp (auxA % Base), b2[i][j] = comp (auxB % Base);
            auxA /= Base, auxB /= Base;
        }
        c[j] = 0;
    }
    for (int i=0; i<2; i++)
        DFT (a2[i], 0, N), DFT (b2[i], 0, N);
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
        {
            for (int k=0; k<N; k++)
                c2[k] = a2[i][k] * b2[j][k];
            DFT (c2, 1, N);
            for (int k=0; k<N; k++)
                c[k] = add (c[k], mul (basePower[i + j], ((long long) (c2[k].a + 0.5)) % mod));
        }
/*    for (int i=0; i<N; i++)
    {
        int real_val = 0;
        for (int j=0; j<=i; j++)
            real_val = add (real_val, mul (a[j], b[i - j]));
        if (real_val != c[i])
        {
            printf ("FFT ERROR on %dth position %d instead of %d\n", i, c[i], real_val);
            printf ("%d\n", Length);
            for (int j=0; j<N; j++)
                printf ("%d ", a[j]);
            printf ("\n");
            for (int j=0; j<N; j++)
                printf ("%d ", b[j]);
            printf ("\n");
            exit (0);
        }
    }*/
}

void ConvolutionII (int a[], int c[], int N)
{
    for (int i=N / 2; i<=N; i++)
        a[i] = 0;
    for (int j=0; j<N; j++)
    {
        int aux = a[j];
        for (int i=0; i<2; i++)
        {
            a2[i][j] = comp (aux % Base);
            aux /= Base;
        }
        c[j] = 0;
    }
    for (int i=0; i<2; i++)
        DFT (a2[i], 0, N);
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
        {
            for (int k=0; k<N; k++)
                c2[k] = a2[i][k] * a2[j][k];
            DFT (c2, 1, N);
            for (int k=0; k<N; k++)
                c[k] = add (c[k], mul (basePower[i + j], ((long long) (c2[k].a + 0.5)) % mod));
        }
}

void calcRev (int N)
{
    for (int i=1; i<N; i++)
    {
        rev[i] = rev[i >> 1] >> 1;
        if (i & 1) rev[i] |= (N >> 1);
    }
}

void assign (int a[], int b[], int N)
{
    for (int i=0; i<N; i++)
        a[i] = b[i];
}

void pow (int a[], int b[], int E, int N)
{
    memset (b, 0, sizeof (b)), b[0] = 1;
    for (int bitPos = 0; (1 << bitPos) <= E; bitPos ++)
    {
        if (E & (1 << bitPos))
        {
            assign (c, b, N);
            Convolution (a, c, b, N);
        }
        assign (c, a, N);
        ConvolutionII (c, a, N);
    }
//    while (E --)
  //      assign (c, b, N), Convolution (a, c, b, N);
}

void Test ()
{
    int N;
    basePower[0] = 1;
//    for (int i=1; i<5; i++)
  //      basePower[i] = mul (basePower[i - 1], Base);
    scanf ("%d", &N), calcRev (N);
    for (int i=0; i<N; i++)
        scanf ("%d", &a[i]);
    for (int i=0; i<N; i++)
        scanf ("%d", &b[i]);
    Convolution (a, b, c, N);
    for (int i=0; i<N; i++)
        printf ("%d ", c[i]);
    printf ("\n");
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

//Test ();
//return 0;
///dp2[i] = numarul de moduri de a tasta de i ori si a ma intoarce la loc (care par sa fie 2^(i/2)*catalan(i/2))
///dp[i] = numarul de moduri de a tasta da i ori plecand de la un sir vid si a ma intoarce (pot tasta backspace in vid mai nou)
///dp3[i][j] = numarul de moduri de a tasta i chestii principale si printre ele de a baga j - i mutari irelevante
scanf ("%d\n%s", &N, sir + 1), M = strlen (sir + 1);
dp[0] = dp2[0] = 1;
for (int i=1; i<=N + 1; i++)
    for (int j=0; j + 2 <= i; j++)
        dp2[i] = add (dp2[i], mul (2 * dp2[j], dp2[i - j - 2]));
for (int i=1; i<=N + 1; i++)
{
    dp[i] = dp[i - 1];
    for (int j=0; j + 2 <= i; j++)
        dp[i] = add (dp[i], mul (2 * dp2[j], dp[i - j - 2]));
}
Length = 1, basePower[0] = 1;
for (int i=1; i<5; i++)
    basePower[i] = mul (basePower[i - 1], Base);
while (Length <= 2 * N + 3) Length += Length;
calcRev (Length);
a[0] = 0;
for (int i=1; i<=N + 1; i++)
    a[i] = dp2[i - 1];
pow (a, b, M, Length);
memset (a, 0, sizeof (a));
a[0] = 0;
for (int i=1; i<=N + 1; i++)
    a[i] = dp[i - 1];
Convolution (a, b, c, Length);
printf ("%d\n", c[N + 1]);
return 0;
}


Measured memory_bytes: 4480