Dreptunghi2

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000;
const int MAXS = 355;
const int MOD = 1e9 + 7;

struct Cell
{
    int x1, y1, x2, y2;
    bool operator <(const Cell& other) const
    {
        if (x1 == other.x1)
        {
            if (x2 == other.x2)
            {
                if (y1 == other.y1)
                    return y2 < other.y2;
                return y1 < other.y1;
            }
            else
            {
                return x2 < other.x2;
            }
        }
        else
        {
            return x1 < other.x1;
        }
    }
};
map<Cell, int>mp;
char s[MAXS];
int rep[MAXS];
int sol[MAXN + 5];
int a[MAXN + 5][MAXN + 5];
int m, k, t;
int mx, my;
void getRep(int n)
{
    int nr = 0;
    for (int i = 1; i <= n; ++i)
    {
        if ('0' <= s[i] && s[i] <= '9')
        {
            nr = nr * 10 + s[i] - '0';
        }
        else
        {
            if (nr)
                rep[++m] = nr, nr = 0;
            if (s[i] == 'H')
                rep[++m] = -1;
            else if (s[i] == 'V')
                rep[++m] = -2;
            else
                rep[++m] = -3;
        }
    }
}
void Cerinta1(int n)
{
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (s[i] == '*')
            ans++;
    cout<<ans<<'\n';
}

void solve(int l, int r)
{
    mx = max(mx, l);
    my = max(my, r);
    if (rep[k] == -3)
    {
        k++;
        return ;
    }
    if (rep[k] == -1)
    {
        k++;
        int nl = l + rep[k];
        k++;
        solve(l, r);
        solve(nl, r);
    }
    else
    {
        k++;
        int nr = r + rep[k];
        k++;
        solve(l, r);
        solve(l, nr);
    }
}

void Cerinta2(int n)
{
    k = 1;
    solve(1, 1);
    cout<<mx<<" "<<my;
}
void Partaj(int x1, int y1, int x2, int y2)
{
    if (rep[k] == -3)
    {
        k++;
        t++;
        for (int i = x1; i <= x2; ++i)
            for (int j = y1; j <= y2; ++j)
                a[i][j] = t;
        return ;
    }
    if (rep[k] == -1)
    {
        k++;
        int nx = x1 + rep[k];
        k++;
        Partaj(x1, y1, nx - 1, y2);
        Partaj(nx, y1, x2, y2);
    }
    else
    {
        k++;
        int ny = y1 + rep[k];
        k++;
        Partaj(x1, y1, x2, ny - 1);
        Partaj(x1, ny, x2, y2);
    }
}

int getw(int x1, int y1, int x2, int y2)
{
    if (mp.count({x1, y1, x2, y2}))
        return mp[ {x1, y1, x2, y2}];
    int ind = -1, r = 0, okk = 0;
    for (int i = x1; i < x2; ++i)
    {
        bool ok = 1;
        for (int j = y1; j <= y2 && ok; ++j)
            if (a[i][j] == a[i + 1][j])
                ok = 0;
        if (ok && a[i][y2] < a[i + 1][y1])
        {
            ind = i;
            okk = 1;
            r = (r + 1LL * getw(x1, y1, ind, y2) * getw(ind + 1, y1, x2, y2)) % MOD;
        }
    }
    ind = -1;
    for (int j = y1; j < y2; ++j)
    {
        bool ok = 1;
        for (int i = x1; i <= x2 && ok; ++i)
            if (a[i][j] == a[i][j + 1])
                ok = 0;
        if (ok && a[x2][j] < a[x1][j + 1])
        {
            ind = j;
            okk = 1;
            r = (r + 1LL * getw(x1, y1, x2, ind) * getw(x1, ind + 1, x2, y2)) % MOD;
        }
    }
    if (okk == 0)
        r = 1;
    mp[ {x1, y1, x2, y2}] = r;
    return r;
}

void Cerinta3(int n)
{
    k = 1;
    solve(1, 1);
    k = 1;
    Partaj(1, 1, mx, my);
    cout<<getw(1, 1, mx, my)<<'\n';
}

void getm(int x1, int y1, int x2, int y2)
{
    int ind = -1;
    for (int i = x1; i < x2; ++i)
    {
        bool ok = 1;
        for (int j = y1; j <= y2 && ok; ++j)
            if (a[i][j] == a[i + 1][j])
                ok = 0;
        if (ok && a[i][y2] < a[i + 1][y1])
        {
            ind = i;
            break;
        }
    }
    if (ind != -1)
    {
        sol[++k] = -1;
        sol[++k] = ind - x1 + 1;
        getm(x1, y1, ind, y2);
        getm(ind + 1, y1, x2, y2);
    }
    else
    {
        for (int j = y1; j < y2; ++j)
        {
            bool ok = 1;
            for (int i = x1; i <= x2 && ok; ++i)
                if (a[i][j] == a[i][j + 1])
                    ok = 0;
            if (ok && a[x2][j] < a[x1][j + 1])
            {
                ind = j;
                break;
            }
        }
        if (ind != -1)
        {
            sol[++k] = -2;
            sol[++k] = ind - y1 + 1;
            getm(x1, y1, x2, ind);
            getm(x1, ind + 1, x2, y2);
        }
        else
        {
            sol[++k] = -3;
        }
    }
}

void Cerinta4(int n)
{
    k = 1;
    solve(1, 1);
    k = 1;
    Partaj(1, 1, mx, my);
    k = 0;
    getm(1, 1, mx, my);
    for (int i = 1; i <= k; ++i)
        if (sol[i] == -1)
            cout<<"H";
        else if (sol[i] == -2)
            cout<<"V";
        else if (sol[i] == -3)
            cout<<"*";
        else
            cout<<sol[i];
    cout<<'\n';
}

int main()
{
    int p;
    cin>>p;
    cin.get();
    cin.getline(s+1, MAXS);
    int len = strlen(s + 1);
    getRep(len);
    if(p == 1)
        Cerinta1(len);
    else if (p == 2)
        Cerinta2(len);
    else if (p == 3)
        Cerinta3(len);
    else
        Cerinta4(len);
    return 0;
}