이상한 꿈

두미트루(Dumitru)는 아주 이상한 꿈을 꾸었다. 문이 잠긴 방 안에 갇혀 있었는데, 그 방에는 상자가 $n$개 있고 각 상자에는 접시가 정확히 $m$개씩 들어 있었다. 각 접시에는 $1$ 이상의 정수가 하나씩 적혀 있다. 방에는 두 정수 $k$와 $l$이 적힌 쪽지가 있었고, 다음 작업을 요구했다.

• 1단계: 첫 번째 상자에서 접시를 하나 골라 그 접시에 적힌 수를 공책에 적고, 그 접시의 수를 $1$로 바꾼 뒤 다시 상자에 넣는다. 이어서 같은 방식으로 두 번째 상자, 세 번째 상자, $\dots$, $n$번째(마지막) 상자까지 차례대로 각 상자에서 접시를 하나씩 골라 그 수를 공책에 적고, 그 접시의 수를 $1$로 바꾼 뒤 상자에 되돌려 놓는다.
• 2단계: 그다음 같은 방식으로 $n-1$번째 상자, $n-2$번째 상자, $\dots$, 두 번째 상자까지(양 끝 포함) 차례대로 각 상자에서 접시를 하나씩 골라 그 수를 공책에 적고, 그 접시의 수를 $1$로 바꾼 뒤 상자에 되돌려 놓는다.

위 방식으로 접시를 고르는 방법들 중에서, 공책에 적힌 모든 수의 곱이 $k$로 나누어떨어지는 서로 다른 방법의 수를 $T$라 하자. $T$가 매우 클 수 있으므로, $T$를 $l$로 나눈 나머지를 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다. 둘째 줄에 두 정수 $k$와 $l$이 공백 하나로 구분되어 주어진다. 이어서 $n$개의 줄이 주어지며, 각 줄에는 공백으로 구분된 $m$개의 정수가 있다. 첫 번째 줄은 첫 번째 상자에 들어 있는 접시들에 적힌 $m$개의 수, 두 번째 줄은 두 번째 상자의 수들, $\dots$ 과 같은 식으로 이어진다.

$T$를 $l$로 나눈 나머지를 정수 하나로 출력한다.

• $3 \le n \le 200$
• $3 \le m \le 10,000$
• $2 \le k \le 200,000$
• $2 \le l \le 30,000$
• 접시에 적힌 수는 $1$ 이상 $1,000,000$ 이하의 정수이다.

첫 번째 예시에서는 공책에 적힌 수들의 곱이 $12$로 나누어떨어지도록 접시를 고르는 방법이 정확히 $12$가지 있다. 두 가지 점에 주의해야 한다.

• 어떤 상자에서 1단계와 2단계에 같은 접시를 고르면, 1단계에서 그 접시의 수가 이미 $1$로 바뀌었으므로 2단계에 공책에 적히는 값은 $1$이 된다.
• 고른 접시들의 값 집합이 같더라도, 고른 접시의 인덱스 조합이 다르면 서로 다른 방법으로 센다.