dlaud5379   1년 전

문제

당신의 상사는 고객 데이터베이스에서 중복 사용자를 제거한 성과를 보고받은 뒤[역자 주: 이전 년도의 D번 문제 참고] 회사 SPAM(System for Publishing Amazing Marketing)을 개선하는 업무를 추가로 맡기려고 한다.

마케팅 활동이 고객들에게는 유용한 정보 전달 수단이지만, 최근 고객센터로 홍보 이메일이 너무 많고, 심지어는 같은 이메일을 여러 통 받았다는 불만이 들어오고 있다.

SPAM은 메일링 리스트로 이루어져 있고, 메일링 리스트에는 고객 주소와 다른 메일링 리스트가 속할 수 있다. 고객 주소는 임의의 시점에 기존 메일링 리스트에 추가할 수 있지만, 메일링 리스트는 새로 생성하는 순간에만 임의의 개수의 기존 메일링 리스트에 추가할 수 있다. 한 번에 여러 메일링 리스트를 생성할 수는 없다. [역자 주: 메일링 리스트의 사이클은 존재하지 않음. 원문에 없는 볼드 처리를 추가했습니다.]

메일링 리스트로 이메일을 보내면 SPAM 시스템이 메일링 리스트에 속한 모든 주소로 이메일을 전송한다. 메일링 리스트에 속한 주소가 고객 주소일 경우 그 고객에게 이메일이 직접 전송되고, 다른 메일링 리스트일 경우 그 메일링 리스트에 대해 같은 과정을 반복한다.

개인정보 보호를 위해 지금부터는 메일링 리스트와 고객 주소를 정수로 치환한다. 예를 들어 메일링 리스트 1, 2, 3과 고객 주소 4, 5가 있고, 메일링 리스트 1에는 메일링 리스트 2, 3이, 메일링 리스트 2에는 고객 주소 4, 5가, 메일링 리스트 3에는 고객 주소 4와 메일링 리스트 2가 속할 때, 메일링 리스트 1에 이메일을 보냈다고 하자. SPAM 시스템에서는 위에서 서술한 대로 메일링 리스트를 처리하며, 이때 메일링 리스트 2와 3이 처리된다. 메일링 리스트 2를 처리하고 나면 고객 주소 4, 5에 이메일이 전송된다. 메일링 리스트 3을 처리하고 나면 고객 주소 4에 이메일이 한 번 더 전송되고, 추가로 메일링 리스트 2가 한 번 더 처리되어 고객 주소 4, 5에 이메일이 역시 한 번 더 전송된다. 결과적으로 고객들에게는 총 5통의 이메일이 전송된다.

당신의 업무는 고객들에게 같은 이메일을 여러 통 전송하지 않도록 SPAM을 최적화하는 것이다. 우선은 시스템을 개선하기 전후로 전송되는 이메일의 수를 계산하는 프로그램을 작성하여라. 위의 예시에서는 시스템을 개선하고 나면 고객들에게는 총 2통의 이메일이 전송되어야 한다.

입력

첫째 줄에 시스템에 등록된 주소의 수 N과 그 중 메일링 리스트인 주소의 수 L이 주어진다. (2 ≤ N ≤ 2000, 1 ≤ L ≤ min(N - 1, 1000)) 모든 주소는 1 이상 N 이하의 서로 다른 정수이며, 1 이상 L 이하의 주소는 메일링 리스트, 나머지는 고객 주소이다.

둘째 줄부터 L + 1줄까지는 메일링 리스트의 정보가 주어진다. i + 1번째 줄에는 i번째 메일링 리스트에 속하는 주소의 수 K와 주소를 표현하는 K개의 정수 M1, M2, ..., Mk가 공백으로 구분되어 주어진다. (1 ≤ K < N, 1 ≤ Mi ≤ N) 모든 고객 주소는 적어도 하나의 메일링 리스트에 속한다.

출력

한 줄에 메일링 리스트 1에 이메일을 전송했을 때 시스템 개선 전과 후 고객들에게 전송되는 이메일의 수 B와 A를 공백으로 구분하여 출력한다. 정답이 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

댓글을 작성하려면 로그인해야 합니다.