You are given an equation $x_1$ + $x_2$ + $x_3$ + ... + $x_k$ = $s$. And also $m$ inequations such as $x_i = x_j$, $x_i \leq x_j$, $x_i \geq x_j$, $x_i \neq x_j$, $x_i < x_j$ and $x_i > x_j$.

Count the number of positive solutions satisfying all the constraints.

Input

The input will consist of multiple test cases.

Each case begins with three integers $s$, $k$, and $m$ ($1 \leq k \leq 12$, $1 \leq s \leq 10^9$, $1 \leq m \leq 100$). The following $m$ lines describe the inequations in such format: "i op j" (without quotes), where "op" is one of the following signs("=", "!=", "<=", ">=", "<", ">").

The number of test cases is less than $1500$. For 95% of the test cases, $k \leq 7$.

Output

For each test case print the answer (number of solutions modulo $10^9+7$) in one line.

Example

Input

3 2 1
1 != 2
3 2 1
1 = 2
50 6 5
1 < 2
1 != 3
3 <= 2
2 = 4
5 >= 6
1000000000 8 12
8 >= 8
2 >= 6
6 != 2
4 = 4
2 < 7
4 <= 1
4 <= 5
1 >= 1
6 <= 1
7 >= 6
8 < 4
4 <= 2

Output

2
0
7700
396619262