Description

设 $N$ 为正整数。给你一个长度为 $N-1$ 的字符串，由 < 和 > 组成。

将 $1\sim N$ 共 $N$ 个数插入上述 $N-1$ 个大于小于号之间（含两端），使得各个大于小于关系满足，有多少种方法？

求出可行的方法数除以 $10^9+7$ 的余数。

Input

输入格式如下：

$N\\s$

$N$ 是整数。

$2≤N≤3000$。

$s$ 是长度为 $N−1$ 的字符串。

$s$ 只由 < 和 > 组成。

Output

输出方法数除以 $10^9+7$ 的余数。

Samples

4
<><

5

有五种排列满足条件，如下所示： (1,3,2,4) (1,4,2,3) (2,3,1,4) (2,4,1,3) (3,4,1,2)

5
<<<<

1

有一种排列满足条件：

(1,2,3,4,5)

20
>>>><>>><>><>>><<>>

217136290

务必输出模 $10^9+7$ 的结果。