给定一个方程 $\sum_{i=1}^{k} x_i = s$, 以及 $m$ 个形如 $x_i = x_j$, $x_i \le x_j$, $x_i \ge x_j$, $x_i \neq x_j$, $x_i < x_j$, 或 $x_i > x_j$ 的不等式。
计数该方程满足所有不等式的正整数解的个数。
输入格式
输入包含多组测试数据
每一组数据的第一行包含三个整数 $s, k, m$。
以下 $m$ 行以 i op j 的形式给出不等关系，其中 op 是 =，!=, <=，>=，<，> 中的一个。
输出格式
对每一组输入数据输出一行一个数，表示方程解数对 $10^9+7$ 取模的结果
样例数据
样例输入
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
样例输出
2 0 7700 396619262
限制
对于 $100\%$ 的数据， $1 \leq k \leq 12$, $1 \leq s \leq 10^9$, $0 \leq m \leq 100$ 。
数组组数小于 $1500$, 对于 $95\%$ 的测试数据 $k\le 7$ 。
特别鸣谢楼天城和吉如一提供试题，数据。