30983번 - 충성! 파란댕댕이

문제

파댕이의 즐거운 대학생활은 순식간에 지나가고, 입영일이 되어 파댕이는 입대를 하게 되었다. 파댕이는 너무 슬프다.

힘든 훈련소 생활을 끝내고, 파댕이는 사단 본부에 배치받았다.

파댕이의 부대에는 두 건물을 연결하는 도로가 있는데, 놀랍게도 세 건물을 연결하는 도로도 있었다. 하지만 파댕이는 훈련소 기간동안 사회의 맛을 보지 못해 세 건물을 연결하는 도로를 처음 봤다. 모든 것이 신기한 파댕이는 부대 곳곳을 돌아다니기 시작했다. 얼마나 시간이 지났을까, 파댕이가 사라진 사실을 알게 된 행정보급관은 무슨 일이 생기지는 않았을까 노심초사하고 있다. 파댕이가 걱정된 행정보급관은 파댕이를 찾기 위해 파댕이가 있을 가능성이 높은 곳부터 찾아보기로 결심했다. 파댕이는 어디에 있을까?

사단에는 $N$개의 건물이 있고, 각 건물에는 1ドル$ 이상 $N$ 이하의 자연수가 중복없이 건물 번호로 주어진다. 파댕이는 1ドル$번 건물에서 출발해 다른 연결된 건물들을 자유롭게 이동한다. 파댕이는 건물에 멈춰서 머무르지 않고, 도로를 따라가다가 중간에 되돌아오지 않는다. 파댕이가 두 건물 사이를 이동하는 데 걸리는 시간은 1ドル$분이며, 세 건물을 연결하는 도로를 이용할 때는 두 배의 시간이 소요된다.

입력

첫 번째 줄에 건물의 개수 $N,ドル 도로의 개수 $M,ドル 파댕이가 출발한 시각으로부터 흐른 시간을 나타내는 $T$가 공백으로 구분되어 정수로 주어진다. $(2 \le N \le 50, 1 \le M \le 1,000, 1 \le T \le 1,000,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 도로의 정보가 한 줄에 하나씩 주어진다. 각 도로는 1ドル$ $a$ $b$ 또는 2ドル$ $a$ $b$ $c$의 형태로 주어지며, 1ドル$ $a$ $b$는 $a$번 건물과 $b$번 건물을 연결하는 도로, 2ドル$ $a$ $b$ $c$는 $a,ドル $b,ドル $c$번 건물을 모두 연결하는 세 건물을 연결하는 도로라는 뜻이다. $(1 \le a, b, c \le N)$

모든 도로는 서로 다른 두 건물 또는 세 건물을 연결하며, 같은 모양의 도로가 여러 개 주어질 수 있다.

출력

파댕이가 $T$분 후 각 건물로 이동할 수 있는 경우의 수를 1,000,000,009ドル$로 나눈 나머지를 한 줄에 하나씩 출력한다. 이동할 때 한 번이라도 다른 도로를 이용한다면 다른 경우의 수이다.

제한

힌트