#include <bits/stdc++.h>
using namespace std;
using ar3 = array<int,3>;

#define repl(i,a,b) for(int (i)=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)

int dh[4] = {-1,0,1,0};
int dw[4] = {0,1,0,-1};

map<int,int> make_par(string command){
  map<int,int> res;
  stack<int> st;
  rep(i,command.size()){
    switch(command[i]){
    case '{':
    case '[':
      st.push(i);
      break;
    case '}':
    case ']':
      int opp = st.top(); st.pop();
      res[i]=opp;
      res[opp]=i;
      break;
    }
  }
  return res;
}

bool judge(ar3 now, const vector<string>& tile, int idx, const string& command){
  bool inv = false;
  int h=now[0];
  int w=now[1];
  int dir=now[2];

  int nh = h+dh[dir];
  int nw = w+dw[dir];

  while(command[idx]=='~'){inv=!inv; idx++;}
  switch(command[idx]){
  case 'N': return (dir==0) ^ inv;
  case 'E': return (dir==1) ^ inv;
  case 'S': return (dir==2) ^ inv;
  case 'W': return (dir==3) ^ inv;
  case 'C': return (tile[nh][nw]=='#') ^ inv;
  case 'T': return true ^ inv;
  default: exit(1);
  }
}

int skip_judge(const string& command, int idx){
  while(true){
    switch(command[idx]){
    case '~':
    case 'N':
    case 'E':
    case 'S':
    case 'W':
    case 'C':
    case 'T':
      idx++;
      break;
    default:
      return idx;
    }
  }
}

bool cango(ar3 now, const vector<string>& tile, int dir){
  int h = now[0];
  int w = now[1];
  dir%=4;
  int nh = h+dh[dir];
  int nw = w+dw[dir];
  return tile[nh][nw]=='.';
}

int main(){
    // input
    int H,W;
    cin>>H>>W;

    vector<string> tile(H);
    string command;
    pair<int,int> st,go;
    rep(h,H)cin>>tile[h];
    cin>> command;

    // analyze
    rep(h,H)rep(w,W){
      switch(tile[h][w]){
      case 's':
        st = {h,w};
        tile[h][w]='.';
        break;
      case 'g':
        go = {h,w};
        tile[h][w]='.';
        break;
      }
    }

    // prepare
    ar3 now = {st.first, st.second, 0};
    map<int,int> par = make_par(command);

    vector<vector<vector<bitset<50>>>> went(
      command.size(), vector<vector<bitset<50>>>(
      4, vector<bitset<50>>(
      H)));

    // calculate
    int idx=0;
    int score=0;
    int dir = now[2];
    while(true){
      switch(command[idx]){
      case '{':
      case '[':
        if(judge(now, tile, idx+1, command))
          idx = skip_judge(command, idx+1);
        else
          idx = par[idx]+1;
        break;
      case '}':
        idx = par[idx];
        break;
      case ']':
        idx++;
        break;
      case '^':
        if(cango(now, tile, dir)){
          now[0]+=dh[dir];
          now[1]+=dw[dir];
        }
        idx++;
        score++;
        break;
      case 'v':
        dir = (dir+2)%4;
        if(cango(now, tile, dir)){
          now[0]+=dh[dir];
          now[1]+=dw[dir];
        }
        idx++;
        score++;
        break;
      case '<':
        now[2] = (now[2]+3)%4;
        idx++;
        score++;
        break;
      case '>':
        now[2] = (now[2]+1)%4;
        idx++;
        score++;
        break;
      }

      int h = now[0];
      int w = now[1];
      dir = now[2];
      //cout<< idx << " "<<h<<" "<<w<<" "<<dir<<endl;
      if(command.size()==idx || went[idx][dir][h][w]){
        cout<<-1<<endl;
        return 0;
      }
      else{
        went[idx][dir][h][w]=true;
      }
      if(h==go.first && w==go.second){
        cout<<score<<endl;
        return 0;
      }
    }
}



Measured memory_bytes: 4896