#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
bool chmin(int &a, int b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
int dh[4] = {-1, 0, 1, 0};
int dw[4] = {0, 1, 0, -1};
int H, W;
string field[55];
string program;
int sh, sw, gh, gw;
int dist[55][55][4][1205];
int match[1205];

void initialize() {
    stack<int> sta;
    for(int i = 0; i < program.size(); i++) {
        if(program[i] == '[' || program[i] == '{') {
            sta.push(i);
            continue;
        }
        if(program[i] == ']' || program[i] == '}') {
            int now = sta.top();
            sta.pop();
            match[i] = now;
            match[now] = i;
        }
    }
}


struct query {
    int h;
    int w;
    int d;
    int i;
    query(int _h, int _w, int _d, int _i) {
        h = _h;
        w = _w;
        d = _d;
        i = _i;
    }
};
bool valid(query &now) {
    char d = program[now.i];
    now.i++;
    if(d == '~') {
        return !valid(now);
    }
    if(d == 'N') return now.d == 0;
    if(d == 'E') return now.d == 1;
    if(d == 'S') return now.d == 2;
    if(d == 'W') return now.d == 3;
    if(d == 'C') {
        return field[now.h+dh[now.d]][now.w+dw[now.d]] == '#';
    }
    return true;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for(int h = 1; h <= H; h++) {
        cin >> field[h];
        field[h] = "#" + field[h];
        for(int w = 1; w <= W; w++) {
            if(field[h][w] == 's') {
                sh = h;
                sw = w;
            }
            if(field[h][w] == 'g') {
                gh = h;
                gw = w;
            }
        }
    }
    cin >> program;
    initialize();
    for(int h = 0; h <= H; h++) {
        for(int w = 0; w <= W; w++) {
            for(int d = 0; d <= 3; d++) {
                for(int i = 0; i <= 1200; i++) dist[h][w][d][i] = INF;
            }
        }
    }
    dist[sh][sw][0][0] = 0;
    deque<query> que;
    que.push_back({sh, sw, 0, 0});
    while(!que.empty()) {
        query now = que.front();
        que.pop_front();
        //cerr << now.h << " " << now.w << " " << now.d << " " << now.i << " " << dist[now.h][now.w][now.d][now.i] << endl;
        if(now.i >= program.size()) continue;
        int nowcost = dist[now.h][now.w][now.d][now.i];
        if(program[now.i] == '[' || program[now.i] == '{') {
            int copyi = now.i;
            now.i++;
            if(valid(now)) {
                if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_front(now);
                continue;
            }
            now.i = match[copyi] + 1;
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_front(now);
            continue;
        }
        if(program[now.i] == '}') {
            now.i = match[now.i];
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_front(now);
            continue;
        }
        if(program[now.i] == ']') {
            now.i++;
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_front(now);
            continue;
        }
        nowcost++;
        char operation = program[now.i];
        now.i++;
        if(operation == '^') {
            int newh = now.h + dh[now.d];
            int neww = now.w + dw[now.d];
            if(field[newh][neww] != '#') {
                now.h = newh;
                now.w = neww;
            }
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_back(now);
            continue;
        }
        if(operation == 'v') {
            int newh = now.h - dh[now.d];
            int neww = now.w - dw[now.d];
            if(field[newh][neww] != '#') {
                now.h = newh;
                now.w = neww;
            }
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_back(now);
            continue;
        }
        if(operation == '<') {
            now.d = (now.d + 3) % 4;
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_back(now);
            continue;
        }
        if(operation == '>') {
            now.d = (now.d + 1) % 4;
            if(chmin(dist[now.h][now.w][now.d][now.i], nowcost)) que.push_back(now);
            continue;
        }
    }
    int ans = INF;
    for(int d = 0; d <= 3; d++) {
        for(int i = 0; i <= program.size(); i++) chmin(ans, dist[gh][gw][d][i]);
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 52444