Хід гри#2431
У картковій грі, в якій беруть участь два гравці, кожен раунд приносить очок. Ці очки діляться між гравцями, причому кожен отримує цілу кількість очок. Гра триває доти, поки принаймні один із гравців не набере очок. Гравець, який до цього моменту має більше очок, оголошується переможцем.
Після такої гри точний протокол рахунку було втрачено, але відомо, хто був лідером після кожного раунду та хто в підсумку переміг. Ваше завдання — визначити кількість можливих варіантів розвитку подій у цій грі, які задовольняють цим умовам. Два варіанти вважаються різними, якщо розподіл очок хоча б в одному раунді відрізняється.
У першому рядку вхідних даних записано два цілих числа і (1 \le N \le 10000, 1 \le k \le 1000). У другому рядку подано потрібну послідовність гри. -ий символ цього рядка — "<", якщо після -го раунду лідирував другий гравець (мав більше очок), ">" — якщо лідирував перший гравець, "=" — якщо рахунок був рівним. Кількість раундів у грі дорівнює кількості символів у цьому рядку.
Виведіть залишок від ділення кількості можливих сценаріїв гри на 10^9+7.
Приклад 1