#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

//          N   E  S  W
int di[] = {-1, 0, 1, 0};
int dj[] = {0,  1, 0, -1};

int h,w;
char g[60][60];
char op[1000];
int vis[60][60][4][1010];
int vis_while[60][60][4][1010];
int dir;
int ci, cj;

char *Prog(char *);
pair<char*,bool> Cond(char *);

pair<char*,bool> Cond(char *p){
    bool inv = false;
    if(*p == '~'){
        inv = true;
        ++p;
    }
    bool res = false ||
        (*p=='N' && dir == 0) ||
        (*p=='E' && dir == 1) ||
        (*p=='S' && dir == 2) ||
        (*p=='W' && dir == 3) ||
        (*p=='C' && g[ci+di[dir]][cj+dj[dir]] == '#') ||
        (*p=='T');
    res ^= inv;
    ++p;
    return make_pair(p,res);
}

char *If(char *p){
    assert(*p == '[');
    ++p;
    bool cond;
    tie(p,cond) = Cond(p);
    if(cond){
        p = Prog(p);
        assert(*p == ']');
        ++p;
        return p;
    } else {
        int d = 1;
        // cout << "C " << p << endl;
        while(d != 0){
            if(*p == '[') ++d;
            else if(*p == ']') --d;
            ++p;
        }
        // cout << "D " << p << endl;
        return p;
    }
}

char *While(char *p){
    assert(*p == '{');
    ++p;
    char *cond_begin = p;
    while(1){
        if(vis_while[ci][cj][dir][p-op]) throw -1;
        vis_while[ci][cj][dir][p-op] = true;
        // cout << ci << ' ' << cj << ' ' << dir << ' ' << p-op << endl;

        bool cond;
        // cout << "A " << p << endl;
        tie(p,cond) = Cond(p);
        // cout << "B " << p << endl;
        // cout << cond << endl;
        if(cond){
            p = Prog(p);
            // cout << "C " << p << endl;
            assert(*p == '}');
            p = cond_begin;
        } else {
            int d = 1;
            while(d != 0){
                if(*p == '{') ++d;
                else if(*p == '}') --d;
                ++p;
            }
            // cout << "D " << p << endl;
            return p;
        }
    }
}

int cnt;
char *Move(char *p){
    if(vis[ci][cj][dir][p-op]) throw -1;
    vis[ci][cj][dir][p-op] = true;
    ++cnt;
    // cout << ci << ' ' << cj << ' ' << dir << endl;
    // cout << *p << endl;

    if(*p == '>') dir = (dir+1) & 3;
    if(*p == '<') dir = (dir-1) & 3;
    if(*p == 'v'){
        int ni = ci + di[(dir+2) & 3];
        int nj = cj + dj[(dir+2) & 3];
        if(g[ni][nj] != '#'){
            ci = ni; cj = nj;
        }
    }
    if(*p == '^'){
        int ni = ci + di[dir];
        int nj = cj + dj[dir];
        if(g[ni][nj] != '#'){
            ci = ni; cj = nj;
        }
    }

    if(g[ci][cj] == 'g') throw cnt;
    ++p;
    return p;
}

char *Statement(char *p){
    if(*p == '['){
        // cout << "H " << p << endl;
        p = If(p);
        // cout << "I " << p << endl;
    } else if(*p == '{'){
        p = While(p);
        // cout << "E " << p << endl;
    } else {
        // cout << "F " << p << endl;
        p = Move(p);
        // cout << "G " << p << endl;
    }
    return p;
}

char *Prog(char *p){
    while(string("[{^v<>").find(*p) != string::npos) p = Statement(p);
    return p;
}

int main(){
    while(cin >> h >> w){
        memset(vis, 0, sizeof vis);
        memset(vis_while, 0, sizeof vis_while);
        cnt = 0;
        dir = 0;
        rep(i,h) cin >> g[i];
        rep(i,h) rep(j,w) if(g[i][j] == 's') ci = i, cj = j;
        cin >> op;
        int ans = -1;
        try {
            Prog(op);
        } catch(int r){
            ans = r;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 116856