#3023. 「CQOI2017」老 C 的键盘

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: M_sea

题目描述

老 C 是个程序员。

作为一个优秀的程序员,老 C 拥有一个别具一格的键盘,据说这样可以大幅提升写程序的速度,还能让写出来的程序在某种神奇力量的驱使之下跑得非常快。

小 Q 也是一个程序员。有一天他悄悄潜入了老 C 的家中,想要看看这个键盘究竟有何妙处。他发现,这个键盘共有 nn 个按键,这 nn 个按键虽然整齐的排成一列,但是每个键的高度却互不相同。聪明的小 Q 马上将每个键的高度用 1n1\sim n 的整数表示了出来,得到一个 1n1\sim n 的排列 h1,h2,...,hnh_1,h_2,...,h_n

为了回去之后可以仿造一个新键盘(新键盘每个键的高度也是一个 1n1\sim n 的排列),又不要和老 C 的键盘完全一样,小 Q 决定记录下若干对按键的高度关系。作为一个程序员,小 Q 当然不会随便选几对就记下来,而是选了非常有规律的一些按键对:对于 i=2,3,,ni=2,3,\ldots ,n ,小 Q 都记录下了一个字符 < 或者 >,表示 hi/2<hih_{i/2}<h_i ​或者 hi/2>hih_{i/2}>h_i。于是,小 Q 得到了一个长度为 n1n-1 的字符串,开开心心的回家了。

现在,小 Q 想知道满足他所记录的高度关系的键盘有多少个。虽然小 Q 不希望自己的键盘和老 C 的完全相同,但是完全相同也算一个满足要求的键盘。答案可能很大,你只需要告诉小 Q 答案 mod 1,000,000,007\bmod\ 1,000,000,007 之后的结果即可。

输入格式

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

输出格式

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

样例

样例输入 1

5 <>><

样例输出 1

3

样例输出 2

5 <<<<

样例输出 2

8

样例输出 3

5 <<>>

样例输出 3

18

数据范围与提示

对于 100%100\% 的数据,1n1001\leq n\leq 100