发现题目给的很像一棵树。。。

就把这棵树建出来。

发现如果把大于小于号分别看成一条有向边， 发现这个题目就是求这个图有多少个拓扑序。对于每一个拓扑序， 直接$$12345$$这样标号就可以得到满足题目要求的序列。

考虑树\(dp\), 设\(f(i, j)\)为\(i\)这个点在这个子树所形成的拓扑序列中在第\(j\)位的方案数。

转移的时候实际上就是合并两个序列。

用\(x\)表示当前点,\(y\)表示儿子。

  • 当\(x > y\)时，

    \(f(x,k) = \sum C(k - 1, i - 1) \times C(sz[x]+sz[y] -k, sz[x] -i) * f(x, i) * f(y, j)\)

    这里的\(k\)从\(i + j\)枚举到\(i + sz[y]\)。

    意思就是， 注意到我们定义的状态是只关心其他的点和当前点的相对大小的， 所以就可以这样算。

    相当于前\(k - 1\)个位置里面有\(i - 1\)个在\(x\)原本所属于的数列里面， 剩下的是\(y\)里面的。

    然后后\(sz[x] + sz[y] - k\)个位置里面有\(sz[x] - i\)个是原本属于\(x\)那个数列的， 剩下的是\(y\)里面的。

    由于我们只关心相对大小以及每个数是来自于哪一个数列， 所以这里只要乘上组合数就可以了。

  • 当\(x < y\)时

    转移一样的， \(k\)从\(i\)到\(i + j - 1\)。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define R register
const int N = 100 + 5;
const int P = 1e9 + 7;

inline int read() {
	int x = 0, f = 1; char a = getchar();
	for(; a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int C[N][N]	;
inline void init() {
	for(R int i = 0; i < N; i ++) {
		C[i][0] = 1;
		for(R int j = 1; j <= i; j ++) 
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
	}
}

int dp[N][N];
int g[N][N];

int n;
char s[N];
int sz[N];

inline void dfs(int x) {
	sz[x] = 1; dp[x][1] = 1;
	for(R int p = 0; p <= 1; p ++) {
		int y = x * 2 + p;
		if(y > n) break;
		dfs(y); 
		for(R int i = 1; i <= sz[x]; i ++) g[x][i] = dp[x][i]; 
		memset(dp[x], 0, sizeof(dp[x]));
		for(R int i = sz[x]; i >= 1; i --) 
			for(R int j = sz[y]; j >= 1; j --) {
				if(s[y] == '>') {
					for(R int k = i + sz[y]; k >= i + j; k --) 
						dp[x][k] = 
					(dp[x][k] + 1LL * C[k - 1][i - 1] * C[sz[x] + sz[y] - k][sz[x] - i] % P * g[x][i] % P * dp[y][j] % P) % P;
				}
				else {
					for(R int k = i + j - 1; k >= i; k --)
						dp[x][k] = 
					(dp[x][k] + 1LL * C[k - 1][i - 1] * C[sz[x] + sz[y] - k][sz[x] - i] % P * g[x][i] % P * dp[y][j] % P) % P;
				}
			}
		sz[x] += sz[y];
	}
}

int main() {
	#ifdef IN
	freopen("a.in", "r", stdin);
	//freopen(".out", "w", stdout);
	#endif
	init();
	n = read(); scanf("%s", s + 2);
	dfs(1);
	int ans = 0;
	for(R int i = 1; i <= n; i ++) ans = (ans + dp[1][i]) % P;
	printf("%d\n", ans);
	return 0;
}