<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>

MOD = 10**9+7
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        n=len(corridor)
        if n == 1:
            return 0
        if n == 2:
            if corridor[0] == "S" and corridor[1] == "S":
                return 1
            return 0
        if n == 3:#sss sps ssp pss ,pps ppp
            cnt=0
            for c in corridor:
                if c == "S":
                    cnt+=1
            if cnt == 2:
                return 1
            return 0
        if n == 4:#sss sps ssp pss ,pps ppp
            cnt=0
            for c in corridor:
                if c == "S":
                    cnt+=1
            if cnt%2 == 1:#1,3
                return 0
            elif cnt == 2 or cnt == 4:
                return 1
        if n == 5:
            cnt=0
            for c in corridor:
                if c == "S":
                    cnt+=1
            if cnt%2 == 1:#1,3,5
                return 0
            elif cnt == 2:
                return 1
            elif cnt == 4:#ssssp, sssps sspss
                if corridor[2] == "P":
                    return 2
                return 1
        #n >= 6
        if n == 6:
            cnt=0
            for c in corridor:
                if c == "S":
                    cnt+=1
            if cnt%2 == 1:#1,3,5
                return 0
            elif cnt == 2 or cnt == n:
                return 1
            elif cnt == 4:
                cnt_s=0
                cnt_p=0
                for c in corridor:
                    if cnt_s < 2 or cnt_s == 3:
                        if c == "S":
                            cnt_s+=1
                    elif cnt_s == 2:
                        if c == "S":
                            cnt_s += 1
                        elif c == "P":
                            cnt_p += 1
                    elif cnt_s == 4:#ss[p..p]ss
                        if cnt_p > 0:
                            return cnt_p+1
                        else:
                            cnt_s = 2
                if cnt_p > 0:
                    return cnt_p+1
                return 1
        if n == 7:
            cnt=0
            for c in corridor:
                if c == "S":
                    cnt+=1
            if cnt%2 == 1:#1,3,5,7
                return 0
            elif cnt == 2 or cnt == n:
                return 1
            elif cnt == 4:
                cnt_s=0
                cnt_p=0
                for c in corridor:
                    if cnt_s < 2 or cnt_s == 3:
                        if c == "S":
                            cnt_s+=1
                    elif cnt_s == 2:
                        if c == "S":
                            cnt_s += 1
                        elif c == "P":
                            cnt_p += 1
                    elif cnt_s == 4:#ss[p..p]ss
                        # print(cnt_s,cnt_p)
                        if cnt_p > 0:
                            return cnt_p+1
                        else:
                            cnt_s = 2
                # print(cnt_s,cnt_p)
                if cnt_p > 0:
                    return cnt_p+1
                return 1
            elif cnt == 6:
                cnt_s=0
                cnt_p=0
                for c in corridor:
                    if cnt_s < 2 or cnt_s == 3:
                        if c == "S":
                            cnt_s+=1
                    elif cnt_s == 2:
                        if c == "S":
                            cnt_s += 1
                        elif c == "P":
                            cnt_p += 1
                    elif cnt_s == 4:#ss[p..p]ss
                        if cnt_p > 0:
                            return cnt_p+1
                        else:
                            cnt_s = 2
                if cnt_p > 0:
                    return cnt_p+1
                return 1
        #n>=8
        cnt=0
        for c in corridor:
            if c == "S":
                cnt+=1
        if cnt == 0:
            return 0
        if cnt%2 == 1:#1,3,5,7
            return 0
        elif cnt == 2 or cnt == n:
            return 1
        #cnt=4,6,8,10,...
        cnt_s=0
        cnt_p=0
        ans = 1
        for c in corridor:
            if cnt_s < 2:
                if c == "S":
                    cnt_s+=1
                if cnt_s == 2 and c == "P":
                    cnt_p+=1
            elif cnt_s == 2:
                if c == "S":
                    cnt_s += 1
                elif c == "P":
                    cnt_p += 1
            elif cnt_s == 3:
                if c == "S":
                    cnt_s+=1
                    if cnt_p > 0:
                        ans *= (cnt_p+1)
                    cnt_s = 2
                    cnt_p = 0
            elif cnt_s == 4:#ss[p..p]ss
                if cnt_p > 0:
                    ans *= (cnt_p+1)
                cnt_s = 2
                cnt_p = 0
            # print("c,ans,cnt_p,cnt_s:",c,ans,cnt_p,cnt_s)

        if cnt_p > 0 or ans > 1:
            return (ans)%MOD#*(cnt_p+1)
        return 1
        #SS|SPPPS(|PP)SPS|SS|SS|SPPPSPP
407