$\{1, 2, \dots, N\}$의 순열 $P$가 주어집니다.
즉, $P$는 $1$부터 $N$까지의 모든 정수를 정확히 한 번씩 포함하는 길이가 $N$인 배열입니다.
이 배열에 대해 다음 연산을 수행할 수 있습니다:
- 인덱스 $i$($1 < i < |P|$)를 선택합니다.
- $P_i = \max(P_{i-1}, P_i, P_{i+1})$로 설정합니다.
- $P$에서 $P_{i-1}$과 $P_{i+1}$을 삭제합니다. 남은 원소들은 다시 $1$부터 시작하도록 인덱스가 재부여됩니다.
이러한 연산을 한 번 수행할 때마다 $P$의 길이는 $2$씩 줄어듭니다. 특히, $P$의 길이가 $1$ 또는 $2$이면 이 연산을 적용할 수 없습니다.
$P$에서 시작하여 이 연산을 0번 이상 수행함으로써 도달할 수 있는 서로 다른 배열의 개수를 구하세요.
이 값은 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지만 구하면 됩니다.
입력
입력은 다음 형식으로 주어집니다:
T N P_1 P_2 ... P_N ...
제약 조건
- 모든 입력값은 정수입니다.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- 모든 $i \ne j$에 대해 $P_i \ne P_j$입니다.
- 모든 테스트 케이스에서 $N^2$의 합은 $5000^2$을 초과하지 않음이 보장됩니다.
출력
각 테스트 케이스에 대해, $P$에 연산을 0번 이상 수행하여 도달할 수 있는 서로 다른 배열의 개수를 $998\,244\,353$으로 나눈 나머지를 하나의 정수로 출력합니다.
예제
예제 입력 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
예제 출력 1
1 2 5 55 365
노트
테스트 케이스 1: 어떤 연산도 수행할 수 없습니다.
테스트 케이스 2: 두 가지 가능성이 있습니다:
- 아무 연산도 수행하지 않습니다. 최종 배열은 $[2, 1, 3]$입니다.
- $i = 2$로 연산을 한 번 수행합니다. 최종 배열은 $[3]$입니다.
도달 가능한 배열은 이뿐입니다.