Byteland-Electronics 生产的微芯片是简单的半导体面板，上面分布着晶体管。某些晶体管对的两端通过特殊的微导线连接。微导线仅沿一个方向导电，且每根导线都有其阻抗（阻抗是电阻的进阶概念）。微芯片的质量衡量标准是微芯片内部阻抗恰好等于 $I$ 的不同路径的数量。

微芯片中的路径是指从一个晶体管到达另一个晶体管（第二个晶体管可以与第一个相同）的任何方式，沿微导线的导电方向行进。每条路径至少包含一根微导线。路径可以经过任何晶体管和微导线任意次数。路径的阻抗定义为该路径上所有微导线阻抗的乘积。

请编写一个程序：

• 从标准输入读取微芯片的描述以及数字 $I$ 和 $k$，
• 计算阻抗为 $I$ 的路径数量除以 $k$ 的余数，
• 将结果写入标准输出。

输入格式

输入的第一行包含四个整数 $n$、$m$、$I$ 和 $k$（$2 \le n \le 50$，$1 \le m \le n(n - 1)$，$1 \le I \le 2 \cdot 10^9$，$2 \le k \le 10^9$），以空格分隔。$n$ 表示微芯片中的晶体管数量，$m$ 表示微导线的数量，$I$ 表示我们要寻找的路径阻抗，$k$ 表示除数。接下来的 $m$ 行，每行包含三个整数 $a_j$、$b_j$ 和 $i_j$（$1 \le a_j, b_j \le n$，$a_j \neq b_j$，$1 \le i_j \le 2 \cdot 10^9$），以空格分隔，表示一根阻抗为 $i_j$ 的微导线，它将电流从晶体管 $a_j$ 传导至晶体管 $b_j$。在测试用例中，有序对 $(a_j, b_j)$ 不会重复出现。

输出格式

标准输出的第一行也是唯一一行应包含一个单词 NIESKONCZONOSC（波兰语中意为“无穷大”），如果阻抗为 $I$ 的路径数量是无限的；否则，输出阻抗为 $I$ 的路径数量除以 $k$ 的余数。

样例

样例输入 1

4 6 6 1000
2 1 3
1 3 2
1 4 2
4 2 4
4 3 3
3 4 2

样例输出 1

5

样例输入 2

4 4 1 1000
2 1 1
4 2 1
3 4 1
1 3 1

样例输出 2

NIESKONCZONOSC