import scala.annotation.tailrec
import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._


  val Array(h, w) = readLine.trim.split(' ').map(_.toInt)
  implicit val environment = new Environment(Array.tabulate(h){_ ⇒ readLine.trim})
  val program = readLine.trim.toList
  program match {
    case p Program Nil ⇒ execute(Robot(environment.findStart, North), p) match {
      case Some(count) ⇒ println(count)
      case _ ⇒ println(-1)
    }
    case _ ⇒ ???
  }

  object Program{
    def unapply(arg: List[Char]):Option[(Statement, List[Char])] = {
      arg match {
        case s Statement t ⇒ Some(takeAll(t, List(s)))
        case _ ⇒ Some(End, arg)
      }
    }
    @tailrec
    private[this] def takeAll(arg: List[Char], states: List[Token]): (Statement, List[Char]) = {
      arg match {
        case s Statement t ⇒ takeAll(t, s::states)
        case _ ⇒ (states.foldLeft(End: Statement){
          case (next, prev) ⇒ prev match {
            case O(o) ⇒ Move(o, next)
            case I(c, s) ⇒ If(c, s, next)
            case W(c, s) ⇒ While(c, s, next)
          }
        }, arg)
      }
    }

  }
  sealed trait Token
  case class O(operation: Operation) extends Token
  case class I(condition: (Robot, Environment) ⇒ Boolean, state: Statement) extends Token
  case class W(condition: (Robot, Environment) ⇒ Boolean, state: Statement) extends Token
  object Statement{
    def unapply(arg: List[Char]): Option[(Token, List[Char])] = {
      arg match {
        case o Operation t ⇒ Some(o, t)
        case i IfState t ⇒ Some(i, t)
        case w WhileState t ⇒ Some(w, t)
        case _ ⇒ None
      }
    }
  }
  object IfState{
    def unapply(arg: List[Char]): Option[(I, List[Char])] = {
      arg match {
        case '['::(c Condition (p Program ']'::t)) ⇒ Some(I(c, p), t)
        case _ ⇒ None
      }
    }
  }
  object WhileState{
    def unapply(arg: List[Char]): Option[(W, List[Char])] = {
      arg match {
        case '{'::(c Condition (p Program '}'::t)) ⇒ Some(W(c, p), t)
        case _ ⇒ None
      }
    }
  }
  object Operation {
    def unapply(arg: List[Char]): Option[(O, List[Char])] = {
      arg match {
        case '^'::t ⇒ Some(O(MoveForward), t)
        case 'v'::t ⇒ Some(O(MoveBack), t)
        case '<'::t ⇒ Some(O(TurnLeft), t)
        case '>'::t ⇒ Some(O(TurnRight), t)
        case _ ⇒ None
      }
    }
  }
  object Condition {
    def unapply(arg: List[Char]): Option[((Robot, Environment) ⇒ Boolean, List[Char])] = {
      arg match {
        case '~'::(c Condition t) ⇒ Some((r, e) => !c(r, e), t)
        case 'N'::t ⇒ Some((r, _) ⇒ r.direction == North, t)
        case 'E'::t ⇒ Some((r, _) ⇒ r.direction == East, t)
        case 'S'::t ⇒ Some((r, _) ⇒ r.direction == South, t)
        case 'W'::t ⇒ Some((r, _) ⇒ r.direction == West, t)
        case 'C'::t ⇒ Some((r, e) ⇒ e.isBlock(r.execute(MoveForward).position), t)
        case 'T'::t ⇒ Some((_, _) ⇒ true, t)
        case _ ⇒ None
      }
    }
  }
  @tailrec
  def execute(robot: Robot, program: Statement, count: Int = 0, stack: List[Goto] = Nil)(implicit environment: Environment): Option[Int] = {
    if (environment.isGoal(robot.position)) Some(count)
    else if (count > 10000000) None
    else {
      program match {
        case End ⇒ stack match {
          case Nil ⇒ None
          case Continue(r, _)::_ if robot == r ⇒ None
          case Break(s)::t ⇒ execute(robot, s, count, t)
          case Continue(_, s)::t ⇒ execute(robot, s, count, t)
        }
        case Move(op, next) ⇒
          val nextPos = robot.execute(op)
          if (environment.isBlock(nextPos.position)) execute(robot, next, count + 1, stack)
          else execute(nextPos, next, count + 1, stack)
        case If(condition, statement, next) ⇒
          if (condition(robot, environment)) execute(robot, statement, count, Break(next)::stack)
          else execute(robot, next, count, stack)
        case w@While(condition, statement, next) ⇒
          if (condition(robot, environment)) execute(robot, statement, count, Continue(robot, w)::stack)
          else execute(robot, next, count, stack)
      }
    }
  }
  sealed trait Goto
  case class Continue(robot: Robot, statement: Statement) extends Goto
  case class Break(statement: Statement) extends Goto
  class Environment(private[this] val mState: Array[String]) {
    def isBlock(coordinate: Coordinate): Boolean = mState(coordinate.y)(coordinate.x) == '#'
    def isGoal(coordinate: Coordinate): Boolean = mState(coordinate.y)(coordinate.x) == 'g'
    def findStart: Coordinate = mState.indices.find(y ⇒ mState(y).contains('s')).flatMap{y ⇒ mState(y).indices.find(x ⇒ mState(y)(x) == 's').map{x ⇒ Coordinate(x, y)}}.get
  }
  case class Robot(position: Coordinate, direction: AbsoluteDirection) {
    def execute(operation: Operation): Robot = {
      operation match {
        case MoveForward ⇒ direction match {
          case North ⇒ Robot(position + Coordinate(0, -1), direction)
          case South ⇒ Robot(position + Coordinate(0, 1), direction)
          case East ⇒ Robot(position + Coordinate(1, 0), direction)
          case West ⇒ Robot(position + Coordinate(-1, 0), direction)
        }
        case MoveBack ⇒ direction match {
          case North ⇒ Robot(position - Coordinate(0, -1), direction)
          case South ⇒ Robot(position - Coordinate(0, 1), direction)
          case East ⇒ Robot(position - Coordinate(1, 0), direction)
          case West ⇒ Robot(position - Coordinate(-1, 0), direction)
        }
        case TurnRight ⇒ Robot(position, direction.turnRight)
        case TurnLeft ⇒ Robot(position, direction.turnLeft)
      }
    }
  }
  sealed trait Statement
  case class Move(operation: Operation, next: Statement) extends Statement
  case class If(condition: (Robot, Environment) ⇒ Boolean, statement: Statement, next: Statement) extends Statement
  case class While(condition: (Robot, Environment) ⇒ Boolean, statement: Statement, next: Statement) extends Statement
  case object End extends Statement

  case class Coordinate(x: Int, y: Int) {
    def +(that: Coordinate): Coordinate = Coordinate(x + that.x, y + that.y)
    def -(that: Coordinate): Coordinate = Coordinate(x - that.x, y - that.y)
  }
  sealed trait Operation
  case object MoveForward extends Operation
  case object MoveBack extends Operation
  case object TurnRight extends Operation
  case object TurnLeft extends Operation
  sealed trait AbsoluteDirection {
    def turnRight: AbsoluteDirection
    def turnLeft: AbsoluteDirection
  }
  case object North extends AbsoluteDirection {
    override def turnRight: AbsoluteDirection = East
    override def turnLeft: AbsoluteDirection = West
  }
  case object South extends AbsoluteDirection {
    override def turnRight: AbsoluteDirection = West
    override def turnLeft: AbsoluteDirection = East
  }
  case object East extends AbsoluteDirection {
    override def turnRight: AbsoluteDirection = South
    override def turnLeft: AbsoluteDirection = North
  }
  case object West extends AbsoluteDirection {
    override def turnRight: AbsoluteDirection = North
    override def turnLeft: AbsoluteDirection = South
  }
  implicit class AbsoluteDirectionExtension(val direction: AbsoluteDirection) {
    def toIndex: Int = direction match {
      case North ⇒ 0
      case South ⇒ 1
      case East ⇒ 2
      case West ⇒ 3
    }
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}


Measured memory_bytes: 439524