<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>
class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        '''
        * move from bottom right to left corner in board
        * I can move up, left or up-left (ie., diagonally)
        * collects points as I move up..
        * return the max_score and the number of paths with this max score..
        ====
        * 2 <= board.length == board[i].length <= 100; it is at most 100..
        * try recursively? => works!!
        '''

        @cache
        def helper(i, j): 
            if i == 0 and j == 0: 
                return 0, 1 # max score, num_paths with max_score

            if i < 0 or j < 0 or board[i][j] == "X": # I am only traversing backwards.. so checking < 0 should be enough instead of 0 <= i < len(board).. and likewise for j.. the cell also cant be an obstable..
                return -inf, 1 # invalidate.. but still count the way as 1

            curr = int(board[i][j]) if board[i][j] != "S" else 0 # if it's a digit point character.. convert to int.. 

            cnts = collections.Counter() # keep track of points, and in how many paths I see this point
            for di, dj in [[-1, 0], [0, -1], [-1, -1]]: # left, up or left-up..
                ni, nj = i + di, j + dj
                rec_max, rec_num_path = helper(ni, nj)
                cnts[rec_max] += rec_num_path
            
            #### based on all cnts of recursive path max and num paths... select the maximum.. 
            max_score = max(list(cnts.keys()))
            return curr + max_score, cnts[max_score] # add current to max_score.. and how many paths had the max_score at each level..

             
        max_score, num_path_score = helper(len(board)-1, len(board[0])-1)
        if max_score == -inf: return [0, 0] # did not find a path from 'S' to 'E'
        
        MOD = ((10**9) + 7)
        return [max_score, num_path_score % MOD]
26300