Một hoán vị ~P = (p_1, p_2, \dots, p_n)~ của ~n~ số nguyên dương đầu tiên được gọi là thỏa mãn xâu điều kiện ~S = s_1s_2\dots s_{n-1}~ chỉ gồm các ký tự '<', '>' nếu với mọi ~i = 1, 2, \dots, n-1~:

• Nếu ~s_i =~ '<' thì ~p_i < p_{i+1}~;

• Nếu ~s_i =~ '>' thì ~p_i > p_{i+1}~.

Yêu cầu: Cho ~n~ và xâu điều kiện ~S~, đếm số hoán vị thỏa mãn ~S~, vì kết quả có thể rất lớn, chỉ cần đưa ra phần dư trong phép chia cho ~10^9 + 7~.

Input

• Dòng 1: số nguyên ~n~ ~(2 \le n \le 3000)~;

• Dòng 2: xâu ~S~ gồm đúng ~n-1~ ký tự '<' hoặc '>'.

Output

Dòng 1: số nguyên là số hoán vị thỏa mãn xâu điều kiện ~S~, lấy modulo ~10^9 + 7~.

Scoring

Sample Input 1

4
<><

Sample Output 1

5

Sample Input 2

5
<<<<

Sample Output 2

1

Sample Input 3

18
>>>><>>><>><>>><<

Sample Output 3

788654084

Notes

Test 1: Có đúng ~5~ hoán vị thỏa mãn xâu điều kiện <>< là ~[1,3,2,4]~, ~[1,4,2,3]~, ~[2,3,1,4]~, ~[2,4,1,3]~, ~[3,4,1,2]~.

Test 2: Chỉ có đúng ~1~ hoán vị thỏa mãn xâu điều kiện <<<< là ~[1,2,3,4,5]~.

Test 3: Kết quả của ví dụ 3 được lấy modulo ~(10^9 + 7)~.