配点: 5 点
問題文
AtCoder国家有 有 N 个城镇,每个城镇都有 它的编号为 1, 2, \cdots, N 。任何 2 两个城镇之间有公路,只需支付交通费(单位:斯努克)即可从一个城镇前往另一个城镇。
AtCoder 国务部长必须首先 确定正整数 X 后,每个 我们决定将团体 (i, j) (i \neq j) 的交通费用设置如下。
- A_{i,j} \neq -1 时间:城市 连接 i 和城市 j 的道路的运输成本为 A_{i,j} 斯努克
- A_{i,j} =-1 时间:城市 连接 i 和城市 j 的道路的运输成本为 X 斯努克
此外,根据Chokdai国王的意愿,必须满足以下要求。
通过选择正确的路线,您可以 总计高达 i 从城市出发 j 总计达 P 小于或等于 Snook 可达的集合。 (i, j) [1 \leq i < j \leq N] 只是 K 存在。
能够满足Chokdai国王愿望的东西。 有多少种选择 X 的方法?但如果数量无限,请报告。
制約
- 2 \leq N \leq 40
- 1 \leq P \leq 10^9
- 0 \leq K \leq \frac{N(N-1)}{2}
- i \neq j 如果 可以认为 1 \leq A_{i,j} \leq 10^8 这个类型的变量里只能放入 A_{i,j}=-1
- i=j 如果 可以认为 A_{i,j}=0
- A_{i,j}=A_{j,i}
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。 逐行打印
N P K
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}
出力
满足Chokdai国王愿望的正整数。
如果 X 的数量是有限的,那么该数量是无限的。 Infinity 。
入力例 1
3 4 2 0 3 -1 3 0 5 -1 5 0
出力例 1
3
例如,X=3 ,则如下 4 斯努克下方可到达的城镇对数量正好是 2 因此,它满足了Chokdai国王的愿望。
- 街 1 来自城市 至 2 哈哈 4 可到达斯努克下方
- 街 1 来自城市 至 3 哈哈 4 可到达斯努克下方
- 街 2 来自城市 至 3 哈哈 4 斯努克下方无法到达
另外, 无需打印X = 2, 3, 4 满足 Chokdai 国王的意愿,而其他时候则不满足,所以答案是 所有 3 。
入力例 2
3 10 2 0 -1 10 -1 0 1 10 1 0
出力例 2
Infinity
X \geq 11 的正整数 X 将实现Chokdai国王的遗愿。因此,有无数个
它应该打印 Infinity 。
入力例 3
13 777 77 0 425 886 764 736 -1 692 660 -1 316 424 490 423 425 0 -1 473 -1 311 -1 -1 903 941 386 521 486 886 -1 0 605 519 473 775 467 677 769 690 483 501 764 473 605 0 424 454 474 408 421 530 756 568 685 736 -1 519 424 0 -1 804 598 911 731 837 459 610 -1 311 473 454 -1 0 479 613 880 -1 393 875 334 692 -1 775 474 804 479 0 579 -1 -1 575 985 603 660 -1 467 408 598 613 579 0 456 378 887 -1 372 -1 903 677 421 911 880 -1 456 0 859 701 476 370 316 941 769 530 731 -1 -1 378 859 0 800 870 740 424 386 690 756 837 393 575 887 701 800 0 -1 304 490 521 483 568 459 875 985 -1 476 870 -1 0 716 423 486 501 685 610 334 603 372 370 740 304 716 0
出力例 3
42