#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

int dx[8] = {0,1,0,-1,1,1,-1,-1};
int dy[8] = {-1,0,1,0,1,-1,1,-1};
char dirchar[] = "^>v<"; // "NESW"

bool visited[1000][50][50][4];

int ans = 0;
char S[50][51];
char commands[1001];
int x, y, dir;

bool check(bool tilde, char c) {
  bool ok = true;

  if (c == 'N') ok = dir == 0;
  if (c == 'E') ok = dir == 1;
  if (c == 'S') ok = dir == 2;
  if (c == 'W') ok = dir == 3;
  if (c == 'C') ok = S[y+dy[dir]][x+dx[dir]] == '#';

  return ok ^ tilde;
}

bool run(int l, int r) {
  if (l >= r) return false;

  if (commands[l] == '{') {
    bool tilde = false;
    char c;
    int nl = l+1, nr;

    if (commands[nl] == '~') {
      tilde = true;
      nl++;
    }
    c = commands[nl++];

    int t = 0;
    for (nr = nl; t || commands[nr] != '}'; nr++) {
      t += commands[nr] == '{';
      t -= commands[nr] == '}';
      assert(t >= 0);
    }
    assert(nr <= r);

    int prevY = -1;
    int prevX = -1;
    int prevD = -1;
    while (check(tilde, c) && nl < nr) {
      if (run(nl, nr)) return true;
      if (prevY == y && prevX == x && prevD == dir) {
        ans = -1;
        return true;
      }
      prevY = y;
      prevX = x;
      prevD = dir;
    }

    if (run(nr+1, r)) return true;

  } else if (commands[l] == '[') {
    bool tilde = false;
    char c;
    int nl = l+1, nr;

    if (commands[nl] == '~') {
      tilde = true;
      nl++;
    }
    c = commands[nl++];

    int t = 0;
    for (nr = nl; t || commands[nr] != ']'; nr++) {
      t += commands[nr] == '[';
      t -= commands[nr] == ']';
      assert(t >= 0);
    }
    assert(nr <= r);

    int prevY = -1;
    int prevX = -1;
    int prevD = -1;
    if (check(tilde, c) && nl < nr) {
      if (run(nl, nr)) return true;

      if (prevY == y && prevX == x && prevD == dir) {
        ans = -1;
        return true;
      }
      prevY = y;
      prevX = x;
      prevD = dir;
    }

    if (run(nr+1, r)) return true;

  } else {
    if (visited[l][y][x][dir]) {
      ans = -1;
      return true;
    }
    visited[l][y][x][dir] = true;

    if (commands[l] == '^') {
      if (S[y+dy[dir]][x+dx[dir]] != '#') {
        y += dy[dir];
        x += dx[dir];
      }
    } else  if (commands[l] == 'v') {
      if (S[y-dy[dir]][x-dx[dir]] != '#') {
        y -= dy[dir];
        x -= dx[dir];
      }
    } else if (commands[l] == '>') {
      dir = (dir + 1) % 4;
    } else if (commands[l] == '<') {
      dir = (dir + 3) % 4;
    } else {
      assert(false);
    }

    ans++;

    if (S[y][x] == 'g') {
      return true;
    }

    if (run(l+1, r)) return true;
  }

  return false;
}

int main(){
  int H, W, sx, sy;

  scanf("%d%d", &H, &W);

  for (int i=0; i<H; i++) {
    scanf("%s", S[i]);
    for (int j=0; j<W; j++) {
      if (S[i][j] == 's') {
        sy = i; sx = j;
      }
    }
  }

  scanf("%s", commands);
  int l = 0;
  int r = strlen(commands);
  x = sx; y = sy; dir = 0;

  debug(r);
  bool goal = run(l, r);

  if (goal) {
    printf("%d\n", ans);
  } else {
    puts("-1");
  }
  return 0;
}



Measured memory_bytes: 12920