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:
and
,
by
,
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:
,
,
,
,
.
,
so all paths in the microchip have impedance
(there are infinitely many such paths).
Task author: Jakub Radoszewski.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.