#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD NUM000007
#define EPS 0.000001
#define NUM 100000
using namespace std;

int H,W,goal_row,goal_col,order_count = 0;
int loop_count = 0; //???????????°??¨
char table[50][51],sentence[1001];
bool FLG; //clear?????????true?????????

enum DIR{
	North,
	East,
	West,
	South,
};

struct Info{
	DIR dir;
	int row,col;
};

Info robot;

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

//??¢??°????????????????????£?¨?
bool isTRUE(char CH);
void parse_IF(int left,int right);
void parse_WHILE(int left,int right);
void parse(int left,int right);


//?????¶?????????????????¢??°
bool isTRUE(char CH){

	int next_row,next_col;

	switch(CH){
	case 'N':
		return robot.dir == North;
	case 'E':
		return robot.dir == East;
	case 'S':
		return robot.dir == South;
	case 'W':
		return robot.dir == West;
	case 'C':
		switch(robot.dir){
		case North:
			next_row = robot.row-1;
			next_col = robot.col;
			break;
		case East:
			next_row = robot.row;
			next_col = robot.col+1;
			break;
		case West:
			next_row = robot.row;
			next_col = robot.col-1;
			break;
		case South:
			next_row = robot.row+1;
			next_col = robot.col;
			break;
		}

		if(rangeCheck(next_row,next_col) == false || table[next_row][next_col] == '#'){ //?????????????????????????????????????????????????£???§????????????
			return true;
		}else{
			return false;
		}
	case 'T':
		return true;
	}

	return false; //must not reach here
}


void parse_IF(int left,int right){ //sentence[left]???sentence[right]???parse

	loop_count++;
	if(loop_count > NUM)return; //?????????????????????

	if(left > right)return;

	bool reverse = false,judge;

	if(sentence[left] == '~'){
		reverse = true;
		left++;
	}

	judge = isTRUE(sentence[left]);

	//?????¶???????????¨?????£?????????parse??????
	if(reverse == false && judge == false)return;
	else if(reverse == true && judge == true)return;

	left++;
	//????????°?????????????????????????????????
	parse(left,right);
}

//????????????????????????????????????????????????
void parse_WHILE(int left,int right){

	int pre = left;

	loop_count++;
	if(loop_count > NUM)return; //?????????????????????

	if(left > right)return;

	bool reverse = false,judge;

	if(sentence[left] == '~'){
		reverse = true;
		left++;
	}

	judge = isTRUE(sentence[left]);

	//?????¶???????????¨?????£?????????parse??????
	if(reverse == false && judge == false)return;
	else if(reverse == true && judge == true)return;

	left++;

	//????????°?????????????????????????????????????????¶?????????????????????
	parse(left,right);
	if(FLG)return;
	parse_WHILE(pre,right);

}

void parse(int left,int right){

	loop_count++;
	if(loop_count > NUM)return; //?????????????????????

	int tmp_left,tmp_right,depth,next_row,next_col;
	bool clear_check;

	tmp_left = left;
	tmp_right = left;

	while(tmp_left <= right){ //??????????????????????????¨??¨?????????????????§

		clear_check = false;

		//1??????????????????&???????¨???\??????
		switch(sentence[tmp_left]){
		case '[': //if???
			depth = 0;
			tmp_left++;
			tmp_right = tmp_left;

			for(;;tmp_right++){
				if(sentence[tmp_right] == '['){
					depth++;
				}
				else if(sentence[tmp_right] == ']'){
					if(depth == 0){ //????????±??????????????¬??§?????????
						break;
					}
					depth--;
				}
			}

			if(tmp_left < tmp_right-1){ //???????????????1????????\????????¨????????´???
				parse_IF(tmp_left,tmp_right-1); //if???????§£?????????
			}

			clear_check = true; //if???????§£???????????????????????¢??????????????§?????????
			tmp_left = tmp_right+1;
			break;
		case '{':  //while???

			depth = 0;
			tmp_left++;
			tmp_right = tmp_left;

			for(;tmp_right <= right;tmp_right++){
				if(sentence[tmp_right] == '{'){
					depth++;
				}
				else if(sentence[tmp_right] == '}'){
					if(depth == 0){ //????????±??????????????¢??¬??§?????????
						break;
					}
					depth--;
				}
			}
			if(tmp_left < tmp_right-1){ //???????????????1????????\????????¨????????´???
				parse_WHILE(tmp_left,tmp_right-1); //if???????§£?????????
			}

			clear_check = true; //if???????§£???????????????????????¢??????????????§?????????
			tmp_left = tmp_right+1;
			break;
		case '^': //????????????
			order_count++;

			switch(robot.dir){
			case North:
				next_row = robot.row-1;
				next_col = robot.col;
				break;
			case East:
				next_row = robot.row;
				next_col = robot.col+1;
				break;
			case West:
				next_row = robot.row;
				next_col = robot.col-1;
				break;
			case South:
				next_row = robot.row+1;
				next_col = robot.col;
				break;
			}

			if(rangeCheck(next_row,next_col) == true && table[next_row][next_col] != '#'){ //????????????????????????????????????????£???§??????
				robot.row = next_row;
				robot.col = next_col;
				clear_check = true; //??´???????????????????????????????????????
			}

			tmp_left++;
			break;
		case 'v': //????????????
			order_count++;

			switch(robot.dir){
			case North:
				next_row = robot.row+1;
				next_col = robot.col;
				break;
			case East:
				next_row = robot.row;
				next_col = robot.col-1;
				break;
			case West:
				next_row = robot.row;
				next_col = robot.col+1;
				break;
			case South:
				next_row = robot.row-1;
				next_col = robot.col;
				break;
			}

			if(rangeCheck(next_row,next_col) == true && table[next_row][next_col] != '#'){ //????????????????????????????????????????£???§??????
				robot.row = next_row;
				robot.col = next_col;
				clear_check = true; //??´???????????????????????????????????????
			}

			tmp_left++;
			break;
		case '<': //??????90????????¢??????
			order_count++;

			switch(robot.dir){
			case North:
				robot.dir = West;
				break;
			case East:
				robot.dir = North;
				break;
			case West:
				robot.dir = South;
				break;
			case South:
				robot.dir = East;
				break;
			}
			tmp_left++;
			break;
		case '>': //??????90????????¢??????
			order_count++;
			switch(robot.dir){
			case North:
				robot.dir = East;
				break;
			case East:
				robot.dir = South;
				break;
			case West:
				robot.dir = North;
				break;
			case South:
				robot.dir = West;
				break;
			}
			tmp_left++;
			break;
		}

		if(clear_check){
			if(FLG)return;

			if(robot.row == goal_row && robot.col == goal_col){
				FLG = true;
				return;
			}
		}
	}
}

int main(){

	int left,right;

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

	robot.dir = North;

	for(int i = 0; i < H; i++){
		scanf("%s",table[i]);
		for(int k = 0; k < W; k++){
			if(table[i][k] == 's'){
				robot.row = i;
				robot.col = k;
			}else if(table[i][k] == 'g'){
				goal_row = i;
				goal_col = k;
			}
		}
	}

	scanf("%s",sentence);

	left = 0;
	for(right = 0; sentence[right] != '\0';right++);
	right--;

	FLG = false;

	parse(left,right);

	//printf("loop_count:%d\n",loop_count);

	if(!FLG)printf("-1\n");
	else{
		printf("%d\n",order_count);
	}
}

Measured memory_bytes: 2748