하늘아 군대 잘 가고

곧 국방의 의무를 다할 하늘이를 위해 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일 논산 훈련소로 입소하였다.