题目描述

塔子哥有 $n$ 个二叉树，他准备把这些二叉树拼接起来，拼接的方式是: 选择一个二叉树 $a$ 的一个叶子，将二叉树 $b$ 的根作为该叶子的左儿子或者右儿子。这样就把 $a$ 和 $b$ 拼接起来了。

现在塔子哥想要拼接出的二叉树的高度尽可能高，他想问你一共有多少种不同的拼接方案数。

输出描述

第一行，两个正整数 $m, n(1\leq m\leq n\leq 2\times 10^5)$ ，表示二叉树的个数和所有二叉树的结点数之和。

接下来是 $n$ 个二叉树，每个二叉树输入如下： 首先一行输入二叉树的结点数 $c_i$ ，之后 $c_i-1$ 行，每行两个点表示这两个点之间有一条父子边。

保证输入的 $c_i - 1$ 条边构成的一定是一棵二叉树，如果一个结点只有一个儿子，那么这个儿子就是左儿子。

注意：对于第 $i$ 个二叉树，其中 $c_i$ 个结点的编号为 $1$ 到 $c_i$ ，每个结点编号各不相同，结点编号为 $1$ 的结点为二叉树的根结点。

输出描述

一个整数，表示不同的拼接方案数。答案对 $10^9+7$ 取模。

样例

输入

2 5
3
1 2
1 3
2
1 2

输出

6

说明

第 $1$ 个二叉树形如：

  1
 / \ 
2   3

第二个二叉树形如：

  1(4)
 /
2(5)

那么可以转换成拼接成如下 6 种情况：

(1)
         1
        / \ 
       2   3
      /
    1(4)
    /
   2(5)

(2)
         1
        / \ 
       2   3
        \
       1(4)
        /
      2(5)

(3)
         1
        / \ 
       2   3
          /
        1(4)
        /
      2(5)

(4)
         1    
        / \ 
       2   3
            \
           1(4)
            /
          2(5)

(5)
        1(4)
        /
      2(5)
      /
     1
    / \ 
   2   3

(6)
        1(4)
        /
      2(5)
        \
         1
        / \ 
       2   3