마이크로칩

Byteland-Electronics가 만드는 마이크로칩은 위에 트랜지스터가 올라간 반도체 판이다. 일부 트랜지스터 쌍의 끝은 마이크로 배선으로 연결되어 있다. 각 마이크로 배선은 한 방향으로만 전기를 흘려보내며, 임피던스(저항을 일반화한 값)를 하나씩 가진다. 마이크로칩의 품질은 그 안에서 임피던스의 곱이 정확히 $I$가 되는 서로 다른 경로의 개수로 정의한다.

여기서 경로란 한 트랜지스터에서 다른 트랜지스터(도착지가 출발지와 같아도 된다)까지, 마이크로 배선을 전기가 흐르는 방향으로만 따라가며 이동하는 모든 방법을 뜻한다. 경로는 마이크로 배선을 적어도 하나 사용하며, 같은 트랜지스터나 배선을 여러 번 지나가도 된다. 경로의 임피던스는 그 경로에 포함된 모든 마이크로 배선의 임피던스를 곱한 값이다.

마이크로칩의 정보와 두 수 $I$, $k$를 읽어, 임피던스가 정확히 $I$인 경로의 개수를 $k$로 나눈 나머지를 출력하는 프로그램을 작성하라.

첫째 줄에 네 정수 $n$, $m$, $I$, $k$가 공백으로 구분되어 주어진다 ($2 \le n \le 50$, $1 \le m \le n(n-1)$, $1 \le I \le 2\cdot10^9$, $2 \le k \le 10^9$). $n$은 트랜지스터의 수, $m$은 마이크로 배선의 수, $I$는 찾고자 하는 경로의 임피던스, $k$는 나눗셈에 사용할 수이다. 이어지는 $m$개의 줄에는 각각 세 정수 $a_j$, $b_j$, $i_j$가 주어진다 ($1 \le a_j, b_j \le n$, $a_j \ne b_j$, $1 \le i_j \le 2\cdot10^9$). 이는 트랜지스터 $a_j$에서 $b_j$로 전기를 흘려보내는 임피던스 $i_j$짜리 마이크로 배선을 뜻한다. 어떤 순서쌍 $(a_j, b_j)$도 두 번 이상 나타나지 않는다.

한 줄을 출력한다. 임피던스가 $I$인 경로의 개수가 무한하면 NIESKONCZONOSC(폴란드어로 무한대)를 출력하고, 그렇지 않으면 그 개수를 $k$로 나눈 나머지를 출력한다.