题目内容

实验室的记录本上有一串长度为 $n$ 的正整数序列，所有数值均不超过 $m$。研究员丢失了原始数据，只依稀记得相邻两项之间的大小关系：已知每对相邻元素要么前项严格大于后项，要么严格小于，要么相等。现在需要根据这些关系还原出所有可能的序列，求一共有多少种不同的序列满足条件。答案对 $10^9+7$ 取模。

序列的长度 $n$ 不超过 $2000$，数值上限 $m$ 不超过 $2000$。

输入描述

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$），分别表示序列长度和每个元素的上限。 第二行包含一个长度为 $n-1$ 的字符串 $s$，仅由字符 '>'、'<'、'=' 组成，依次描述第 $i$ 个元素与第 $i+1$ 个元素之间的大小关系：'>' 表示前项大于后项，'<' 表示前项小于后项，'=' 表示两者相等。

输出描述