중앙값

으아함... 새벽 3시까지 ByteStation을 하지 말았어야 했다. 알고리즘 교수님의 단조로운 목소리에 점점 정신이 멀어진다...

잠깐. 무슨 일이지? 온라인 수업 중에 잠이 들어서 오후, 밤, 다음 날 아침까지 내리 잤던 것이다. 그렇다면... 시험! 숨을 고를 틈도 없이 교수님이 문제를 설명하기 시작한 바로 그 순간에 교실로 뛰어 들어간다.

시험 과제는 수열의 중앙값을 구하는 것이다. 중앙값은 정렬했을 때 가운데에 놓이는 원소이다. 수열의 길이가 짝수이면 중앙값은 두 가운데 값 중 작은 값이다. 해법의 의사 코드를 적은 뒤, 교수님이 준 예시 수열에 그 코드를 따라가며 시뮬레이션해야 한다.

기억을 더듬어 보니 강의에서 비슷한 내용이 나왔던 것 같다. 무슨 마법 같은 알고리즘이었는데... 마법의 3? 수열을 여러 부분으로 나누고, 각 부분을 재귀적으로 푼 다음 결과를 합치는 방식이었던 것 같다...

남은 단편적인 기억을 바탕으로 다음과 같은 알고리즘을 만들었다:

function magicThrees(sequence)
  if the length of the sequence is no more than 2 then
    return the smallest value in sequence
  otherwise
    part_1, part_2, part_3 = splitIntoThreeParts(sequence)
    median_i = magicThrees(part_i) dla i = 1, 2, 3
    return the median of [median_1, median_2, median_3]

여기서 splitIntoThreeParts는 수열을 길이가 최대한 비슷한 세 개의 연속된 조각으로 나눈다. 구체적으로 조각의 길이는 원래 수열의 길이에 따라 $[s, s, s]$, $[s + 1, s, s]$ 또는 $[s + 1, s + 1, s]$가 된다. 예를 들어 수열 [8, 2, 6, 6, 3, 5, 7, 1]은 [8, 2, 6], [6, 3, 5], [7, 1]로 나뉜다.

시험을 마치고 나서야 이 알고리즘이 그다지 마법 같지 않으며, 항상 제대로 동작하지는 않는다는 것을 깨달았다. 적어도 시험에 나온 예시 수열에서는 동작했을지도 모른다... 안타깝게도 그 수열에 대한 기억도 알고리즘만큼 흐릿하다. 원소는 거의 전부 기억나지만 몇 개의 값은 확실하지 않다. 다만 수열에 나타나는 모든 값의 범위는 기억한다. 모든 원소는 닫힌 구간 $[0, m-1]$에 속해야 했다.

값을 모르는 원소에 값을 채우는 방법의 수를 구하라. 이때 결과 수열에 대해 magicThrees를 실행하면 (위에서 정의한) 올바른 중앙값이 나와야 한다. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

입력의 첫 줄에는 테스트 케이스의 개수 $z$가 주어진다. 이어서 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$, $m$ ($n \ge 1$, $1 \le m \le 10^9$)이 주어진다. 각각 테스트 수열의 길이와 수열 원소 값의 상한이다.

둘째 줄에는 테스트 수열이 주어진다. 범위 $[-1, m-1]$의 정수 $n$개로 이루어지며, 값을 모르는 원소는 $-1$로 표시된다.

값을 모르는 원소의 개수를 $q$라고 하면, 각 테스트 케이스는 다음 중 하나의 그룹에 속한다:

• $1 \le z \le 100$, $1 \le q \le 10$, $n \le 3^4 = 81$
• $z = 15$, $1 \le q \le 20$, $n \le 3^5 = 243$
• $z = 3$, $q = 30$, $n \le 3^8 = 6\,561$

각 테스트 케이스에 대해 정수 $r$ ($0 \le r < 10^9 + 7$) 하나를 출력한다. 이것이 문제에서 묻는 답이다.

첫 번째 테스트 케이스에서는 모르는 두 값이 무엇이든 magicThrees가 올바른 중앙값을 반환하므로, 답은 $10^2 = 100$이다.

두 번째 테스트 케이스에서는 모르는 값이 $20$ 이하일 때에만 magicThrees가 올바른 중앙값을 반환하므로, $21$가지이다.

세 번째 테스트 케이스에서는 모르는 두 값이 모두 $10$보다 작거나 모두 클 때 magicThrees가 잘못된 중앙값을 반환하므로, $100^2 - (10^2 + 89^2) = 1979$가지이다.