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

constexpr int dx[4] = {0, 1, 0, -1}; // north, west, south, east
constexpr int dy[4] = {-1, 0, 1, 0};

vector<int> par;

int expr(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v);
int while_(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v);
int if_(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v);

int exec(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v) {
    int res = 0;
    while(p < s.size() && v[y][x] != 'g' && s[p] != ']' && s[p] != '}') {
        res += expr(s, p, dir, y, x, v);
    }
    return res;
}

int expr(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v) {
    int res = 0;
    if(p < s.size() && v[y][x] != 'g') {
        if(s[p] == '{') {
            res += while_(s, p, dir, y, x, v);
        } else if(s[p] == '['){
            res += if_(s, p, dir, y, x, v);
        } else {
            if(s[p] == '^') {
                int ny = y + dy[dir], nx = x + dx[dir];
                if(ny < v.size() && nx < v[0].size() && v[ny][nx] != '#') {
                    y = ny;
                    x = nx;
                }
                ++p;
            } else if(s[p] == 'v') {
                int ny = y + dy[(dir+2)%4], nx = x + dx[(dir+2)%4];
                if(ny < v.size() && nx < v[0].size() && v[ny][nx] != '#') {
                    y = ny;
                    x = nx;
                }
                ++p;
            } else if(s[p] == '<') {
                dir = (dir + 3) % 4;
                ++p;
            } else if(s[p] == '>') {
                dir = (dir + 1) % 4;
                ++p;
            } else {
                cout << "pos: " << p << " c: " << s[p] << endl;
                assert("exec" && false);
            }
            res++;
        }
    }
    return res;
}

bool cond(string const& s, int& p, int dir, int y, int x, vector<string> const& v) {
    if(s[p] == '~') {
        return !cond(s, ++p, dir, y, x, v);
    }
    bool res = false;
    if(s[p] == 'N') {
        res = dir == 0;
    } else if(s[p] == 'E') {
        res = dir == 1;
    } else if(s[p] == 'S') {
        res = dir == 2;
    } else if(s[p] == 'W') {
        res = dir == 3;
    } else if(s[p] == 'C') {
        res = v[y+dy[dir]][x+dx[dir]] == '#';
    } else if(s[p] == 'T') {
        res = true;
    } else {
        cout << "p: " << p << "  c: " << s[p] << endl;
        assert("cond" && false);
    }
    ++p;
    return res;
}

int if_(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v) {
    int last = par[p];
    ++p;
    int res = 0;
    if(cond(s, p, dir, y, x, v)) {
        res = exec(s, p, dir, y, x, v);
    }
    p = last + 1;
    return res;
}

int while_(string const& s, int& p, int& dir, int& y, int& x, vector<string> const& v) {
    int last = par[p];
    ++p;
    int tmpp = p;
    int res = 0;
    map<tuple<int, int, int>, bool> visited;
    while(cond(s, p = tmpp, dir, y, x, v)) {
        auto t = make_tuple(dir, y, x);
        if(visited[t]) {
            throw runtime_error("infinit");
        }
        visited[t] = true;
        res += exec(s, p, dir, y, x, v);
        if(v[y][x] == 'g') {
            return res;
        }
    }
    p = last + 1;
    return res;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> v(H);
    string s;
    int sy, sx;
    for(int i=0; i<H; ++i) {
        cin >> v[i];
        for(int j=0; j<W; ++j) {
            if(v[i][j] == 's') {
                sy = i;
                sx = j;
            }
        }
    }
    cin >> s;
    par.resize(s.size());
    stack<int> while_pos;
    stack<int> if_pos;
    for(int i=0; i<s.size(); ++i) {
        if(s[i] == '{') {
            while_pos.push(i);
        } else if(s[i] == '}') {
            int f = while_pos.top();
            while_pos.pop();
            par[f] = i;
        }
        if(s[i] == '[') {
            if_pos.push(i);
        } else if(s[i] == ']') {
            int f = if_pos.top();
            if_pos.pop();
            par[f] = i;
        }
    }
    int p = 0, dir = 0;
    try {
        int res = exec(s, p, dir, sy, sx, v);
        if(v[sy][sx] == 'g') {
            cout << res << endl;
        } else {
            cout << -1 << endl;
        }
    } catch(...) {
        cout << -1 << endl;
    }
}


Measured memory_bytes: 3348