한가람고등학교에는 학생 명이 있다. 학생들은 번호가 으로 중복 없이 매겨져 있다.
각 학생은 자기 자신을 제외한 정확히 한 명의 학생을 짝사랑한다. 선생님은 일부 학생에 대해서만 그 학생이 짝사랑하는 사람의 번호를 알고 있으며, 아직 알지 못하는 학생도 있다.
선생님은 모든 정보가 완성되었을 때, 정확히 쌍의 학생이 서로 좋아하도록 만드는 가능한 경우의 수를 알고 싶다. 여기서 서로 좋아하는 한 쌍이란, 서로 다른 두 학생 가 는 를 짝사랑하고 는 를 짝사랑하는 경우를 말한다.
각 테스트 케이스에 대해 각각에 대한 가능한 경우의 수를 구하여라. 가능한 경우의 수가 매우 클 수 있으므로, 답은 으로 나눈 나머지를 출력한다.
입력은 다음과 같은 형식으로 주어진다.
(테스트 케이스 ) (테스트 케이스 ) (테스트 케이스 )
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 한 줄에 개의 정수를 공백으로 구분하여 출력한다.
번째 정수는 일 때 가능한 경우의 수를 으로 나눈 나머지여야 한다.
학생들의 성별은 생각하지 않도록 한다.
각 테스트 케이스에서 는 번 학생에 대한 정보를 의미한다. 이면 번 학생이 누구를 짝사랑하는지 아직 모른다는 뜻이다. 이면 번 학생은 번 학생을 짝사랑한다는 뜻이다.
