시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 4 2 2 50.000%

문제

문자열 S의 i번째 접미사는 S의 i번째 글자에서 시작하는 접미사(Suffix)이다.

예를 들어, S = "abcde"인 경우에 0번째 접미사는 "abcde", 3번째 접미사는 "de" 이다.

S의 접미사 배열은 S의 모든 접미사를 사전 순으로 정렬한 배열이다. 이 때, 배열에 들어있는 값은 접미사 번호이고, 정렬은 접미사 번호에 해당하는 접미사로 수행하게 된다.

예를 들어, S = "abca"인 경우에 접미사 배열은 (3, 0, 1, 2)가 된다.

길이가 N인 접미사 배열이 주어졌을 때, 그 접미사 배열을 만들 수 있는 문자열 S의 개수를 구하는 프로그램을 작성하시오.

N이 매우 크기 때문에, 다음과 같은 연산을 통해서 접미사 배열 SA를 만든다. 먼저, 접미사 배열 SA[i] = i로 초기화를 하고, 그 다음 총 M개의 연산을 통해서 접미사 배열을 만들어야 한다.

  • 0 u v: SA의 u번째 부터 v번째 까지를 배열의 가장 앞에 붙인다. 즉, 이 연산을 사용한 후의 접미사 배열은 SA[u], SA[u+1], ..., SA[v], SA[1], SA[2], ..., SA[i-1], SA[v+1], ..., SA[N]이 되어야 한다.
  • 1 u v: SA의 u번째 부터 v번째 까지를 뒤집는다. 즉, 이 연산을 사용한 후의 접미사 배열은 SA[1], SA[2], ..., SA[u-1], SA[v], SA[v-1], ..., SA[u+1], SA[u], SA[v+1], ..., SA[N]이 되어야 한다.

이 문제에서 문자열이란 양의 정수로 이루어진 배열이다. 이 때, 문자열에 포함된 서로 다른 정수의 개수는 문자열에 포함되어 있는 가장 큰 정수와 같아야 한다. 예를 들어, (1, 2, 2), (4, 5, 1, 2, 3)은 올바른 문자열이지만, (1, 1, 3), (-1, 0, 1, 2)는 올바른 문자열이 아니다.

입력

첫째 줄에 문자열의 길이 N (1 ≤ N ≤ 109)과 M (0 ≤ M ≤ 105)가 주어진다. 둘째 줄부터 M개의 줄에 접미사 배열을 만드는 연산이 한 줄에 하나씩 주어진다.

출력

입력으로 주어진 접미사 배열 SA를 이용해 만들 수 있는 문자열 S의 개수를 109+7로 나눈 나머지를 출력한다.

예제 입력 1

4 2
1 2 3
0 3 4

예제 출력 1

4

힌트

가장 처음 접미사 배열은 [1, 2, 3, 4]이다.

첫 번째 연산을 수행하고 난 다음 접미사 배열은 [1, 3, 2, 4]가 되고, 두 번째 연산을 수행한 다음에는 [2, 4, 1, 3]이 된다.

가능한 문자열은 (2, 1, 2, 2), (2, 1, 3, 2), (3, 1, 3, 2), (3, 1, 4, 2)가 있다.

출처