Problem statement: The Sultan had a permutation of numbers from 1 to N. For interest, he put inequality signs ">" and "<" between adjacent permutation numbers. For example, if the permutation was [1, 3, 2, 5, 4], then it would be [1<3>2<5>4]. He got tired of playing with his swap and went to make himself a mango smoothie. While the Sultan was preparing a smoothie, his cat entered the room and erased all the numbers, but the inequality signs remained. Now the Sultan is interested in how many permutations exist that satisfy these inequalities. Since there can be many ways, he asked you to help him and give an answer modulo 998244353. __

A permutation of numbers of length N is an array of N integers, where each number from 1 to N occurs exactly 1 time. For example, [1 2 3] and [4 2 1 3] are permutations, but [1 2 2] and [1 2 3 5] are not. __

Input The first line contains an integer N — the length of the permutation. The second line contains a string of N-1 characters "<" or ">".

Output Print the number of permutations modulo 998244353.

So there some subtasks

n<=10 — 10 points

n<=20 — 10 points

n<=500 — 30 points

n<=2000 — 60 points

Examples:

Input

5

<><<

Output

9

Input

3

<>

Output

2

I already have idea for first subtask using n! solution