def numPermsDISequence(S):
    dp = [1] * (len(S) + 1)
    for c in S:
        if c == "I":
            dp = dp[:-1]
            for i in range(1, len(dp)):
                dp[i] += dp[i - 1]
        else:
            dp = dp[1:]
            for i in range(len(dp) - 1)[::-1]:
                dp[i] += dp[i + 1]
    return dp[0] % (10**9 + 7)

print(numPermsDISequence('IDDDIIDIIIIIIIIDIDID'))
print(198853198924 % (10**9 + 7))