## 原始题面

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] ([x] is an integer in range $$[0, 10000000]$$)

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

### Hint

For the first case, there are $$3$$ combinations: $$0$$ apple and $$5$$ peaches, $$1$$ apple and $$4$$ peaches, $$2$$ apples and $$3$$ peaches

For the second case, apparently, it's impossible that the amount of apple is below zero. So the answer is $$0$$

Author: LI, Dinghua

## 复杂度

$$O(n2^n)$$

Show code