每年的这个时候,幸福即将来临,您可以看到喜马拉雅地区各地的人们在庆祝。喜马拉雅地区有n个健身房。第 i 个道馆里有 gi 神奇宝贝。喜马拉雅地区有 m 种不同的神奇宝贝类型,编号从 1 到 m。节日里设立了一个特殊的进化营,声称可以进化任何神奇宝贝。神奇宝贝的类型在进化后可能会发生变化,但受到以下限制:如果两个神奇宝贝在进化前具有相同的类型,则它们在进化后也将具有相同的类型。另外,如果两个神奇宝贝在进化前有不同的类型,那么它们在进化后也会有不同的类型。神奇宝贝也有可能在进化前后具有相同的类型。
形式上,进化计划是 {1, 2, ..., m} 的排列 f,这样 f(x) = y 意味着 x 类型的 Pokemon 进化为 y 类型的 Pokemon。
道馆的领导们对特殊进化营很感兴趣,他们都计划进化他们的神奇宝贝。山上的协议规定,在每个道馆中,对于每种类型的神奇宝贝,进化任何神奇宝贝之前该类型的神奇宝贝数量应等于按照进化计划进化所有神奇宝贝后该类型神奇宝贝的数量。他们现在想找出有多少种不同的进化计划满足该协议。
两个进化计划 f1 和 f2 是不同的,如果它们在两个计划中至少有一种神奇宝贝类型进化成不同的神奇宝贝类型,即。 e.存在 i 使得 f1(i) ≠ f2(i)。
你的任务是找出有多少种不同的进化计划是可能的,这样如果所有道馆中的所有神奇宝贝都进化了,那么每个道馆中每种类型的神奇宝贝的数量保持不变。由于答案可能很大,因此输出它对 109 + 7 求模。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 1 ≤ m ≤ 106) — 道馆数量和 Pokemon 类型数量。
接下来的 n 行包含道馆中神奇宝贝的描述。其中第 i 行以整数 gi (1 ≤ gi ≤ 105) 开头——第 i 个道馆中 Pokemon 的数量。之后是 gi 整数,表示第 i 个道馆中神奇宝贝的类型。这些整数中的每一个都在 1 和 m 之间。
神奇宝贝总数(所有gi的总和)不超过5·105。
输出
输出有效演化计划的数量模 109 + 7。
示例
输入 #1
2 3 2 1 2 2 2 3
输出 #1
1
输入 #2
1 3 3 1 2 3
输出 #2
6
输入 #3
2 4 2 1 2 3 2 3 4
输出 #3
2
输入#4
2 2 3 2 2 1 2 1 2
输出#4
1
输入 #5
3 7 2 1 2 2 3 4 3 5 6 7
输出 #5
24
注意
第一种情况,唯一可能的演化方案是:
$$1 \rightarrow 1, \; 2 \右箭头 2, \; 3 \右箭头 3.$$
在第二种情况下,(1,2,3)的任何排列都是有效的。
对于第三种情况,有两种可能的方案:
$$1 \rightarrow 1, \; 2 \右箭头 2, \; 3 \右箭头 4, \; 4 \右箭头 3;$$
$$1 \rightarrow 1, \; 2 \右箭头 2, \; 3 \右箭头 3, \; 4 \右箭头 4.$$
第四种情况,唯一可能的演化方案是:
$$1 \rightarrow 1,\ 2 \rightarrow 2.$$