Game Progress
In a card game played by two players, each round is worth k points. These points are divided between the two players, with each receiving an integer portion. The game continues until at least one player reaches N points. The player with the higher score at that point is declared the winner.
After one such game, the exact score record was lost, but it is known who was leading after each round and who ultimately won. Your task is to determine the number of possible ways the game could have unfolded, given these leadership conditions. Two scenarios are considered distinct if the distribution of points differs in at least one round.
Input
The first line of the input contains two integers, N and k (1 ≤ N ≤ 10000, 1 ≤ k ≤ 1000). The second line describes the required sequence of the game. The i-th character of this line is "<" if the second player was leading (had more points) after the i-th round, ">" if the first player was leading, and "=" if the players were tied. The number of rounds in the game corresponds to the number of characters in this line.
Output
Print the remainder when the number of possible game scenarios is divided by 10^9+7.