승리하라

야구팬인 송이는 응원하는 팀이 1위를 했으면 좋겠다는 마음에 남은 경기 결과를 예측해서 지금 자기 팀이 어떤 상황인지 파악해 보려고 한다.

리그에는 게임이 총 $M$개 있다. 게임마다 두 팀이 참여하며 무승부는 없어서, 한 팀이 반드시 이기고 다른 팀은 진다. 이긴 팀은 승점 1점을 얻는다. 리그에서 단독 1위가 되려면 모든 팀 가운데 승점이 가장 높아야 하고, 같은 승점을 가진 다른 팀이 없어야 한다.

송이의 응원팀이 단독 1위가 될 수 있는 경우의 수를 구하여라. 경기를 진행하는 순서가 달라도 경기 결과가 같으면 하나의 경우로 센다.

첫째 줄에 팀의 수 $N$, 경기의 수 $M$, 응원하는 팀 번호 $K$가 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000;$ $1 \leq K \leq N)$

다음 $M$개의 줄에는 (팀 번호 1, 팀 번호 2, 경기 결과) 형태로 경기 내용이 주어진다. 팀 번호는 $1$ 이상 $N$ 이하의 정수이며, 팀 번호 1과 팀 번호 2는 서로 다름이 보장된다. 경기 결과가 $0$이면 아직 진행되지 않은 경기, $1$이면 팀 번호 1의 팀이 이긴 경기, $2$이면 팀 번호 2의 팀이 이긴 경기이다. 아직 진행되지 않은 경기는 최대 $20$경기이며, 입력에 응원하는 팀이 나오지 않을 수도 있다.

입력으로 주어지는 수는 모두 정수이다.

아직 진행되지 않은 경기가 모두 진행되었을 때, 응원하는 팀이 단독 1위가 되는 경우의 수를 출력한다.