In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

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.

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.

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.

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.

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.*