You are given an equation x1 + x2 + x3 + ... + xk = s. And also m inequations such as xi = xj, xi ≤ xj, xi ≥ xj, xi ≥ xj, xi < xj and xi > xj.
Count the number of positive solutions satisfying all the constraints.
输入描述:
The input will consist of multiple test cases.
Each case begins with three integers s, k, and m (1 ≤ k ≤ 12, 1 ≤ s ≤ 10^9, 1 ≤ m ≤ 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 ≤ 7.
输出描述:
For each test case print the answer (number of solutions modulo 10^9+7) in one line.
示例1
输入
复制
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