eolymp
bolt
Try our new interface for solving problems
Problems

Ход игры

Ход игры

Time limit 1 second
Memory limit 64 MiB

Есть некоторая карточная игра, в которую играют два игрока. Каждую раздачу разыгрывается k очков. Какую-то часть этих очков (целое число) получает один игрок, оставшиеся очки получает второй. Игра продолжается до тех пор, пока хотя бы один из игроков не наберет N очков. Игрок, набравший к этому моменту большее количество очков, считается победителем.

После одной из игр не сохранился ее протокол, но известно какой из игроков лидировал после каждого раунда и соответственно кто победил в игре. Вычислите количество вариантов, по которым мог происходить ход игры с соблюдением заданных условий лидерства. Два варианта считаются различными, если хотя бы в одном из раундов очки распределились различным образом.

Input data

В первой строке входного файла заданы два целых числа N и k (1N10000, 1k1000). Вторая строка определяет требуемый ход игры. i-ый символ этой строки равен "<"', если после i-го раунда лидировал (имел большее количество очков) второй игрок, ">", если лидировал первый игрок, "=", если игроки имели одинаковое количество очков. Общее количество раундов в игре равно количеству символов в заданной строке.

Output data

В выходной файл выведите остаток от деления количества вариантов хода игры на 10^9+7.

Examples

Input example #1
3 1
<<<=>
Output example #1
1