#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = (1LL<<32);
const int N = 1e4+10;

int pw[N];
int first[N];
bool can[N];

signed main()
{
    int n;
    string t,s;

   cin >> n >> t >> s;

   int tot = t.length();

   pw[0] = 1;
   for(int i=1;i<=n;i++) pw[i] = (pw[i-1]*tot)%MOD;

   int sz = s.length();

   //can[i] = 1 if first i characters of and last i characters of S are same.
   for(int i=1;i<=sz;i++)
   {
       can[i] = 1;
       for(int j=0;j<i;j++) can[i]&=(s[j] == s[sz-i+j]);
   }

   //first[i] = number of strings of length i such that S ends at i for the first time
   //1 - indexed
   for(int i=1;i<sz;i++) first[i] = 0;

   for(int i=sz;i<=n;i++)
   {
       first[i] = pw[i-sz];

       for(int j=sz;j<=i-sz;j++)
           first[i] = (first[i] - (first[j]*pw[i-sz-j])%MOD + MOD)%MOD;

       for(int j=max(sz,i-sz+1);j<i;j++)
           if(can[j-i+sz])
           {
                 first[i] = (first[i] - first[j] + MOD)%MOD;
           }
   }

   int end = 0;

   for(int i=1;i<=n;i++) end = (end + (first[i]*pw[n-i])%MOD)%MOD;

   int res = (pw[n] - end + MOD)%MOD;

   cout << res << '\n';
}