#6378. 「是男人就过8题——Pony.ai」EquationsAndInequations

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

给定一个方程 \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 , 1 \leq m \leq 100

数组组数小于 1500 , 对于 95\% 的测试数据 k\le 7

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