#include "bits/stdc++.h"
using namespace std;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2643&lang=jp
typedef long long ll;
typedef pair<int, int> pii;
#define INF 1<<30
#define LINF 1LL<<60
#define MAX_C 1210311
int H, W;
pii loc, g;
vector<vector<char>> masu;
bool goal_f = false;
int move_cnt = 0;
int dir = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void _IF(int& at, string& str);
void _While(int& at, string& str);
void _Move(int& at, string& str);
bool _Logic(int& at, string& str);

void _IF(int & at, string & str){
	if (_Logic(at,str)) {
		_Move(at, str);
		if (goal_f) { at = str.length(); return; }
	}
	else {
		int paren = 1;
		while (paren != 0) {
			if (str[at] == '[')paren++;
			if (str[at] == ']') paren--;
			at++;
		}
	}
}

void _While(int & at, string & str){
	int _at = at;
	int roop_cnt = 0;
	while (_Logic(at, str)) {
		roop_cnt++;
		if (roop_cnt > MAX_C) { at = str.length();return; }
		if (move_cnt > MAX_C) { at = str.length();  return; }
		_Move(at, str);
		at = _at;
		if (goal_f) { at = str.length(); return; }
	}
	int paren = 1;
	while (paren != 0) {
		if (str[at] == '{') paren++;
		if (str[at] == '}') paren--;
		at++;
	}
}

void _Move(int & at, string & str){
	while (true) {
		if (str[at] == '[') {
			at++;
			_IF(at, str);
			if (goal_f) { at = str.length(); return; }
		}
		else if (str[at] == '{') {
			at++;
			_While(at, str);
			if (at == str.length())return;
			if (goal_f) { at = str.length(); return; }
		}
		else {
			if (at == str.length())return;
			if (str[at] == ']' || str[at] == '}') { at++; return;}
			move_cnt++;
			if (str[at] == '^') {
				int nx = loc.first + dx[dir], ny = loc.second + dy[dir];
				if (masu[nx][ny] != '#') {
					loc.first = nx; loc.second = ny;
				}
			}
			else if(str[at] == '>') {
				dir = (dir + 1) % 4;
			}
			else if (str[at] == '<') {
				dir = (dir + 3) % 4;
			}
			else if (str[at] == 'v') {
				int nx = loc.first + dx[(dir + 2) % 4],ny = loc.second + dy[(dir + 2) % 4];
				if (masu[nx][ny] != '#') {
					loc.first = nx; loc.second = ny;
				}
			}
			at++;

			if (loc == g) {
				goal_f = true;
				cout << move_cnt << endl;
				at = str.length(); return;
			}
		}
	}
}

bool _Logic(int & at, string & str){
	bool not_f = false;
	if (str[at] == '~') { not_f = true; at++; }
	if (str[at] == 'N') { at++; return (not_f ? dir != 0 : dir == 0); }
	if (str[at] == 'E') { at++; return (not_f ? dir != 1 : dir == 1); }
	if (str[at] == 'S') { at++; return (not_f ? dir != 2 : dir == 2); }
	if (str[at] == 'W') { at++; return (not_f ? dir != 3 : dir == 3); }
	if (str[at] == 'C') {
		int nx = loc.first + dx[dir], ny = loc.second + dy[dir];
		if (masu[nx][ny] == '#') {
			at++; return !not_f;
		}
		else {
			at++; return not_f;
		}
	}
	at++;
	return !not_f;
}


int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	/* input */
	cin >> H >> W;
	masu.resize(H, vector<char>(W));
	for (int i = 0; i < H;i++) {
		for (int j = 0; j < W;j++) {
			cin >> masu[i][j];
			if (masu[i][j] == 's') { loc = { i,j }; masu[i][j] = '.'; }
			if (masu[i][j] == 'g') { g = { i,j }; masu[i][j] = '.'; }
		}
	}
	string ebnf; cin >> ebnf;
	int at = 0;
	_Move(at, ebnf);
	if (!goal_f) {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3196