#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

int prog(string &s, int &i);
int str(string &s, int &i);
int sif(string &s, int &i);
int swhile(string &s, int &i);
int sact(string &s, int &i);
int rule(string &s, int &i);
bool isGoal(int &x, int &y);

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
int dir = 0;
char f[60][60];
int x, y;
int ct = 0, ctwhile = 0;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    REP(i, N)REP(j, M){
        cin >> f[i][j];
        if(f[i][j] == 's'){
            y = i;
            x = j;
        }
    }
    string s;
    cin >> s;
    int i = 0;
    int ans;
    try{
        ans = prog(s, i);
    }catch(int res){
        ans = res;
    }
    if(!isGoal(x, y)) ans = -1;
    cout << ans << "\n";

    return 0;
}

int prog(string &s, int &i){
    int val = 0;
    while(s[i] == '{' 
        || s[i] == '[' 
        || s[i] == '^'
        || s[i] == '>'
        || s[i] == 'v'
        || s[i] == '<' ){
        val += str(s, i);
        if(isGoal(x, y)) return val;
    }
    return val;
}

int str(string &s, int &i){
    switch(s[i]){
    case '[':
        return sif(s, i);
    case '{':
        return swhile(s, i);
    default:
        return sact(s, i);
    }
}

int sif(string &s, int &i){
    int val = 0;
    i++;    // '['
    if(rule(s, i)) val = prog(s, i);
    int brac = 0;
    while(brac != -1){
        if(s[i] == '[') brac++;
        else if(s[i] == ']') brac--;
        i++;    // <sact> ]
    }
    return val;
}

int swhile(string &s, int &i){
    int val = 0;
    i++;    // {
    int irule = i;
    while(rule(s, i)){  // <rule>
        ctwhile++;
        val += prog(s, i);
        i = irule;
        if(isGoal(x, y)) break;
        if(ctwhile >= 5000000) throw -1;
    }
    if(isGoal(x, y)) return val;
    int brac = 0;
    while(brac != -1){
        if(s[i] == '{') brac++;
        else if(s[i] == '}') brac--;
        i++;    // <sact> }
    }
    return val;
}

int sact(string &s, int &i){
    ct++;
    switch(s[i]){
    case '^':
        if(f[y+dy[dir]][x+dx[dir]] != '#'){
            y += dy[dir];
            x += dx[dir];
        }
        break;
    case 'v':
        if(f[y-dy[dir]][x-dx[dir]] != '#'){
            y -= dy[dir];
            x -= dx[dir];
        }
        break;
    case '<':
        dir = (dir+3)%4;
        break;
    case '>':
        dir = (dir+1)%4;
        break;
    }
    // cout << x << " " << y << " " << s[i] << "\n";
    if(ct >= 5000000) throw -1;
    i++;    // <sact>
    return 1;
}

int rule(string &s, int &i){
    int res = 0, rev = 0;
    if(s[i] == '~'){
        rev = 1;
        i++;    // ~
    }
    switch(s[i]){
    case 'N':
        if(dir == 0) res = 1; 
        break;
    case 'E':
        if(dir == 1) res = 1; 
        break;
    case 'S':
        if(dir == 2) res = 1; 
        break;
    case 'W':
        if(dir == 3) res = 1; 
        break;
    case 'C':
        if(f[y+dy[dir]][x+dx[dir]] == '#') res = 1;
        break;
    case 'T':
        res = 1;
        break;
    }
    if(rev) res = (res+1)%2;
    i++;    // (rule)
    return res;
}

bool isGoal(int &x, int &y){
    if(f[y][x] == 'g') return true;
    else return false;
}


Measured memory_bytes: 3308