给定一个方程 $\sum _{i=1}^k{x}_i=s$, 以及 $m$ 个形如 $x_i=x_j$, $x_i\le x_j$, $x_i\ge x_j$, $x_i\ne 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

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

对于 $100\mathrm{\%}$ 的数据， $1\le k\le 12$, $1\le s\le {10}^9$, $0\le m\le 100$ 。

数组组数小于 $1500$, 对于 $95\mathrm{\%}$ 的测试数据 $k\le 7$ 。

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

时间限制：$6\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载