AT_dp_t Permutation

给定一个正整数 $N$ 和一个由小于号 `` 组成的长度为 $N-1$ 的字符串 $s$。 你需要找到一个排列 $(p_1,\ p_2,\ p_3,\ ...,\ p_N)$，满足对于任意 $i\ (1 \leq i \leq N-1)$，如果 $s_i$ 为 `` 则 $p_i > p_{i+1}$。求满足性质的排列 $p$ 的方案数**对 ${10}^{9}+7$ 取模**后的值。

请按照以下格式输入： > $N$ > > $s$

输出满足条件的方案个数对 ${10}^{9}+7$ 取模后的值。

### 数据范围与约定 - $N$ 是正整数 - $2 \leq N \leq 3000$ - $s$ 是一个长度为 $N-1$ 的字符串 - 字符串 $s$ 包含字符 `` ### 样例解释 1 有 $5$ 个满足条件的排列，分别是： - $(1,\ 3,\ 2,\ 4)$ - $(1,\ 4,\ 2,\ 3)$ - $(2,\ 3,\ 1,\ 4)$ - $(2,\ 4,\ 1,\ 3)$ - $(3,\ 4,\ 1,\ 2)$ ### 样例解释 2 有 $1$ 个满足条件的排列 $(1,\ 2,\ 3,\ 4,\ 5)$。 ### 样例解释 3 **注意输出结果要对 ${10}^{9}+7$ 取模。**