问题 D: 园艺大师

问题 D: 园艺大师

时间限制: 1 Sec  内存限制: 128 MB
提交: 16  解决: 2
[状态] [讨论版] [提交] [命题人:]
题目描述
小钾立志成为传说中的园艺大师,因此开始练习修剪技术。
园林中有 n 株灌木排成一排,且它们的高度都为一个正整数 h。对于每株灌木,小钾可以进行一次修剪,使其高度变成一个小于 h 的任意正整数;或是不进行修剪,使其高度仍为 h。为了保持灌木丛整体的美观,小钾还提出了 n−1 个要求,第 i 个要求为下列的一种:
  1. 第 i 株灌木的高度严格小于第 i+1 株
  2. 第 i 株灌木的高度严格大于第 i+1 株
我们称两种修剪方案不同,当且仅当存在某株灌木的最终高度在两种方案中不同。当小钾将所有不同的修剪方案都完成时,他就能提升为园艺大师。但是他实在太忙了,因此请你帮他计算所有不同的修剪方案数量对质数109+7 取模后的值。
输入
第一行包含两个整数 n, h (2≤n≤3×1031≤h≤106),含义见题目描述。
第二行包含一个长度为 n−1 的字符串,仅由字符 "<" 与 ">"(不包括引号)组成,表示小钾的要求。若第 i 个字符为 "<",则要求为"第 i 株灌木的高度严格小于第 i+1 株";若第 i 个字符为 ">",则要求为"第 i 株灌木的高度严格大于第 i+1 株"。
输出
输出一行一个整数,表示所有不同的修剪方案数量对质数 109+7 取模后的值。
样例输入 Copy
3 3
<>
样例输出 Copy
5
提示
样例输入二
5 12
<>><
样例输出二
16522
第一个样例中,一共有 5 种符合要求的方案:(1,2,1), (1,3,1), (1,3,2), (2,3,1), (2,3,2)。