13924번 - 접미사 배열 3

문자열 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 ≤ 10⁹)과 M (0 ≤ M ≤ 10⁵)가 주어진다. 둘째 줄부터 M개의 줄에 접미사 배열을 만드는 연산이 한 줄에 하나씩 주어진다.

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

가장 처음 접미사 배열은 [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)가 있다.