Fruit Ninja is a famous game all over world and Edward seems to be good at it. However, after broke the record many a time, Edward thought that it's too easy to get high score in that game, and that it must be more challenging to write a game like Fruit Ninja. Soon, Edward began his new program Fruit Ninja made in China.
According to Edward's design, there are exactly n kinds of fruit in the game, and exactly m fruits will appear on the screen at the beginning of a new game. What's more, to make the display of the game more colorful, for some kinds of fruits, there are limits to their amount. For example, Edward may make a rule that the amount of apple displayed on the screen should be less than 3, and that of peach should be greater than 1.
As a math-lover at the same time, Edward wants to know the total number of combination of the fruits displayed on the screen at the beginning of a game.
Input
The input contains multiple test cases, seperated by an empty line.
The first line of each test case contains two positive integer n, the number of different kinds of fruit, and m, the number of fruits that will appear on the screen at the beginning of a game. Then follows k (k ≤ n) lines describe the limits to some fruits. The decription is a line in certain format "[FruitName]: [less|greater] than [x]", which means the amount of [FruitName] should be less(greater) than x.
For all tests cases, 0 ≤ n ≤ 16, 1 ≤ m ≤ 10000000, and we ensure that fruitnames in the decriptions will be all different and make up of only lower case latin latters, and its length is less than 10. n = 0 indicates the end of input, and you should output nothing for this case.
Output
For each case, output an integer in a single line: total number(mod 100000007) of combination of the fruits displayed on the screen at the beginning of a game.
Sample Input
2 5
apple: less than 3
peach: greater than 1
1 18
apple: less than 0
4 10
fan: less than 1
rou: less than 7
tang: less than 6
cai: greater than 4
0 1
Sample Output
3
0
21
