거짓 편지

일부 정부 사업은 관공서가 직접 수행하지 않고 민간 기업에 위탁한다. 사업을 맡기에 가장 적합한 후보를 고르는 일은 따로 선정된 전문가 위원회의 몫이다. 선정 절차가 시작되기 전에 모든 후보 기업은 자신의 제안을 담은 편지를 보내고, 위원회는 가격과 품질을 근거로 가장 좋은 제안을 고른다.

여기까지가 원칙이다. 그러나 현실에서는 위원회에 건넨 뇌물에 따라 승자가 이미 정해져 있는 경우가 많고, 이런 부정을 감추기 위해 가짜 후보 기업을 절차에 끼워 넣는다. 물론 이 가짜 기업들이 보낸 제안 편지도 실제로 접수된 것처럼 꾸며야 한다. 이런 일이 워낙 잦다 보니, 누군가는 미리 정해 둔 문장 목록에서 다음 규칙에 따라 편지를 자동으로 조립해 주는 편지 생성기를 만들었다.

• 어떤 문장은 인사말이며 편지의 맨 앞에만 올 수 있다. 모든 편지는 반드시 인사말로 시작해야 한다.
• 어떤 문장은 맺음말이며 편지의 맨 뒤에만 올 수 있다. 모든 편지는 반드시 맺음말로 끝나야 한다.
• 같은 문장은 한 편지 안에서 두 번 이상 나올 수 없다.
• 각 문장에는 바로 뒤에 이어질 수 있는 문장들의 목록이 정해져 있다. 예를 들어 “안녕하세요”라는 문장 뒤에 “이상으로 제안을 마칩니다”가 올 수는 없다.
• 편지는 정해진 길이를 가져야 한다. 즉 편지에 들어가는 문장의 개수가 정확히 지정된다.

편지 생성기의 규칙이 주어질 때, 만들 수 있는 서로 다른 올바른 편지의 총 개수를 구하여 가짜 편지를 찾아내는 일을 도와라.

입력은 여러 개의 시나리오로 이루어진다. 각 시나리오는 네 개의 양의 정수 N, L, B, F가 적힌 줄로 시작한다.

• N ($1 \le N \le 1000$) 은 전체 문장의 개수이다.
• L ($1 \le L \le 1000000$) 은 편지에 들어가야 하는 문장의 개수(길이)이다.
• B ($1 \le B \le 1000$) 는 인사말 문장의 개수이다.
• F ($1 \le F \le 1000$) 는 맺음말 문장의 개수이다.

이어서 N개의 줄에 각 문장의 후속 규칙이 주어진다. 각 줄은 문장 번호 $i$, 정수 $D_i$ ($0 \le D_i \le 1000$), 그리고 문장 $i$ 바로 뒤에 이어질 수 있는 문장들의 번호 $D_i$개로 이루어진다.

그다음 B개의 줄에는 시작(인사말) 문장이 될 수 있는 문장의 번호가 하나씩 주어지고, 마지막 F개의 줄에는 끝(맺음말) 문장이 될 수 있는 문장의 번호가 하나씩 주어진다.

시나리오 목록은 네 개의 0이 적힌 줄로 끝나며, 이 줄은 처리하지 않는다.

생성기 자체는 문장이 중복되는지 검사하지 않으며, 이는 항상 후속 규칙에 의해 보장된다. 따라서 규칙을 지키면 어떤 편지에도 같은 문장이 두 번 나오지 않고, 인사말은 맨 앞에만, 맺음말은 맨 뒤에만 나온다고 가정해도 된다.

각 시나리오마다, 정확히 L개의 문장으로 이루어진 올바른 편지의 총 개수를 한 줄에 출력한다. 이 값은 매우 커질 수 있으며 $2^{32}$ 을 넘을 수도 있다. 주어진 길이의 올바른 편지가 하나도 없으면 대신 impossible 을 출력한다.