Maze Path Finder

In this problem, you are given a maze represented as a grid of characters. The maze contains walls ('#'), an entry point marked by 'S', an exit marked by 'E', and other cells that may be open ('.') or contain one of the directional markers (v, ^, >, <). A move is allowed if it obeys the following rules:

• Moving up is allowed if the cell immediately above is either ., E, or v.
• Moving down is allowed if the cell immediately below is either ., E, or ^.
• Moving left is allowed if the cell immediately to the left is either ., E, or >.
• Moving right is allowed if the cell immediately to the right is either ., E, or <.

Your task is to determine whether there exists a valid path from the start ('S') to the exit ('E') using a depth-first search (DFS) strategy. If such a path exists, output True; otherwise, output False.

The movement conditions can be summarized in the following LaTeX formulas:

For a move upward: $$grid[r-1][c] \in \{'.',\; E,\; v\}.$$

For a move downward: $$grid[r+1][c] \in \{'.',\; E,\; ^\}.$$

For a move to the left: $$grid[r][c-1] \in \{'.',\; E,\; >\}.$$

For a move to the right: $$grid[r][c+1] \in \{'.',\; E,\; <\}.$$

inputFormat

The input is given via standard input (stdin). The first line contains two integers R and C (the number of rows and columns, respectively). This is followed by R lines, each containing a string of length C representing a row of the maze.

outputFormat

Output a single line to standard output (stdout) containing either True if there is a valid path from 'S' to 'E' or False otherwise.

## sample

5 5
#####
#S..#
#.#E#
#.###
#####

True