ICPCCamp 2017에 오신 것을 환영합니다
시간 제한1초메모리 제한512 MB
n개의 대회 순위표와 마지막 결승 순위가 주어질 때, (X, Y)-규칙으로 만들 수 있는 ICPCCamp 팀 집합의 개수를 10^9+7로 나눈 나머지로 구합니다.
문제
ICPCCamp 팀은 블로그에 나온 신비로운 규칙에 따라 뽑히는 경우가 많다 (?).
개의 팀에는 번 번호가 붙어 있다. 이 중에서 ICPCCamp 팀을 고르기 위해 번의 선발 대회가 열린다. 번째 대회에 참가하는 팀 수는 이다. 마지막 번째 대회는 매우 중요한 EasyCamp-Final이므로 항상 이다. 번째 대회의 순위표는 이며, 이는 팀 가 그 대회에서 등을 했다는 뜻이다.
규칙은 다음과 같이 동작한다. 먼저 음이 아닌 정수 , 와 의 순열 을 고른다. 그다음 목록 에서 처음 나오는 서로 다른 개의 팀을 ICPCCamp 팀으로 뽑는다. 즉 목록은 EasyCamp-Final의 앞 개 팀으로 시작하고, 이어서 의 순서대로 처음 개 대회의 1등 팀, 같은 순서로 2등 팀이 나열되는 식으로 진행된다.
Bobo는 , , 를 자유롭게 고를 수 있을 때, 가능한 ICPCCamp 팀 집합의 개수를 로 나눈 나머지로 알고 싶어 한다.
다가오는 World Finals에서 즐거운 시간 보내세요!
입력
입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝에서 끝난다. 각 테스트 케이스는 다음과 같다.
첫 줄에 정수 , (, )이 주어진다.
이어지는 개의 줄 중 번째 줄에는 정수 와 그 뒤에 개의 정수 ()가 주어진다.
마지막 줄에는 개의 정수 ()이 주어진다. 각 에 대해 는 서로 다르다.
모든 테스트 케이스에 걸쳐 의 합과 의 합은 각각 을 넘지 않는다.
출력
각 테스트 케이스마다 가능한 집합의 개수를 로 나눈 나머지를 정수 하나로 출력한다.