题目描述

老C是个程序员。
作为一个优秀的程序员，老C拥有一个别具一格的键盘，据说这样可以大幅提升写程序的速度，还能让写出来的程序在某种神奇力量的驱使之下跑得非常快。
小Q也是一个程序员。有一天他悄悄潜入了老C的家中，想要看看这个键盘究竟有何妙处。他发现，这个键盘共有n个按键，这n个按键虽然整齐的排成一列，但是每个键的高度却互不相同。聪明的小Q马上将每个键的高度用1~n的整数表示了出来，得到一个1~n的排列$h_1,h_2,...,h_n$。
为了回去之后可以仿造一个新键盘（新键盘每个键的高度也是一个1~n的排列），又不要和老C的键盘完全一样，小Q决定记录下若干对按键的高度关系。作为一个程序员，小Q当然不会随便选几对就记下来，而是选了非常有规律的一些按键对：对于$i=2,3,...,n$，小Q都记录下了一个字符<或者>，表示$h_{i/2}<h_i$或者$h_{i/2}>h_i$。于是，小Q得到了一个长度为n-1的字符串，开开心心的回家了。
现在，小Q想知道满足他所记录的高度关系的键盘有多少个。虽然小Q不希望自己的键盘和老C的完全相同，但是完全相同也算一个满足要求的键盘。答案可能很大，你只需要告诉小Q答案mod 1,000,000,007之后的结果即可。

输入格式：

输入共1行，包含一个正整数n和一个长度为n-1的只包含<和>的字符串，分别表示键盘上按键的数量，和小Q记录的信息，整数和字符串之间有一个空格间隔。

输出格式：

输出共1行，包含一个整数，表示答案mod 1,000,000,007后的结果。

输入样例#1：

5 <>><

输出样例#1：

3

输入样例#2：

5 <<<<

输出样例#2：

8

输入样例#3：

5 <<>>

输出样例#3：

18