Problem: A robot, a wall, and a goal are installed on the board, and a program that describes the behavior pattern of the robot is given.

The given program is represented by the following EBNF.


Program: = {statement};
Statement: = if statement | while statement | action statement;
if statement: = "[", condition, program, "]";
while statement: = "{", condition, program, "}";

Action statement: = "^" | "v" | "<" | ">";
Condition: = ["~"], "N" | "E" | "S" | "W" | "C" | "T";


A "program" consists of 0 or more "sentences", and if there is one or more sentences, the sentences are executed one by one in order from the first sentence. A "statement" is one of an "action statement", an "if statement", and a "while statement". The "action statement" is one of "^", "v", "<", ">", and the following actions are executed respectively.

* "^": Advance
* "v": Retreat
* "<": Rotate 90 degrees to the left
* ">": Rotate 90 degrees to the right



The "if statement" is an arrangement of "[", "condition", "program", "]" in order, and is executed by the following procedure.

1. Determine if the content of the "condition" is true
2. If the judgment is true, execute the contents of the "program" and end the processing of this if statement.
3. If the judgment is false, the processing of this if statement ends.



A "while statement" is an arrangement of "{", "condition", "program", and "}" in order, and is executed by the following procedure.

1. Determine if the content of the "condition" is true
2. If the judgment is true, execute the contents of "Program" and return to 1.
3. If the judgment is false, the processing of this while statement ends.



The "condition" is one of "N", "E", "S", "W", "C", "T", and can be prefixed with "~". Each description represents the following boolean values.

* If "~" is added at the beginning, the boolean value is reversed.
* N: True if facing north, false otherwise
* E: True if facing east, false otherwise
* S: True if facing south, false otherwise
* W: True if facing west, false otherwise
* C: True if there is a wall in front of you, false otherwise
* T: Always true



It is assumed that the robot is initially facing north. Robots cannot pass through walls and can only move empty squares. If the program tries to perform an action that passes over a wall, the robot will not move and will stay in place. Finally, when the robot reaches the goal, it interrupts all the programs that are being executed, even if they remain, and stops the operation.

At this time, I would like to know how long it will take for the robot to reach the goal. Since the robot can execute condition judgment and program loading at a very high speed, it is only the "action statement" that determines the actual operation time. Therefore, please tell me how many times this robot executes the "motion statement" before reaching the goal.

It is considered that the "action statement" has been executed even if the action of the "action statement" is not actually performed when trying to execute an action that passes over the wall.

Constraints

* 1 ≤ H, W ≤ 50
* 1 ≤ s number of characters ≤ 1,000
* ai, j is one of ".", "#", "S", "g"
* "s" and "g" appear only once each
* If i = 1 or i = H or j = 1 or j = W, then ai, j = "#" (the outer circumference of the board is guaranteed to be surrounded by a wall)
* The program given as s is syntactically correct

Input

The input is given in the following format.


H W
a1,1a1,2 ... a1, W
a2,1a2,2 ... a2, W
:::
aH, 1aH, 2 ... aH, W
s


H is the height of the board and W is the width of the board.

Next, the state of the board viewed from directly above is given. The top, bottom, left, and right of this board correspond to north, south, west, and east, respectively. Ai and j, which represent the state of each cell, are one of the following characters.

* "s": Robot (robot initial position. This square is guaranteed to have no walls)
* "g": Goal
* "#": Wall (Robots cannot move on the wall)
* ".": An empty square



The program given to the robot is input as a character string in s.

Output

If you can reach it, output "the number of" action statements "executed before reaching it". If you cannot reach it, output "-1". In addition, when trying to execute an action that passes over a wall, " Note that even if the action of the "action statement" is not performed, it is considered that the "action statement" has been executed (input example 1).

Examples

Input

5 3
###
#g#
#.#
#s#
###
^<^<vv


Output

5


Input

5 3

g#
.#
s#

^<^<vv


Output

5


Input

5 7

.#g..#
.###.#
s....#

{T{~C^}<}


Output

17


Input

5 7

.#g..#
.###.#
s....#

{T{~C^}>}


Output

-1

Solution (in CPP):

Solution:
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-5L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define seg_size 262144LL
#define MOD 998244353LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

// geometry library

typedef complex<long double> Point;
typedef pair<complex<long double>, complex<long double>> Line;

typedef struct Circle {
    complex<long double> center;
    long double r;
}Circle;

//内積、 dot(a,b) = |a||b|cos()
long double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}
//外積、cross(a,b) = |a||b|sin()
long double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

//線分と点の距離
long double Dist_Line_Point(Line a, Point b) {
    if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);
    if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);
    return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);
}

//線分の交差判定
int is_intersected_ls(Line a, Line b) {
    return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < 0) &&
        (cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < 0);
}

//線分の交点
Point intersection_l(Line a, Line b) {
    Point da = a.second - a.first;
    Point db = b.second - b.first;
    return a.first + da * cross(db, b.first - a.first) / cross(db, da);
}

//線分と線分の距離
long double Dist_Line_Line(Line a, Line b) {
    if (is_intersected_ls(a, b) == 1) {
        return 0;
    }
    return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });
}

//円と円の交点
pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {
    long double dist = abs(a.center - b.center);
    assert(dist <= eps + a.r + b.r);
    assert(dist+eps >= abs(a.r - b.r));
    Point target = b.center - a.center;
    long double pointer = target.real() * target.real() + target.imag() * target.imag();
    long double aa = pointer + a.r * a.r - b.r * b.r;
    aa /= 2.0L;
    Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa))/pointer,
            (aa* target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer};
    Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,
        (aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };
    r = r + a.center;
    l = l + a.center;
    return mp(l, r);
}

//end of geometry

template<typename A>
A pows(A val, ll b) {
    assert(b >= 1);
    A ans = val;
    b--;
    while (b) {
        if (b % 2) {
            ans *= val;
        }
        val *= val;
        b /= 2LL;
    }
    return ans;
}

template<typename A>
class Compressor {
public:
    bool is_zipped = false;
    map<A, ll> zipper;
    map<ll, A> unzipper;
    queue<A> fetcher;
    Compressor(){
        is_zipped = false;
        zipper.clear();
        unzipper.clear();
    }
    void add(A now) {
        assert(is_zipped == false);
        zipper[now] = 1;
        fetcher.push(now);
    }
    void exec() {
        assert(is_zipped == false);
        int cnt = 0;
        for (auto i = zipper.begin(); i != zipper.end(); ++i) {
            i->second = cnt;
            unzipper[cnt] = i->first;
            cnt++;
        }
        is_zipped = true;
    }
    ll fetch() {
        assert(is_zipped == true);
        A hoge = fetcher.front();
        fetcher.pop();
        return zipper[hoge];
    }
    ll zip(A now) {
        assert(is_zipped == true);
        assert(zipper.find(now) != zipper.end());
        return zipper[now];
    }
    A unzip(ll a) {
        assert(is_zipped == true);
        assert(a < unzipper.size());
        return unzipper[a];
    }
    ll next(A now) {
        auto x = zipper.upper_bound(now);
        if (x == zipper.end()) return zipper.size();
        return (ll)((*x).second);
    }
    ll back(A now) {
        auto x = zipper.lower_bound(now);
        if (x == zipper.begin()) return -1;
        x--;
        return (ll)((*x).second);
    }
};

template<typename A>
class Matrix {
public:
    vector<vector<A>> data;
    Matrix(vector<vector<A>> a) :data(a){

    }
    Matrix operator + (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = obj.data[i][q] + (this -> data[i][q]);
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator - (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = this->data[i][q] - obj.data[i][q];
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator * (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data[0].size());
        REP(i, this -> data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[0].size()) {
                A hoge = (this -> data[i][0]) * (obj.data[0][q]);
                for(int t = 1;t < obj.data[i].size();++t){
                    hoge += this -> data[i][t] * obj.data[t][q];
                }
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix &operator *= (const Matrix obj) {
        *this = (*this * obj);
        return *this;
    }
    Matrix& operator += (const Matrix obj) {
        *this = (*this + obj);
        return *this;
    }
    Matrix& operator -= (const Matrix obj) {
        *this = (*this - obj);
        return *this;
    }
};

class modint {
public:
    using u64 = std::uint_fast64_t;
    u64 value = 0;
    u64 mod;
    modint(ll a, ll b): value(((a%b) + 2 * b) % b),mod(b) {

    }
    modint operator+(const modint rhs) const{
        return modint(*this) += rhs;
    }
    modint operator-(const modint rhs) const{
        return modint(*this) -= rhs;
    }
    modint operator*(const modint rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator/(const modint rhs) const{
        return modint(*this) /= rhs;
    }
    modint& operator+=(const modint rhs) {
        assert(rhs.mod == mod);
        value += rhs.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
    modint& operator-=(const modint rhs) {
        assert(rhs.mod == mod);
        if (value < rhs.value) {
            value += mod;
        }
        value -= rhs.value;
        return *this;
    }
    modint& operator*=(const modint rhs) {
        assert(rhs.mod == mod);
        value = (value *  rhs.value) % mod;
        return *this;
    }
    modint& operator/=(modint rhs) {
        assert(rhs.mod == mod);
        ll rem = mod - 2;
        while (rem) {
            if (rem % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            rem /= 2LL;
        }
        return *this;
    }
    friend ostream& operator<<(ostream& os, modint& p) {
        os << p.value;
        return (os);
    }
};

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define int ll
int grid[50][50];
bool check[4][50][50][1000];
int back[2000];
int nexts[2000];
void solve(){
    int h, w;
    cin >> h >> w;
    pair<int, int> goal, now;
    int move = 0;
    REP(i, h) {
        string s;
        cin >> s;
        REP(q, w) {
            if (s[q] == '#') {
                grid[i][q] = 1;
            }
            else if (s[q] == 's') {
                now = mp(i, q);
            }
            else if(s[q] == 'g'){
                goal = mp(i, q);
            }
        }
    }
    string s;
    cin >> s;
    stack<int> gogo;
    REP(i, s.length()) {
        if (s[i] == '[' || s[i] == '{') {
            gogo.push(i);
        }
        if (s[i] == ']' || s[i] == '}') {
            int hoge = gogo.top();
            gogo.pop();
            back[i] = hoge;
            nexts[hoge] = i + 1;
        }
    }
    int itr = 0;
    int ans = 0;
    int dx[4] = { -1,0,1,0 };
    int dy[4] = { 0,1,0,-1 };
    auto mover = [h, w](pair<int, int> now, int move) {
        int dx[4] = { -1,0,1,0 };
        int dy[4] = { 0,1,0,-1 };
        int x = now.first + dx[move];
        int y = now.second + dy[move];
        if (x >= 0 && x < h && y >= 0 && y < w) {
            if (grid[x][y] == 0) return mp(x, y);
        }
        return now;
    };
    while (itr != s.length()) {
        if (s[itr] == '['||s[itr] == '{') {
            int jumping = nexts[itr];
            itr++;
            int exc = 0;
            if (s[itr] == '~') {
                exc = 1;
                itr++;
            }
            string m = "NESW";
            int valid = -1;
            REP(q, m.length()) {
                if (m[q] == s[itr]) {
                    if (q == move) {
                        valid = 1;
                    }
                    else {
                        valid = 0;
                    }
                    break;
                }
            }
            if (valid == -1) {
                if (s[itr] == 'T') {
                    valid = 1;
                }
                if (s[itr] == 'C') {
                    //skipped
                    if (mover(now, move) == now) {
                        valid = 1;
                    }
                    else {
                        valid = 0;
                    }
                }
            }
            valid ^= exc;
            if (valid == 0) {
                itr = jumping;
            }
            else {
                itr++;
            }
        }
        else if (s[itr] == '}') {
            itr = back[itr];
        }
        else if (s[itr] == ']') {
            itr++;
        }
        else {
            ans++;
            if (s[itr] == '<') {
                move += 3;
                move %= 4;
            }
            else if (s[itr] == '>') {
                move++;
                move %= 4;
            }
            else {
                if (s[itr] == '^') {
                    now = mover(now, move);
                }
                else {
                    now = mover(now, (move + 2)%4);
                }
            }
            itr++;
        }
        if (check[move][now.first][now.second][itr] == 1) {
            cout << -1 << endl;
            return;
        }
        check[move][now.first][now.second][itr] = 1;
        if (now == goal) {
            cout << ans << endl;
            return;
        }
    }
    cout << -1 << endl;
}

#undef int
int main() {
    init();
    solve();
}