#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<set>
#include<stack>
#include<string.h>

using namespace std;

char a[60][60];
int h,w;
int rx,ry;
int ans;
int dir=0;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
string s;

int go(string str){
    if(str=="")return 0;
    for(int i=0;i<str.length();i++){
        if(str[i]=='['){
            char condition=str[++i];
            bool tr;
            int rev=0;
            if(condition=='~'){
                rev=1;
                condition=str[++i];
            }
            string program;
            int j,l=1;
            for(j=i;j<str.length();j++){
                if(str[j]=='['){
                    l++;
                } else if(str[j]==']'){
                    l--;
                }
                if(l==0){
                    program=str.substr(i+1,j-i-1);
                    i=j;
                    break;
                }
            }
            if(condition=='N'){
                if(dir==0){
                    tr=true;
                } else {
                    tr=false;
                }
            } else if(condition=='E'){
                if(dir==1){
                    tr=true;
                } else {
                    tr=false;
                }
            } else if(condition=='S'){
                if(dir==2){
                    tr=true;
                } else {
                    tr=false;
                }
            } else if(condition=='W'){
                if(dir==3){
                    tr=true;
                } else {
                    tr=false;
                }
            } else if(condition=='C'){
                int nx=rx+dx[dir];
                int ny=ry+dy[dir];
                if(nx>=0&&nx<w&&ny>=0&&ny<h&&a[ny][nx]=='#'){
                    tr=true;
                } else {
                    tr=false;
                }
            } else if(condition=='T'){
                tr=true;
            }
            if(rev){
                tr=!tr;
            }
            if(!tr){
                continue;
            }
            int ret=go(program);
            if(ret==1){
                return 1;
            } else if(ret==0){
            }
        } else if(str[i]=='{'){
            set<pair<int,pair<int,int> > >pos;
            
            char condition=str[++i];
            bool tr;
            int rev=0;
            if(condition=='~'){
                rev=1;
                condition=str[++i];
            }
            string program;
            int j,l=1;
            for(j=i;j<str.length();j++){
                if(str[j]=='{'){
                    l++;
                } else if(str[j]=='}'){
                    l--;
                }
                if(l==0){
                    program=str.substr(i+1,j-i-1);
                    i=j;
//                    cout<<"program: "<<program<<endl;
                    break;
                }
            }
            while(1){
                //cout<<"rx: "<<rx<<"    ry: "<<ry<<endl;
                if(condition=='N'){
                    if(dir==0){
                        tr=true;
                    } else {
                        tr=false;
                    }
                } else if(condition=='E'){
                    if(dir==1){
                        tr=true;
                    } else {
                        tr=false;
                    }
                } else if(condition=='S'){
                    if(dir==2){
                        tr=true;
                    } else {
                        tr=false;
                    }
                } else if(condition=='W'){
                    if(dir==3){
                        tr=true;
                    } else {
                        tr=false;
                    }
                } else if(condition=='C'){
                    int nx=rx+dx[dir];
                    int ny=ry+dy[dir];
                    if(nx>=0&&nx<w&&ny>=0&&ny<h&&a[ny][nx]=='#'){
                        tr=true;
                    } else {
                        tr=false;
                    }
                } else if(condition=='T'){
                    tr=true;
                }
                if(rev){
                    tr=!tr;
                }
                if(!tr){
//                    cout<<"break!!! i:"<<i<<"  str"<<endl;
                    break;
                }
//                cout<<"in while program: "<<program<<endl;
                int ret=go(program);
//                cout<<"out while program: "<<program<<endl;
                if(ret==1){
                    return 1;
                } else if(ret==0){
                    //return 0;
                    //break;
                }
                
                if(pos.count(make_pair(dir,make_pair(rx, ry)))){
//                    cout<<"found        dir:"<<dir<<" rx: "<<rx<<"  ry:"<<ry<<endl;
//                    cout<<"returning -1    program: "<<program<<endl;
                    return 0;
                }
                pos.insert(make_pair(dir,make_pair(rx, ry)));
//                cout<<"inserting        dir:"<<dir<<" rx: "<<rx<<"  ry:"<<ry<<endl;
            }
            
        } else if(str[i]=='^'){
            ans++;
            int nx=rx+dx[dir];
            int ny=ry+dy[dir];
            if(nx>=0&&nx<w&&ny>=0&&ny<h&&a[ny][nx]!='#'){
                rx=nx,ry=ny;
//                cout<<"rx: "<<rx<<"   ry: "<<ry<<endl;
                if(a[ry][rx]=='g'){
                    return 1;
                }
            }
        } else if(str[i]=='v'){
            ans++;
            int nx=rx-dx[dir];
            int ny=ry-dy[dir];
            //cout<<"i: "<<i<<"  nx: "<<nx<<"  ny: "<<ny<<endl;
            if(nx>=0&&nx<w&&ny>=0&&ny<h&&a[ny][nx]!='#'){
                rx=nx,ry=ny;
                if(a[ry][rx]=='g'){
                    return 1;
                }
            }
        } else if(str[i]=='<'){
            ans++;
            dir=(dir+3)%4;
           // cout<<"dir: "<<dir<<endl;
        } else if(str[i]=='>'){
            ans++;
            dir=(dir+1)%4;
        }
        //cout<<rx<<" "<<ry<<endl;
    }
    return 0;
}

int main(){
    //freopen("/Users/shitian/Desktop/gcj/gcj/2643-in47.txt", "r", stdin);
    ans=0;
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
            if(a[i][j]=='s'){
                rx=j,ry=i;
            }
        }
    }
    cin>>s;
    int ret=go(s);
    if(ret==1){
        cout<<ans<<endl;
    } else if(ret==-1){
        cout<<-1<<endl;
    } else {
        cout<<-1<<endl;
    }
}

Measured memory_bytes: 1632