#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
 
int H, W;
string program;
vector<string> F;
int curY, curX, dir;
int gY, gX;
bool used[1000][50][50][4];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
 
int check(int &pc) {
  bool isNot = false;
  bool ok = false;
  if(program[pc] == '~') {
    pc++;
    isNot = true;
  }
  char c = program[pc];
  ++pc;
  if(c == 'N' && dir == 0) ok = true;
  if(c == 'W' && dir == 1) ok = true;
  if(c == 'S' && dir == 2) ok = true;
  if(c == 'E' && dir == 3) ok = true;
  if(c == 'C' && F[curY + dy[dir]][curX + dx[dir]] == '#') ok = true;
  if(c == 'T') ok = true;
  if(isNot) return !ok;
  return ok;
}
 
int main() {
  cin >> H >> W;
  F.resize(H);
  for(int i = 0; i < H; ++i) {
    cin >> F[i];
  }
  cin >> program;
  int N = program.size();
  stack<int> if_stk;
  stack<int> while_stk;
  vector<int> else_go(N);
  vector<int> begin_go(N);
  vector<int> end_go(N);
  for(int i = 0; i < (int)program.size(); ++i) {
    if(program[i] == '{') while_stk.push(i);
    if(program[i] == '[') if_stk.push(i);
    if(program[i] == '}') {
      int ret = while_stk.top();
      while_stk.pop();
      begin_go[i] = ret;
      end_go[ret] = i;
    }
    if(program[i] == ']') {
      int ret = if_stk.top();
      if_stk.pop();
      else_go[ret] = i;
    }
  }
  for(int y = 0; y < H; ++y) {
    for(int x = 0; x < W; ++x) {
      if(F[y][x] == 's') {
        curY = y;
        curX = x;
        dir = 0;
        F[y][x] = '.';
      }
      if(F[y][x] == 'g') {
        gY = y;
        gX = x;
        F[y][x] = '.';
      }
    }
  }
  int pc = 0;
  int step = 0;
  memset(used, 0, sizeof(used));
  while(true) {
#if 0
    cerr << endl;
    cerr << program << endl;
    for(int i = 0; i < pc; ++i) {
      cerr << ' ';
    }
    cerr << '^' << endl;
    cerr << "curY = " << curY << endl;
    cerr << "curX = " << curX << endl;
    cerr << "dir = " << dir << endl;
#endif
 
    if(used[pc][curY][curX][dir]) {
      step = -1;
      break;
    }
    if(curY == gY && curX == gX) {
      break;
    }
    used[pc][curY][curX][dir] = true;
    if(program[pc] == '^') {
      step++;
      pc++;
      int tY = curY + dy[dir % 4];
      int tX = curX + dx[dir % 4];
      if(F[tY][tX] == '.') {
        curY = tY;
        curX = tX;
      }
    }
    else if(program[pc] == 'v') {
      step++;
      pc++;
      int tY = curY + dy[(dir + 2) % 4];
      int tX = curX + dx[(dir + 2) % 4];
      if(F[tY][tX] == '.') {
        curY = tY;
        curX = tX;
      }
    }
    else if(program[pc] == '<') {
      step++;
      pc++;
      dir = (dir + 1) % 4;
    }
    else if(program[pc] == '>') {
      step++;
      pc++;
      dir = (dir + 3) % 4;
    }
    else if(program[pc] == '[') {
      int tmp = pc;
      pc++;
      if(!check(pc)) {
        pc = else_go[tmp] + 1;
      }
    }
    else if(program[pc] == ']') {
      pc++;
    }
    else if(program[pc] == '{') {
      int tmp = pc;
      pc++;
      if(!check(pc)) {
        pc = end_go[tmp] + 1;
      }
    }
    else if(program[pc] == '}') {
      pc = begin_go[pc];
    }
  }
  cout << step << endl;
}

Measured memory_bytes: 11008