#P1806. 2024.4.7-XHS-第三题-塔子哥的题解点赞方案

2024.4.7-XHS-第三题-塔子哥的题解点赞方案

题目描述

塔子哥写了 nn 篇题解,编号从 11nn,但是塔子哥忘了每篇题解有多少人点赞了。

现在他有如下两种信息:

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

在这些信息的条件下,所有题解的点赞量一共有多少种不同可能(答案对 109+710^9+7 取模)?

输入描述

第一行为两个正整数 n,m(1n,m2000)n,m(1 \leq n,m \leq 2000),分别表示塔子哥的题解数量 nn,以及每篇题解的点赞量的上限 mm

第二行为一个长度为 n1n-1 的字符串 ss,只包括 '>''<''=' 三种字符:

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

输出描述

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

样例输入 1

4 3
<=>

样例输出 1

5

样例输入 2

4 3
>>>

样例输出 2

0