拜特兰帝国由排成一排的 $n$ 个行星组成。行星从 $1$ 到 $n$ 进行编号。你正在计划你的拜特兰之旅，但缺乏便利的交通工具让你感到烦恼。

如今，拜特兰帝国唯一可用的交通工具是传送。不幸的是，拜特兰的传送系统使用起来相当棘手。每个行星都有一个传送中心，可以是“向前的”或“向后的”。向前传送中心与向后传送中心的不同之处在于：从向前传送中心出发，你可以旅行到任何编号更大的行星；而从向后传送中心出发，你可以旅行到任何编号更小的行星。正式地，如果行星 $i$ 拥有一个向前传送中心，你可以用它旅行到任何行星 $j > i$；如果行星 $i$ 拥有一个向后传送中心，你可以旅行到任何行星 $j < i$。

你的梦想是恰好访问每个行星一次。你的旅行可以从任何行星开始。对于拜特兰帝国的每个行星 $i$，你想知道有多少种合法的旅行，它们从任意行星开始，恰好访问每个行星一次，并最终在行星 $i$ 结束。由于你经常遇到这种情况，你想计算的值可能太大，因此你只需要求出它们模 $10^9 + 7$ 的余数。

输入格式

输入包含一个长度为 $n$ ($1 \le n \le 5000$) 的字符串 $s$，表示所有行星上传送中心的描述。该字符串的每个字符要么是 '<'，要么是 '>'。如果第 $i$ 个行星拥有向后传送中心，则第 $i$ 个字符为 '<'；如果拥有向前传送中心，则为 '>'。

输出格式

输出 $n$ 个整数 —— 对于每个行星 $i$，输出在行星 $i$ 结束的合法旅行数量模 $10^9 + 7$ 的余数。

样例

输入样例 1

>><

输出样例 1

1 2 1

输入样例 2

><>>><

输出样例 2

1 2 2 4 8 1

说明

在第一个样例中：

• 结束于行星 1 的唯一合法旅行是 $2 \to 3 \to 1$。
• 结束于行星 2 的所有合法旅行是 $3 \to 1 \to 2$ 和 $1 \to 3 \to 2$。
• 结束于行星 3 的唯一合法旅行是 $1 \to 2 \to 3$。