하늘아 군대 잘 가고

곧 국방의 의무를 다할 하늘이를 위해 MatKor 부원 $M$명이 $N$개의 전구를 이용하는 공연을 계획하고 있다. 전구에는 1번부터 $N$번까지 번호가 있고, 부원에게도 1번부터 $M$번까지 번호가 있다. 각 전구는 꺼짐, 어둡게 켜짐, 밝게 켜짐 중 하나의 상태이다.

전구마다 스위치를 조작해 상태를 바꿀 수 있다. 꺼짐, 어둡게 켜짐, 밝게 켜짐 상태에서 스위치를 왼쪽으로 돌리면 각각 밝게 켜짐, 꺼짐, 어둡게 켜짐이 된다. 같은 상태에서 오른쪽으로 돌리면 각각 어둡게 켜짐, 밝게 켜짐, 꺼짐이 된다.

각 부원은 자신의 차례에 정해진 행동을 한다. 정해진 행동이란 부원마다 0개 이상의 정해진 전구에 대해, 정해진 방향으로 스위치를 한 번씩 돌리는 것이다. 부원마다 조작할 스위치와 돌릴 방향이 정해져 있다. 한 부원이 같은 전구의 스위치를 여러 번 조작하는 경우는 없다.

처음에 전구는 모두 꺼져 있다. 1초마다 부원을 한 명씩 배정해 총 $K$초 동안 공연을 진행한다. 배정된 부원은 자신의 차례에 정해진 행동을 한다. $K$초가 지난 뒤 전구가 다시 모두 꺼진 상태가 되도록 하는 부원 배정 방법의 수를 구하라. 한 부원이 여러 번 배정되어도 되고, 한 번도 배정되지 않아도 된다. 순서가 다르면 다른 방법으로 센다.

첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1\le N\le 10;$ $1\le M\le 10^5;$ $1\le K\le 10^{18})$

두 번째 줄부터 1번 부원부터 차례대로 $M$명의 부원 정보가 주어진다.

$i$번 부원의 정보는 첫 줄에 그 부원이 자신의 차례에 조작할 전구의 개수 $C_i$로 주어진다. $(0\le C_i \le N)$ 이어서 $C_i$개의 줄에 한 줄에 하나씩 조작할 전구 번호와 스위치를 돌리는 방향이 공백으로 구분되어 주어진다. 전구 번호는 오름차순으로 주어진다. 전구 번호는 1 이상 $N$ 이하의 정수이다. 방향은 왼쪽으로 돌리면 L, 오른쪽으로 돌리면 R로 주어진다.

공연이 끝난 뒤 모든 전구가 다시 꺼진 상태가 되도록, 총 $K$초 동안 매초 부원 한 명을 배정하는 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.

단, $10^9+7$은 소수이다.

하늘이는 실제로 3월 4일 논산 훈련소에 입소하였다.