#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)
 
const int H = 55, W = 55;
const int L = 1111;
 
string board[H];
int h,w;
string in;
 
bool isClear;
int walk=0;
 
int memo_if[L];
int memo_while[L];
 
int visit[H][W][4][L];
 
int x;
int y;
int dir;
 
int dx[4] ={0,1,0,-1};
int dy[4] ={-1,0,1,0};
 
 
void input(){
    cin>>h>>w;
    rep(i,h)cin>>board[i];
    cin>>in;
    in += "*";
 
    rep(i,L)memo_if[i]=memo_while[i];
 
    rep(i,h){
        rep(j,w){
            if(board[i][j]=='s'){
                board[i][j]='.';
                x = j;
                y = i;
                dir = 0;
            }
        }
    }
}
 
int sim_program(int);
 
bool sim_check(int st){
    char c = in[st];
 
    if(c=='N')return dir==0;
    if(c=='E')return dir==1;
    if(c=='S')return dir==2;
    if(c=='W')return dir==3;
 
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    if(c=='C')return board[ny][nx]=='#';
 
 
    return true;
}
 
int sim_if(int st){
    bool rev = false;
    if(in[st]=='~'){
        rev = true;
        st++;
    }
    bool res = rev^sim_check(st);
    st++;
 
    if(res){
        int res = sim_program(st);
        if(res==-1)return res;
    }
    return 0;
}
 
int sim_while(int st){
 
    int first = st;
    while(1){
 
        if(visit[y][x][dir][st]==1)return -1;
        visit[y][x][dir][st] = 1;
    bool rev = false;
        if(in[st]=='~'){
            rev = true;
            st++;
        }
        bool res = rev^sim_check(st);
        st++;
 
        if(res){
            int res = sim_program(st);
            if(res==-1)return res;
        }else{
            break;
        }
 
        st = first;
    }
    return 0;
}
 
int sim_simple(int st){
    char c = in[st];
 
    int nx = x;
    int ny = y;
    if(c=='^'){
        nx = x + dx[dir];
        ny = y + dy[dir];
    }
    if(c=='v'){
        nx = x - dx[dir];
        ny = y - dy[dir];
    }
    if(board[ny][nx]=='#'){
        nx = x;
        ny = y;
    }
 
    x = nx;
    y = ny;
 
 
    if(c=='<')dir = (dir+3)%4;
    if(c=='>')dir = (dir+1)%4;
 
    //printf("aa %d   %d %d %d\n",st,x,y,dir);
    walk++;
 
    if(board[y][x]=='g'){
        isClear = true;
        return -1;
    }
 
    if(visit[y][x][dir][st]==1)return -1;
    visit[y][x][dir][st]=1;
 
    return 0;
}
 
bool isSimple(char c){
    if(c=='^')return true;
    if(c=='v')return true;
    if(c=='>')return true;
    if(c=='<')return true;
    return false;
}
 
int end_if(int st){
    if(memo_if[st]!=0)return memo_if[st];
    int cnt = 0;
    int pos = st;
    while(1){
        if(in[pos]=='[')cnt++;
        if(in[pos]==']')cnt--;
        if(cnt==0){
            return memo_while[st]=pos;
        }
        pos++;
    }
 
    return -1;
}
 
int end_while(int st){
    if(memo_while[st]!=0)return memo_while[st];
    int cnt = 0;
    int pos = st;
    while(1){
        if(in[pos]=='{')cnt++;
        if(in[pos]=='}')cnt--;
        if(cnt==0){
            return memo_if[st]=pos;
        }
        pos++;
    }
    return -1;
}
 
int sim_program(int st){
 
    while(1){
 
        if(in[st]=='*' || in[st]=='}' || in[st]==']')return 0;
 
        if(in[st]=='['){
            int res = sim_if(st+1);
            if(res==-1)return res;
            st = end_if(st)+1;
            continue;
        }
        if(in[st]=='{'){
            int res = sim_while(st+1);
            if(res==-1)return res;
            st = end_while(st)+1;
            continue;
        }
        if(isSimple(in[st])){
            int res = sim_simple(st);
            if(res==-1)return res;
            st++;
            continue;
        }
    }
}
 
int solve(){
    sim_program(0);
    if(isClear)return walk;
    return -1;
}
 
 
int main(){
    input();
    cout<<solve()<<endl;
}

Measured memory_bytes: 47140