adbrack (VNOJ)

// https://oj.vnoi.info/problem/adbrack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e2 + 5;

/// M là số chữ số ước lượng, nhớ thay đổi với các bài/ Bản dùng vector (an toàn) ở đây: https://pastebin.com/tvmKwAQA
/// Nếu không có phép nhân thì nên đẩy BASE lên 1e17 hoặc 1e18
/// a = Bignum(5) || a = Bignum("5") đều được, tuy nhiên khuyến khích dùng loại 1
/// cin >> a hay a.read() đều được
/// cout << a hay a.print() đều được, khuyến khích dùng loại 1
/// Phép chia và phép mod chỉ dùng cho số nguyên và cho ra kết quả nguyên
/// Phép nhân fft

using cd = complex<long double>;
const long double PI = acos(-1);
const int M = 100;
const ll BASE = 1e7;
const int gd = log10(BASE);
const int maxn = M / gd + 1;
struct Bignum
{
    int n;
    ll a[maxn];
    Bignum(ll x = 0)
    {
        memset(a, 0, sizeof a);
        n = 0;
        do
        {
            a[n++] = x % BASE;
            x /= BASE;
        } while (x);
    }
    Bignum(const string &s)
    {
        Convert(s);
    }
    ll stoll(const string &s)
    {
        ll ans(0);
        for (auto i : s)
            ans = ans * 10 + i - '0';
        return ans;
    }
    void Convert(const string &s)
    {
        memset(a, 0, sizeof a);
        n = 0;
        for (int i = s.size() - 1; ~i; --i)
        {
            int j = max(0, i - gd + 1);
            a[n++] = stoll(s.substr(j, i - j + 1));
            i = j;
        }
        fix();
    }
    void fix()
    {
        ++n;
        for (int i = 0; i < n - 1; ++i)
        {
            a[i + 1] += a[i] / BASE;
            a[i] %= BASE;
            if (a[i] < 0)
            {
                a[i] += BASE;
                --a[i + 1];
            }
        }
        while (n > 1 && a[n - 1] == 0)
            --n;
    }
    Bignum &operator+=(const Bignum &x)
    {
        n = max(n, x.n);
        for (int i = 0; i < n; ++i)
            a[i] += x.a[i];
        fix();
        return *this;
    }
    Bignum &operator-=(const Bignum &x)
    {
        for (int i = 0; i < x.n; ++i)
            a[i] -= x.a[i];
        fix();
        return *this;
    }
    void fft(vector<cd> &a, bool invert)
    {
        int n = a.size();

        for (int i = 1, j = 0; i < n; i++)
        {
            int bit = n >> 1;
            for (; j & bit; bit >>= 1)
                j ^= bit;
            j ^= bit;

            if (i < j)
                swap(a[i], a[j]);
        }

        for (int len = 2; len <= n; len <<= 1)
        {
            double ang = 2 * PI / len * (invert ? -1 : 1);
            cd wlen(cos(ang), sin(ang));
            for (int i = 0; i < n; i += len)
            {
                cd w(1);
                for (int j = 0; j < len / 2; j++)
                {
                    cd u = a[i + j], v = a[i + j + len / 2] * w;
                    a[i + j] = u + v;
                    a[i + j + len / 2] = u - v;
                    w *= wlen;
                }
            }
        }

        if (invert)
        {
            for (cd &x : a)
                x /= n;
        }
    }
    Bignum &operator*=(const Bignum &x)
    {
        int m = 1;
        while (m < n + x.n)
            m <<= 1;
        vector<cd> fa(m), fb(m);
        for (int i = 0; i < m; ++i)
        {
            fa[i] = a[i];
            fb[i] = x.a[i];
        }
        fft(fa, false); /// dft
        fft(fb, false); /// dft
        for (int i = 0; i < m; i++)
            fa[i] *= fb[i];
        fft(fa, true); ///Interpolation
        n = m;
        for (int i = 0; i < n; ++i)
            a[i] = round(fa[i].real());
        fix();
        return *this;
    }
    Bignum &operator/=(const ll &x)
    {
        ll r = 0ll;
        for (int i = n - 1; i > -1; --i)
        {
            r = r * BASE + a[i];
            a[i] = r / x;
            r %= x;
        }
        fix();
        return *this;
    }
    Bignum operator+(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c += s;
        return c;
    }
    Bignum operator-(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c -= s;
        return c;
    }
    Bignum operator*(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c *= s;
        return c;
    }
    Bignum operator/(const ll &x)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c /= x;
        return c;
    }
    ll operator%(const ll &x)
    {
        ll ans(0);
        for (int i = n - 1; ~i; --i)
            ans = (ans * BASE + a[i]) % x;
        return ans;
    }
    int com(const Bignum &s) const
    {
        if (n < s.n)
            return 1;
        if (n > s.n)
            return 2;
        for (int i = n - 1; i > -1; --i)
            if (a[i] > s.a[i])
                return 2;
            else if (a[i] < s.a[i])
                return 1;
        return 3;
    }
    bool operator<(const Bignum &s) const
    {
        return com(s) == 1;
    }
    bool operator>(const Bignum &s) const
    {
        return com(s) == 2;
    }
    bool operator==(const Bignum &s) const
    {
        return com(s) == 3;
    }
    bool operator<=(const Bignum &s) const
    {
        return com(s) != 2;
    }
    bool operator>=(const Bignum &s) const
    {
        return com(s) != 1;
    }
    void read()
    {
        string s;
        cin >> s;
        Convert(s);
    }
    void print()
    {
        int i = n;
        while (i > 0 && a[i] == 0)
            --i;
        cout << a[i];
        for (--i; ~i; --i)
            cout << setw(gd) << setfill('0') << a[i];
    }
    friend istream &operator>>(istream &in, Bignum &x)
    {
        string s;
        in >> s;
        x.Convert(s);
        return in;
    }
    friend ostream &operator<<(ostream &out, const Bignum &x)
    {
        int i = x.n;
        while (i > 0 && x.a[i] == 0)
            --i;
        out << x.a[i];
        for (--i; ~i; --i)
            out << setw(gd) << setfill('0') << x.a[i];
        return out;
    }
};

char open[] = {'(', '[', '{'},
     close[] = {')', ']', '}'};

int n, k;
Bignum dp[N][N / 2], ans(0), Pow[N / 2];
string s;

void Read()
{
    //freopen("test.INP", "r", stdin);
    //freopen("test.OUT", "w", stdout);
    cin >> n >> k >> s;
    s = " " + s;
}

void Solve()
{
    dp[0][0] = Pow[0] = Bignum(1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= n - i && j <= i && j <= k; ++j)
        {
            dp[i][j] = dp[i - 1][j + 1];
            if (j)
                dp[i][j] += dp[i - 1][j - 1];
        }
        if (i <= n / 2)
            Pow[i] = Pow[i - 1] * Bignum(3);
    }

    string cnt;
    cnt.reserve(n);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 3 && open[j] < s[i]; ++j)
            if (!((n - i - (cnt.size() + 1)) & 1))
                ans += Pow[(n - i - (cnt.size() + 1)) / 2] * dp[n - i][cnt.size() + 1];

        if (cnt.size() && cnt.back() < s[i])
            ans += Pow[(n - i - (cnt.size() - 1)) / 2] * dp[n - i][cnt.size() - 1];

        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            cnt.push_back(s[i] == '(' ? ')' : (s[i] == '[' ? ']' : '}'));
        else
            cnt.pop_back();

        //cout << i << " " << ans << "\n";
    }

    cout << ans + 1;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}