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