Microchips

Memory limit: 32 MB

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 .

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.

Task

Write a program which:

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

Input

The first line of input contains four integers , , and (, , , ), separated by single spaces. represents the number of transistors in the microchip, - the number of micro-wires, - impedance of paths we are looking for and - the number by which division is performed. Each of the following lines contains three integers , and (, , ), separated by single spaces and representing a micro-wire with impedance , which conducts electricity from transistor to transistor . None of the ordered pairs appears more than once in a test case.

Output

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 is infinite, or the remainder of the division of the number of paths with impedance by in the opposite case.

Example

For the input data:

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

the correct result is:

5

and for the input data:

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

the correct answer is:

NIESKONCZONOSC

In the first example, all paths with impedance are:

• ,
• ,
• ,
• ,
• .

Task author: Jakub Radoszewski.