#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef string::const_iterator State;
class ParseError
{
};

int ans = 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int x, y;
int ang = 0;
bool over;

vector<string> mp;
map<State, State> ifmp;
map<State, State> whilemp;
void ifst(State &begin);
void whilest(State &begin);

void consume(State &begin, char expected)
{
    if (*begin == expected)
    {
        begin++;
    }
    else
    {
        cerr << "Expected '" << expected << "' but got '" << *begin << "'"
             << endl;
        cerr << "Rest string is '";
        while (*begin)
        {
            cerr << *begin++;
        }
        cerr << "'" << endl;
        throw ParseError();
    }
}

void init(State &begin)
{
    stack<State> ifstack;
    stack<State> whilestack;
    while (*begin)
    {
        if (*begin == '[')
        {
            ifstack.push(begin);
        }
        if (*begin == ']')
        {
            auto to = ifstack.top();
            ifstack.pop();
            ifmp[to] = begin;
            ifmp[begin] = to;
        }

        if (*begin == '{')
        {
            whilestack.push(begin);
        }
        if (*begin == '}')
        {
            auto to = whilestack.top();
            whilestack.pop();
            whilemp[to] = begin;
            whilemp[begin] = to;
        }
        begin++;
    }
}

void move(State &begin)
{

    if (*begin == '^')
    {
        if (mp[y + dy[ang]][x + dx[ang]] != '#')
        {
            x += dx[ang];
            y += dy[ang];
        }
    }
    if (*begin == 'v')
    {
        if (mp[y - dy[ang]][x - dx[ang]] != '#')
        {
            x -= dx[ang];
            y -= dy[ang];
        }
    }

    if (*begin == '>')
    {
        ang = (ang + 1) % 4;
    }

    if (*begin == '<')
    {
        ang = (ang + 3) % 4;
    }
    begin++;

    ans++;
    if (mp[y][x] == 'g')
    {
        cout << ans << endl;
        exit(0);
    }

    return;
}

bool condition(State &begin)
{

    if (*begin == '~')
    {
        begin++;
        return !condition(begin);
    }
    if (*begin == 'N')
    {
        begin++;
        return ang == 0;
    }
    if (*begin == 'E')
    {
        begin++;
        return ang == 1;
    }
    if (*begin == 'S')
    {
        begin++;
        return ang == 2;
    }
    if (*begin == 'W')
    {
        begin++;
        return ang == 3;
    }
    if (*begin == 'C')
    {
        begin++;
        return mp[y + dy[ang]][x + dx[ang]] == '#';
    }
    if (*begin == 'T')
    {
        begin++;
        return true;
    }
    cerr << "ERROR in  condition: begin = " << *begin << endl;
    exit(1);
}

void prog(State &begin)
{
    //cerr << "prog" << endl;
    //cerr << *begin << endl;
    while (*begin && *begin != '}')
    {
        if (*begin == ']')
            begin++;
        else if (*begin == '[')
        {
            ifst(begin);
        }
        else if (*begin == '{')
        {
            whilest(begin);
        }
        else
        {
            move(begin);
        }
    }
}

void whilest(State &begin)
{

    auto elsepos = whilemp[begin];
    auto startpos = begin;
    consume(begin, '{');
    map<vector<int>, bool> visited;
    visited.clear();
    while (condition(begin))
    {

        prog(begin);
        begin = startpos;
        consume(begin, '{');
        if (visited[{x, y, ang}] == true)
        {
            cout << -1 << endl;
            exit(0);
        }
        visited[{x, y, ang}] = true;
    }
    begin = elsepos;
    consume(begin, '}');
}
void ifst(State &begin)
{
    auto elsepos = ifmp[begin];
    begin++;
    if (condition(begin) == true)
    {
        prog(begin);
    }
    else
    {
        begin = elsepos;
    }
}
int main()
{
    int h, w;
    cin >> h >> w;
    mp.clear();
    rep(i, h)
    {
        string s;
        cin >> s;
        mp.push_back(s);
    }
    rep(i, h) rep(j, w)
    {
        if (mp[i][j] == 's')
        {
            x = j;
            y = i;
            break;
        }
    }

    string code = "";
    cin >> code;

    State begin = code.begin();
    init(begin);
    begin = code.begin();
    prog(begin);
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 3324