<p>Along a long library corridor, there is a line of seats and decorative plants. You are given a <strong>0-indexed</strong> string <code>corridor</code> of length <code>n</code> consisting of letters <code>&#39;S&#39;</code> and <code>&#39;P&#39;</code> where each <code>&#39;S&#39;</code> represents a seat and each <code>&#39;P&#39;</code> represents a plant.</p>

<p>One room divider has <strong>already</strong> been installed to the left of index <code>0</code>, and <strong>another</strong> to the right of index <code>n - 1</code>. Additional room dividers can be installed. For each position between indices <code>i - 1</code> and <code>i</code> (<code>1 &lt;= i &lt;= n - 1</code>), at most one divider can be installed.</p>

<p>Divide the corridor into non-overlapping sections, where each section has <strong>exactly two seats</strong> with any number of plants. There may be multiple ways to perform the division. Two ways are <strong>different</strong> if there is a position with a room divider installed in the first way but not in the second way.</p>

<p>Return <em>the number of ways to divide the corridor</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>. If there is no way, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/1.png" style="width: 410px; height: 199px;" />
<pre>
<strong>Input:</strong> corridor = &quot;SSPPSPS&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, <strong>each</strong> section has exactly <strong>two</strong> seats.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/2.png" style="width: 357px; height: 68px;" />
<pre>
<strong>Input:</strong> corridor = &quot;PPSPSP&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/12/3.png" style="width: 115px; height: 68px;" />
<pre>
<strong>Input:</strong> corridor = &quot;S&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no way to divide the corridor because there will always be a section that does not have exactly two seats.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == corridor.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>corridor[i]</code> is either <code>&#39;S&#39;</code> or <code>&#39;P&#39;</code>.</li>
</ul>

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        if corridor.count("S") % 2 == 1:
            return 0
        MOD = 10**9+7

        @functools.lru_cache(maxsize=None)
        def helper(i):
            # Count number of seats from i to end or until 3rd seat.
            secondSeatIdx = None
            numSeats = 0
            for j in range(i,len(corridor)):
                if corridor[j] == "S":
                    numSeats += 1
                if numSeats == 2 and secondSeatIdx is None:
                    secondSeatIdx = j
                elif numSeats == 3:
                    # Product rules :
                    # If there are N ways to split here and M ways later,
                    # then total number of ways is N*M.
                    # If we finish up with less than 2 seats, return 0
                    # so that overall result is 0.
                    return ((j-secondSeatIdx)*helper(j))%MOD
            # j == len(corridor)-1:
            return 0 if numSeats < 2 else 1
        return helper(0)%MOD

    # def numberOfWays(self, corridor: str) -> int:
    #     # return 0 if odd number of seats.
    #     count = corridor.count("S")
    #     if count == 0 or count %2 == 1:
    #         return 0

    #     MOD = 10**9+7
    #     @functools.lru_cache(maxsize=None)
    #     def helper(i):
    #         if corridor[i:].count("S") == 2:
    #             return 0
    #         secondSeatIdx = None
    #         numSeats = 0
    #         for j in range(i,len(corridor)):
    #             if corridor[j] == "S":
    #                 numSeats += 1
    #             if numSeats == 2 and secondSeatIdx is None:
    #                 secondSeatIdx = j
    #             elif numSeats == 3:
    #                 return j-secondSeatIdx+helper(j)%MOD
    #         return float("-inf")
    #     res = helper(0)
    #     if res < 0:
    #         return 0
    #     return res%MOD if res > 0 else 1

    #     # def helperOLD(i):
    #     #     # if i == len(corridor):
    #     #     #     return 0
    #     #     seatIndices = []
    #     #     for j in range(i,len(corridor)):
    #     #         if corridor[j] == "S":
    #     #             if len(seatIndices) == 2:
    #     #                 j -= 1
    #     #                 break
    #     #             else:
    #     #                 seatIndices.append(j)
    #     #     # At the end, j will be 1 left of the 3rd seat, if one exists.
    #     #     # therefore, [i,j] contains exactly 2 seats
    #     #     # If we are at last position, return -inf if number of seats in
    #     #     # last partition is less than 
    #     #     if j == len(corridor) - 1:
    #     #         if len(seatIndices) < 2:
    #     #             return float("-inf")
    #     #         else:
    #     #             return 1
    #     #     return j-seatIndices[-1]+1 + helper(j+1)

    #     # res = helper(0) 
    #     # return 0 if res == float("-inf") else res
774