問題文

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 スヌーク

また、チョクダイ国王の意向により、以下の要件を満たさなければなりません。

経路を適切に選ぶことで街 i から街 j まで合計 P スヌーク以下で到達可能であるような組 (i, j) [1 \leq i < j \leq N] がちょうど K 個存在する。

チョクダイ国王の意向を満たすような 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}
• 入力は全て整数

入力例 1

3 4 2
0 3 -1
3 0 5
-1 5 0

出力例 1

3

例えば、X=3 とすると、以下の通り 4 スヌーク以下で到達可能な街の組の数はちょうど 2 なので、チョクダイ国王の意向を満たします。

• 街 1 から 街 2 へは 4 スヌーク以下で到達可能
• 街 1 から 街 3 へは 4 スヌーク以下で到達可能
• 街 2 から 街 3 へは 4 スヌーク以下で到達不可能

また、X = 2, 3, 4 のときチョクダイ国王の意向を満たし、これ以外のときは満たさないので、答えは 3 です。

入力例 2

3 10 2
0 -1 10
-1 0 1
10 1 0

出力例 2

Infinity

X \geq 11 である全ての正の整数 X においてチョクダイ国王の意向を満たします。よって、無限個存在するので 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