#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=55,INF=1<<30;
clock_t start,endd;
int H,W;
string S,X="NESWCT";
int sh,sw,gh,gw;
char T[MAX][MAX];
vector<int> dh={-1,0,1,0},dw={0,1,0,-1};
int h,w,dir,t,lim=5000005;

bool yame=false;

void bun(int &i);
void dousa(int &i);
bool jouken(int &i);

void bun(int &i){
    endd=clock();
    const double time=static_cast<double>(endd-start)/CLOCKS_PER_SEC*1000.0;
    if(time>=1800) t=lim;
    //cout<<"bun    "<<t<<" "<<h<<" "<<w<<" "<<X[dir]<<" "<<S[i]<<endl;
    while(i<si(S)){
        if(yame) return;
        
        if(t>=lim){
            cout<<-1<<endl;
            yame=1;
            return;
        }
        if(h==gh&&w==gw){
            cout<<t<<endl;
            yame=1;
            return;
        }
        
        if(S[i]=='['){
            i++;
            bool ok=jouken(i);
            
            if(ok){
                bun(i);
                i++;
            }
            else{
                int cnt=1;
                while(i<si(S)&&cnt){
                    if(S[i]=='[') cnt++;
                    if(S[i]==']') cnt--;
                    i++;
                }
            }
        }else if(S[i]=='{'){
            i++;
            while(1){
                int save=i;
                bool ok=jouken(i);
                
                if(ok){
                    bun(i);
                    i=save;
                }else{
                    int cnt=1;
                    while(i<si(S)&&cnt){
                        if(S[i]=='{') cnt++;
                        if(S[i]=='}') cnt--;
                        i++;
                    }
                    break;
                }
            }
        }else if(S[i]==']'){
            return;
        }else if(S[i]=='}'){
            return;
        }else{
            dousa(i);
        }
    }
}

void dousa(int &i){
    endd=clock();
    const double time=static_cast<double>(endd-start)/CLOCKS_PER_SEC*1000.0;
    if(time>=1800) t=lim;
    //cout<<"dousa  "<<t<<" "<<h<<" "<<w<<" "<<X[dir]<<" "<<S[i]<<endl;
    if(yame) return;
    
    if(t>=lim){
        cout<<-1<<endl;
        yame=1;
        return;
    }
    if(h==gh&&w==gw){
        cout<<t<<endl;
        yame=1;
        return;
    }
    
    if(S[i]=='^'){
        int toh=h+dh[dir],tow=w+dw[dir];
        if(T[toh][tow]!='#'){
            h=toh;
            w=tow;
        }
    }else if(S[i]=='v'){
        int toh=h+dh[(dir+2)%4],tow=w+dw[(dir+2)%4];
        if(T[toh][tow]!='#'){
            h=toh;
            w=tow;
        }
    }else if(S[i]=='<'){
        dir=(dir+3)%4;
    }else{
        dir=(dir+1)%4;
    }
    t++;
    i++;
}

bool jouken(int &i){
    endd=clock();
    const double time=static_cast<double>(endd-start)/CLOCKS_PER_SEC*1000.0;
    if(time>=1800) t=lim;
    //cout<<"jouken "<<t<<" "<<h<<" "<<w<<" "<<X[dir]<<" "<<S[i]<<endl;
    if(yame) return 0;
    
    if(t>=lim){
        cout<<-1<<endl;
        yame=1;
        return 0;
    }
    if(h==gh&&w==gw){
        cout<<t<<endl;
        yame=1;
        return 0;
    }
    bool gyaku=false,cor=false;
    if(S[i]=='~'){
        gyaku=true;
        i++;
    }
    
    for(int j=0;j<6;j++){
        if(S[i]==X[j]){
            if(dir==j) cor=true;
            if(j==4){
                int toh=h+dh[dir],tow=w+dw[dir];
                if(T[toh][tow]=='#') cor=true;
            }
            if(j==5) cor=true;
        }
    }
    
    i++;
    
    if(cor&&!gyaku) return true;
    if(!cor&&gyaku) return true;
    
    return false;
    
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    start=clock();
    
    cin>>H>>W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>T[i][j];
            if(T[i][j]=='s'){
                sh=i;
                sw=j;
            }
            if(T[i][j]=='g'){
                gh=i;
                gw=j;
            }
        }
    }
    
    h=sh;
    w=sw;
    dir=0;
    t=0;
    
    cin>>S;
    int i=0;
    bun(i);
    
    if(!yame) cout<<-1<<endl;
}



Measured memory_bytes: 3216