给定一个方程 $\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$ 的不等式。

计数该方程满足所有不等式的正整数解的个数。

Input

输入包含多组测试数据

每一组数据的第一行包含三个整数 $s, k, m$。

以下 $m$ 行以 i op j 的形式给出不等关系，其中 op 是 =，!=, <=，>=，<，> 中的一个。

Output

对每一组输入数据输出一行一个数，表示方程解数对 $10^9+7$ 取模的结果.

Sample 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

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$ 。

特别鸣谢楼天城和吉如一提供试题，数据。

时间限制：$6\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载