题目描述

给定一个长度为 $n$ 的字符串 $s$ ，其中 $s[i]$ 是: $“D”$ 意味着减少，或者 $“I”$ 意味着增加

有效排列 是对有 $n + 1$ 个在 $[0, n]$ 范围内的整数的一个排列 $perm$ ，使得对所有的 $i$：

• 如果 $s[i] == 'D'$，那么 $perm[i] > perm[i+1]$，以及；
• 如果 $s[i] == 'I'$，那么 $perm[i] < perm[i+1]$。

返回 有效排列 $perm$ 的数量 。因为答案可能很大，所以请 返回你的答案对 $10^9 + 7$ 取余 。

输入格式

第一行一个整数 $n$；

第二行一个字符串 $s$。

输出格式

一行一个整数表示答案。

示例 1：

1
D

1

解释： 唯一的有效排列是 [1,0]，因为 1 > 0 满足 'D' 的要求。

示例 2：

2
ID

2

解释： 有效的排列有 [0,2,1] 和 [1,2,0]：

• [0,2,1]：0 < 2（满足 'I'），2 > 1（满足 'D'）
• [1,2,0]：1 < 2（满足 'I'），2 > 0（满足 'D'）

示例 3:

3
DID

5

解释：

(0, 1, 2, 3) 的五个有效排列是：

(1, 0, 3, 2)

(2, 0, 3, 1)

(2, 1, 3, 0)

(3, 0, 2, 1)

(3, 1, 2, 0)

提示:

• $n == s.length$
• $1 <= n <= 200$
• $s[i]$ 不是 $'I'$ 就是 $'D'$