<p>You are given a square <code>board</code>&nbsp;of characters. You can move on the board starting at the bottom right square marked with the character&nbsp;<code>&#39;S&#39;</code>.</p>

<p>You need&nbsp;to reach the top left square marked with the character <code>&#39;E&#39;</code>. The rest of the squares are labeled either with a numeric character&nbsp;<code>1, 2, ..., 9</code> or with an obstacle <code>&#39;X&#39;</code>. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.</p>

<p>Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, <strong>taken modulo <code>10^9 + 7</code></strong>.</p>

<p>In case there is no path, return&nbsp;<code>[0, 0]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> board = ["E23","2X2","12S"]
<strong>Output:</strong> [7,1]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> board = ["E12","1X1","21S"]
<strong>Output:</strong> [4,2]
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> board = ["E11","XXX","11S"]
<strong>Output:</strong> [0,0]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= board.length == board[i].length &lt;= 100</code></li>
</ul>
MOVES = [(-1, -1), (-1, 0), (0, -1)]

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        # Store the modulo value
        MOD = 10**9 + 7
        
        # Convert board into numbers and obstacles
        board = [[int(c) if c not in ('E', 'S', 'X') else c for c in row] for row in board]
        
        # Initialize state with max score and path count
        state = {'score': 0, 'times': 0}
        
        # Call helper function with memoization
        memo = {}
        result = self.helper(board, len(board) - 1, len(board[0]) - 1, memo)
        
        # If no valid path exists, return [0, 0]
        if result[1] == 0:
            return [0, 0]
        
        # Return final max score and number of paths mod 10**9 + 7
        return [result[0] % MOD, result[1] % MOD]

    def helper(self, board, i, j, memo):
        MOD = 10**9 + 7
        
        # If we're at the start (0,0), there's no score, but exactly 1 path
        if (i, j) == (0, 0):
            return (0, 1)
        
        # If the current position is already memoized, return the result
        if (i, j) in memo:
            return memo[(i, j)]
        
        # If the current position is an obstacle or invalid, return (0, 0)
        if board[i][j] == 'X':
            return (0, 0)
        
        # Initialize variables to store max score and number of paths
        max_score = 0
        num_paths = 0
        
        # Explore all possible moves (up, left, diagonal)
        for move in MOVES:
            new_i = i + move[0]
            new_j = j + move[1]
            
            # Check bounds and if the move is valid
            if new_i >= 0 and new_j >= 0 and board[new_i][new_j] != 'X':
                next_score, next_paths = self.helper(board, new_i, new_j, memo)
                
                # If the new score is higher, update max score and reset paths
                if next_score > max_score:
                    max_score = next_score
                    num_paths = next_paths
                # If the new score is the same, add the number of paths
                elif next_score == max_score:
                    num_paths = (num_paths + next_paths) % MOD
        
        # Add the current cell's value to the max score, unless it's 'S' or 'E'
        if board[i][j] != 'S' and board[i][j] != 'E':
            max_score += board[i][j]
        
        # Memoize the result for this cell
        memo[(i, j)] = (max_score, num_paths)
        
        return memo[(i, j)]


# MOVES = [(-1,-1), (-1, 0), (0, -1)]

# class Solution:
#     def pathsWithMaxScore(self, board: List[str]) -> List[int]:
#         state = {'score': 0, 'times': 0}
#         board = [[int(c) if c not in ('E','S','X') else c for c in row] for row in board]
#         self.helper(board, state, len(board) - 1, len(board[0]) - 1, 0, {})
#         return [state['score'], state['times'] % (10 ** 9 + 7)]

#     def helper(self, board, state, i, j, score, memo):
#         if (i, j) == (0, 0):
#             if score > state['score']:
#                 state['score'] = score
#                 state['times'] = 1
#             elif score == state['score']:
#                 state['times'] += 1
#             print(score)
#             return (0, 1)
#         if board[i][j] != 'S':
#             if (i,j) in memo:
#                 score += memo[(i,j)][0]
#                 if score > state['score']:
#                     state['score'] = score
#                     state['times'] = memo[(i,j)][1]
#                 elif score == state['score']:
#                     state['times'] += memo[(i,j)][1]
#                 print(score)
#                 return memo[(i,j)]
#             score += board[i][j]
#         m_score = [0, 1]
#         for m in MOVES:
#             new_i = i+m[0]
#             new_j = j+m[1]
#             if new_i >= 0 and new_j >= 0 and board[new_i][new_j] != 'X':
#                 new_score = self.helper(board, state, new_i, new_j, score, memo)
#                 if new_score[0] == m_score[0]:
#                     m_score[1] *= new_score[1]
#                 elif m_score[0] < new_score[0]:
#                     m_score = new_score
#                 # m_score = max(self.helper(board, state, new_i, new_j, score, memo), m_score)
#         if board[i][j] != 'S':
#             m_score[0] += board[i][j]
#             memo[(i,j)] = m_score
#         # else: 
#             # out = m_score
#         return m_score
        
19100