← 返回题目列表

AtCoder · abc233_c

F. 产品

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有 N 袋。
包 i 包含 L_i 球。的 j第一个球 (1\leq j\leq L_i) 装在袋子里 i 有一个正整数 a_{i,j} 。

我们将从每个袋子中挑选一个球。
有多少种方法来拾取球,使得所拾取的球上写的数字的乘积为 X?

在这里,我们区分所有球,即使球上写有相同的数字。

约束

  • N \geq 2
  • L_i \geq 2
  • 袋中球数的乘积最多为 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
  • 1 \leq a_{i,j} \leq 10^9
  • 1 \leq X \leq 10^{18}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}

输出

打印答案。


示例输入 1

2 40
3 1 8 4
2 10 5

示例输出 1

2

选择时 3-袋中的第一个球 1 和 1-st 袋中球 2,我们有 a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
选择时 2-nd 球在袋子里 1 和 2-nd 球在袋子里 2,我们有 a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
没有其他方法可以制造该产品 40,所以答案是 2.


示例输入 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

示例输出 2

45

请注意,我们区分所有球,即使球上写有相同的数字。


示例输入 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

示例输出 3

0

可能没有办法制作该产品 X.