In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
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:
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:
In the first example, all paths with impedance are:
Task author: Jakub Radoszewski.