2147. Number of Ways to Divide a Long Corridor

T: O(n)
S: O(n)

```java
class Solution {
    public int numberOfWays(String corridor) {
        List<Integer> seatIndexs = new ArrayList<>();

        for (int i = 0; i < corridor.length(); i++) {
            char c = corridor.charAt(i);
            if (c == 'S') {
                seatIndexs.add(i);
            }
        }
        if (seatIndexs.size() % 2 == 1 || seatIndexs.size() == 0) { // odd, no way
            return 0;
        }
        long result = 1;
        int prev2ndSeatIdx = seatIndexs.get(1); // now at least 2 seats
        for (int i = 2; i < seatIndexs.size(); i +=2) {
            long ways = seatIndexs.get(i) - prev2ndSeatIdx;
            result = (result * ways) % 1_000_000_007;
            prev2ndSeatIdx = seatIndexs.get(i+1);
        }  
        return (int)result;
    }
}

/**
T: O(n)
S: O(n)
odd is 0 

default at least 1 way
use 2nd seat as the pre
so only cal bewteen seat(2nd) and seat(next 1st) , how many ways there (seat(next 1st)'s index - seat(2nd)'s index )


0 is also a way
S: [0,1,4,6]
      p i p
  x  x
 01234
   x
"SSPPSPS"
3


index: [0,1,2,3,6,7,8,9, 11, 13]
 012345678901234
"SSSSPPSSSSPSPSP"
        0  1 2    4   6    8
             x  
index: [0,(1,2),3,6,7,8,9, 11, 13]

1*1
                 x
index: [0,1,2,(3,6),7,8,9, 11, 13]
1*(6-3) = 3
                     x 
index: [0,1,2,3,6,(7,8),9, 11, 13]
3 *1 = 3
                          x
index: [0,1,2,3,6,7,8,(9, 11), 13]
3 *(11-9) = 6

in conclusion:
 012345678901234
"SSSSPPSSSSPSPSP"
     3     2  -> 3 * 2 = 6  (ways need to product together!)

"SSSS|P|P|SSSS|P|SPSP"     
last P is nonsense
so continuous SSSS -> is still 1


 */
```