被锤给了方程组: $$\begin{cases} x_1+x_2+ \dots +x_n=S\\ x_1,x_2,\dots,x_n>0\\ \end{cases} $$
以及额外的m个形如$x_{a_i}\ op\ x_{b_i}$的附加条件。
其中op是$<,>,=,\leq,\geq,\neq$中的一种。
被锤想要知道询问方程组解数对$1000000007(10^9+7)$取膜的结果。
但是由于被锤不知道int乘int会爆int,他需要你的帮助。
输入格式
本题有多组数据。
第一行一个正整数$T$，表示数据组数。
对于每组数据,第一行三个正整数$n,m,S$,含义同题面描述。
接下来$m$行,每行形如$a_i\ op\ b_i$,其中$a_i,b_i$为$[1,n]$之间的互异正整数,$op$为$<,>,=,<=,>=,!=$中的一种字符串。
注意同一行输入的两个相邻元素之间有恰好一个空格。
输出格式
$T$行，一行一个数字，表示答案。
样例一
input
1 2 1 3 1 != 2
output
2explanation
$x_1=2,x_2=1$或者$x_1=1,x_2=2$。
样例二
见下发文件
数据范围
| 测试点编号 | $n\leq$ | $S\leq$ | 特殊性质 | |
|---|---|---|---|---|
| $1$ | $5$ | $10^3$ | \ | |
| $2$ | $6$ | $10^3$ | \ | |
| $3$ | $7$ | $10^3$ | \ | |
| $4$ | $7$ | $10^9$ | \ | |
| $5$ | $8$ | $10^3$ | \ | |
| $6$ | $8$ | $10^9$ | \ | |
| $7$ | $9$ | $10^3$ | \ | |
| $8$ | $9$ | $10^9$ | \ | |
| $9$ | $10$ | $10^3$ | \ | |
| $10$ | $10$ | $10^9$ | \ | |
| $11$ | $11$ | $10^3$ | \ | |
| $12$ | $11$ | $10^9$ | \ | |
| $13$ | $12$ | $10^3$ | $m=0$ | |
| $14$ | $12$ | $10^9$ | $m=0$ | |
| $15$ | $12$ | $10^9$ | $m=0$ | |
| $16$ | $12$ | $10^3$ | $op='<'$或$'>'$ | |
| $17$ | $12$ | $10^9$ | $op='<'$或$'>'$ | |
| $18$ | $12$ | $10^9$ | $op='<'$或$'>'$ | |
| $19$ | $12$ | $10^3$ | \ | |
| $20$ | $12$ | $10^9$ | \ |
对于所有测试点满足$T\leq1000$。
不超过$50$数据满足$n>7$。
时间限制：$6s$
空间限制：$256MB$
