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