패셔니스타인 당신에게는 서로 다른 옷 벌이 있다. 당신은 앞으로 일 동안 매일 이 중 한 벌을 입으려고 한다.
패셔니스타에게 옷 벌은 너무 적지 않냐고? 영리한 당신은 다 생각해둔 바가 있다.
당신은 오늘 만나는 사람에게 최근 6일 동안 보여 주었던 옷을 또 보여 주지 않을 것이다. 그래서 각 날짜마다 최근 일 중 오늘 만날 사람들이 당신의 옷차림을 보았던 날짜들을 정리해 두었다.
일차에는 개의 날짜 간격 가 주어진다. 당신은 일차에 입는 옷이, 지정된 모든 날짜 에 입었던 옷과 달라지도록 계획을 세우려고 한다. 예를 들어 , 이라면 어제와 사흘 전에 입었던 옷은 오늘 입지 않는다.
지정된 날짜 중 하루라도 입었던 옷은 오늘 입을 수 없다. 그 밖의 옷은 오늘 만날 사람들이 본 적 없는 옷이라 자유롭게 입을 수 있다.
조건을 만족하는 옷차림 계획의 수를 으로 나눈 나머지를 구하여라. 두 계획은 하루라도 입는 옷이 다르면 서로 다른 계획이다.
첫째 줄에 계획을 세울 날짜의 수 이 주어진다.
다음 개의 줄에는 일차부터 일차까지의 정보가 순서대로 주어진다. 일차의 줄에는 정수 와, 이어서 개의 정수 가 공백으로 구분되어 주어진다. 이면 그 줄에는 만 주어진다.
조건을 만족하는 옷차림 계획의 수를 으로 나눈 나머지를 출력한다.
첫 번째 예제에서는 각 날짜에 가능한 선택지가 , , , , 가지이므로 답은 이다.
두 번째 예제에서 일차와 일차에 같은 옷을 입는 계획은 개이다. 서로 다른 옷을 입는 계획은 개이므로, 답은 이다.
세 번째 예제에서 첫 이틀에 같은 옷을 입으면 일차에는 벌 중 하나를 고를 수 있고, 서로 다른 옷을 입으면 벌 중 하나를 고를 수 있다. 따라서 답은 이다.
