#include "bits/stdc++.h"

using namespace std;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int h, w;
vector<string> a(50); // 盤面
string news = "NESW";

// vis[i][j][d][index] := 位置(i, j), 方向d で s[index] を実行したか
bool vis[50][50][4][1010];
bool ended = false; // ゴールした or 無限ループに入った
string s; // 命令列
int pos = 0; // 次に見る命令位置
int x, y; // ロボットのいる行, 列
int dir = 0; // ロボットの向いている方向(北N, 東E, 南S, 西W)
int ret = 0; // 移動回数

void program();
void statement();
void ifs();
void whiles();
void moves();
bool cond();

// program := {statement}
// statement := ifs | whiles | moves
// ifs := '[', cond, program, ']'
// whiles := '{', cond, program, '}'
// moves := '^' | '<' | 'v' | '>'
// cond := ['~'], N | E | S | W | C | T

void program()
{
    if (ended)
        return;
    while (pos < (int)s.size())
    {
        if (ended)
            return;
        if (s[pos] == '}' || s[pos] == ']')
            return;
        statement();
    }
}

void statement()
{
    if (ended)
        return;
    assert(pos < (int)s.size());
    if (s[pos] == '[')
    {
        ifs(); // if
    }
    else if (s[pos] == '{')
    {
        whiles(); // while
    }
    else
    {
        assert(s[pos] == '^' || s[pos] == 'v' || s[pos] == '<' || s[pos] == '>');
        moves(); // move
    }
}

void ifs()
{
    if (ended)
        return;
    pos++; // [
    bool f = cond();
    if (f)
    {
        program();
        pos++; // ]
    }
    else
    {
        int cnt = 1;
        while (cnt)
        {
            if (s[pos] == '[')
                cnt++;
            else if (s[pos] == ']')
                cnt--;
            pos++;
        }
    }
}

void whiles()
{
    if (ended)
        return;
    if (vis[x][y][dir][pos])
    {
        // 無限ループ検出
        ended = true;
        ret = -1;
        return;
    }
    else
    {
        vis[x][y][dir][pos] = 1;
    }
    int spos = pos;
    pos++; // {
    bool f = cond();
    if (f)
    {
        program();
        pos = spos;
        whiles();
    }
    else
    {
        int cnt = 1;
        while (cnt)
        {
            if (s[pos] == '{')
                cnt++;
            else if (s[pos] == '}')
                cnt--;
            pos++;
        }
    }
}

void moves()
{
    if (ended)
        return;
    ret++;
    if (s[pos] == '<')
        dir = (dir + 3) % 4; // left rotate
    else if (s[pos] == '>')
        dir = (dir + 1) % 4; // right rotate
    else if (s[pos] == '^')
    {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (a[nx][ny] != '#')
        {
            x = nx;
            y = ny;
        }
    }
    else
    {
        assert(s[pos] == 'v');
        int nd = (dir + 2) % 4;
        int nx = x + dx[nd], ny = y + dy[nd];
        if (a[nx][ny] != '#')
        {
            x = nx;
            y = ny;
        }
    }
    if (a[x][y] == 'g')
    {
        ended = true;
    }
    pos++;
}

bool cond()
{
    if (ended)
        return false;
    if (s[pos] == '~')
    {
        pos++;
        return !cond();
    }
    if (s[pos] == 'T')
    {
        pos++;
        return true;
    }
    if (s[pos] == 'C')
    {
        pos++;
        int nx = x + dx[dir], ny = y + dy[dir];
        return a[nx][ny] == '#';
    }
    char c = s[pos];
    pos++;
    for (int i = 0; i < 4; i++)
    {
        if (c == news[i])
        {
            return dir == i;
        }
    }
    assert(false);
    return false;
}

int main()
{
    cin >> h >> w;
    for (int i = 0; i < h; i++)
    {
        cin >> a[i];
        for (int j = 0; j < w; j++)
        {
            if (a[i][j] == 's')
            {
                x = i;
                y = j;
                a[i][j] = '.';
            }
        }
    }
    cin >> s;
    program();
    if (a[x][y] != 'g')
        ret = -1;
    cout << ret << endl;
}



Measured memory_bytes: 12448