【题目描述】

给出 $n$ 个点 $m$ 条边的无向连通图，边的编号为 $1\sim m$，边的权值是一个 $1\sim m$ 的排列。

记 $d(u,v)$ 为 $u,v$ 之间最大边权最小的路径中的最大边的编号。给出所有的 $d(u,v)$，求有多少种给边赋值的方案符合限制（保证至少存在一种方案符合限制），答案对 $10^9+7$ 取模。

【输入格式】

第一行两个整数，表示 $n,m$。

第 $2\sim n$ 行，第 $i$ 行为 $i-1$ 个整数，分别为 $d(i,1),d(i,2),\dots,d(i,i-1)$ 。

第 $n+1\sim n+m$ 行，每行两个整数 $u_i,v_i$ ，表示一条连接 $u_i,v_i$ 的无向边。（保证无重边、自环）

【输出格式】

一行一个整数，符合要求的赋值方案数目对 $10^9+7$ 取模的余数。

【样例 #1】

输入：

3 2
2 
1 1 
3 2
2 1

输出：

1

【样例 #2】

输入：

4 5
5 
4 5 
2 2 2 
4 1
4 2
3 2
3 1
2 1

输出：

3

【样例 #3】

$见选手目录下的 \texttt{transport/transport3.in} 与 \texttt{transport/transport3.ans} $。

【样例 #3】

$见选手目录下的 \texttt{transport/transport4.in} 与 \texttt{transport/transport4.ans} 。$。

【数据范围和约定】

对于所有子任务，$1 \leq n\leq 1000,1\leq m\leq 4000$。