Microchips produced by Byteland-Electronics are simple semiconductor panels with transistors located on top of them. The ends of some pairs of transistors are connected using special micro-wires. Micro-wires conduct electricity in one direction only and each of them is characterized by its impedance (impedance is a more advanced version of resistance). The quality of a microchip is measured as the number of different paths inside of the microchip with impedance equal exactly to $ I $.

By a path in the microchip we mean any way of getting from one transistor to another one (the second transistor can be the same as the first one), traveling through micro-wires in the direction of their electricity conduction. Each path consists of at least one micro-wire. A path can pass through any transistor and micro-wire an arbitrary number of times. Impedance of a path is defined as the product of the impedances of all micro-wires on that path.

Write a program which:

• reads from the standard input a description of a microchip and numbers $ I $ and $ k $,
• calculates the remainder of the division of the number of paths with impedance $ I $ by $ k $,
• writes the result to the standard output.

Input Format

The first line of input contains four integers $ n $, $ m $, $ I $ and $ k $ (2 ≤ $ n $ ≤ 50, $1 ≤ m ≤ n(n - 1)$, $1 ≤ I ≤ 2·10^{9}$, $2 ≤ k ≤ 10^{9}$), separated by single spaces. $ n $ represents the number of transistors in the microchip, $ m $ - the number of micro-wires, $ I $ - impedance of paths we are looking for and $ k $ - the number by which division is performed. Each of the following $ m $ lines contains three integers $ a_{j} $, $ b_{j} $ and $ i_{j} $ (1 ≤ $ a_{j} $, $ b_{j} $ ≤ $ n $, $ a_{j} ≠ b_{j} $, $1 ≤ i_{j} ≤ 2·10^{9}$), separated by single spaces and representing a micro-wire with impedance $ i_{j} $, which conducts electricity from transistor $ a_{j} $ to transistor $ b_{j} $. None of the ordered pairs ($ a_{j} $, $ b_{j} $) appears more than once in a test case.

Output Format

The first and only line of the standard output should contain one word NIESKONCZONOSC (i.e. infinity in Polish), if the number of paths with impedance $ I $ is infinite, or the remainder of the division of the number of paths with impedance $ I $ by $ k $ in the opposite case.

Example

Input

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

Output

5

Input 2

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

Output 2

NIESKONCZONOSC