DuyenHai2020_PASSWORD

#include <iostream>
#include <cstdio>
#include <vector>
#define task "PASSWORD"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 3;
const ll mod = 1e9 + 7;
ll in[45], dp[N][35];
string s, p, tmp;
vector<int> v;
int n, m;

ll stoi(int i, int j)
{
    ll ans = 0;
    for (; i <= j; ++i)
        ans = ans * 10 + tmp[i] - '0';
    return ans;
}

ll Pow(ll a, ll b)
{
    ll tmp = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            tmp = tmp * a % mod;
        a = a * a % mod;
    }
    return tmp;
}

void Convert()
{
    v.push_back(0);
    for (int i = 0; i < tmp.size(); ++i)
    {
        if (tmp[i] >= 'a' && tmp[i] <= 'z')
            s.push_back(tmp[i]);
        else
        {
            int j = i;
            while (j < tmp.size() && tmp[j] >= '0' && tmp[j] <= '9')
                ++j;
            v.push_back(stoi(i, j - 1));
            i = j - 1;
        }
    }
    s = " " + s;
    p = " " + p;
}

void Read()
{
    cin >> n >> m >> tmp >> p;
    Convert();
}

void Add(ll &x, ll y)
{
    x += y;
    if (x >= mod)
        x -= mod;
}

void Solve()
{
    for (int i = 1; i <= 40; ++i)
        in[i] = Pow(i, mod - 2);
    for (int i = 0; i < s.size(); ++i)
        dp[i][0] = 1;
    for (int i = 1; i < s.size(); ++i)
        for (int j = 1; j < p.size(); ++j)
        {
            if (s[i] == p[j])
            {
                ll now = 1;
                dp[i][j] = dp[i - 1][j];
                for (int t = 1; t <= v[i] && t <= j && p[j - t + 1] == p[j]; ++t)
                {
                    now = now * (v[i] - t + 1) % mod * in[t] % mod;
                    Add(dp[i][j], dp[i - 1][j - t] * now % mod);
                }
            }
            else
                dp[i][j] = dp[i - 1][j];
            //cout << dp[i][j] << (j == p.size() - 1 ? "\n" : " ");
        }
    cout << (dp[s.size() - 1][p.size() - 1] % mod + mod) % mod;
}

main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Read();
    Solve();
}