思路

动态规划。

状态定义

$dp[i][j]$ 表示前 i 篇分享，第 i 篇分享的点赞量为 j 的情况下，有多少种不同方案数。

状态转移

题目描述

小红写了 $n$ 篇题解，编号从 $1$ 到 $n$，但是小红忘了每篇题解有多少人点赞了。

现在他有如下两种信息：

• 每篇题解的点赞量都为正数，且不超过 $m$。
• 第 $i$ 篇题解的点赞量和第 $i+1$ 篇题解的点赞量的大小关系。

在这些信息的条件下，所有题解的点赞量一共有多少种不同可能（答案对 $10^9+7$ 取模）？

输入描述

第一行为两个正整数 $n,m(1 \leq n,m \leq 2000)$，分别表示小红的题解数量 $n$，以及每篇题解的点赞量的上限 $m$。

第二行为一个长度为 $n-1$ 的字符串 $s$，只包括 '>'、'<'、'=' 三种字符：

• 如果 $s[i]='>'$，则第 $i$ 篇题解的点赞量严格大于第 $i+1$ 篇题解的点赞量。
• 如果 $s[i]='<'$，则第 $i$ 篇题解的点赞量严格小于第 $i+1$ 篇题解的点赞量。
• 如果 $s[i]='='$，则第 $i$ 篇题解的点赞量等于第 $i+1$ 篇题解的点赞量。

输出描述

输出一个整数表示所有题解的点赞量一共有多少种不同可能（答案对 $10^9+7$ 取模）。

样例输入 1

4 3
<=>

样例输出 1

5

样例输入 2

4 3
>>>

样例输出 2

0