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