1
class Solution {
2
  public int numPermsDISequence(String s) {
3
    int length = s.length();
4
    int mod = 1000000007;
5
    int[] dp1 = new int[length + 1];
6
    int[] dp2 = new int[length];
7
    for (int j = 0; j <= length; j++) {
8
      dp1[j] = 1;
9
    }
10
    for (int i = 0; i < length; i++) {
11
      if (s.charAt(i) == 'I') {
12
        for (int j = 0, curr = 0; j < length - i; j++) {
13
          dp2[j] = curr = (curr + dp1[j]) % mod;
14
        }
15
      } else {
16
        for (int j = length - i - 1, curr = 0; j >= 0; j--) {
17
          dp2[j] = curr = (curr + dp1[j + 1]) % mod;
18
        }
19
      }
20
      dp1 = Arrays.copyOf(dp2, length);
21
    }
22
    return dp1[0];
23
  }
24
}