DP, DFS up and down 
Approach
n := len(s), up + down + start = n
DP dp := make([][]int, n+1) caching for process at index start with up and down is meaning for total greater and les
# Approach
- `n := len(s)`, `up + down + start = n`
- DP `dp := make([][]int, n+1)` caching for process at index `start` with `up` and `down` is meaning for total greater and less than number is picking at index `start`.

# Complexity
- Time complexity:O(n^2)

- Space complexity:O(n^2)

# Code
```golang []

func numPermsDISequence(s string) int {
	n := len(s)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	rs := 0
	for start := n - 1; start >= 0; start-- {
		m := n - start
		for i := 0; i <= m; i++ {
			up := m - i
			down := i
			rsi := dfs(up, down, start, s, dp)
			if start == 0 {
				rs += rsi
				rs %= 1000000007
			}
		}
	}
	return rs
}
func dfs(up, down, start int, s string, dp [][]int) int {

	if start == len(s) {
		return 1
	}
	rs := dp[up][down]
	if rs != -1 {
		return rs
	}
	rs = 0
	if s[start] == 'I' && up > 0 {
		for i := 1; i <= up; i++ {
			rs += dfs(up-i, down+i-1, start+1, s, dp)
			rs %= 1000000007
		}
	} else if s[start] == 'D' && down > 0 {
		for i := 1; i <= down; i++ {
			rs += dfs(up+i-1, down-i, start+1, s, dp)
			rs %= 1000000007
		}
	}
	dp[up][down] = rs
	return rs
}
```
['Go']