$history = {}

class Goal < Exception; end
class Loop < Exception; end

$count = 0

def check(id)
	raise Goal if $x == $gx && $y == $gy
	a = [$x, $y, $dx, $dy, id]
	raise Loop if $history[a]
	$history[a] = 1
	$count += 1
end

def wall
	$a[$y + $dy][$x + $dx] == ?#
end

def right(id)
	check(id)
	$dx, $dy = -$dy, $dx
end

def left(id)
	check(id)
	$dx, $dy = $dy, -$dx
end

def forward(id)
	check(id)
	unless wall 
		$x += $dx
		$y += $dy
	end
end

def backward(id)
	check(id)
	unless $a[$y - $dy][$x - $dx] == ?#
		$x -= $dx
		$y -= $dy
	end
end

m, n = gets.split.map &:to_i
$a = (1..m).map { gets.chomp.scan /./ }

$dx = 0
$dy = -1
(0..m-1).each do |i|
	(0..n-1).each do |j|
		if $a[i][j] == ?s
			$y, $x = i, j
		end
		if $a[i][j] == ?g
			$gy, $gx = i, j
		end
	end
end

s = gets.chomp

cond = /~*[NESWCT]/
non_par = /[^{}\[\]]/

0 while s.gsub!(/\[(#{cond})(#{non_par}+)\]/, 'if \1;\2;end;') || s.gsub!(/{(#{cond})(#{non_par}+)}/, 'while \1;\2;end;')

s.gsub!(?T, "true")
s.gsub!(?~, ?!)
s.gsub!(?C, "wall")
s.gsub!(?N, "north")
s.gsub!(?E, "east")
s.gsub!(?W, "west")
s.gsub!(?S, "south")

action_id = 0
s.gsub!(?^) {"forward(#{action_id += 1});"}
s.gsub!(?v) {"backward(#{action_id += 1});"}
s.gsub!(?<) {"left(#{action_id += 1});"}
s.gsub!(?>) {"right(#{action_id += 1});"}

s.gsub!(?;, "\n")

begin
	eval s
rescue Goal
	p $count
rescue Loop
	p -1
end