시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

입력

The first line of input contains four integers n, m, I and k (2 ≤ n ≤ 50, 1 ≤ mn(n - 1), 1 ≤ I ≤ 2·109, 2 ≤ k ≤ 109), 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 ajbj and ij (1 ≤ aj, bjn, ajbj, 1 ≤ ij ≤ 2·109), separated by single spaces and representing a micro-wire with impedance ij, which conducts electricity from transistor aj to transistor bj. None of the ordered pairs (aj, bj) 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 I is infinite, or the remainder of the division of the number of paths with impedance I by k in the opposite case.

예제 입력 1

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

예제 출력 1

5

In the first example, all paths with impedance 6 are:

  • 2 → 1 → 4,
  • 2 → 1 → 3,
  • 1 → 4 → 3,
  • 3 → 4 → 3,
  • 4 → 3 → 4.

예제 입력 2

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

예제 출력 2

NIESKONCZONOSC

 

In the second example, all micro-wires have impedance equal to 1, so all paths in the microchip have impedance 1 (there are infinitely many such paths).