题目描述

给定一个长为 $n$ 的字符串 $s$，$s$ 由 <，> 和 ? 构成。$s$ 应该看作是一部分排列的模板，匹配 $s$ 的排列需要满足以下条件：

• 1. 排列由 $0$ 到 $n$ 的整数组成，每个数字只出现一次，记作 $a_0,a_1,\cdots,a_n$
• 2. 若 $s_i$ 为 <，则要求 $a_i<a_{i+1}$
• 3. 若 $s_i$ 为 >，则要求 $a_i>a_{i+1}$
• 4. 若 $s_i$ 为 ?，则 $a_i$ 和 $a_{i+1}$ 的大小关系任意

请计算，有多少种排列可以匹配 $s$？ 由于答案可能很大，输出方案数模 $10^9+7$ 的余数。

输入格式

第一行：单个字符串，表示给定的模板，只有 <，> 和 ? 三种字符。

输出格式

输出共一行：单个整数，表示方案数模 $10^9+7$ 的余数。

<<

1

<?

3

数据范围

设 $s$ 的长度为 $n$，则有

• 对于$30\%$的数据： $1\leq n \leq 10$
• 对于$60\%$的数据： $1\leq n \leq 100$
• 对于$100\%$的数据： $1\leq n \leq 1000$