데카르트 트리

최근 대학 강의에서 바샤는 데카르트 트리를 배웠다. 데카르트 트리는 각 정점에 키와 우선순위 두 값을 저장하는 이진 트리로, 키에 대해서는 이진 탐색 트리이고 우선순위에 대해서는 최대 힙이다. 즉

• 정점 $v$의 왼쪽 부분 트리에 있는 모든 정점의 키는 정점 $v$의 키보다 작다.
• 정점 $v$의 오른쪽 부분 트리에 있는 모든 정점의 키는 정점 $v$의 키보다 크다.
• 정점 $v$의 자식들의 우선순위는 정점 $v$의 우선순위보다 크지 않다.

시험에서 바샤는 다음과 같은 문제를 받았다. (키, 값) 형태의 $n$개의 쌍이 주어지고, $i$번째 쌍은 $(i, y_i)$이다. 정점 $i$의 키로 $i$를, 우선순위로 $y_i$를 사용해 데카르트 트리를 만드는 방법의 수를 구해야 한다. 이 수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 구한다.

두 데카르트 트리는 루트가 다르거나, 두 트리에서 서로 다른 조상을 가지는 정점이 존재하면 서로 다른 것으로 본다.

첫째 줄에는 테스트 케이스의 수 $t$가 주어진다. 그다음에 각 테스트 케이스의 설명이 이어진다.

각 테스트 케이스의 설명은 두 줄로 이루어진다. 첫째 줄에는 트리의 정점 수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어진다. 둘째 줄에는 $n$개의 정수 $y_i$ ($1 \le y_i \le 10^9$)가 주어지며, $i$번째 정점의 우선순위이다.

모든 테스트 케이스의 $n$의 합은 $2 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 주어진 우선순위 집합으로 만들 수 있는 서로 다른 데카르트 트리의 수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.