题目描述

众所周知，粉兔喜欢打原神。

提瓦特大陆是一个$n$个点的有向图，标号从$1$到$n$。提瓦特大陆四通八达，对于点$i$，除了$k_i$个点以外，$i$向其它点都有一条边。边长均为$t_i$。

小粉兔每天在提瓦特大陆游玩25小时，所以他可能会从每个点走到每个点。为了统计提瓦特大陆的情况，小粉兔想要知道

$$\sum_{i=1}^n\sum_{i=1}^n dist(i,j) \times B^{(i-1)n+j} \mod 1000000007$$

其中$dist(i,j)$为图上$i$到$j$的最短距离。如果无法到达，则为$154154154$。

输入格式

第一行输入两个数$n,B$。

接下来$n$行，第$i$行先输入两个数$t_i, k_i$，然后输入$k_i$个互不相同的数$e_{i,1},\cdots,e_{i,k_i}$（$1\le e_{i,j}\le n, e_{i,j}\ne i$）

输出格式

样例1

Input

3 2
1 0
1 2 1 3
1 1 2

Output

332332888

Hint

dist如下

Dist	1,*	2,*	3,*
*,1	0	154154154	1
*,2	1	0	2
*,3		154154154	0

答案为$154154154\times (2^4+2^6) + (2^2+2^3+2^7+2\times 2^8)$。

样例2

Input

6 154
1 1 4 
5 1 4
191981 0
9 2 3 2
6 1 2
154154 3 1 5 4

Output

926990349

数据范围

对于所有数据，有$1\le n\le 5\times 10^5, \sum k_i^2\le 10^7, 2\le B<1000000007, 0\le t_i\le 10^9$。

下表中留空表示无特殊限制。

Test#	$n$	$\sum k_i^2$	其他
1-5	$\le 154$
6		$=0$
7-8			$k_i\le 1$
9-10			$k_i\le 2$
11-13			$t_i=1$
14-15	$\le 50000$
16-20